Практические последствия формальной грамматики?

В каждом курсе "Вступление к компиляторам" рассматриваются общепринятые подмножества контекстно-свободных грамматик: LL (k), SLR (k), LALR (k), LR (k). Нам также говорят, что для любого заданного k каждая из этих грамматик является подмножеством следующего.

То, что я никогда не видел, - это объяснение того, какие типы синтаксических функций языка программирования могут потребовать перехода к другому языковому классу. Там очевидная практическая мотивация для парсеров GLR, а именно, избежание нечестивого смешения парсера и таблицы символов при синтаксическом анализе С++. Но как насчет различий между двумя "стандартными" классами, LL и LR?

Два вопроса:

  • Какие (общие) синтаксические конструкции могут быть проанализированы с помощью LR (k), но не LL (k ')?
  • Каким образом, если таковые имеются, эти конструкции проявляются как желательные языковые конструкции?

Там есть правдоподобный аргумент в пользу уменьшения владения языком, делая k как можно меньшим, потому что язык, требующий многих, многих токенов взгляда, будет труднее для людей разобрать, а также "сложнее" для машин для разбора. Вопрос (2) неявно спрашивает, заканчивается ли то же рассуждение как между классами, так и внутри класса.

edit: Здесь один пример, чтобы проиллюстрировать виды ответов, которые я ищу, но для обычных языков вместо контекстно-свободных:

При описании обычного языка обычно получается три оператора: +, * и ?. Теперь вы можете удалить + без снижения мощности языка; вместо записи x+ вы пишете xx*, и эффект тот же. Но если x - какое-то большое и волосатое выражение, два x, вероятно, расходятся во времени из-за забвения человека, давая синтаксически правильное регулярное выражение, которое не соответствует оригинальному намерению автора. Таким образом, даже если добавление + не требует строгого добавления мощности, оно делает запись менее подверженной ошибкам.

Существуют ли конструкции с подобными практическими (человеческими?) эффектами, которые должны быть "удалены" при переключении с LR на LL?

Ответы

Ответ 1

Анализ (я утверждаю) немного похож на сортировку: проблема, которая была в центре многих размышлений в первые дни CS, что привело к набору хорошо понятых решений с некоторыми хорошими теоретическими результатами.

Я утверждаю, что картина, которую мы получаем (или даем, для тех из нас, кто учит) в классе компиляторов, в какой-то степени является красивым ответом на неправильный вопрос.

Чтобы более точно ответить на ваш вопрос, грамматика LL (1) не может анализировать всевозможные вещи, которые вы можете проанализировать; "естественная" формулировка "if" с необязательным "else", например.

Но подождите! Не могу ли я переформулировать свою грамматику как грамматику LL (1), а затем исправить исходное дерево, пройдя по ней потом? Что вы можете! В какой-то степени именно это и ставит вопрос о том, какую грамматику использует ваш парсер в значительной степени.

Кроме того, когда я был студентом (1990-94), грамматики, чувствительные к пробелам, были явно работой Дьявола; теперь проекты Python и Haskell возвращают чувствительность к пробегу в свет. Кроме того, синтаксический анализ Packrat говорит "черт с вашей теоретической чистотой: я просто собираюсь определить парсер как набор правил, и мне все равно, к какому классу принадлежит моя грамматика". (Перефразировать)

В заключение я бы согласился с тем, что, по вашему мнению, было вашим подразумеваемым предложением: в 2009 году четкое понимание разницы между классами LL (k) и LR (k) менее важно само по себе, чем способность формулировать и отлаживать грамматику, которая делает ваш генератор синтаксического анализа счастливым.

Ответ 2

Разница между LL и LR заключается в основном в механизме просмотра. Люди обычно говорят, что парсеры LR несут больше "контекста". Чтобы увидеть это практически, рассмотрим рекурсивное определение грамматики с S в качестве стартового символа:

A -> Ax | x 
B -> Ay
C -> Az
S -> B | C

Когда k - небольшое фиксированное значение, разбор строки, такой как xxxxxxy, является задачей, более подходящей для парсера LR. Однако в наши дни популярные парнеры LL, такие как ANTLR, не ограничивают k такими небольшими значениями, и большинство людей больше не заботятся.

Я надеюсь, что это более или менее соответствует вашему вопросу. Конечно, Кнут показал, что любой однозначный контекстно-свободный язык может быть распознан какой-либо грамматикой LR (1). Однако на практике мы также относимся к переводу.

В качестве дополнительной заметки: вам также может понравиться читать http://www.antlr.org/article/needlook.html.

Это отнюдь не доказано, но я всегда сомневался в том, что LR-подобный синтаксический анализ действительно похож на то, как работает мозг при чтении определенных обозначений. Например, при чтении английского предложения довольно очевидно, что мы читаем слева направо. Но рассмотрите рисунок ниже:

.,, |,,.

Я скорее ожидаю, что с короткими шаблонами, такими как этот, люди буквально не читают "dot dot dot dot dot dot dot dot dot dot dot" слева направо, а скорее обрабатывают шаблон параллельно или, по крайней мере, в некотором роде нечеткой итерационной манеры. Другими словами, я не считаю, что мы обязательно читаем все шаблоны в порядке слева направо с помощью линейного представления, которое использует парсер LL/LR.

Кроме того, если мы можем описать любой контекстно-свободный язык с использованием грамматики LR (1), тогда ясно, что просто распознавание строки не совпадает с "пониманием" ее.

Ответ 3

Ну, для одного, левые рекурсивные определения невозможны в граммах LL (k) (насколько я знаю), не знают о других. Это не делает невозможным определить другие вещи просто огромную боль, чтобы сделать иначе. Например, объединение выражений может быть простым в леворекурсивном языке (в псевдокоде):

lexer rule expression = other rules
                        | expression
                        | '(' expression ')';

Что касается синтаксически полезных вещей, которые могут быть сделаны с лево-рекурсией, um делает более простые грамматики считаться синтаксически полезными?

Ответ 4

Возможности языка не ограничены его синтаксисом и грамматикой.

Можно определить любую функцию языка с грамматикой LL (k), она может быть не очень читаема для людей.