Каковы различия между 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)

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

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

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

Answer 2

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