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