Искусство программирования для Unix

Реймонд Эрик Стивен

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

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

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

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

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

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

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

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

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

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

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

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

При разрешении

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

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

Майк Леек.

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

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

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

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

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

Если существует возможность реализовать анализатор на языке более высокого уровня, чем С (что и рекомендуется; см. главу 14), то следует рассмотреть такие эквивалентные средства, как PLY в Python (которое охватывает функции lex и уасс)⁹⁵или Perl-модули PY и Parse::Yapp, либо Java-пакеты CUP⁹⁶, Jack⁹⁷ или Yacc/M⁹⁸.

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