Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Categories:

Иерархия Хомского

Существуют два подхода к описанию грамматики языков: генеративный и аналитический.
В первом случае грамматику описывают через набор правил, применяя которые можно получить все валидные предложения языка, а во-втором как набор правил по синтаксическому разбору любого данного предложения. Подходы эти существенно неэквивалентны: самое общее семейство языков в генеративном смысле — языки, для которых существует алгоритм построения всех допустимых текстов данного языка (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.
Subscribe

  • (no subject)

    Встретил фотографию толпы футбольных фанатов, и она меня скорее напугала, у меня уж точно нет желания быть там среди них. Но внезапно я понял, что…

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 22 comments

  • (no subject)

    Встретил фотографию толпы футбольных фанатов, и она меня скорее напугала, у меня уж точно нет желания быть там среди них. Но внезапно я понял, что…

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…