Парсерный оверкилл?

[metaclass]

Внезапно понадобилось сделать парсер строк с грамматикой подобного вида:
ИмяКласса | ИмяКласса(Параметр0,...)

Можно было бы не вдумываясь, склепать что-нибудь типа "найти скобки, до скобок - имя класса, внутри скобок разделить по запятым".
Но мне домашний паук из розетки приказал это сделать на генераторах парсеров, в частности fslex/fsyacc, что заняло немного больше времени, но как минимум, я теперь смогу при необходимости нормально менять грамматику или писать новые парсеры, разобравшись на простом примере.

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

Comments

[thedeemon.livejournal.com]

Комбинаторы это дело реализуют, а сами они гораздо проще в реализации и использовании, чем это может показаться. Там кода-то строк 20.

[permea-kra.livejournal.com]

Ну их нафиг, там надо очень тщательно за строением грамматики следить. Левой рекурсии низзя, легко напороться на экпонециальные затраты времени... Нафиг, нафиг.

[gabaidulin.livejournal.com]

Пакрат не решает эту проблему разве?

[permea-kra.livejournal.com]

Не-а. Пусть char 'x' - завершается успешно, если встретился x, а || порождает парсер, принимающий либо лево, либо право. Тогда парсер
a = ( a || char 'x' ++ something ) свалится в бесконечную рекурсию. В тоже время нормальный парсер-генератор такую грамматику вполне отработает. От мемоизации промежуточных результатов ничего не изменится.

Данная проблема принципиально неразрешима в рамках традиционных парсер комбинаторов, нужно имитировать один из универсальных алгоритмов парсинга. Часть библиотек отслеживает такую дурную рекурсию и ругаются, но это паллиатив.

[gabaidulin.livejournal.com]

Ну значит manual по scala видимо говорит про какую-то другую левую рекурсию ?

http://www.scala-lang.org/api/current/scala/util/parsing/combinator/PackratParsers.html

[permea-kra.livejournal.com]

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

[gabaidulin.livejournal.com]

Хмм. Ну вообще с точки зрения кода эту будет тот же парсер комбинатор(то есть мы строим грамматику состоящую из простых правил с использованием простых парсеров, комбинируя их в более сложные с помощью специальных операторов), надо будет добавить with PackratParser и использовать lazy vals. Ну-да ладно.