LINUX.ORG.RU

Создание анализаторов текста при помощи yacc и lex

 , , , ,


0

0

В этой статье на примере создания простого калькулятора показано, как создать анализатор при помощи инструментов lex/flex и yacc/bison, а затем более подробно рассмотрено, как применить эти принципы к синтаксическому разбору текста. Синтаксический разбор текста - анализ и извлечение ключевых частей текста - важная часть многих приложений. В UNIX® многие элементы операционной системы зависят от синтаксического анализа текста: оболочка, которая используется для взаимодействия с системой, распространенные утилиты и команды типа awk или Perl, вплоть до компилятора Си, используемого для разработки приложений. Анализаторы собственной разработки можно использовать в UNIX-программах (и не только UNIX) для создания простых анализаторов конфигурации или даже для создания своего собственного языка программирования.

>>> Подробности

★★★

Проверено: maxcom ()

Re: Создание анализаторов текста при помощи yacc и lex

>В этой статье на примере создания простого *калькулятора* показано, как создать анализатор при помощи инструментов lex/flex и yacc/bison

не читал, но по ссылке ходить боюсь о_О

volh ★★ ()

Re: Создание анализаторов текста при помощи yacc и lex

Да. Статья - Ъ.

dikiy ★★☆☆☆ ()

Re: Создание анализаторов текста при помощи yacc и lex

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

а вы используете бизон в своих проектах?

anonymous ()

Re^2: Создание анализаторов текста при помощи yacc и lex

> баян.. я ещё в институте калькулятор на бизоне делал. там у них это самый главный пример был. почему то мне кажется и единственный =))

> а вы используете бизон в своих проектах?


Допустим, не бизон, а antlr, но используем. А поцчему ви спгашиваете?

gaa ★★ ()

Re: Создание анализаторов текста при помощи yacc и lex

во-первых пример создания калькулятора есть в info bison. во-вторых домащняя страничка IBM_dW сасед. если смотреть её без картинок то вместо стрелки на следующую страницу написано "на предыдущую страницу". вместо стрелки на предыдущую страницу красуется та же надпись.

а вообще разработчики gcc посчитали что бизон ацтой и выкинули его из гнуса4. в гнус3 он был. хотя может счас опять посчитают что он крут?

капча lipsed говорит что lisp - наше все

anonymous ()

Re: Создание анализаторов текста при помощи yacc и lex

О! Как ни странно, но давно хотел почитать про эти две тулзы. Как раз кстати.

Bohtvaroh ★★★★ ()

Re: Создание анализаторов текста при помощи yacc и lex

прочитал статью и не понял: как с помощью bison/flex построить AST? В статье просто распечатываются строковые лексемы, не строится дерево разбора (CST), не строится семантическое дерево в AST. Пример с интерпретатором слишком простой, ничего не показывает. Куда интереснее пример с транслятором исходников с одного языка в другой (желательно, не как с распечаткой строковых лексем, как тот макрос с распечаткой ассемблерной вставки в статье). На таком комплексном примере понадобилось бы и построить AST из CST, трансформировать его из одного входного языка через метаязык в другой целевой, как-то обеспечить автоматическое построение CST/разных AST из единой спецификации, какая-то обработка ошибок, тестирование, профилирование и оценка производительности парсера. Для введения в предмет, впрочем, статья неплохая. Хотя на современных средствах вроде ANTLR/LLVM/HLVM/BNFC/Happy можно найти и более жизненный пример, весь цикл целиком в рамках одного инструментария.

anonymous ()

Re: Создание анализаторов текста при помощи yacc и lex

> прочитал статью и не понял: как с помощью bison/flex построить AST? В статье просто распечатываются строковые лексемы, не строится дерево разбора (CST), не строится семантическое дерево в AST. Пример с интерпретатором слишком простой, ничего не показывает. Куда интереснее пример с транслятором исходников с одного языка в другой (желательно, не как с распечаткой строковых лексем, как тот макрос с распечаткой ассемблерной вставки в статье). На таком комплексном примере понадобилось бы и построить AST из CST, трансформировать его из одного входного языка через метаязык в другой целевой, как-то обеспечить автоматическое построение CST/разных AST из единой спецификации, какая-то обработка ошибок, тестирование, профилирование и оценка производительности парсера. Для введения в предмет, впрочем, статья неплохая. Хотя на современных средствах вроде ANTLR/LLVM/HLVM/BNFC/Happy можно найти и более жизненный пример, весь цикл целиком в рамках одного инструментария.

А что почитать более полноценного посоветуете по теме?

Bohtvaroh ★★★★ ()

Re: Создание анализаторов текста при помощи yacc и lex

Да и нечего там по ссылке делать. Все дружно читаем первые 3-4-е главы Керниган/Пайк "Введение в UNIХ" от 19хх-лохматого года. Потом в руки берётся двухтомник Д.Грис "Создание компиляторов" и вдумчиво читается до потери пульса. Потом всё это, убирается в дальний угол, присыпается другой макулатурой, и все дружно идём работать. Т.к. жить на что-то надо.

Капча:nerwed - поди догадайся на что она намекает ....

anonymous ()

Re: Создание анализаторов текста при помощи yacc и lex

>не читал, но по ссылке ходить боюсь о_О

И праина.

Системные требования

Нет.


Продолжительность

2 часа

Форматы
html

Проснулись! Усцыкуха!

vada ★★★★★ ()

Re: Создание анализаторов текста при помощи yacc и lex

для программирующих на С++ рекомендую boost.spirit - удобная штука, при этом никаких зависимостей от внешних утилит

ott ★★★★★ ()

Re: Создание анализаторов текста при помощи yacc и lex

А spirit? =)

ierton ()

Re: Создание анализаторов текста при помощи yacc и lex

Юзаю yapp - yacc для перла. (Там есть AST, если кому надо.)

Но мощностей yacc не хватает, так как грамматика внезапно перестала быть LRn. Что можно использовать в таком случае?

anonymous ()

Re: Создание анализаторов текста при помощи yacc и lex

> для программирующих на С++ рекомендую boost.spirit - удобная штука, при этом никаких зависимостей от внешних утилит

Ты бы видел как оно тормозит при компиляции грамматике языка большего чем язык калькулятора. Bison2.3 с шаблоном для С++ (lalr1) и ручным сканером неплохо работают, но тоже есть недостатки.

А antlr3 для С++ так никто еще и не сделал :(

anonymous ()

Re: Создание анализаторов текста при помощи yacc и lex

> Но мощностей yacc не хватает, так как грамматика внезапно перестала быть LRn. Что можно использовать в таком случае?

А что за язык такой?

anonymous ()

Re: Создание анализаторов текста при помощи yacc и lex

> а ты попробуй написать полноценный шелл с паплайнами, эндами, орами, ковычками без лекса\бисона

Вот как раз пазбор синтаксиса шелла замечательно реализуется при помощи ручного рекурсивного разбора.

anonymous ()

Re: Создание анализаторов текста при помощи yacc и lex

Классно! А я еще много-много лет назад читал книжицу Кернигана и Пайка. И надо же, там тоже калькулятор на lex + yacc рассматривался. Вот оказывается, кто идеи у ИбэМе ворует! И если бы не IBM EE/A сидели бы мы тут без знания, что "UNIX - универсальная среда программирования".

Bioreactor ★★★★★ ()

Re: Создание анализаторов текста при помощи yacc и lex

а что означает "Поделиться этой статьей: забобрить" ?

anonymous ()

Re: Создание анализаторов текста при помощи yacc и lex

> Потом всё это, убирается в дальний угол, присыпается другой макулатурой, и все дружно идём работать. Т.к. жить на что-то надо.

Лузерство.

sv75 ★★★★★ ()

Re: Создание анализаторов текста при помощи yacc и lex

>> А antlr3 для С++ так никто еще и не сделал :(

> То есть оно только для жавы/C#, ни С, ни С++?


Для C есть, для C++ обещают, но пока что не сделали.

gaa ★★ ()

Re: Создание анализаторов текста при помощи yacc и lex

> Для C есть, для C++ обещают, но пока что не сделали.

А! То есть там именно голый С? Очень хорошо, а то в apt-cache show antlr3 что-то нехорошеее пишут про С...

sv75 ★★★★★ ()

Re: Создание анализаторов текста при помощи yacc и lex

Есть вроде Antlr2.7/C++ http://antlr.org/grammar/list "C++ David Wigg Wed Dec 19, 2007 03:48 This is my final update of the CPP_parser (V3.2) using ANTLR V2.7 to generate C++ parser in C++. I now wish to hand it on to someone else for maintenance and further development (eg. to use ANTLR V3.0). David Wigg, wiggjd@bcs.org.uk"

есть D, тоже 2.7

anonymous ()

Re: Создание анализаторов текста при помощи yacc и lex

Нда, в то время, как прогрессивное человечество использует packrat и GLR, пользуется прогрессивными генераторами парсеров, такими, как Antlr, IBM решили осчастливить нас рассказом о технологии тридцатилетней давности.

anonymous ()

Re: Создание анализаторов текста при помощи yacc и lex

> Потом всё это, убирается в дальний угол, присыпается другой макулатурой, и все дружно идём работать. Т.к. жить на что-то надо.

Намекаешь, что ты лузер, работаешь быдлокодером, и тебе всё это в работе ни разу не пригдилось? Так тут кроме тебя самого никто и не виноват.

anonymous ()

Re: Создание анализаторов текста при помощи yacc и lex

А вот можно ли как-то обзорно рассказать о современных парсерах, средах и направлениях развития?
Вот одно направление "классический LALR парсер". В духе YACC/Golden Parser/Ragel/lemon/ANTLR/SableCC и т.п. В итоге, конечный автомат для разбора. Куда оно развивается? В сторону большей "инструментальности" -- готовые грамматики, IDE вроде ANTLR Works или GoldParser Builder, для отладки грамматики, интеграция на разных этапах от грамматики до CST/AST/кодогенератора.
Вот второе направление -- комбинаторные парсеры, GLR, Packrat. Куда оно развивается? Парсер на Хаскелле в принципе можно вывести неявно из единой спецификации (в которой и грамматика, и кодогенератор, и подписанные узлы для AST вроде LBNF из BNFC). Сама программа -- расширяемый парсер. Куда развиваются они, в сторону лучших O(n), в сторону более широких грамматик?
В общем не очень понятно как отлаживать парсер, по производительности, в худшем/лучшем/реальном случае. Что-то вроде юниттестов. Не очень понятен процесс отладки (расширения самого парсера). Ну типа проверка на не описанные типы и использование замыканий/switch..case/системы типов для отлова этого момента. Не очень понятен процесс диагностики ошибок для функционального парсера, на лиспе, или там хаскелле.
Да, в OCaML вроде есть какой-то встроенный lex. Где его место, для чего он годится, а для чего -- не очень применим?

anonymous ()

Re: Создание анализаторов текста при помощи yacc и lex

точнее, генератор LL(k) парсеров.

Tokenizer есть и в стандартной библиотеке С и в Java и это не далеко ушло от lex который есть в каком то там Lisp-е.

anonymous ()

Re: Создание анализаторов текста при помощи yacc и lex

опять калькулятор! сколько можно? это уже даже не боян -- это классика.

beastie ★★★★★ ()

Re^2: Создание анализаторов текста при помощи yacc и lex

>> Для C есть, для C++ обещают, но пока что не сделали.

> А! То есть там именно голый С? Очень хорошо, а то в apt-cache show antlr3 что-то нехорошеее пишут про С...


Я какой вообще смысл юзать antlr для C при живом yacc?

gaa ★★ ()

Re: Re^2: Создание анализаторов текста при помощи yacc и lex

> Я какой вообще смысл юзать antlr для C при живом yacc?

Например, для генерации боле понятных пользователю сообщений об ошибках. yacc/bison во многих случаев позволяет писать сообщения уровня unexpected 'TOKEN'".

anonymous ()

Re: Создание анализаторов текста при помощи yacc и lex

А мы в свое время в универе делали компилятор на бизоне чего-угодно в Java байт-код... У меня objective-c был, у других ПХП, смоллтолк и т.д.

И ничо, работало.

alexey_ ()

Re: Создание анализаторов текста при помощи yacc и lex

>ANTLR - это LL(k) парсер.

да, напутал, LALR -- это GoldParser. Не суть, вопрос всё тот же: чем так интересен именно GLR и Packrat, и куда развивается это направление? И почему выбрал именно их, из-за более широкого класса грамматик или из-за более быстрого алгоритма?

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.