Ограничения генераторов грамматики и парсера PEG?
Мне очень понравилось пользоваться YARD:
http://code.google.com/p/yardparser/
http://www.codeproject.com/KB/recipes/yard-tokenizer.aspx
Мне удалось построить полностью функциональный калькулятор. Я оцениваю YARD, чтобы сделать парсер PHP. Пожалуйста, сообщите об ограничениях PEG-грамматики и генераторов парсера. Большое спасибо!
2 ответа
Я думаю, что большая "проблема" с PEG заключается в том, что они не вписываются в обычную таксономию грамматик, так как работают совершенно иначе. Нормальные грамматики являются "задом наперед" в том смысле, что они описывают все возможные предложения (программы), которые могут быть сгенерированы. PEG описывают, как анализировать - они приходят к проблеме с другого конца.
На мой взгляд, это более естественный способ думать о проблеме, и, конечно же, для любого рукописного синтаксического анализатора (рекурсивного спуска) я бы больше ничего не делал.
Основным ограничением грамматик PEG является то, что они вообще не имеют дело с неоднозначностью.
Безусловно, это также их сила, поскольку работа с неясностями является одной из самых неприятных частей использования инструмента CFG (контекстно-свободной грамматики).
С PEG вы имеете дело с неоднозначностями, упорядочивая правило, которому хотите соответствовать, перед другим правилом, которое будет соответствовать неоднозначно, но которое вам не нужно.
Проблема в том, что вы не всегда знаете даже некоторые или даже какие-либо двусмысленности в языке или грамматике и генераторах PEG, по крайней мере те, которые я пробовал, не анализируйте грамматику на предмет неоднозначности, чтобы помочь вам найти их, а затем разработать и упорядочить ваши правила, чтобы правильно с ними справиться.
Генераторы парсеров CFG, такие как yacc и bison, анализируют вашу грамматику и сообщают обо всех неясностях. К сожалению, они часто сообщают о них довольно загадочно, что может быть трудно понять. И, конечно, часто трудно исправить грамматику, чтобы справиться с ними. Но, по крайней мере, вы будете знать, что они существуют.
С PEG грамматикой вы можете быть блаженно неосведомлены о неясностях в вашей концептуальной грамматике, потому что, как только вы сделаете ее PEG, у нее больше не будет двусмысленности, у нее просто будут соответствующие правила и, возможно, бездействующие правила, которые также будут совпадать, если бы они имели более высокий уровень старшинство. Они могут не отображаться в вашем тестировании, но могут появиться после выпуска.
С грамматикой CFG вы вынуждены иметь дело с неясностями во время разработки, но это будет нелегко.
В случае, если я не проясню, вот шестилетняя дискуссия Джошуа Хабермана на блоге Lambda the Ultimate Языки программирования: PEGs и Packrat Parsing не являются ответом.