Практические последствия питания формальной грамматики?
Каждое студенческое Введение к курсу Компиляторов рассматривает обычно реализованные подмножества контекстно-свободных грамматик: LL (k), SLR (k), LALR (k), LR (k). Нам также преподают, что для любого данного k, каждая из тех грамматик является подмножеством следующего.
То, что я никогда не видел, является объяснением того, какие виды языка программирования синтаксические функции могли бы потребовать перемещения в другой класс языка. Существует очевидная практическая мотивация для GLR парсеров, а именно, избегая безобразного смешения синтаксического анализатора и таблицы символов при парсинге C++. Но что относительно различий между двумя "стандартными" классами, LL и LR?
Два вопроса:
- Какие (общие) синтаксические конструкции могут быть проанализированы с LR (k), но не LL (k')?
- В каких путях, если таковые имеются, те конструкции проявляют как желательные конструкции языка?
Существует вероятный аргумент в пользу того, чтобы уменьшить мощность языка путем создания k как можно меньше, потому что язык, требующий многих, много маркеров предвидения будут более трудны для людей проанализировать, а также "тяжелее" чтобы машины проанализировали. Вопрос (2) неявно спрашивает, заканчивает ли то же обоснование тем, что содержало между классами, а также в классе.
править: Вот один пример для иллюстрирования видов ответов, которые я ищу, но для регулярных языков вместо контекстно-свободного:
При описании регулярного языка каждый обычно получает три оператора: +, *, и ?. Теперь, можно удалить + не уменьшая мощность языка; вместо записи x+, Вы пишете xx*, и эффект является тем же. Но если x некоторое большое и волосатое выражение, два xs, вероятно, будут отличаться со временем из-за человеческого забвения, приводя к синтаксически корректному регулярному выражению, которое не соответствует намерению исходного автора. Таким образом, даже при том, что добавление + строго не добавляет питание, оно действительно делает нотацию менее подверженной ошибкам.
Есть ли конструкции с практичным подобным (человек?) эффекты, которые должны быть "удалены" при переключении от LR до LL?
4 ответа
Парсинг (я утверждаю) немного похож на сортировку: проблема, которая была предметом многих размышлений в первые дни CS, что привело к набору хорошо понятных решений с некоторыми хорошие теоретические результаты.
Я утверждаю, что картина, которую мы получаем (или даем тем из нас, кто преподает) в классе компиляторов, в некоторой степени является прекрасным ответом на неправильный вопрос.
Ответить ваш вопрос более прямо, грамматика LL (1) не может анализировать все виды вещей, которые вы, возможно, захотите проанализировать; например, «естественная» формулировка «if» с необязательным «else»
Но подождите! Разве я не могу переформулировать свою грамматику как грамматику LL (1), а затем исправить дерево исходных текстов, пройдя по нему после этого? Что вы можете! До некоторой степени, это то, что делает вопрос о том, какую грамматику использует ваш синтаксический анализатор, в значительной степени спорным.
Кроме того, когда я был студентом (1990-94), грамматики, чувствительные к пробелам, явно были делом рук дьявола; Теперь же в проектах Python и Haskell снова появляется чувствительность к пробелам. Кроме того, синтаксический анализ Packrat говорит: «Для проверки вашей теоретической чистоты: я просто собираюсь определить синтаксический анализатор как набор правил, и меня не волнует, к какому классу принадлежит моя грамматика». (перефразировано)
Таким образом, я согласен с тем, что, как я считаю, является вашим подразумеваемым предложением: в 2009 году четкое понимание разницы между классами LL (k) и LR (k) само по себе менее важно, чем способность формулировать и отлаживать грамматику, которая делает ваш генератор синтаксического анализатора счастливым.
когда я был студентом (1990-94), грамматики, чувствительные к пробелам, явно были делом рук Дьявола; Теперь же в проектах Python и Haskell снова появляется чувствительность к пробелам. Кроме того, синтаксический анализ Packrat говорит: «Для проверки вашей теоретической чистоты: я просто собираюсь определить синтаксический анализатор как набор правил, и меня не волнует, к какому классу принадлежит моя грамматика». (перефразировано)Таким образом, я согласен с тем, что, как я считаю, является вашим подразумеваемым предложением: в 2009 году четкое понимание разницы между классами LL (k) и LR (k) само по себе менее важно, чем способность формулировать и отлаживать грамматику, которая делает ваш генератор синтаксического анализатора счастливым.
когда я был студентом (1990-94), грамматики, чувствительные к пробелам, явно были делом рук Дьявола; Теперь же в проектах Python и Haskell снова появляется чувствительность к пробелам. Кроме того, синтаксический анализ Packrat говорит: «Чтобы проверить вашу теоретическую чистоту: я просто собираюсь определить синтаксический анализатор как набор правил, и меня не волнует, к какому классу принадлежит моя грамматика». (перефразировано)В общем, я бы согласился с тем, что я считаю подразумеваемым предложением: в 2009 году четкое понимание разницы между классами LL (k) и LR (k) само по себе менее важно, чем способность формулировать и отлаживать грамматику, которая делает ваш генератор синтаксического анализатора счастливым.
дизайны возвращают в свет чувствительность к пустому пространству. Кроме того, синтаксический анализ Packrat говорит: «Для проверки вашей теоретической чистоты: я просто собираюсь определить синтаксический анализатор как набор правил, и меня не волнует, к какому классу принадлежит моя грамматика». (перефразировано)В общем, я бы согласился с тем, что я считаю подразумеваемым предложением: в 2009 году четкое понимание разницы между классами LL (k) и LR (k) само по себе менее важно, чем способность формулировать и отлаживать грамматику, которая делает ваш генератор синтаксического анализатора счастливым.
дизайны возвращают в свет чувствительность к пустому пространству. Кроме того, синтаксический анализ Packrat говорит: «Чтобы проверить вашу теоретическую чистоту: я просто собираюсь определить синтаксический анализатор как набор правил, и меня не волнует, к какому классу принадлежит моя грамматика». (перефразировано)Таким образом, я согласен с тем, что, как я считаю, является вашим подразумеваемым предложением: в 2009 году четкое понимание разницы между классами LL (k) и LR (k) само по себе менее важно, чем способность формулировать и отлаживать грамматику, которая делает ваш генератор синтаксического анализатора счастливым.
ну, во-первых, леворекурсивные определения невозможны в грамматиках LL (k) (насколько я знаю), не знаю о других. Это не делает невозможным определение других вещей, просто огромная боль делать иначе. Например, составление выражений может быть простым на леворекурсивном языке (в псевдокоде):
lexer rule expression = other rules
| expression
| '(' expression ')';
Что касается синтаксически полезных вещей, которые могут быть сделаны с помощью левой рекурсии,
The capabilities of a language are not limited by its syntax and grammar.
It's possible to define any language feature with an LL(k) grammar, it just might not be very readable to humans.
Разница между 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-подобный синтаксический анализ похож на то, как работает мозг при чтении определенных обозначений. Например, при чтении предложения на английском довольно очевидно, что мы читаем слева направо. Но рассмотрим схему, представленную ниже:
. . . . . | . . . . .
Я скорее ожидаю, что с короткими шаблонами, такими как этот, люди не будут буквально читать «точка, точка, точка, точка, точка, точка, точка, точка, точка, точка, точка, точка, точка» слева направо, а скорее будут обрабатывать узор параллельно или, по крайней мере, в некоторых своего рода нечеткий итеративный способ. Другими словами, я не верю, что мы обязательно читаем все шаблоны слева направо с таким линейным просмотром вперед, который использует анализатор LL / LR.
Кроме того,