Ограничения генераторов грамматики PEG и синтаксических анализаторов?

Question

Мне очень нравилось пользоваться YARD:

http://www.ootl.org/yard/

http://code.google.com/p/yardparser/

http://www.codeproject.com/KB/recipes/yard-tokenizer.aspx

Мне удалось сконструировать полностью функциональный калькулятор.Я оцениваю YARD для создания PHP-парсера.Пожалуйста, любезно сообщите об ограничениях генераторов грамматики PEG и синтаксических анализаторов.Большое вам спасибо!

Answer 1

Я думаю, что большая "проблема" с привязками заключается в том, что они не вписываются в обычную таксономию грамматик, поскольку они работают принципиально по-другому.Обычные грамматики являются "обратными" в том смысле, что они описывают все возможные предложения (программы), которые могут быть сгенерированы.Привязки описывают, как выполнять синтаксический анализ - они подходят к проблеме с другой стороны.

На мой взгляд, это более естественный способ обдумать проблему, и, конечно, для любого написанного от руки парсера (с рекурсивным спуском) я бы не стал делать ничего другого.

Answer 2

Основное ограничение грамматик PEG заключается в том, что они вообще не имеют дела с двусмысленностью.

Безусловно, в этом также заключается их сильная сторона, поскольку работа с двусмысленностями - одна из самых неприятных частей использования инструмента CFG (контекстно-свободная грамматика).

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

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

Генераторы синтаксического анализа CFG, такие как yacc и bison, анализируют вашу грамматику и сообщают обо всех двусмысленностях.К сожалению, они часто сообщают о них в довольно загадочной форме, в которой бывает трудно разобраться.И, конечно, часто бывает трудно исправить грамматику, чтобы справиться с ними.Но, по крайней мере, вы будете знать, что они существуют.

С помощью грамматики ПРИВЯЗКИ вы можете пребывать в блаженном неведении о двусмысленностях в вашей концептуальной грамматике, потому что, как только вы сделаете ее привязкой, в ней больше не будет двусмысленностей, у нее просто будут соответствующие правила и, возможно, молчаливо недоступные правила, которые также соответствовали бы, если бы у них был более высокий приоритет.Они могут не отображаться в вашем тестировании, но могут появиться после выпуска.

С CFG-грамматиками вы вынуждены иметь дело с неоднозначностями во время разработки, но это будет нелегко.

---

На тот случай, если я не совсем ясно объясняю, вот дискуссия шестилетней давности Джошуа Хабермана на Лямбда -предельный блог о языках программирования: Привязки и синтаксический анализ Packrat - это не ответ.