15.3.1. yacc и lex

15.3.1. yacc и lex

Программы yacc и lex являются инструментальными средствами для генерации синтаксических анализаторов языков программирования. В главе 8 отмечалось, что свой первый мини-язык программист часто создает случайно, а не как часть запланированной конструкции. В результате, как правило, появляется созданный вручную синтаксический анализатор, который приводит к чрезмерным затратам времени на сопровождение и отладку, особенно, если разработчик не поймет, что часть разработанного им кода является синтаксическим анализатором и не отделит его соответствующим образом от остальной части кода приложения. Генераторы синтаксических анализаторов являются инструментами, которые позволяют добиться большего, чем создание случайной, узкоспециальной реализации. Они не только позволяют разработчику выразить спецификацию грамматики на более высоком уровне, но и четко отделяют сложность реализации синтаксического анализатора от остального кода.

Если разработчик достиг того момента, когда планируется реализовать мини- язык с нуля, а не путем расширения или внедрения существующего языка сценариев или анализатора XML, то утилиты yacc и lex, вероятно, окажутся наиболее важными инструментами после компилятора С.

Как lex, так и yacc генерируют код для одной функции, соответственно, для "получения лексемы из входного потока" и для "синтаксического анализа последовательности лексем на предмет ее соответствия грамматике". Обычно созданная yacc функция синтаксического анализатора вызывает функцию анализатора лексем, сгенерированного lex, каждый раз при необходимости получения следующей лексемы. Если в yacc-сгенерированном синтаксическом анализаторе вообще не существует написанных пользователем обратных вызовов С, то работа данного анализатора сводится только к проверке синтаксиса. Возвращаемое значение сообщит вызывающей программе о совпадении входных данных с ожидаемой грамматикой.

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

Утилита yacc имеет довольно некрасивый интерфейс — через экспортируемые глобальные переменные с именным префиксом yy_. Это связано с тем, что программа yacc предшествовала структурам С. Фактически yacc предшествовала самому языку С; первая реализация утилиты была написана на языке В, предшественнике С. Грубый, хотя и эффективный алгоритм, используемый в сгенерированных yacc синтаксических анализаторах при попытках восстановления после ошибок анализа (лексемы выталкиваются до тех пор, пока не обнаружится явная ошибка), также может привести к проблемам, включая утечки памяти.

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

Стив Джонсон.

Программа lex — генератор лексических анализаторов. Она входит в состав того же функционального семейства, что и grep(1) и awk(1), но является более мощной, поскольку позволяет подготовить произвольный С-код для выполнения при каждом совпадении. Программа принимает декларативный мини-язык и создает "скелетный" С-код.

Для того чтобы понять работу lex-сгенерированного анализатора лексем, существует грубый, но удобный способ — мысленная инверсия работы grep(1). Тогда как grep(1) принимает одно регулярное выражение и возвращает список совпадений во входном потоке данных, каждый вызов lex-сгенерированного анализатора лексем принимает список регулярных выражений и указывает, какое выражение встречается следующим в потоке данных.

Разделение анализа ввода на распознавание лексем и синтаксический анализ потока лексем является полезным тактическим приемом, даже если в ходе разработки утилиты Yacc и Lex не используются, а "лексемы" не имеют ничего общего с обычными лексемами в компиляторе. Неоднократно я убеждался, что разделение обработки входных данных на два уровня значительно упрощает код и облегчает понимание, несмотря на сложность, внесенную самим разделением.

Генри Спенсер.

Утилита lex была написана для автоматизации создания лексических анализаторов (анализаторов лексем) для компиляторов. Впоследствии оказалось, что она имеет удивительно широкий диапазон применения для других видов распознавания образцов, и с тех пор описывается как "швейцарский нож Unix-программирования"[125].

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

Джон Джарвис (John Jarvis) в Холмделе (Holmdel — лаборатория AT&T) использовал lex для поиска неисправностей в монтажных платах. Он сканировал плату, применял методику кодирования цепей для представления границ областей на плате, а затем использовал Lex для определения образцов, с помощью которых можно было бы находить распространенные ошибки монтажа.

Майк Леск.

Важнее то, что мини-язык lex-спецификации является более высокоуровневым и компактным, чем эквивалентный С-код, написанный вручную. Доступны модули для использования flex (версия с открытым исходным кодом) с Perl (их можно найти в Web с помощью фразы "lex perl"), а также идентично работающая реализация, которая является частью средства PLY в Python.

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

Утилита yacc — генератор синтаксических анализаторов. Она также была написана для автоматизации части работы по написанию компиляторов, yacc принимает на входе грамматическую спецификацию в декларативном мини-языке, подобном BNF (Backus-Naur Form — запись Бэкуса-Наура), с С-кодом, связанным с каждым элементом грамматики. Данная программа генерирует код для функции синтаксического анализа, которая при вызове принимает текст, соответствующий грамматике из входного потока. По мере распознавания каждого грамматического элемента, функция анализатора запускает связанный С-код.

Комбинация утилит lex и yacc весьма эффективна для написания языковых интерпретаторов всех видов. Хотя большинству Unix-программистов никогда не придется выполнять данный вид универсального построения компилятора, для которого задумывались эти инструменты, они чрезвычайно полезны для написания анализаторов синтаксиса конфигурационных файлов и узкоспециальных мини-языков.

Сгенерированные с помощью lex анализаторы лексем работают очень быстро при распознавании низкоуровневых образцов во входных потоках, однако известный утилите lex язык регулярных выражений плохо подходит для вычисления или распознавания рекурсивно вложенных структур. Для их анализа потребуется yacc. С другой стороны, несмотря на то, что теоретически возможно написать yacc-грамматику с собственным сбором лексем, такая грамматика была бы перегружена кодом, а анализатор был бы крайне медленным. Для анализа входных лексем следует использовать lex. Таким образом, данные инструменты являются симбиотическими.

Если существует возможность реализовать анализатор на языке более высокого уровня, чем С (что и рекомендуется; см. главу 14), то следует рассмотреть такие

эквивалентные средства, как PLY в Python (которое охватывает функции lex и yacc)[126] или Perl-модули PY и Parse::Yapp, либо Java-пакеты CUP[127], Jack[128] или Yacc/M[129].

Как и в случае с макропроцессорами, одной из проблем, связанных с генераторами кода и препроцессорами, является то, что ошибки компиляции в сгенерированном коде могут содержать номера строк сгенерированного кода (который редактировать нежелательно), а не номера строк во входных данных генератора (т.е. там, где необходимо внести изменения). В утилитах yacc и lex данная проблема решается такими же конструкциями #line, что и в препроцессоре С. Они устанавливают текущий номер строки для отчета об ошибках. Любая программа, генерирующая код на С или С++, должна работать аналогичным образом.

В более широком смысле хорошо спроектированные генераторы процедурного кода никогда не должны требовать от пользователя исправлять вручную или даже просматривать сгенерированный код. Создание корректного кода является непосредственной задачей генератора.

Данный текст является ознакомительным фрагментом.