Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 26
Многие писали ЛР на эту тему в своих ВУЗах. Я на этом собачатинки тоже отведал. Когда-то дела «рекурсивный спуск» на С++, ох как же это давно было…
>По поводу удобства: в основном, каждый хвалит тот инструмент, к которому привык, и питает неприязнь к непривычному.
>Например, процитирую один «лучший ответ» со stackoverflow, касательно спора «ANTLR vs. bison»:
> In terms of personal taste, I think that LALR grammars are a lot easier to construct and debug. The downside is you have to deal with somewhat cryptic errors like shift-reduce
>and (the dreaded) reduce-reduce. These are errors that Bison catches when generating the parser, so it doesn't effect the end-user experience, but it can make the development
> process a bit more interesting.
Вот не разделяю вашей иронии тут. Вменяемые сообщения об ошибках — это действительно очень важное качество результирующего продукта. И LR()/LALR тут реально проигрывает.
>Например, процитирую один «лучший ответ» со stackoverflow, касательно спора «ANTLR vs. bison»:
> In terms of personal taste, I think that LALR grammars are a lot easier to construct and debug. The downside is you have to deal with somewhat cryptic errors like shift-reduce
>and (the dreaded) reduce-reduce. These are errors that Bison catches when generating the parser, so it doesn't effect the end-user experience, but it can make the development
> process a bit more interesting.
Вот не разделяю вашей иронии тут. Вменяемые сообщения об ошибках — это действительно очень важное качество результирующего продукта. И LR()/LALR тут реально проигрывает.
Лолвут?
Вменяемые сообщения об ошибках разбора у бизона есть: habrahabr.ru/blogs/programming/99397/#comment_3073829
These are errors that Bison catches when generating the parser, so it doesn't effect the end-user experience
Вменяемые сообщения об ошибках разбора у бизона есть: habrahabr.ru/blogs/programming/99397/#comment_3073829
Это вы про «Один раз делаю дифф, и накладываю его на сгенерированный парсер сразу после генерации, той же строчкой в мейкфайле.»? :-)
по поводу error-verbose — это фича исключительно бизона. Скажем byacc не имеет ее. И кстати, насколько я помню — этот error-verbose в старых бизонах тоже отсутствует. ДЛя линукса это не очень важно, а на юниксах можно любую версию yacc встретить
по поводу error-verbose — это фича исключительно бизона. Скажем byacc не имеет ее. И кстати, насколько я помню — этот error-verbose в старых бизонах тоже отсутствует. ДЛя линукса это не очень важно, а на юниксах можно любую версию yacc встретить
Я не понимаю вашей логики. LR реально проигрывает потому, что когда-то в бизоне не было этой фичи?
Встретить antlr на юниксах, мне кажется, сложнее, чем современого бизона. (Или какую замену вы предлагаете?)
Встретить antlr на юниксах, мне кажется, сложнее, чем современого бизона. (Или какую замену вы предлагаете?)
логика в том, что: допиливать сообщения об ошибках приходится в любом случае. В случае с LR грамматиками гемороя больше. Эмпирически так сказать установленный факт.
что касается antlr — он может жить везде где живет ява, это же просто jar. но я кстати им не ползуюсь практически.
По поводу замены — В большинстве случаев я использую LL(сколько получится), рисую синтаксические диаграммы вирта, и по ним уже пишу парсер. «Функция на правило», пишется быстро, с такой скоростью, с какой вообще можно писать. И естественно с любой обработкой ошибок там замечательно.
Есть пара мелких старых проектов где использовал продукционные правила флойда для парсера.
Это я к тому что выбор далеко не ограничивается bison, i.e. LALR() против antlr ie LL()
что касается antlr — он может жить везде где живет ява, это же просто jar. но я кстати им не ползуюсь практически.
По поводу замены — В большинстве случаев я использую LL(сколько получится), рисую синтаксические диаграммы вирта, и по ним уже пишу парсер. «Функция на правило», пишется быстро, с такой скоростью, с какой вообще можно писать. И естественно с любой обработкой ошибок там замечательно.
Есть пара мелких старых проектов где использовал продукционные правила флойда для парсера.
Это я к тому что выбор далеко не ограничивается bison, i.e. LALR() против antlr ie LL()
Что касается бизона — он может жить везде, где есть компилятор Си, это же просто программа на Си :)
Не пытаюсь свести выбор к «bison vs. antlr»: просто именно таков был спор на stackoverflow, из которого вы неожиданно заключили об отсутствии в бизоне вменяемых сообщений об ошибках.
Не пытаюсь свести выбор к «bison vs. antlr»: просто именно таков был спор на stackoverflow, из которого вы неожиданно заключили об отсутствии в бизоне вменяемых сообщений об ошибках.
Вы невнимательно читали — не только в бизоне. В LR/LALR распознавалках.
Из за их природы. Потому что они принимают решение по _правому_ символу в нетерминале. А человеку надо в сообщение левый символ, с которым проблема.
>Что касается бизона — он может жить везде, где есть компилятор Си, это же просто программа на Си :)
Ох не дразнитесь. И сами С везде разные, и клонов yacc целый зоопарк.
Из за их природы. Потому что они принимают решение по _правому_ символу в нетерминале. А человеку надо в сообщение левый символ, с которым проблема.
>Что касается бизона — он может жить везде, где есть компилятор Си, это же просто программа на Си :)
Ох не дразнитесь. И сами С везде разные, и клонов yacc целый зоопарк.
В качестве преимуществ ANTLR в том споре приводят всё что угодно, кроме качеств собственно парсинга
Основным критерием является производительность труда программиста. «Качество собственно парсинга», если имеется ввиду производительность, при этом должно быть на приемлемом уровне, не более того.
Техническая сложность в том, что каждый новый символ, от которого зависит выполнение развёртки, увеличивает размерность таблиц перехода
В ANTLR есть возможность изменять глубину заглядывания вперед локально. То есть, для «почти» LL(1) грамматики можно построить парсер, который будет вести себя как LL(1), а в особо сложном месте заглянет вперед на нужное количество лексем (возможно, бесконечное). Это называется guessing mode: парсеру говорят, если вход от текущего места разберется как вот эта конструкция, то выбирай эту альтернативу, иначе — другую.
И нет там никаких глобальных таблиц перехода.
Но всегда правильнее преобразовать грамматику, а к lookahead прибегать только в особо запущенных случаях.
OP: '{' OPS '}' // блок
| EXPR ';' // выражение
| 'if' '(' EXPR ')' OP
| 'if' '(' EXPR ')' OP 'else' OP
| 'while' '(' EXPR ')' OP
| 'exit' ';' ;
И нет там никаких глобальных таблиц перехода.
Ниже в тексте объясняю, что он рекурсивный.
Но всегда правильнее преобразовать грамматику
Не вижу преобразования?
«Качество собственно парсинга», если имеется ввиду производительность
Речь шла о качествах, а не об абстрактном всеобъемлющем качестве.
Наверное, лучше было написать «характеристики собственно парсинга».
Имеел в виду: набор поддерживаемых грамматик (леворекурсивные не годятся), возможность изменять действия при разборе (например, структуру генерируемого дерева), и т.п.
В конечном счёте, эти характеристики влияют именно на объём труда для программиста.
-
Повторюсь: каждый программист эффективнее работает с тем, с чем привык. Для одних это бизон, для других antlr, и в этом нет ничего удивительного.
>«Качество собственно парсинга», если имеется ввиду производительность, при этом должно быть на приемлемом уровне, не более того.
it depends. Например для sql выражений скорость разбора — очень важна.
it depends. Например для sql выражений скорость разбора — очень важна.
Значит, приемлемый уровень в данном случае высок. Но с какого-то момента скорость разбора перестанет играть существенную роль, узкие места будут в другом. Из технологий, которые обеспечат такую скорость разбора, надо выбирать такую, которая минимизирует затраты на разработку (надо рассматривать весь жизненный цикл).
Я бы просто написал так:
но можно и так:
так что заглядывание вперед всё же поможет, как раз потому, что может быть произвольной длины.
Зачем нам куча дополнительных нетерминалов, когда есть extended bnf?
EXPR: NUM ( OP NUM )*;
Это одно из самых страшных зол, которые только бывают. Сгенерированный код не должен залатываться! Вместо этого DSL должен допускать вставку кода, которая попадет в нужное место сгенерированного кода.
OP: '{' OPS '}' // блок
| EXPR ';' // выражение
| 'if' '(' EXPR ')' OP ( 'else' OP )?
| 'while' '(' EXPR ')' OP
| 'exit' ';' ;
но можно и так:
OP: '{' OPS '}' // блок
| EXPR ';' // выражение
// вроде, можно не дублировать, но не помню синтаксис
| ( 'if' '(' EXPR ')' OP 'else' OP )=> 'if' '(' EXPR ')' OP 'else' OP
| 'if' '(' EXPR ')' OP
| 'while' '(' EXPR ')' OP
| 'exit' ';' ;
так что заглядывание вперед всё же поможет, как раз потому, что может быть произвольной длины.
Зачем нам куча дополнительных нетерминалов, когда есть extended bnf?
EXPR: NUM ( OP NUM )*;
невозможность написания «заплаток» на сгенерированный код, потому что он меняется при изменении грамматики, да ещё и размножается по десяткам функций.
Это одно из самых страшных зол, которые только бывают. Сгенерированный код не должен залатываться! Вместо этого DSL должен допускать вставку кода, которая попадет в нужное место сгенерированного кода.
Это одно из самых страшных зол, которые только бывают. Сгенерированный код не должен залатываться!
Имхо, зависит от назначения и от времени жизни кода.
-
Вспомнил байку: что когда Нойс и ко. изобрели интегральную схему, умудрённые опытом специалисты, привыкшие регулярно перепаивать в больших электронных устройствах вышедшие из строя радиодетали, заключили: «эта штука не найдёт практического применения — ведь сломанную ИС невозможно починить, и необходимо заменять целиком.»
Нюансы бывают. Но я формулировал правило для простых смертных, гуру могут им не следовать :)
Свой первый транслятор я писал, чтобы уйти от регулярного исправления сгенерированного кода в больших объемах :)
Свой первый транслятор я писал, чтобы уйти от регулярного исправления сгенерированного кода в больших объемах :)
Совершенно не гур и не гурий имел в виду: например, для экспериментального прототипа твикабельность ценнее удобства сопровождения, разве нет?
Для экспериментального проекта важнее всего низкие трудозатраты на эксперимент. Эксперимент — это результат любым способом, в том числе и правкой сгенерированного кода. А удобство сопровождения — это, в числе прочего, низкие трудозатраты на внесение изменений правильным способом, который не ломает технологию и не снижает качество кода. Так что да, твикабельность ценее. Но эксперименты реализуются не правкой сгенерированного кода, а правкой исходного.
// вроде, можно не дублировать, но не помню синтаксис
| ( 'if' '(' EXPR ')' OP 'else' OP )=> 'if' '(' EXPR ')' OP 'else' OP
| 'if' '(' EXPR ')' OP
не.
Вот так:
'if' '(' expr ')' op ( ('else') => 'else' op)?
то есть когда распознали then оператор, глянули на один символ вперед. Если он 'else', то продолжаем разбор. Никакое дублирование тут не нужно.
Получил по почте комментарий от незарегистрированного на Хабре читателя:
Логично в качестве позиции ошибки показывать самую правую, до которой сумела добраться хотя бы одна развёртка, — т.е. последнюю позицию, до которой у парсера ещё были надежды, что текст распарсится удачно.Вообще-то да, есть. Например вот тут: www.meta-alternative.net/mbase.html
Предполагаю, что есть реализации packrat, в которых локализация ошибки реализована именно так.
Более того, у packrat гораздо больше возможностей умного обнаружения ошибок чем у любого другого подхода, потому как в любой момент времени полно метаданных — и перепробованные варианты, и те что обломались, и те что сработали. На каждый можно вполне декларативно навесить логику сообщений об ошибках.
Так же, преимущество packrat перед автоматным LL — возможноть реализации левой рекурии в лоб.
Ну и важнейшее свойство packrat — он lexerless во первых, и расширяемый во вторых. Можно наследовать свойства грамматик, можно расширять грамматики динамически.
Всё это многократно перевешивает мизерные и неинтересные пролемы с большим линейным коэффициентом (есть куча оптимизаций, сокращающих его до минимума) и расходом памяти — на самом деле не так уж и много ее надо — для языков вроде C++ надо помнить не больше чем один top level declaration, а они обычно коротенькие.
Пример того, что можно делать с расширяемыми грамматиками см. вот тут и подробнее тут.
Так что не надо так людей packrat-ом запугивать. У packrat и GLR большое будущее, а автоматам пришел заслуженный конец.
Вам я написал, потому как когда-то у меня была точно такая же позиция (в MBase это легко прослеживается по предыдущей версии автоматного LL-генератора), и у меня был весьма прочищающий мозги разговор с автором языка Kathadin. Мне тогда это пошло на пользу. Возможно, и вам пригодится знание о том, на что способен packrat.
P.S.:
Тем более, что одно из самых естественных применений для новых компиляторов — поддержка всяких компактных платформ, где сэкономленная память имеет значение.Делаем сейчас компактный драйвер для встраиваемых устройств, на основе Clang + LLVM. Там, соответственно, банальный hard-coded recursive descent parser. Clang, как известно, рвет по скорости парсинга всех прочих в хвост и в гриву (хоть он и «ленивый слон»). Так вот, я жалею, что это не Packrat. Для такого типа грамматики мемоизацию можно или отключить или ограничить, а преимуществ было бы немало.
одно из самых естественных применений для новых компиляторов — поддержка всяких компактных платформ, где сэкономленная память имеет значение
Не могу согласиться. Обычно используется кросс-компиляция.
Логично в качестве позиции ошибки показывать самую правую, до которой сумела добраться хотя бы одна развёртка
На первый взгляд да, на практике бывают ситуации, когда ошибочный текст действительно оказывается [почти] правильной, но совсем не той конструкцией.
Я бы несколько вариантов ошибки попробовал показать. Типа, если вы хотели написать объявление функции, то вот тут ошибка, а если объявление массива — то тут.
Иногда делают так: собирают информацию о типичных ошибках. Расширяют язык так, чтобы типично ошибочные конструкции вошли в язык. Сообщение об ошибке становится действием, которое долно выполняться при распознавании этих конструкций. Эвристика, но качество может приподнять.
Рассказывали байку, кажется про DECовский С++ компилятор, который умел компенсировать пропущенные (или лишние?) разделители. Первое сообщение — тут у вас точки с запятой не хватает, не волнуйтесь, я ее сама вставлю. Второе — а чего это у вас тут точка с запятой лишняя? Позиция та же. :)
Кстати, вот что я всё хочу добавить, но забываю. Классические компиляторы уже не обеспечивают достаточное количество возможностей. При проектировании «инструмента обработки формального текста» надо учитывать потребности IDE. Иначе придется отдельно реализовывать автопродолжение, outline и прочие стандартные средства. А для IDE надо уметь частично разбирать некорректные программы, извлекая из них максимум возможной информации. К примеру, компилятор, закончив синтаксический разбор, уже не имеет права останавливаться, если были ошибки — всё равно надо пытаться выделить декларации верхнего уровня и т.п.
Отличные материалы! Спасибо.
Мне кажется, что в этой заметке уместно было упомянуть S-грамматику. Это LL без альтернатив: первый токен в правой части правил всегда терминальный и однозначно идентифицирует правило.
Мне кажется, что в этой заметке уместно было упомянуть S-грамматику. Это LL без альтернатив: первый токен в правой части правил всегда терминальный и однозначно идентифицирует правило.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Компиляция. 5: нисходящий разбор