[содержание] [назад] [пред] [вверх] [след] [вперед] 2. принципы bisonв этой главе вводятся многие основные понятия, без которых детальное описание bison не будет иметь смысла. если вы ещё не знаете, как использовать bison или yacc, мы предлагаем вам начать с внимательного чтения этой главы. 2.1 языки и контекстно-свободные грамматикидля того, чтобы 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 является оператор
должно существовать множество других правил для `оператор', по одному на каждый вид оператора c. один нетерминальный символ должен быть отмечен как специальный, определяющий завершённое высказывание на языке. он называется начальным символом. в компиляторе это означает полную программу на входе. в языке c эту роль играет нетерминальный символ `последовательность определений и объявлений'. например, `1 + 2' является правильным выражением c -- правильной частью программы на c -- но не является правильной целой программой на c. в контекстно-свободной грамматике c это следует из того, что `выражение' не является начальным символом. анализатор bison читает на входе последовательность лексем и группирует их, используя правила грамматики. если вход правилен, конечным результатом будет свёртка всей последовательности лексем в одну группу, которой соответствует начальный символ грамматики. если мы используем грамматику c, весь входной текст в целом должен быть `последовательностью определений и объявлений'. если это не так, анализатор сообщит о синтаксической ошибке. 2.2 от формальных правил к входному тексту bisonформальная грамматика -- это математическая конструкция. чтобы определить язык для bison, вы должны написать файл, описывающий грамматику в синтаксисе bison -- файл грамматики bison. см. раздел 4. файлы грамматики bison.
нетерминальный символ формальной грамматики на входе bison представляется
идентификатором, таким же как идентификатор c. по соглашению их нужно
записывать в нижнем регистре, например:
представление в bison нетерминальных символов также называется типом
лексем. типы лексем также могут быть представлены идентификаторами в
стиле c. по соглашению эти идентификаторы следует записывать в верхнем
регистре, чтобы отличить их от нетерминалов, например, терминальный символ также может быть представлен как однолитерная константа, как однолитерная константа c. вам стоит делать так всегда, когда лексема представляет собой просто одиночную литеру (скобку, знак плюс и т.д.) -- используйте ту же литеру в качестве терминального символа для этой лексемы. третий способ представления терминального символа -- представление строковой константой c из нескольких литер. см. раздел 4.2 символы, терминальные и нетерминальные, для получения большей информации.
правила грамматики также содержат выражение в синтаксисе bison. например,
вот правило bison для оператора c stmt: return expr ';' ; см. раздел 4.3 синтаксис правил грамматики. 2.3 семантические значенияформальная грамматика выбирает лексемы только по их виду, например, если в правиле упоминается терминальный символ `целочисленная константа', это означает, что в этой позиции грамматически допустима любая целочисленная константа. точное значение константы не имеет значения для разбора -- если `x+4' грамматически допустимо, то `x+1' или `x+3989' равно допустимы. но точное значение очень важно, чтобы после разбора определить, что означает входной текст. компилятор, не могущий различить в программе константы 4, 1 и 3989, бесполезен! поэтому каждая лексема в грамматике bison характеризуется как типом лексемы, так и семантическим значением. см. раздел 4.5 определение семантики языка.
тип лексемы -- это терминальный символ, определённый в грамматике, такой
как
семантическое значение несёт всю остальную информацию о смысле лексемы,
такую как значение целого или имя идентификатора (такие лексемы как
например, входная лексема может классифицироваться как лексема типа
каждая группа, так же как и её нетерминальный символ, может иметь семантическое значение. например, в калькуляторе выражение обычно имеет семантическое значение, представляющее собой число. в компиляторе языка программирования выражение обычно имеет семантическое значение в виде дерева, описывающего смысл выражения. 2.4 семантические действиячтобы быть полезной, программа должна делать нечто большее, чем разбор входного текста -- она должны также создавать некий выход, основанный на входе. в грамматике bison правило грамматики может содержать действие, состоящее из операторов c. каждый раз, когда анализатор распознаёт текст, соответствующий правилу, выполняется его действие. см. раздел 4.5.3 действия. чаще всего целью действия является вычисление семантического значения всей конструкции по семантическим значениям её частей. предположим, например, что у нас есть правило, гласящее, что выражение может быть суммой двух выражений. когда анализатор распознаёт такую сумму, каждое из подвыражений имеет семантическое значение, описывающее, как оно построено. действию этого правила следует создать значение подобного вида для только что распознанного большего выражения. например, вот правило, говорящее, что выражение может быть суммой двух подвыражений: expr: expr '+' expr { $$ = $1 + $3; } ; действие сообщает, как получить семантическое значение выражения суммы из значений двух подвыражений. 2.5 положениямногие приложения, такие как интерпретаторы или компиляторы, должны генерировать подробные и информативные сообщения об ошибках. для обеспечения этого должно быть возможно отслеживать позицию в тексте или положение каждой синтаксической конструкции. bison предоставляет механизм работы с такими положениями. каждая лексема имеет семантическое значение. аналогично, каждой лексеме сопоставлено положение, но тип положений одинаков для всех лексем и групп. более того, создаваемый анализатор снабжён структурой данных для информации о положениях, задаваемой по умолчанию (см. раздел 4.6 отслеживание положений, для получения дальнейшей информации).
как и с семантическими значениями, в действиях можно получить доступ к
положениям, используя специальный набор конструкций. в приведённом выше
примере положение группы в целом --
когда обнаруживается текст, соответствующий правилу, для вычисления
семантического значения его левой части используется действие по умолчанию
(см. раздел 4.5.3 действия). точно так же, для положений используется другое действие
по умолчанию. однако действия для положений в большинстве случаев достаточно,
в том смысле, что обычно не нужно описывать формирование 2.6 выходной текст bison: файл анализаторакогда вы запускаете bison, вы подаёте ему на вход файл грамматики bison. выходным текстом является исходный текст на c, осуществляющий разбор языка, описываемого грамматикой. этот файл называется анализатором bison. имейте в виду, что утилита bison и анализатор bison -- это две разные программы: утилита bison -- это программа, создающая на выходе анализатор bison, который затем становится частью вашей программы. задачей анализатора bison является сборка лексем в группы в соответствии с правилами грамматики, например, объединение идентификаторов и знаков операций в выражения. по мере выполнения этой задачи анализатор выполняет действия, сопоставленные используемым правилам грамматики.
лексемы поступают из функции, называемой лексическим анализатором,
которую вы должны каким-либо образом предоставить (например, написав её
на c). анализатор bison вызывает лексический анализатор каждый раз, когда
ему нужна новая лексема. он не знает, что находится "внутри" лексемы
(хотя её семантическое значение может отражать это). обычно лексический
анализатор получает лексемы анализом литер текста, но bison не зависит
от этого. см. раздел 5.2 функция лексического анализатора
файл анализатора bison -- это код на c, определяющий функции
все имена переменных и функций в файле анализатора bison, помимо
определённых в написанных вами действиях и имён типов лексем, начинаются
с `yy' или `yy'. сюда входят интерфейсные функции, такие как
функция лексического анализатора
в некоторых случаях файл анализатора bison включает системные заголовки,
и тогда при написании вашего кода следует учитывать, что некоторые
идентификаторы зарезервированы такими заголовками. на некоторых не-gnu
системах включаются заголовки 2.7 этапы использования bisonреальный процесс разработки языка с использованием bison, от спецификации грамматики до работающего компилятора или интерпретатора, содержит следующие этапы:
чтобы превратить этот исходный код в работающую программу, вы должны выполнить следующие шаги:
2.8 обзор схемы грамматики bisonвходной файл утилиты bison -- это файл грамматики bison. общий вид файла грамматики bison следующий: %{ объявления c %} объявления bison %% правила грамматики %% дополнительный код на c `%%', `%{' и `%}' -- это знаки пунктуации, присутствующие в любом файле грамматики bison для разделения его секций.
объявления c могут определять типы и переменные, используемые в действиях.
вы также можете использовать команды препроцессора для определения
используемых там макросов и объявления bison задают имена терминальных и нетерминальных символов и могут также описывать приоритет операций и типы данных семантических значений различных символов. правила грамматики определяют, как каждый нетерминальный символ собирается из своих частей.
дополнительный код на c может содержать любой код на c, который вы хотите
использовать. часто здесь находится определение лексического анализатора
[содержание] [назад] [пред] [вверх] [след] [вперед] |