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

[metaclass]

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

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

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

Comments

[smalgin.livejournal.com]

Если введение новой зависимости от fslex/fsyacc не проблема и код хорошо документирован, то это никакой не оверкилл, а все правильно.

А то всякое бывает, от раздутия дистрибутива до maintenance nightmares...

[justy-tylor.livejournal.com]

Наоборот. Генераторы парсеров это низкоуровневая EBNF на входе и обычно неудобный bottom-up на выходе.

Если же делать парсер на одном из рабочих языков проекта, то можно использовать в описании особые паттерны и комбинаторы (начиная с sepBy), специфичные для рассматриваемых грамматик, а также выдавать пользователю более вменяемый фидбэк при отклонении от них. Размер кода при этом может оказаться меньше, чем то, чем потом приходится обкручивать результаты *yacc.

[metaclass.livejournal.com]

Да, на комбинаторах это должно быть явно гуманнее.

[lemantar.livejournal.com]

а чем банальный регэксп не угодил?

[metaclass.livejournal.com]

Может и подошел бы, но их я знаю еще хуже, чем генераторы парсеров :)
Я с ходу не вспомню, как описать такую грамматику регэкспом, да чтобы на выходе сразу получить результат.

[lionet.livejournal.com]

ИмяКласса | ИмяКласса(Параметр0,...)

[A-Za-z0-9]+\s*(\([a-z0-9]+(,\s*[a-z0-9]+)*\))?

[lemantar.livejournal.com]

для латинских букв вполне

[lionet.livejournal.com]

А чем банальный PEG не угодил?

[metaclass.livejournal.com]

Вот мне только не хватало еще и это реализовывать, хотя как средство отмазаться от писания отчетов о проделанной работе хорошо. "С 1 по 7 июня: реализую PEG на F#" :)

[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. Ну-да ладно.

[raydac.livejournal.com]

у нас на работе предалагают вариант "долго и правильно", но тут контора богатая, за чужие бабки можно долго и правильно и даже безрезультатно если чо

[blackyblack.livejournal.com]

Ответ на вопрос зависит от того, сколько в дальнейшем появится разных грамматик для парсения. Пока их одна и больше не предвидится, то лучше разбирать руками. Когда их становится больше 3-х, то лучше использовать парсер/генератор парсеров.

[trueblacker.livejournal.com]

Вопрос можно префразировать. Какая пара из невозможной троицы (цена, время, качество) наиболее кошерна? При такой постановке отсутствие единственно верного подхода очевидна.
Скилл проджектляйтера, тимлида и прочих архитектуреров как раз и заключается в умении ппавильно расставить весовые коэффициенты в компонентах этой троицы применительно к конкретной задаче, набору доступных ресурсов и прогнозируемому спросу. В общем виде, разумеется, решения нет.
Что касается пауков, то все ок, пока их не начинаешь путать с тараканами.

[jdevelop.livejournal.com]

я бы сказал, что ответ на вопрос зависит от того, что и как может делать команда

если они не знают про парсер-комбинаторы зато джедаи в регэкспах - то вас нужно изолировать от общества их и дать им работу работать

[aamonster.livejournal.com]

Зависит от того, делать один раз или потом ещё 10 раз понадобится (и при этом правильные методы уже будут так же быстры, а в сложных случаях и быстрее)

[gabaidulin.livejournal.com]

PEG или парсер комбинаторы. На dot net вроде есть приличный PEG. Yacc/Lex после них настоящая боль.

[os80.livejournal.com]

>не является ли использование правильных методик оверкиллом?
Если моё мнение интересует, то - является. Более того, Ваш вопрос надо переформулировать по-другому - является ли разумным использование формата, для парсинга которого нужны правильные методики.