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

На этой странице wikipedia:

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

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

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

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

Говорят ли, что грамматика ПЭГ превосходит CFG?

Ответ 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-conflict, поскольку он не может решить, должен ли он сдвигаться (читать другой токен) или уменьшать (заполнять node) при достижении ключевого слова else. Конечно, есть способы обойти эту проблему.

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

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

Ответ 2

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