В этой главе вводятся многие основные понятия, без которых детальное описание Bison не будет иметь смысла. Если вы ещё не знаете, как использовать Bison или Yacc, мы предлагаем вам начать с внимательного чтения этой главы.
Для того, чтобы Bison мог разобрать программу на каком-то языке, этот язык должен быть описан контекстно-свободной грамматикой. Это означает, что вы определяете одну или более синтаксических групп и задаёте правила их сборки из составных частей. Например, в языке C одна из групп называется `выражение'. Правило для составления выражения может выглядеть так: "Выражение может состоять из знака `минус' и другого выражения". Другое правило: "Выражением может быть целое число". Как вы может видеть, правила часто бывают рекурсивными, но должно быть по крайней мере одно правило, выводящее из рекурсии.
Наиболее распространённой формальной системой для представления таких правил в удобном для человека виде является форма Бэкуса-Наура (БНФ, Backus-Naur Form, BNF), которая была разработана для описания языка Algol 60. Любая грамматика, выраженная в форме Бэкуса-Наура является контекстно-свободной грамматикой. Bison принимает на вход, в сущности, особый вид БНФ, адаптированный для машинной обработки.
Bison может работать не со всеми контекстно-свободными грамматиками, а только с грамматиками класса LALR(1). Коротко, это означает, что должно быть возможно определить, как разобрать любую часть входа, заглядывая вперёд не более, чем на одну лексему. Строго говоря, это описание LR(1)-грамматики, класс LALR(1) имеет дополнительные ограничения, которые не так просто объяснить. Но в обычной практике редко встречаются LR(1)-грамматики, которые не являются LALR(1). См. раздел 6.7 Загадочные конфликты свёртка/свёртка, для получения большей информации.
В правилах формальной грамматики языка каждый вид синтаксических единиц или групп называется символом. Те из них, которые формируются группировкой меньших конструкций в соответствии с правилами грамматики, называются нетерминальными символами, а те, что не могут разбиты -- терминальными символами или типами лексем. Мы называем часть входного текста, соответствующую одному терминальному символу лексемой, а соответствующую нетерминальному символу -- группой.
Для примера терминальных и нетерминальных символов можно использовать язык C. Лексемами C являются идентификаторы, константы (числовые и строковые), и различные ключевые слова, знаки арифметических операций и пунктуации. Таким образом, терминальные символы грамматики C это: `идентификатор', `число', `строка' и по одному символу на каждое ключевое слово, знак операции или пунктуации: `if', 'return', `const', `static', `int', `char', `знак плюс', `открывающая скобка', `закрывающая скобка', `запятая' и многие другие (эти лексемы могут быть разбиты на литеры, но это уже вопрос составления словарей, а не грамматики).
Вот простая функция на языке C, разбитая на лексемы:
@ifnotinfo
int /* ключевое слово `int' */
square (int x) /* идентификатор, открывающая круглая скобка, */
/* идентификатор, идентификатор, закрывающая */
/* круглая скобка */
{ /* открывающая фигурная скобка */
return x * x; /* ключевое слово `return', идентификатор, звёздочка, */
/* идентификатор, точка с запятой */
} /* закрывающая фигурная скобка */
Синтаксические группы C это: выражение, оператор, объявление и определение функции. Они представлены в грамматике C нетерминальными символами `выражение', `оператор', `объявление' и `определение функции'. Полная грамматика, для того, чтобы выразить смысл этих четырёх, использует десятки дополнительных языковых конструкций, каждой из которых соответствует свой нетерминальный символ. Пример выше является определением функции, он содержит одно объявление и один оператор. В операторе каждое `x', так же, как и `x * x' являются выражениями.
Каждому нетерминальному символу должны быть сопоставлены правила грамматики,
показывающие, как он собирается из более простых конструкций. Например, одним
из операторов C является оператор return, это может быть описано
правилом грамматики, неформально читающимся так:
`Оператор' может состоять из ключевого слова `return', `выражения' и `точки с запятой'.
Должно существовать множество других правил для `оператор', по одному на каждый вид оператора C.
Один нетерминальный символ должен быть отмечен как специальный, определяющий завершённое высказывание на языке. Он называется начальным символом. В компиляторе это означает полную программу на входе. В языке C эту роль играет нетерминальный символ `последовательность определений и объявлений'.
Например, `1 + 2' является правильным выражением C -- правильной частью программы на C -- но не является правильной целой программой на C. В контекстно-свободной грамматике C это следует из того, что `выражение' не является начальным символом.
Анализатор Bison читает на входе последовательность лексем и группирует их, используя правила грамматики. Если вход правилен, конечным результатом будет свёртка всей последовательности лексем в одну группу, которой соответствует начальный символ грамматики. Если мы используем грамматику C, весь входной текст в целом должен быть `последовательностью определений и объявлений'. Если это не так, анализатор сообщит о синтаксической ошибке.
Формальная грамматика -- это математическая конструкция. Чтобы определить язык для Bison, вы должны написать файл, описывающий грамматику в синтаксисе Bison -- файл грамматики Bison. См. раздел 4. Файлы грамматики Bison.
Нетерминальный символ формальной грамматики на входе Bison представляется
идентификатором, таким же как идентификатор C. По соглашению их нужно
записывать в нижнем регистре, например: expr, stmt или
declaration.
Представление в Bison нетерминальных символов также называется типом
лексем. Типы лексем также могут быть представлены идентификаторами в
стиле C. По соглашению эти идентификаторы следует записывать в верхнем
регистре, чтобы отличить их от нетерминалов, например, INTEGER,
IDENTIFIER, IF, или RETURN. Терминальный символ,
соответствующий конкретному ключевому слову языка следует называть так же,
как это ключевое слово выглядит в верхнем регистре. Терминальный символ
error зарезервирован для восстановления после ошибок. См. раздел 4.2 Символы, терминальные и нетерминальные.
Терминальный символ также может быть представлен как однолитерная константа, как однолитерная константа C. Вам стоит делать так всегда, когда лексема представляет собой просто одиночную литеру (скобку, знак плюс и т.д.) -- используйте ту же литеру в качестве терминального символа для этой лексемы.
Третий способ представления терминального символа -- представление строковой константой C из нескольких литер. См. раздел 4.2 Символы, терминальные и нетерминальные, для получения большей информации.
Правила грамматики также содержат выражение в синтаксисе Bison. Например,
вот правило Bison для оператора C return. Точка с запятой в кавычках
является однолитерной лексемой, представляющей часть синтаксиса оператора
C, а отдельная точка с запятой и двоеточие являются знаками пунктуации
Bison, используемыми во всех правилах.
stmt: RETURN expr ';'
;
См. раздел 4.3 Синтаксис правил грамматики.
Формальная грамматика выбирает лексемы только по их виду, например, если в правиле упоминается терминальный символ `целочисленная константа', это означает, что в этой позиции грамматически допустима любая целочисленная константа. Точное значение константы не имеет значения для разбора -- если `x+4' грамматически допустимо, то `x+1' или `x+3989' равно допустимы.
Но точное значение очень важно, чтобы после разбора определить, что означает входной текст. Компилятор, не могущий различить в программе константы 4, 1 и 3989, бесполезен! Поэтому каждая лексема в грамматике Bison характеризуется как типом лексемы, так и семантическим значением. См. раздел 4.5 Определение семантики языка.
Тип лексемы -- это терминальный символ, определённый в грамматике, такой
как INTEGER, IDENTIFIER или ','. Он даёт всю информацию,
необходимую для принятия решения, где допустимо появления лексемы и как
группировать её с другими лексемами. Правила грамматик не знают о
лексемах ничего, кроме их типов.
Семантическое значение несёт всю остальную информацию о смысле лексемы,
такую как значение целого или имя идентификатора (такие лексемы как ',',
просто знаки пунктуации, не нуждаются в каком-либо семантическом значении).
Например, входная лексема может классифицироваться как лексема типа
INTEGER и иметь семантическое значение 4. Другая входная лексема
может иметь тот же тип INTEGER, но значение 3989. Если правило
грамматики говорит, что допустима лексема типа INTEGER, будет
принята любая из этих двух лексем, потому что обе они имеют тип
INTEGER. Когда анализатор принимает лексему, он отслеживает её
семантическое значение.
Каждая группа, так же как и её нетерминальный символ, может иметь семантическое значение. Например, в калькуляторе выражение обычно имеет семантическое значение, представляющее собой число. В компиляторе языка программирования выражение обычно имеет семантическое значение в виде дерева, описывающего смысл выражения.
Чтобы быть полезной, программа должна делать нечто большее, чем разбор входного текста -- она должны также создавать некий выход, основанный на входе. В грамматике Bison правило грамматики может содержать действие, состоящее из операторов C. Каждый раз, когда анализатор распознаёт текст, соответствующий правилу, выполняется его действие. См. раздел 4.5.3 Действия.
Чаще всего целью действия является вычисление семантического значения всей конструкции по семантическим значениям её частей. Предположим, например, что у нас есть правило, гласящее, что выражение может быть суммой двух выражений. Когда анализатор распознаёт такую сумму, каждое из подвыражений имеет семантическое значение, описывающее, как оно построено. Действию этого правила следует создать значение подобного вида для только что распознанного большего выражения.
Например, вот правило, говорящее, что выражение может быть суммой двух
подвыражений:
expr: expr '+' expr { $$ = $1 + $3; }
;
Действие сообщает, как получить семантическое значение выражения суммы из значений двух подвыражений.
Многие приложения, такие как интерпретаторы или компиляторы, должны генерировать подробные и информативные сообщения об ошибках. Для обеспечения этого должно быть возможно отслеживать позицию в тексте или положение каждой синтаксической конструкции. Bison предоставляет механизм работы с такими положениями.
Каждая лексема имеет семантическое значение. Аналогично, каждой лексеме сопоставлено положение, но тип положений одинаков для всех лексем и групп. Более того, создаваемый анализатор снабжён структурой данных для информации о положениях, задаваемой по умолчанию (см. раздел 4.6 Отслеживание положений, для получения дальнейшей информации).
Как и с семантическими значениями, в действиях можно получить доступ к
положениям, используя специальный набор конструкций. В приведённом выше
примере положение группы в целом -- @$, в то время как положения
подвыражений -- @1 и @3.
Когда обнаруживается текст, соответствующий правилу, для вычисления
семантического значения его левой части используется действие по умолчанию
(см. раздел 4.5.3 Действия). Точно так же, для положений используется другое действие
по умолчанию. Однако действия для положений в большинстве случаев достаточно,
в том смысле, что обычно не нужно описывать формирование @$ для
каждого правила. При вычислении нового положения для данной группы по
умолчанию анализатор берёт начало первого символа и конец последнего.
Когда вы запускаете Bison, вы подаёте ему на вход файл грамматики Bison. Выходным текстом является исходный текст на C, осуществляющий разбор языка, описываемого грамматикой. Этот файл называется анализатором Bison. Имейте в виду, что утилита Bison и анализатор Bison -- это две разные программы: утилита Bison -- это программа, создающая на выходе анализатор Bison, который затем становится частью вашей программы.
Задачей анализатора Bison является сборка лексем в группы в соответствии с правилами грамматики, например, объединение идентификаторов и знаков операций в выражения. По мере выполнения этой задачи анализатор выполняет действия, сопоставленные используемым правилам грамматики.
Лексемы поступают из функции, называемой лексическим анализатором,
которую вы должны каким-либо образом предоставить (например, написав её
на C). Анализатор Bison вызывает лексический анализатор каждый раз, когда
ему нужна новая лексема. Он не знает, что находится "внутри" лексемы
(хотя её семантическое значение может отражать это). Обычно лексический
анализатор получает лексемы анализом литер текста, но Bison не зависит
от этого. См. раздел 5.2 Функция лексического анализатора yylex.
Файл анализатора Bison -- это код на C, определяющий функции yyparse,
реализующую грамматику. Эта функция не образует целую программу на C -- вы
должны предоставить некоторые дополнительные функции. Одна из них --
лексический анализатор. Другая -- функция, вызываемая анализатором для
сообщения об ошибке. Кроме того, выполнение программы на C должно начинаться
с функции main: вы должны создать её и вызывать из неё yyparse,
иначе анализатор никогда не заработает. См. раздел 5. Интерфейс анализатора на C.
Все имена переменных и функций в файле анализатора Bison, помимо
определённых в написанных вами действиях и имён типов лексем, начинаются
с `yy' или `YY'. Сюда входят интерфейсные функции, такие как
функция лексического анализатора yylex, функция сообщения об ошибке
yyerror и сама функция анализатора yyparse. Также это относится
к многочисленным идентификаторам, используемым во внутренних целях. Поэтому
вам следует избегать использования идентификаторов C, начинающихся с
`yy' или `YY' в грамматике Bison, за исключением определённых
в этом руководстве.
В некоторых случаях файл анализатора Bison включает системные заголовки,
и тогда при написании вашего кода следует учитывать, что некоторые
идентификаторы зарезервированы такими заголовками. На некоторых не-GNU
системах включаются заголовки <alloca.h>, <stddef.h> и
<stdlib.h>, поскольку это необходимо для объявления функций выделения
памяти и связанных типов. Другие системные заголовки могут быть включены,
если вы придадите ненулевое значение YYDEBUG (см. раздел 9. Отладка вашего анализатора).
Реальный процесс разработки языка с использованием Bison, от спецификации грамматики до работающего компилятора или интерпретатора, содержит следующие этапы:
yylex).
Он также может быть создан с помощью Lex, но использование Lex в этом
руководстве не обсуждается.
Чтобы превратить этот исходный код в работающую программу, вы должны выполнить следующие шаги:
Входной файл утилиты Bison -- это файл грамматики Bison. Общий вид
файла грамматики Bison следующий:
%{
Объявления C
%}
Объявления Bison
%%
Правила грамматики
%%
Дополнительный код на C
`%%', `%{' и `%}' -- это знаки пунктуации, присутствующие в любом файле грамматики Bison для разделения его секций.
Объявления C могут определять типы и переменные, используемые в действиях.
Вы также можете использовать команды препроцессора для определения
используемых там макросов и #include для включения файлов заголовков,
делающих всё вышеперечисленное.
Объявления Bison задают имена терминальных и нетерминальных символов и могут также описывать приоритет операций и типы данных семантических значений различных символов.
Правила грамматики определяют, как каждый нетерминальный символ собирается из своих частей.
Дополнительный код на C может содержать любой код на C, который вы хотите
использовать. Часто здесь находится определение лексического анализатора
yylex и подпрограммы, вызываемые действиями правил грамматики. В
простых программах здесь может находится и вся остальная часть программы.