Обычно входная информация, читаемая программой, всегда обладает некоторой структурой; про любую программу, читающую входной поток мы можем сказать, что она задает некоторый входной язык. Входной язык может быть либо сложным, как язык программирования, либо простым, выглядящим как последовательность чисел. Но к сожалению, обычные средства ввода ограничены по возможностям, трудны в использовании и зачастую не содержат механизмов проверки корректности.
YACC представляет собой универсальный инструмент для описания входного потока программ. Это имя является сокращением фразы "
yet another compiler compiler" ("еще один компилятор компиляторов"). Пользователь задает как структуру входного потока, так и фрагменты программ, вызываемые при распознавании объектов в потоке. Компилятор компиляторов (или генератор программ синтаксического разбора, далее просто генератор) переводит спецификацию в некоторую подпрограмму, управляющую процессом ввода. Часто оказывается удобным осуществлять управление пользовательской задачей с помощью этой подпрограммы.
Подпрограмма, построенная генератором, для чтения базовой входной лексемы вызывает предоставляемую пользователем функцию. Таким образом, пользователь может описывать входной поток либо в терминах отдельных символов, либо более высокоуровневыми конструкциями (именами, числами). Пользовательская функция может обрабатывать и некоторые особенности входного потока, такие, как комментарии и соглашения о продолжении, что обычно облегчает грамматическую спецификацию. Класс спецификаций довольно широк: это грамматики LALR с набором правил.
Генератор используется как для разработки компиляторов широко распространенных языков (языки С, АПЛ, Паскаль, Ратфор и пр.), так и для нетрадиционных приложений (язык управления фотонаборной установкой, языки настольных калькуляторов, система доступа к документам, отладчик Фортрана).
Генератор предоставляет широкие возможности для задания структуры входного потока программы. Пользователь YACC задает спецификацию, управляющую процессом ввода, к которой относятся правила для описания структуры потока, фрагменты программ, вызываемые при распознавании этих правил, низкоуровневые функции для выполнения первичного ввода. По этой спецификации генератор строит функцию, управляющую процессом ввода. Эта функция, называемая синтаксическим анализатором, вызывает низкоуровневую пользовательскую подпрограмму (
лексический анализатор), для выделения базовых элементов (лексем) из входного потока. Лексемы обрабатываются в соответствии с правилами, описывающими входной поток (грамматическими правилами). При распознавании такого правила вызывается соответствующий фрагмент пользовательской программы. Обратите внимание, что при этом можно возвращать значения, которые могут применяться в других фрагментах. Сам генератор написан на мобильном диалекте языка С, все действия и генерируемые подпрограммы также записываются на С. Более того, большинство синтаксических соглашений также соответствуют языку С.
Сердцем входной спецификации является набор грамматических правил. Каждое правило описывает допустимую структуру и присваивает ей имя. Например, правилом могла бы быть следующая строка:
date:month_name day '.' year ;
Date, month_name, day, year представляют собой некторые объекты входного потока, подразумевается, что они где-то определены. Символ запятой заключен в апострофы; это означает, что она должна восприниматься непосредственно. Двоеточие и точка с запятой выполняют роль знаков пунктуации в правилах и не влияют на распознавание входного потока. Учитывая приведенное определение, следующая строка
July 4, 1776
могла бы быть выделена этим правилом.
Важная часть обработки входного потока выполняется лексическим анализатором. Эта подпрограмма читает входной поток, выделяет в нем низкоуровневые структуры и передает эти лексемы синтаксическому анализатору. Объекты, распознаваемые лексическим анализатором, называются терминальными символами, в отличие от объектов, распознаваемых синтаксическим анализатором, которые называются нетерминальными символами. Во избежание путаницы будет называть терминальные символы лексемами.
При принятии решения, будут ли входные структуры распознаваться лексическими или грамматическими правилами, пользователю предоставляется значительная свобода. Например, для предыдущего примера можно записать следующие правила:
month_name: 'J''a''n';
month_name: 'F''e''b';
.
.
.
month_name: 'D''e''c';
Тогда лексический анализатор распознавал бы только отдельные символы, а month_name был бы нетерминальным символом. Такие низкоуровневые правила ведут к трате времени и пространства и могут сильно усложнить спецификацию (вплоть до невозможности ее обработки генератором). Обычно лексический анализатор распознает имена месяцев и возвращает соответствующую информацию. В этом случае month_name считается лексемой. Символы с непосредственным значением, такие, как запятая, также должны проходить через лексический анализатор и считаются лексемами.
Способы спецификация весьма гибки. К приведенному примеру сравнительно несложно добавить следующее правило:
date:month:'/'day'/'year ;
Оно позволяет ввод фразы
7/4/1776
в качестве синонима для
July 4, 1776
В большинстве случаев новое правило может быть включено в работающую систему с минимальными усилиями и достаточно безопасно. Читаемый входной поток может не соответствовать спецификации. Ошибки обнаруживаются с максимальной быстротой, какую теоретически может предоставить просмотр слева направо. Таким образом, во-первых, снижается вероятность обработки неправильных данных, во-вторых, такие данные обычно можно быстро обнаружить. Процедуры обработки ошибок, задаваемые как часть входной спецификации, позволяют повторный ввод при неверных данных, либо продолжение процесса ввода после пропуска некорректной информации.
В некоторых случаях генератор не может построить анализатор из заданного набора спецификаций. Например, в них может содержаться противоречие, или требование более мощного механизма распознавания, нежели доступный. Первый случай соответствует ошибкам проектирования, последний может устраняться либо усложнением лексического анализатора, либо переписью грамматических правил. Хотя yacc и не может обработать все возможные спецификации, по мощности он сопоставим с аналогичными системами. Более того, если некоторые конструкции для него представляют сложности, часто эти конструкции будут сложны и для вас. Пользователи сообщают, что благодаря дисциплине формулировки правильных спецификаций, применяемой в yacc, концептуальные ошибки проектирования выявляются на ранних этапах разработки.