Каковы различия между PEG и CFG?

Question

С этой страницы википедии:

Принципиальная разница между контекстно-свободными грамматиками и грамматиками синтаксического анализа выражений состоит в том, что оператор выбора PEG упорядочен. Если первая альтернатива успешна, вторая альтернатива игнорируется. Таким образом, упорядоченный выбор не является коммутативным, в отличие от неупорядоченного выбора, как в контекстно-свободных грамматиках и регулярных выражениях. Упорядоченный выбор аналогичен операторам мягкой резки, доступным в некоторых языках логического программирования.

Почему оператор выбора PEG замыкает сопоставление? Это потому, что минимизировать использование памяти (из-за запоминания)?

Я не уверен, что оператор выбора в регулярных выражениях, но давайте предположим, что это: /[aeiou]/ соответствовать гласной. Так что это регулярное выражение коммутативно, потому что я мог бы написать его в любом из 5! (пять факторных) перестановок гласных символов? т.е. /[aeiou]/ ведет себя так же, как /[eiaou]/, В чем преимущество того, что он коммутативный? (см. некоммутативность PEG)

Следствием этого является то, что, если CFG транслитерируется непосредственно в PEG, любая неоднозначность в первом разрешается путем детерминистического выбора одного дерева разбора из возможных разборов. Тщательно выбирая порядок, в котором указываются грамматические альтернативы, программист имеет большой контроль над тем, какое дерево разбора выбрано.

Это говорит о том, что грамматика PEG превосходит CFG?

Answer 1

Грамматика CFG является недетерминированной, что означает, что некоторые входные данные могут привести к двум или более возможным деревьям разбора. Хотя большинство генераторов синтаксических анализаторов на основе CFG имеют ограничения по определимости грамматики. Он выдаст предупреждение или ошибку, если у него есть два или более выбора.

Грамматика PEG является детерминированной, что означает, что любой вход может быть проанализирован только одним способом.

Взять классический пример; Грамматика

if_statement := "if" "(" expr ")" statement "else" statement
              | "if" "(" expr ")" statement;

применяется к входу

if (x1) if (x2) y1 else y2

может быть проанализирован как

if_statement(x1, if_statement(x2, y1, y2))

или же

if_statement(x1, if_statement(x2, y1), y2)

CFG-парсер генерирует конфликт Shift/Reduce, так как он не может решить, должен ли он сдвигаться (читать другой токен) или уменьшать (завершать узел) при достижении ключевого слова "else". Конечно, есть способы обойти эту проблему.

PEG-парсер всегда выберет первый выбор.

Какой из них лучше, решать вам. Мое мнение таково, что часто PEG-грамматику легче писать, а грамматику CFG легче анализировать.

Answer 2

Я думаю, что вы путаете CFG с LR и с неопределенностью. Грамматики не являются детерминированными / недетерминированными, хотя их синтаксические анализаторы могут быть. Неоднозначная грамматика по-прежнему является CFG, если она соответствует определению, и для нее можно построить детерминированный синтаксический анализатор, выполняющий то же, что и PEG.

Answer 3

PEG и CFG — это два разных способа определения языка. Если вы пишете синтаксический анализатор вручную, велики шансы, что вы напишете так называемый синтаксический анализатор рекурсивного спуска. Парсер рекурсивного спуска автоматически разрешает любые неясности в вашей грамматике, но делает это молча и, вероятно, не так, как вам хотелось бы. Проблема в том, что вы никогда не обнаружите двусмысленности, которые были разрешены автоматически, если только вы тщательно не протестируете свой синтаксический анализатор. PEG — это, по сути, формализация парсеров рекурсивного спуска, и поэтому у них возникает эта проблема. Примеры этой проблемы см. в разделе Как поиск с возвратом влияет на язык, распознаваемый синтаксическим анализатором?и https://cs.stackexchange.com/questions/143480/dragon-book-4-4-5-exercise/143975.

У CFG есть много теории, подтверждающей их, но у PEG не так много. Набор языков, которые могут быть закодированы с помощью CFG, и те, которые могут быть закодированы с помощью PEG, частично перекрываются, но не охватывают друг друга.

Для более тщательного рассмотрения этого вопроса я рекомендую отличное эссе « Какой синтаксический анализ?»