В чем разница между PEG и CFG?

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

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

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

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

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

Означает ли это, что грамматика PEG превосходит грамматику CFG?

33
задан Jonathan Leffler 31 March 2011 в 14:10
поделиться