LINUX.ORG.RU

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

 , , , ,


0

0

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

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

★★★

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

Ответ на: комментарий от anonymous

> Не суть, вопрос всё тот же: чем так интересен именно GLR и Packrat, и куда развивается это направление?

GLR - тем, что умеет работать с противоречивыми грамматиками, такими, как C++ (см. elkhound + elsa). Packrat - тем, что он работает без отдельного лексера, что это приличная и эффективная замена не только парсерам, но и традиционным регулярным выражениям, тем, что грамматики расширяемы (в том числе и в рантайме), тем, что PEG для многих проще для понимания чем EBNF, ну и конечно же O(n).

anonymous
()
Ответ на: комментарий от anonymous

> если смотреть её без картинок то ...

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

anonymous
()
Ответ на: комментарий от anonymous

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

Специалисты в таком случае советуют использовать голову. Для некоторых языков можно написать и LL и LR грамматики. Если уже LR не хватает, значит что-то не так :)

anonymous
()
Ответ на: комментарий от anonymous

> Если уже LR не хватает, значит что-то не так :)

Конечно же в C++ что-то глубоко, фатально не так. Но он, падла, был, есть, и будет есть. И эту гниль надо как-то парсить.

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

anonymous
()
Ответ на: комментарий от anonymous

>книгу дракона :)

Гнига дракона конечно полезна - но она не совсем по теме. Она скорее дял создателей локсобисонантлров.

r ★★★★★
()

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

Вообще-то никуда они его не выкинули. Для С++ они сделали парсер рекурсивного спуска, но это еще в 2002 г. было. А для С так и остался бизон.

> Ты бы видел как оно тормозит при компиляции грамматике языка большего чем язык калькулятора.

На парсинге оно может тормозить только если у вас _очень_ кривые руки. Основное время при компиляции обычно занимает генерация кода.

anonymous
()
Ответ на: комментарий от anonymous

> На парсинге оно может тормозить только если у вас _очень_ кривые руки.

Ага ага, или парсер написан прямыми руками, делает почти O(n) и абсолютно нечитабелен, или кривыми руками оттранслирован один в один понятный и красивый EBNF, и тормозит оно вплоть до O(exp(n)).

На фиг нам таких спиритов не надо.

anonymous
()
Ответ на: комментарий от anonymous

Да уж, изясняться надо на православном ложбане. Под него и грамматика удобная есть.

anonymous
()
Ответ на: комментарий от anonymous

> Для С++ они сделали парсер рекурсивного спуска, но это еще в 2002 г. было. А для С так и остался бизон.

гм. А как в llvm clang с этим?

anonymous
()
Ответ на: комментарий от anonymous

> Ага ага, или парсер написан прямыми руками, делает почти O(n) и абсолютно нечитабелен, или кривыми руками оттранслирован один в один понятный и красивый EBNF, и тормозит оно вплоть до O(exp(n)).

Пардон. Я думал вы это про бизона.

>> Для С++ они сделали парсер рекурсивного спуска, но это еще в 2002 г. было. А для С так и остался бизон.

>гм. А как в llvm clang с этим?

Понятия не имею.

anonymous
()
Ответ на: комментарий от r

>Гнига дракона конечно полезна - но она не совсем по теме. Она скорее дял создателей локсобисонантлров.

А что тогда читать по теме?

zabivator
()
Ответ на: комментарий от zabivator

>А что тогда читать по теме?

Смотря для чего. Если для напопробоватьдля начала - что-нить идущее вместе с выбранным пакетом - например antlr book. Есть мнение что одна из лучших книг по парсерам вот эта http://www.cs.vu.nl/~dick/PTAPG.html

r ★★★★★
()
Ответ на: комментарий от anonymous

Бизон то умеет. Но они нам древний yacc впарить пытаются.

anonymous
()
Ответ на: комментарий от exercitor

> Не знаю как сейчас, но в начальных версиях гугль юзал flex, по причине тормознутости yacc.

Ну если им хватало информации выдаваемой сканером, хватило бы и кучки regex-пов.

anonymous
()

пример с калькулятором невозбранно уныл. Лучше бы перевели более прикольный пример http://www.ibm.com/developerworks/linux/library/l-pirates4/?S_TACT=105AGX99&a... -- там тот же flex/yacc используется в простенькой RPG играчке для описания конфигов и скриптового языка. Если кто хотел работать с конфигами на lex/yacc, можно начать с него.

anonymous
()
Ответ на: комментарий от anonymous

> пример с калькулятором невозбранно уныл. Лучше бы перевели более прикольный пример http://www.ibm.com/developerworks/linux/library/l-pirates4/?S_TACT=105AGX99&a...... -- там тот же flex/yacc используется в простенькой RPG играчке для описания конфигов и скриптового языка. Если кто хотел работать с конфигами на lex/yacc, можно начать с него.

Такого рода статьи на gamedev.ru лежат

anonymous
()
Ответ на: комментарий от anonymous

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

Например ДВОРНИКОМ - приносить пользу, а не головную боль...

> Т.к. жить на что-то надо.

Эт пральна - на жизнь хватит

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

А вот не надо nerwed - работа на свежем воздухе укрепляет тело
и дух.
А после работы мохно позволить себе подобные вкусности. ((

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