![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Иерархия Хомского
Oct. 2nd, 2014 07:13 pmСуществуют два подхода к описанию грамматики языков: генеративный и аналитический.
В первом случае грамматику описывают через набор правил, применяя которые можно получить все валидные предложения языка, а во-втором как набор правил по синтаксическому разбору любого данного предложения. Подходы эти существенно неэквивалентны: самое общее семейство языков в генеративном смысле — языки, для которых существует алгоритм построения всех допустимых текстов данного языка (enumerable languages). Самое общее семейство языков в аналитическом смысле — decidable languages, то есть языки, для которых существует алгоритм, определяющий, является ли данный набор буковок допустимым текстом данного языка.
В теории языков программирования нас интересует и то, и другое.
– С одной стороны, нужно парсить исходники. Тут нас интересуют грамматики, поддающиеся синтаксическому разбора методом рекурсивного спуска. То есть это языки, в которых предложение можно разбить на куски и снабдить куски аннотациями, в которых указан весь релевантный контекст, а затем анализировать эти куски по-отдельности. Конечно же существуют естественные языки (немецкий, китайский), в которых теоретически невозможно проанализировать кусок текста, обладая ограниченным контекстом: в общем случае прийдётся перелопатить весь текст на предмет бэклинков. Однако это _плохое_ свойство языка, использование таких оборотов в естественных языках это плохой стиль и источник фатальных ошибок при восприятии текста читателем.
Дизайнер формального языка никогда не допустит такой несуразицы.
– С другой стороны, набор порождающих правил (устроенный в духе естественной дедукции) нужен для того чтобы описать систему типов языка и заниматься анализом программ. Тут, однако, нужно отметить, что порождающие правила де-факто пораждают уже аннотированные синтаксические деревья, а не текст.
Грамматики для первого пункта лучше всего описываются в терминах Parsing expression grammars, либо на комбинаторах. Грамматики для второго пункта лучше всего описываются в терминах Indexed grammars или слабо-эквивалентного ему (если мы реально хотим аннотированные деревья-со-связями) higher-parametric indexed inductive type families.
Языки же натуральные лучше всего описываются в терминах Range concatenation grammars, строгом надклассе Indexed grammars, уже не допускающем анализ текста сверху вниз inplace (рекурсивный спуск), но всё ещё допускающим синтаксический анализ как таковой (т.е. в результате анализа мы таки получаем аннотированное дерево-со-связями). Это наиболее общее семейство языков, допускающее синтаксический анализ за полиномиальное время.
Если писать книгу по синтаксическим алгоритмам и NLP (например TAOCP тома 5 и 6), то нужно исходить именно из этих двух формализмов.
* * *
Мой вопрос в том, стоит ли вообще упоминать о таком семействе как Context-sensitive languages? Во-первых они бесят меня тем, что у них совершенно misleading название. Когда читаешь название, думаешь, что речь о языках, у которых правило разбора зависит от контекста, так это как раз indexed grammars. А контекстно-зависимые языки следовало бы называть monotonically enumerable languages.
Я не знаю, является ли это семейство языков естественным в каком-то смысле, кроме того что такие языки генерируются линейно-ограниченными автоматами/монотонными правилами замены.
Всё-таки зря Хомский пронумеровал уровни своей иерархии: 0 = любые, 1 = контекстно-зависимые, 2 = контекстно-свободные, 3 = регулярные. Как-то он не ожидал, что есть ещё несколько естественных классов, а класс context-sensitive languages ни для чего не нужен на практике. Насколько я понимаю, на сегодняшний день известны следующие естественные классы языков, допускающих синтаксический анализ:
regular < semi-regular* < linear-time < context-free < tree-context-free < minimalist < indexed < polynomial-time.
Причём что естественнее, контекстно-свободные грамматики на строках или контекстно-свободные грамматики на деревьях, это ещё вопрос. А вторые строго общее первых.
(*aka Nested word languages, эквивалентно описываются как log-time-parsable параллелизоваными комбинаторами/булевыми схемами.)
* * *
Дай бог крепкого здоровья и сил Дональду Эрвину Кнуту, очень хочется почитать TAOCP том 6, где он как всегда разберёт всё по полочами по части языков и расставит точки над i.
В первом случае грамматику описывают через набор правил, применяя которые можно получить все валидные предложения языка, а во-втором как набор правил по синтаксическому разбору любого данного предложения. Подходы эти существенно неэквивалентны: самое общее семейство языков в генеративном смысле — языки, для которых существует алгоритм построения всех допустимых текстов данного языка (enumerable languages). Самое общее семейство языков в аналитическом смысле — decidable languages, то есть языки, для которых существует алгоритм, определяющий, является ли данный набор буковок допустимым текстом данного языка.
В теории языков программирования нас интересует и то, и другое.
– С одной стороны, нужно парсить исходники. Тут нас интересуют грамматики, поддающиеся синтаксическому разбора методом рекурсивного спуска. То есть это языки, в которых предложение можно разбить на куски и снабдить куски аннотациями, в которых указан весь релевантный контекст, а затем анализировать эти куски по-отдельности. Конечно же существуют естественные языки (немецкий, китайский), в которых теоретически невозможно проанализировать кусок текста, обладая ограниченным контекстом: в общем случае прийдётся перелопатить весь текст на предмет бэклинков. Однако это _плохое_ свойство языка, использование таких оборотов в естественных языках это плохой стиль и источник фатальных ошибок при восприятии текста читателем.
Дизайнер формального языка никогда не допустит такой несуразицы.
– С другой стороны, набор порождающих правил (устроенный в духе естественной дедукции) нужен для того чтобы описать систему типов языка и заниматься анализом программ. Тут, однако, нужно отметить, что порождающие правила де-факто пораждают уже аннотированные синтаксические деревья, а не текст.
Грамматики для первого пункта лучше всего описываются в терминах Parsing expression grammars, либо на комбинаторах. Грамматики для второго пункта лучше всего описываются в терминах Indexed grammars или слабо-эквивалентного ему (если мы реально хотим аннотированные деревья-со-связями) higher-parametric indexed inductive type families.
Языки же натуральные лучше всего описываются в терминах Range concatenation grammars, строгом надклассе Indexed grammars, уже не допускающем анализ текста сверху вниз inplace (рекурсивный спуск), но всё ещё допускающим синтаксический анализ как таковой (т.е. в результате анализа мы таки получаем аннотированное дерево-со-связями). Это наиболее общее семейство языков, допускающее синтаксический анализ за полиномиальное время.
Если писать книгу по синтаксическим алгоритмам и NLP (например TAOCP тома 5 и 6), то нужно исходить именно из этих двух формализмов.
Мой вопрос в том, стоит ли вообще упоминать о таком семействе как Context-sensitive languages? Во-первых они бесят меня тем, что у них совершенно misleading название. Когда читаешь название, думаешь, что речь о языках, у которых правило разбора зависит от контекста, так это как раз indexed grammars. А контекстно-зависимые языки следовало бы называть monotonically enumerable languages.
Я не знаю, является ли это семейство языков естественным в каком-то смысле, кроме того что такие языки генерируются линейно-ограниченными автоматами/монотонными правилами замены.
Всё-таки зря Хомский пронумеровал уровни своей иерархии: 0 = любые, 1 = контекстно-зависимые, 2 = контекстно-свободные, 3 = регулярные. Как-то он не ожидал, что есть ещё несколько естественных классов, а класс context-sensitive languages ни для чего не нужен на практике. Насколько я понимаю, на сегодняшний день известны следующие естественные классы языков, допускающих синтаксический анализ:
regular < semi-regular* < linear-time < context-free < tree-context-free < minimalist < indexed < polynomial-time.
Причём что естественнее, контекстно-свободные грамматики на строках или контекстно-свободные грамматики на деревьях, это ещё вопрос. А вторые строго общее первых.
(*aka Nested word languages, эквивалентно описываются как log-time-parsable параллелизоваными комбинаторами/булевыми схемами.)
Дай бог крепкого здоровья и сил Дональду Эрвину Кнуту, очень хочется почитать TAOCP том 6, где он как всегда разберёт всё по полочами по части языков и расставит точки над i.
