дддд ееееее м м oooo сссс д д е мм мм o o с с д д е м м м м o o с с д д еееее м м м o o с д д е м м o o с д д е м м o o с с дддддддд ееееее м м oooo сссс демосдемосдемосдемосдемосдемосдемосдемосде емосдемосдемосдемосдемосдемосдемосдемосдем мо мо ос ос сд ОПЕРАЦИОННАЯ СИСТЕМА сд де де ем ДЕМОС ем мо мо ос ос сд сд де Версия 1.0 де ем ем мо мо сдемосдемосдемосдемосдемосдемосдемосдемосд демосдемосдемосдемосдемосдемосдемосдемосде КОМПИЛЯТОР КОМПИЛЯТОРОВ YACC Давидов Михаил Изгияевич Антонов Вадим Геннадьевич МОСКВА - 1985 1 ОПИСАНИЕ ЯЗЫКА YACC Давидов М.И. Шульгейфер О.Е. 2 В документе приводится описание языка программирования YACC, предназначенного для разработки синтаксических анали- заторов. 2 ВВЕДЕНИЕ Значительная часть создаваемых программ, рассчитанных на определенную структуру входной информации, явно или неявно включает в себя некоторую процедуру синтаксического анализа. В задачах, где пользователю при задании входной информации предоставляется относительная свобода (в отношении сочетания и последовательности структурных элементов), синтаксический анализ достаточно сложен. При решении подобных задач су- щественную поддержку могут оказать сервисные программы, осу- ществляющие построение синтаксических (грамматических) ана- лизаторов на основе заданных сведений о синтаксической структуре входной информации. YACC относится к числу этих сервисных программ - генераторов грамматических анализато- ров. Поскольку обширной областью, где наиболее явно видна не- обходимость (нетривиального) грамматического анализа, а сле- довательно и его автоматизации, является область создания трансляторов (в частности, компиляторов), программы, подоб- ные YACC, получили еще название компиляторов (или генерато- ров) компиляторов. Заметим, что понятие транслятора может относиться не только к языкам программирования, но и к командным языкам, входным языкам любых диалоговых систем, языкам управления технологическими процессами и т.п. Пользователь YACC должен описать структуру своей входной информации (ГРАММАТИКУ) как набор ПРАВИЛ в виде, близком к Бэкусово-Науровской форме (БНФ). Каждое правило описывает грамматическую конструкцию, называемую НЕТЕРМИНАЛЬНЫМ СИМВОЛОМ, и сопоставляет ей имя. С точки зрения грамматичес- кого разбора правила рассматриваются как правила вывода (подстановки). Грамматические правила описываются в терминах некоторых исходных конструкций, которые называются лексичес- кими единицами, или ЛЕКСЕМАМИ. Имеется возможность задавать лексемы непосредственно (литерально) или употреблять в грам- матических правилах имя лексемы. Как правило, имена сопос- тавляются лексемам, соответствующим классам об'ектов, конкретное значение которых не существенно для целей грамма- тического анализа. (Иногда в литературе с понятием лексемы совпадает понятие терминального символа; однако, ряд авторов называет терминальными символами отдельные символы стан- дартного набора). Примерами имен лексем могут служить "ИДЕНТИФИКАТОР" и "ЧИСЛО", а введение таких лексем позволяет обобщить конкретные способы записи идентификаторов и чисел. В некоторых случаях имена лексем служат для придания прави- лам большей выразительности. Лексемы должны распознаваться программой лексического анализа, определяемой пользователем. Пользователь же предва- рительно выбирает конструкции,которые более удобно и эффек- тивно распознавать непосредственно, и в соответствии с этим об'являет имена лексем. Пользовательская программа лексичес- кого анализа - ЛЕКСИЧЕСКИЙ АНАЛИЗАТОР - осуществляет чтение реальной входной информации и передает грамматическому ана- лизатору распознанные лексемы. 3 Как уже отмечалось, YACC обеспечивает автоматическое построение лишь процедуры грамматического анализа. Однако, действия по обработке входной информации обычно должны вы- полняться по мере распознавания на входе тех или иных допус- тимых грамматических конструкций. Поэтому наряду с заданием грамматики входных текстов YACC предусматривает воможность описания для отдельных конструкций семантических процедур (ДЕЙСТВИЙ) с тем, чтобы они были включены в программу грам- матического разбора. В зависимости от характера пользова- тельских семантических процедур (интерпретация распознанного фрагмента входного текста, генерация фрагмента об'ектного кода, отметка в справочной таблице или форматирование верши- ны в дереве разбора) генерируемая с помощью YACC программа будет обеспечивать кроме анализа тот или иной вид обработки входного текста, в частности, его компиляцию или интерпрета- цию. Итак, пользователь YACC подготавливает общее описание (СПЕЦИФИКАЦИИ) обработки входного потока, включающее прави- ла, описывающие входные конструкции, кодовую часть, к кото- рой должно быть организовано обращение при обнаружении этих конструкций, и программу ввода базовых элементов потока (лексический анализатор). Kомпилятор компиляторов обеспечи- вает создание подпрограммы (грамматического анализатора), реализующей процедуру обработки входного потока в соот- ветствии с заданными спецификациями. YACC написан на языке Си и работает под управлением сис- темы ДЕМОС. К компонентам компилятора компиляторов относятся выполня- емый файл yacc, библиотека стандартных программ /lib/liby.a, Файл /usr/lib/yaccpar. Заключительная фаза построения компи- лятора требует применения компилятора языка Си. 4 1. ПРИНЦИПЫ РАБОТЫ YACC Грамматические анализаторы, создаваемые с помощью YACC, реализуют так называемый LALR(1)-разбор, являющийся модифи- кацией одного из основных методов разбора "снизу вверх" - LR(k)-разбора (буквы L(eft) и R(ight) в обоих сокращениях означают соответственно чтение входных символов слева напра- во и использование правостороннего вывода. Индекс в скобках показывает число предварительно просматриваемых лексических единиц). Любой разбор по принципу "снизу вверх" (или восходящий разбор) состоит в попытке приведения всей совокупности вход- ных данных (входной цепочки) к так называемому "начальному символу грамматики" (это понятие будет об'яснено в разделе 4.1) путем последовательного применения правил вывода. В каждый момент грамматического разбора анализатор нахо- дится в некотором СОСТОЯНИИ, определяемом предысторией раз- бора, и в зависимости от очередной лексемы предпринимает то или иное действие для перехода к новому состоянию. Различают два типа действий: "СДВИГ", т.е. чтение следующей входной лексемы, и "СВЕРТКУ", т.е. применение одного из правил подстановки для замещения нетерминалом последовательности символов, соответствующей правой части правила. Работа YACC по генерации процедуры грамматического анализа заключается в построении таблиц, которые для каждого из состояний опреде- ляют тип действий анализатора и номер следующего состояния в соответствии с каждой из входных лексем. Любой метод разбора требует грамматик с определенными свойствами. В этом смысле YACC предполагает контекстно- свободные грамматики со свойствами LALR(1). LALR(1)- грамматики, являясь подмножеством LR(1)-грамматик, допускают при построении таблиц разбора сокращение общего числа состо- яний за счет об'единения идентичных состояний, различающихся только набором символов-следователей (символов, которые могут следовать после применения одного из правил вывода, если разбор по этому правилу проходил через данное состо- яние). Другие грамматики являются неоднозначными для приня- того в YACC метода разбора и вызовут конфликты (раздел 5). Однако, если язык, описываемый данной грамматикой, в принци- пе допускает задание грамматики, однозначной для данного ме- тода разбора, то YACC позволяет без перестройки грамматики построить грамматический анализатор, разрешающий конфликты на основе механизма приоритетов (раздел 5). 5 2. ВХОДНЫЕ И ВЫХОДНЫЕ ФАЙЛЫ, СТРУКТУРА ГРАММАТИЧЕСКОГО АНАЛИЗАТОРА Входная информация для YACC задается в СПЕЦИФИКАЦИОННОМ ФАЙЛЕ, структура которого рассматривается в разделе 4. На выходе компилятора компиляторов в результате обработки спецификаций создается файл y.tab.c с исходным текстом Си- процедур, составляющих грамматический анализатор. Основной в файле y.tab.c является процедура yyparse, реализующая алго- ритм грамматического разбора. При формировании ее YACC ис- пользует файл /usr/lib/yaccpar, содержащий неизменяемую часть анализатора. Кроме yyparse, в файл y.tab.c YACC вклю- чает построенные им таблицы разбора, описания и программные фрагменты пользовательских спецификаций. Процедура yyparse представляет собой целочисленную функцию, возвращающую значение 0 или 1. Значение 0 возвраща- ется в случае успешного разбора по достижении признака конца файла, значение 1- в случае несоответствия входного текста заданным спецификациям. Процедура yyparse содержит многок- ратное обращение к процедуре лексического анализа yylex, текст которой либо переносится в файл y.tab.c из специфика- ционного файла, либо прикомпоновывается впоследствии. Дляорганизации обращения к процедуре yyparse в библиотеке YACC существует стандартная процедура main, не содержащая помимо обращения к yyparse никаких действий. Пользователь может написать собственную процедуру main, включив в нее как начальные действия, предваряющие вызов yyparse (установка нужных режимов, открытие файлов, частичное заполнение таблиц), так и действия по завершении разбора, которым должен предшествовать анализ возвращаемого yyparse значения; действиями в случае успешного разбора могут быть закрытие файлов, вывод результатов, вызов следующей фазы транслятора, в частности, повторный вызов yyparse. Для замены стандартной процедуры пользовательской программой main она должна быть описана в спецификационном файле или присоединена на этапе вызова Си- компилятора для подготовки исполняемой программы. Кроме выходного файла y.tab.c,YACC может дополнительно генерировать следующие выходные файлы: y.output содержащий описание состояний анализатора и сообщения о конфликтах (раздел 6) y.tab.h содержащий описание лексем (раздел 4.3). Для генерации этих файлов требуется задание соответству- ющих флагов при вызове YACC. 6 3. ПРОЦЕДУРА ПОСТРОЕНИЯ ГРАММАТИЧЕСКОГО АНАЛИЗАТОРА Построение грамматического анализатора осуществляетсЯ в два этапа. На первом этапе файл спецификаций входного языка обрабатывается компилятором компиляторов YACC, для чего за- дается командная строка yacc [-vd] yfile Здесь yfile - имя файла спецификаций, а флаги имеют следу- ющий смысл: v - сформировать в файле y.output подробное описание грам- матического анализатора; d - сформировать в файле y.tab.h описание лексем. Текстовые файлы y.output и y.tab.h содержат справочную информацию для пользователя, и никак не используются на втором этапе построения грамматического анализатора. Основной результат работы YACC - процедура yyparse и грамматические таблицы - помещается в файл y.tab.c. На вто- ром этапе построения грамматического анализатора для получе- ния в файле a.out исполняемой программы компилируется файл y.tab.c и присоединяются другие программные компоненты: cc y.tab.c [cfile...ofile...lfile...] -ly cfile, ofile, lfile - имена исходных, об'ектных и библиотеч- ных файлов, содержащих присоединяемые процедуры. В этот спи- сок не включается имя стандартной библиотеки YACC /lib/liby.a, ее подключение обеспечивается заданием флага ly. Этот флаг полезно считать обязательным. 7 4. ЗАДАНИЕ ВХОДНОЙ ИНФОРМАЦИИ YACC 4.1. Структура спецификационного файла Пользовательские спецификации, задающие правила организа- ции входной информации и алгоритм ее обработки, об'единяются в спецификационный файл следующей структуры: декларации %% правила %% программы Ядром спецификационного файла и единственной его обяза- тельной частью является секция правил. При отсутсивии секции программ может быть опущена вторая группа "%%"; следователь- но, минимальная допустимая конфигурация входного файла имеет вид: %% правила Пробелы, знаки табуляции и перевода строки игнорируются, недопустимо лишь появление их в именах. Комментарий, ограни- ченный символами "/*" в начале и "*/" в конце, может нахо- диться между любыми двумя разделителями в любой секции вход- ного файла. СЕКЦИЯ ПРАВИЛ состоит из одного или нескольких граммати- ческих правил. Эти правила должны определять все допустимые входные конструкции и связанные с определенными конструкци- ями действия по обработке входного потока. Назначение СЕКЦИИ ДЕКЛАРАЦИЙ состоит в основном в задании информации о лексемах. СЕКЦИЯ ПРОГРАММ представляет собой некоторый набор проце- дур на языке Си, которые должны включаться в текст программы грамматического разбора. Например, это могут быть процедура лексического анализа yylex и пользовательские процедуры, вы- зываемые в действиях. 4.2. Секция правил В данной секции с помощью набора грамматических правил должны быть определены все конструкции, из которых впос- ледствии будут строиться входные тексты. Не подлежат опреде- лению в секции правил лишь конструкЦии, выбранные пользова- телем в качестве лексем, считающиеся для грамматического анализа исходными единицами. Правила задаются в форме, близ- кой БНФ. 8 Правило, определяющее синтаксический вид конструкции, за- дается таким образом: <имя нетерминального символа>: опреде- ление; здесь ':' и ';' специальные символы YACC. Правая часть правила - определение - представляет собой упорядочен- ную последовательность элементов (нетерминальных символов и лексем), составляющих описываемую конструкцию. При граммати- ческом разборе такая последовательность в результате приме- нения правила заменяется нетерминальным символом, имя кото- рого указано в левой части. нетерминальные символы в опреде- лении задаются именами, а лексемы - именами или литералами. Запись имен и литералов совпадает с записью идентификаторов и символьных констант, принятой в Си. Правило: P_HEAD:NAME '('P_LIST')'; определяет нетерминал P_HEAD как последовательность 4-х эле- ментов: два элемента заданы литерально, два других - имена- ми. По виду правила нельзя заключить, относятся эти имена к лексемам или нетерминальным символам. YACC считает именами нетерминалов все имена, не об'явленные в секции деклараций именами лексем (разд.4.3). Все нетерминалы должны быть опре- делены, т.е. имя каждого из них должно появиться в левой части хотя бы одного правила. Допустимо задание нескольких правил, определяющих один нетерминальный символ, т.е. правил с одинаковой левой частью. Такие правила определяют конструкции, идентичные на некотором уровне. Ниже приводятся три правила, определяющие виды операторов в некотором языке: statement : assign_stat ; statement : if_then_stat; statement : goto_stat; Правила с общей левой частью можно задавать в сокращенной записи, без повторения левой части, используя для разделения альтернативных определений символ "|". Предыдущие правила можно переписать в виде statement : assign_stat | if_then_stat | goto_stat; При необходимости с любым правилом можно связать действие - набор операторов языка Си, которые будут выполняться при каждом распознавании конструкции во входном тексте. Действие не является обязательным элементом правил. Действие заключается в фигурные скобки и помещается вслед за правой частью правила, т.е. правило с действием имеет вид: <имя нетерминального символа>: определение {действие}; Точка с запятой после правила с действием может опускаться. При использовании сокращенной записи правил с общей левой частью следует иметь в виду, что действие может относиться только к отдельному правилу, а не к их совокупности. Следу- ющий пример иллюстрирует задание действий в случае правил с общей левой частью. 9 statement: assign_stat | if_then_stat {printf("if_оператор/n");} | goto_stat {kgoto++; printf("goto_оператор0);} На операторы, входящие в действия, не накладывается ника- ких ограничений. В частности, в действиях могут содержаться вызовы любых функций. Отдельные операторы могут быть помече- ны, к ним возможен переход из других действий. Существует возможность задания действий, которые будут выполняться по мере распознавания отдельных фрагментов пра- вила. Действие в этом случае помещается после одного из эле- ментов правой части так, чтобы положение действия соот- вествовало моменту разбора, в который данному действию будет передано управление. Например, в правиле if_then_stat:IF'('expression')'{действие1} THEN statement';'{действие 2} действия заданы с таким расчетом, чтобы при разборе строки вида if (a>b) then x=a; действие 1 выплнялось при нахождении правой круглой скобки, а действие 2 - по окончании разбора. Для того, чтобы действия имели реальный смысл, они, как правило, должны использовать некоторые общие переменные, т.е. переменные, доступные во всех действиях и сохраняющие свои значения по окончании очередного действия. Такие пере- менные описываются в начале секции правил, все описание ог- раничивается с двух сторон строками %{ и %} Здесь же могут находиться произвольные операторы Си, рассматриваемые как общие действия для всех правил. Дополним приведенный выше фрагмент спецификаций для statement с тем, чтобы осуществлялся подсчет и вывод на печать операторов goto %{ int kgoto; %} prog: DECLS {kgoto=0;} stats {printf("Р,kgoto);} stats: statement | stats statement; statement:assign_stat ... | if_then_stat ... 10 | goto_stat {kgoto++; ... } Укажем еще на два вида об'ектов, использующихся в дей- ствиях. Это, во-первых, глобальные переменные, которые опи- сываются в секции деклараций (разд.4.3), и, во-вторых, спе- циальные переменные (псевдопеременные),облегчающие взаимос- вязь между действиями и связь их с лексическим анализатором. Работе с псевдопеременными посвящен раздел 4.5. Структура входной информации описывается в наборе правил иерархически, т.е. каждое правило соответствует определенному уровню структурного разбиения. Однако, последовательность задания правил может не отражать этой иерархии и быть вполне произ- вольной. Единственно необходимой для YACC является информа- ция о том, какой из нетерминалов задает вершину иерархии, т.е. соотвествует конструкциям, определяющим входной текст в целом. Этот нетерминал принято называть НАЧАЛЬНЫМ СИМВОЛОМ. Приведение входного текста к начальному символу является целью грамматического анализатора. По умолчанию YACC считает начальным символом тот нетерминал, имя которого стоит в левой части первого из правил. Однако, если определять на- чальный символ в первом правиле пользователю неудобно, он может явно задать имя начального символа в секции деклара- ций. Существует два специфических вида правил, на которые по- лезно обратить внимание. Во-первых, это пустое правило вида <имя нетерминального символа>: ; определяющее пустую последовательность символов. Сочетание пустого правила с другими правилами, определяющими тот же нетерминальный символ, является одним из способов указать на необязательность вхождения соответствующей конструкции. Нап- ример, совокупность правил целое_число:знак целое_без_знака; знак: | '+'|'-'; определяет возможность задания целых чисел со знаком и без него. Другой способ описать эту возможность состоит в зада- нии следующей группы правил: целое_число:знак целое_без_знака | целое_без_знака ; знак: '+'|'-'; С пустым правилом может быть обычным образом связано дей- ствие: ИМЯ: {тело_действия} ; Во-вторых, правила часто описывают некоторую конструкцию ре- курсивно, т.е. правая часть может рекурсивно включать опре- деляемый нетерминальный символ. Различают леворекурсивные правила вида: <имя нетерминала>:<имя нетерминала> <многократно повторяемый фрагмент>; и праворекурсивные вида 11 <имя нетерминала>: <многократно повторяемый фрагмент> <имя нетерминала>; YACC допускает оба вида рекурсивных правил, однако, при использовании правил с правой рекурсией об'ем анализатора увеличивается, а во время разбора возможно переполнение внутреннего стека анализатора. Рекурсивные правила необходимы при задании последователь- ностей и списков. Следующие примеры иллюстрируют универсаль- ный способ описания этих конструкций: последовательность: элемент | последовательность элемент; список: элемент|список ',' элемент; Заметим, что в каждом из этих случаев первое правило (не со- держащее рекурсии) будет применено только для первого эле- мента, а второе (рекурсивное) - для всех последующих. Нетер- минальные символы, связанные с последовательностями или списками разнородных элементов, могут описываться произволь- ным числом рекурсивных и нерекурсивных правил. Например, группа правил идентификатор: буква | '$' | идентификатор буква| идентификатор цифра| идентификатор '_' ; описывает идентификатор как последовательность букв, цифр и символов "_", начинающуюся с буквы или символа "$". Следует обратить внимание на то, что рекурсивные правила не имеют смысла, если для определяемого ими нетерминала не задано ни одного правила без рекурсии. Для обеспечения возможности за- дания пустых списков или последовательностей в качестве не- рекурсивного правила используется пустое: последовательность : | последовательность элемент ; Сочетание пустых и рекурсивных правил является удобным способом представления грамматик и ведет к большей их общности, однако,некорректное использование пустых правил может вызывать конфликтные ситуации (раздел 5) из-за неод- нозначности выбора нетерминала, соответствующего пустой пос- ледовательности. 4.3. Секция деклараций Секция деклараций состоит из последовательности строк двух видов: строк- директив и строк исходного текста. Строки исходного текста без изменений копируются в выход- ной файл y.tab.c и могут содержать операторы препроцессора и описание внешних об'ектов. Область действия переменных, опи- санных в секции деклараций, распространяется на весь специ- фикационный файл, т.е. они доступны как в операторах действий, так и в процедурах, находящихся в секции программ. 12 Строки-директивы начинаются символом "%" (этот символ в YACC играет роль своего рода esc-символа). Две специальные директивы %{ и %} ограничивают с двух сторон группы строк исходного текста. Остальные директивы служат для задания дополнительной инфор- мации о грамматике. 13 5. ДЕКЛАРАЦИЯ ИМЕН ЛЕКСЕМ %token <список имен лексем> Пользователь при описании грамматики решает, какие конструкции целесообразнее непосредственно выделять из вход- ного текста на этапе лексического анализа, и на уровне этих конструкций (лексем) задает грамматические правила. Все виды лексем, кроме литералов, обозначаются некоторыми именами и под этими именами фигурируют в секции правил. Благодаря дек- ларации имен лексем в директиве %token YACC отличает имена лексем от имен нетерминальных символов. Однако, декларация ни в коей мере не обеспечивает распознавания лексем, и поль- зователю рекомендуется считать для себя директиву %token на- поминанием о необходимости построения лексического анализа- тора (разд.4.4) и руководствоваться этой директивой при его написании. Пример декларации имен лексем: %token IDENT CONST ЗНАК IF THEN GOTO Заметим, что ключевые слова описываемого входного языка часто бывает удобно считать лексемами. Имена лексем могут совпадать с этими ключевыми словами, недопустимым является лишь совпадение имен лексем с зарезервированными словами языка Си. В примере во избежание недоразумений для имен лексем использованы прописные буквы. 14 6. ДЕКЛАРАЦИЯ ПРИОРИТЕТОВ И АССОЦИАТИВНОСТИ ЛЕКСЕМ %left <список лексем> %right <список лексем> %nonassos <список лексем> Лексемы в данных директивах задаются литералами или име- нами. В последнем случае декларация приоритета заменяет также декларацию имени лексемы, хотя в целях обеспечения наглядности описания является желательным присутствие в списке директивы %token всего набора имен лексем. Содержательный смысл декларации приоритетов и ассоциатив- ности выясняется в разделе 5 в связи с вопросом о разрешении конфликтов грамматического разбора. Использование лексемы само по себе не требует задания ее приоритета или ассоци- ативности. При первом появлении лексемы или литерала в секции декла- раций за каждым из них может следовать неотрицательное целое число, рассматриваемое как НОМЕР ТИПА лексемы. По умолчанию номера типов всех лексеМ определяются YACC следующим обра- зом: - для литерала номером типа лексемы считается числовое значение данного литерального символа, рассматриваемого как однобайтовое целое число; - лексемы,обозначенные именами, в соответствии с очеред- ностью их об'явления получают последовательные номера, начиная с 257; - специальная лексема error, зарезервированная для обра- ботки ошибок (раздел 7), получает номер типа 256. Для каждого имени лексемы независимо от того, переопреде- лен ли ее номер пользователем, YACC генерирует в выходном файле y.tab.c оператор макропрепроцессора #deline <имя лексемы> <номер типа> В случае переопределения номера типа литеральной лексемы также формируется оператор #define, например, директива %left 'z' 258 породит оператор #define z 258 Заметим, что возможно переопределение номеров лишь для буквенных литералов. При вызове YACC с флагом -d последовательность операторов #define помещается также в информационный файл y.tab.h. Переопределив при необходимости ряд номеров типов лек- сем,пользователь должен проверить уникальность номеров у 15 всех используемых лексем. 16 7. ДЕКЛАРАЦИЯ ИМЕНИ НАЧАЛЬНОГО СИМВОЛА %start <имя начального символа> Директива отменяет действующий по умолчанию выбор в ка- честве начального символа нетериминала, определяемого первым грамматическим правилом. 7.1. Секция программ В секцию программ помещается описание пользовательских процедур, которые должны быть включены в генерируемую прог- рамму грамматического анализа. Любая из определяемых пользо- вателем программных компонент может находиться в секции программ спецификационного файла, либо присоединяться на этапе вызова Си-компилятора для трансляции файла y.tab.c и компоновки выходной программы. Перечислим процедуры, которые одним из этих способов должны быть заданы: - лексический анализатор - функция с именем yylex(); - все процедуры, вызовы которых содержатся в действиях, связанных с грамматическими правилами; - главная процедура main() при необходимости заменить ее стандартный библиотечный вариант, который имеет вид main() {return (yyparse();} - процедура обработки ошибок yyerror() - также для замены библиотечного варианта (его текст приводится ниже). #include yyerror(s)char *s; { fprintf(stderr, "%s0, s);} Для обеспечения корректной работы грамматического анали- затора функция лексического анализа yylex должна быть согла- сована с конкретной спецификацией грамматики и удовлетворять определенным требованиям. Основная задача функции yylex сос- тоит во вводе из входного потока ряда очередных символов до выявления конструкции, соответствующей одной из лексем, и возвращении номера типа этой лексемы. Для нелитеральных лексем номером типа может служить об'явленное в секции дек- лараций имя лексемы (с помощью механизма #define YACC обес- печивает замену его нужным номером), в случае литералов но- мером типа является числовое значение символа (если оно не было переопределено). Алгоритм поиска должен заключаться в попытке нахождения сначала более сложных (нелитеральных) лексем и лишь при несовпадении ни с одной из них текущих элементов ввода возвращать номер типа литеральной лексемы (любой однозначный символ, не начинающий ни одну из возмож- ных лексем, сам образует лексему). Приведем текст процедуры лексического анализа, распозна- ющей идентификаторы и целые числа: 17 #include yylex() {char c; while ((c=getc(stdin))==' '||c=='0); if(c>='0'&&c<='9){ while((c=getc(stdin))>='0'&&c<='9'); ungetc(c,stdin)); return (CONST);} if (c>='a'&&c<='z'){ while ((c=getc(stdin))>'a'&&c<='z' ||c>='0'&&c<='9'); ungetc(c,stdin); return (NAME);} return (c); } Сложность лексического анализатора зависит от того, какие структурные единицы взяты за основу при описании граммати- ческих правил. Детализовав грамматику до отдельных символов, можно обойтись простейшим лексическим анализатором, осу- ществляющим только их ввод: yylex() {return (getchar());} Однако, в этом случае число правил растет, а грамматичес- кий разбор оказывается менее эффективным. Поэтому пользова- тель обычно должен найти некоторый компромис при выборе на- бора лексем. В процедуре лексического анализа кроме выделения лексем можно предусмотреть некоторую обработку лексем определенных типов, в частности, запоминание конкретных значений лексем. Кроме того, эти значения обычно требуется передать граммати- ческому анализатору. С этой целью нужное значение должно быть присвоено внешней переменной целого типа с именем yylval. Если функция yylex находится в отдельном файле, то эта переменная должна быть об'явлена: extern int yylval; Уточним, что в дальнейшем ЗНАЧЕНИЕМ ЛЕКСЕМЫ мы будем на- зывать значение, присвоенное при ее распознавании переменной yylval; значение, возвращаемое функцией yylex, является но- мером типа лексемы. Примером значения лексемы могут слуить числовое значение цифры, вычисленное значение константы, ад- рес идентификатора в таблице имен (построение таблицы имен удобно осуществлять лексическим анализатором). Заметим, что, хотя значение yylval устанавливается с целью использования его в действиях, непосредственное обращение к переМенной yylval в действии не имеет смысла (поскольку в yylval всегда находится значение последней выделенной лексемы). Доступ в действиях к значениям лексем осуществляется с помощью специ- ального механизма, описанного в разделе 4.5. 7.2. Действия с использованием псевдопеременных Для обеспечения связи между действиями, а также между действиями и лексическим анализатором создаваемые YACC грам- матические анализаторы поддерживают специальный стек, в ко- тором сохраняются значения лексем и нетерминальных символов. Значение лексемы автоматически попадает в стек после ее рас- познавания лексическим анализатором (напомним, что им счита- ется текущее значение переменной yylval). После каждой 18 свертки вычисляется значение нетерминала, заместившего свер- нутую строку, и помещается в вершину стека; значения элемен- тов правой части примененного правила перед этим выталкива- ются из стека. Заметим, что таким образом к моменту свертки любого правила все значения нетериналов в правой части ока- зываются вычисленными в результате сверток. Способ вычисле- ния значения нетерминала будет рассмотрен ниже. Описанный механизм не требует вмешательства пользователя и предоставляет ему следующие возможности: - Использовать в действиях, осуществляемых после свертки по правилу, значение любого элемента его правой части. Доступ к этим значениям обеспечивается набором так на- зываемых ПСЕВДОПЕРЕМЕННЫХ с именами $1,$2,..., где $i соответствует значению i-го элемента; элементы правой части правила нумеруются слева направо без различия лексем и нетерминальных символов, например, в правиле P_Head: P_name '('P_list')'; псевдопеременные $1,$2,$3,$4 относились бы соот- ветственно к P_name, '(',P_list,')'; - Формировать в действиях значение, образованного в ре- зультате свертки нетерминала путем присвоения этого значения псевдопеременной с именем $$. Так, в правиле expr: expr '+'expr { $$=$1+$3;} значением нового нетерминала expr станет сумма ранее вычисленных значений двух других нетерминалов expr. Eсли в действии не определяется значение переменной $$ (а также если действие отсутствует), значением нетерми- нала после свертки по умолчанию становится значение первого элемента правой части, т.е. неявно выполняется присваивание $$=$1; Пример (вычисление значения целого числа) %token DIGIT %% ... CONST:DIGIT | CONST DIGIT {$$=$1*10+$2;} ... %% yylex ( ) {char c; if((c=getchar())>='0'&& c<='9') {yylval=c-'0'; return (DIGIT);} ... Здесь при свертке по первому правилу нетерминал CONST получает значение первой цифры, присвоенное в функции yylex () переменной yylval; при каждой свертке по вто- рому правилу явно вычисляется значение нового нетерми- нала CONST. 19 Несколько иная ситуация в отношении использования псевдо- переменных имеет место для правил, содержащих действия внут- ри правоЙ части. На самом деле YACC интерпретирует правило вида A: B C {действие 1} D {действие 2} K {действие 3} как A: B C EMPTY1 D EMPTY2 K; EMPTY1: {действие 1} EMPTY2: {действие 2} и в точке, где вставлено действие, при разборе осуществляет- ся свертка по пустому правилу, сопровождающаяся выполнением указанНого действия. При этом независимо от характера дей- ствия очередной элемент в стеке значений отводится для хра- нения значения неявно присутствующего "пустого" нетерминала. В действии, находящемся в конце правила, соглашение о значе- ниях псевдопеременных остается прежним, если иметь в виду наличие дополнительных символов. В приведенном выше правиле в действии 3 для доступа к значениям элементов B, C, D, K следовало бы использовать соответственно псевдопеременные $1, $2, $4, $6; псевдоперемнные $3, $5 хранят результаты действий 1 и 2. В действиях, находящихся внутри правила, с помощью псевдоперемнных $i доступны значения расположенных левее элементов, а также результаты предшествующих вставлен- ных в тело действий. Результатом внутреннего действия (т.е. значением неявного нетерминалА) является значение, присвоен- ное в этом действии псевдопеременной $$, при отсутствии та- кого присваивания результат действия не определен. Заметим, что присваивание значения псевдопеременной $$ во внутренних действиях не вызывает предварительной установки значения не- терминала, стоящего в левой части правила: это значение в любом случае устанавливется только действием в конце правила или считается равным значению $1. В нашем примере в действии 1 доступными являются только значения элементов B и C (им соответствуют псевдопеременные $1 и $2), а в действии 2 - значения элементов B, C, D и ре- зультат действия 1 с помощью псевдоперемнных $1, $2, $4, $3. Следующий пример иллюстрирует варианты использования псевдо- переменных: %token ИМЯ КЛЮЧ1 КЛЮЧ2 КОНЕЦ - - - - - - - %% входной_поток: данные КОНЕЦ {printf("Данные занесены в файл %s0,$1);} данные: ИМЯ { $$ = creat( $1,0666 );} КЛЮЧ1 КЛЮЧ2 { $$ = option( $3,$4 );} упр_строка'0{ converse( 0,$5,$6 ); write( $1,$6,80 ); } текст { converse( 1,$5,$8 ); write( $1,$6,$8 ); close( $1 ); } упр_строка: - - - - текст : - - - - . . . 20 Управляющая строка и текст преобразуются в соответствии с заданными ключами и записываются в файл с указанным именем. Значением нетерминала "данные" в результате неявного дей- ствия становится значение лексемы ИМЯ (адрес строки с именем файла присваивается в лексическом анализаторе переменной yylval). 21 8. КОНФЛИКТЫ ГРАММАТИЧЕСКОГО РАЗБОРА Заданная грамматика является неоднозначной, если су- ществует входная строка, которая в соответствии с этой грам- матикой может быть разобрана двумя или более различными спо- собами. Рассмотрим, например, набор правил, описывающих константное арифметическое выражение: expr: CONST /*1*/ | expr '+'expr /*2*/ | expr '-'expr /*3*/ | expr '*'expr /*4*/ | expr '/'expr; /*5*/ Описывая возможность построения выражения из двух выраже- ний, соединенных знаком арифметической операции, правила не- однозначно определяют путь разбора некоторых входных строк. Так, строка вида: expr*expr-expr допускает два пути разбора, приводящих к различным группи- ровкам ее элементов: expr*(expr-expr) и (expr*expr) - expr С точки зрения работы грамматического анализатора данная ситуация проявляется в неоднозначности выбора действия при вводе лексемы '-' в момент, когда разобранная часть строки приведена к виду expr*expr. Два возможных действия анализа- тора состоят в следующем: - Можно ввести следующий символ и без применения правила подстановки перейти в новое состояние. В разделе 1 мы назвали такое действие сдвигом. Выбор сдвига приведет к тому, что в одном из следующих состояний ко второй части конструкции для приведения ее к expr будет приме- нено правило (3), а затем вся полученная конструкция сведется к expr применением правила (4). - Можно сразу применить к конструкции expr*expr правило (4), тем самым приведя ее к expr, и без ввода нового символа перейти в очередное состояние. Такое действие в разделе 1 было названо сверткой. Использование свертки в данном состоянии приведет к применению в дальнейшем правила (3) для свертывания оставшейся части конструк- ции в expr. Неоднозначность такого рода будем называть конфликтом "сдвиг/свертка". (Выше этот конфликт был умышленно показан на примере выражения, порядок разбора которого существен в связи с различием приоритетов операций. На самом деле 22 конфликт сдвиг/свертка возникает и при разборе такой строки как expr-expr-expr. В этом случае разница в разборе ведет лишь к трактовке операции "-" как лево- или правоассоциатив- ной. Однако, как известно, ассоциативность иногда играет важную роль, например, для операций присваивания, возведения в степень). Возможен другой вид конфликта, состоящий в выбо- ре между двумя возможными свертками; будем называть его конфликтом "свертка/свертка". Для примера подобного конфлик- та приведем грамматику, задающую десятичную и шестнадцате- ричную форму записи константы: const: const_10 /*1*/ | const_16 ; /*2*/ const_10: dec_sequence; /*3*/ const_16: hex_sequence 'x'; /*4*/ dec_sequence:digit /*5*/ | dec_sequense digit; /*6*/ hec_sequense:digit /*7*/ | ABCDEF /*8*/ |hex_sequense digit /*9*/ |hex_sequence ABCDEF; /*10*/ ABCDEF : 'A'|'B'|'C'|'D'|'E'|'F'; digit:'0'|'1'|'2'|'3'|'4'|'5'|'6' |'7'|'8'|'9'; При появлении на входе первой же десятичной цифры (если с нее начинается последовательность) после ее замены нетерми- налом digit возникает конфликт между двумя возможными свертками: к нетерминалу dec_sequence в результате примене- ния правила (5) и к нетерминалу hex_sequence с помощью пра- вила (7). Заметим, что эта грамматика, в отличиe от грамма- тики в предыдущем примере, не позволяет корректно разобрать какую-либо строку двумя способами и в принципе нетерминал CONST определен однозначно. Однако, алгоритм разбора с простмотром вперед на 1 символ не в состоянии правильно осу- ществить выбор нужного правила. Следовательно, в этом случае речь идет о неоднозначности грамматики по отношению к приня- тому в YACC методу разбора. Поскольку вопрос о принципиаль- ной неоднозначности грамматики формально неразрешим, будем в дальнейшем понимать под неоднозначностью невозможность для анализатора в некоторые моменты разбора выбрать очередное действие. Каждая ситуация (т.е. появление в некотором состо- янии некоторой входной лексемы), которая при разборе способ- на вызвать конфликт "сдвиг/свертка" или "свертка/ свертка", выявляется YACC уже на этапе построения грамматического ана- лизатора. При этом YACC выдает сообщение о числе выявленных конфликтных ситуаций обоих видов, а в выходной файл y.output (если он формируется) помещается подробное описание всех конфликтов. Однако, YACC не считает наличие конфликтов фа- тальной ошибкой грамматики и строит грамматический анализа- тор, заранее разрешая все возможные конфликты путем выбора в каждой ситуации единственного действия. При работе YACC используются два способа разрешения конфликтов. Первый способ действует по умолчанию, т.е. при отсутствии специальной пользовательской информации, и заклю- чается в применении следующих двух правил для выбора дей- ствия в конфликтных ситуациях: 23 - В случае конфликта сдвиг/свертка по умолчанию делается сдвиг. - В случае конфликта свертка/свертка по умолчанию делает- ся свертка по тому из конкурирующих правил, которое за- дано первым в спецификационном файле. Грамматический анализатор, построенный с исполтьзованием этих правил, может не обеспечивать "правильного" с точки зрения пользовательской грамматики разбора. В чатстности, для первого из приведенных выше примеров разбор заключался бы в сворачивании арифметических выражений справа налево без учета приоритетов операций. Во втором примере в результате замены первой конструкции digit нетерминалом dec_sequense все числа, начинающиеся с цифры, разбирались бы как десятич- ные, а появление одной из букв от A до F или символа "x" в конце числа неверно трактовалось как ошибка во входном тексте. Однако, в ряде ситуаций описанный способ разрешения конфликтов приводит к нужному результату. Например, рассмот- рим фрагмент грамматики языка программирования, описывающий условный оператор: оператор: IF '('условие')' оператор /*1*/ | IF '('условие')' оператор ELSE оператор; /*2*/ Входная строка вида: IF(C1) IF(C2) S1 ELSE S2 вызвала бы при разборе конфликт сдвиг/свертка в момент прос- мотра символа ELSE. Введенная часть строки к этому времени имеет вид: IF (условие) IF (условие) оператор Если выполнить свертку второй части конструкции по правилу (1), то строка сведется к: IF (условие) оператор (Заметим, что применить еще раз правило(1) мешает просмот- ренный заранее символ ELSE). После ввода конструкции S2 и замены ее нетерминалом "оператор" к строке: IF (условие) оператор ELSE оператор будет применено правило (2). Полученный разбор соответствует следующей интерпретации входной строки: IF (c1) {IF(c2) S1} ELSE S2 При альтернативном подходе в случае применения сдвига в момент появления ELSE входная строка была бы введена пол- ностью: 24 IF (условие) IF (условие) оператор ELSE оператор Ко второй части строки можно применить правило (2), а затем свернуть полученную конструкцию: IF (условие) оператор по правилу (1). Такой разбор соответствует второй возможной интерпретации входной строки: IF (c1) {IF(c2) S1 ELSE S2} Как известно, в большинстве языков программирования принята именно эта интерпретация (каждый ELSE относится к ближайшему предшествующему IF). Значит, выбор сдвига, осуществляемый по умолчанию, для данной грамматики верен. В качестве рекомендации отметим,что применение принципа умолчания для конфликтов сдвиг/свертка приводит к положи- тельному результату, если в грамматике принята правоассоци- ативная интерпретация соответствующих конструкций и для них отсутствует понятие приоритета. Что касается конфликтов свертка/свертка, то стандартный способ их разрешения оказы- вается полезным только тогда, когда при любых конфликтах между данными двумя правилами справедлив выбор одного и того же правила. В любом случае, если YACC сообщил о наличии конфликтных ситуаций, пользователь должен тщательно проанализировать со- держательный смысл каждого конфликта и правильность выбран- ного YACC действия. Вся необходимая для этого информация со- держится в файле y.output, структура которого будет рассмот- рена ниже. Если оказалось, что конфликты разрешены неудов- летворительно, то грамматика должна быть перестроена или уточнена пользователем. В случае конфликтов свертка/свертка всегда требуется изменение самих грамматических правил; для конфликтов сдвиг/свертка есть возможность без перестройки правил уточнить грамматику путем задания информации о при- оритетах и ассоциативности лексем и правил. В качестве примеров устранения конфликтов путем изменения правил приведем перестроенные варианты рассматривавшихся выше грамматик. Поскольку исходные конфликтыне грамматики полностью удовлетворяют требованиям генирируемых ими языков, но содержат недостаточно информации для однозначного разбо- ра, перестройка правил носит уточняющий характер. Перестроенная грамматика константного арифметического вы- ражения: expr: expr1 | expr '+' expr1 | expr '-' expr1; expr1: CONST | expr1 '*' CONST | expr1 '/' CONST; 25 Ниже будет приведен также вариант грамматики, полученной из исходной введением приоритетов (без перестройки правил). Перестроенная грамматика для задания константы: const: const_10 | const_16; const_10: dec_sequence ; const_16: hex_sequence 'x' | dec_sequense 'x'; dec_sequence: digit | dec_sequence digit; hex_sequence: ABCDEF | dec_sequence ABCDEF | hex_sequence ABCDEF |hex_sequence dec_sequence; ABCDEF:... digit:... Рассмотрим теперь второй из используемых YACC способов раз- решения конфликтов, базирующийся на задании пользователем информации о приоритетах и ассоциативности. Отметим предва- рительно две основные причины конфликтности грамматик: - принципиальная невозможность задать генерируемый язык бесконфликтной грамматикой; - недостаточность информации для построения однозначного грамматического разбора. Грамматики, конфликтные по второй причине, всегда допускают преобразование правил до полного устранения конфликтов; в случае конфликтов сдвиг/свертка YACC всегда может построить для этих грамматик корректный разбор путем разрешения конфлик- тов. Для грамматик, конфликтных по причине 1, попытки разрешения конфликтов не приведут к нужному результату. Однако, надо убедиться в том, что конфликтная граммати- ка действительно отражает входной язык: возможно, конфликты не имеют отношения к этому языку, а вызваны неоднозначностью другого, реально описанного языка. Вообще, конфликты стоит рассматривать как повод прове- рить грамматику на соответствие языку (хотя последнее не гарантируется и отсутствием конфликтов). Задание приоритетов для неверной грамматики не приведет к гене- рации нужного языка, но может замаскировать ошибки, сняв вопрос о конфликтах. Приоритетное разрешение конфликтов сдвиг/свертка состоит в том, что с обоими действиями YACC ассоциирует приоритеты (со сдвигом - приоритет лексемы, чтение которой вызывает данный конфликт, со сверткой - приоритет конкурирующего пра- вила) и выбирает более приоритетное действие. В случае ра- венства приоритетов YACC руководствуется при выборе свой- ством ассоциативности. Приоритеты и ассоциативность отдель- ных лексем (явно) и правил (явно и неявно) задаются пользо- вателем, все остальные приоритеты считаются неизвестными. YACC использует для разрешения конфликта данный способ, если известны приоритеты обоих конкурирующих действий. Поэтому для разрешения ряда конфликтов на приоритетной основе необ- ходимо установить приоритеты участвующих в них лексем и пра- вил. 26 Следует понимать,что задание приоритетов не ведет к устранению конфликтов и не делает грамматику однозначной. Но в отличие от конфликтов, разрешаемых YACC по принципу умол- чания, пользователь получает здесь возможность управлять разрешением конфликтов. YACC, сообщая общее число конфлик- тов, не учитывает в нем конфликтов, разрешенных в соот- ветствии с информацией о приоритетах, и не включает в выход- ной файл y.output описания этих конфликтов. Приоритеты и ассоциативность лексем задаются в секции деклараций с помощью директив трех видов: % left <список лексем> % right <список лексем> % nonassoc <список лексем> Каждая директива приписывает всем перечисленным в списке лексемам одинаковый приоритет. Директивы %left и %right од- новременно задают соответственно левую или правую ассоци- ативность лексем. Директива %nonassoc говорит об отсутствии у перечисленных лексем свойства ассоциативности. Устанавли- ваемый директивами приоритет не имеет численного выражения, а его относительное значение возрастает сверху вниз. Пример задания приоритетов лексем: %token OR NOR XOR AND NAND %right '=' %left OR NOR XOR %left AND NAND %left '+' '-' %left '*' '/' /* самый низкий приоритет имеет лексема */ Приоритет правила автоматически определяется приоритетом последней лексемы в теле правила. Если в секции деклараций для этой лексемы не задан приоритет или если правая часть правила вообще не содержит лексем, то приоритет правила не определен. Этот принцип можно отменить явным заданием при- оритета правила равным приоритету любой (имеющей приоритет) лексемы с помощью директивы: %prec <лексема> помещенной вслед за правой частью правила (перед точкой с запятой или действием). Например, правилу: expr: '-' expr %prec '*'; директива %prec придает приоритет лексемы '*' (лексема '-' при задании грамматики выражений часто используется для обозначения унарной и бинарной операций, имеющих разный при- оритет; с помощью директивЫ %prec унарной операции можно приписать более высокий приоритет. Иногда, чтобы связать с правилом приоритет, не совпадающий с приоритетом ни одной лексемы, вводят псевдолексему, задав ей в секции деклараций уникальный приоритет, и приписывают приоритет псевдолексемы правилу. В примере грамматики настольного калькулятора, при- водимом в приложении, с операцией "унарный минус" связан приоритет псевдолексемы UMINUS). 27 Сформулируем теперь полностью используемые YACC правила разрешения конфликтов сдвиг/свертка на основе информации о приоритетах и ассоциативности (напомним, что конфликты свертка/свертка разрешаются только по принципу умолчания): - Если для входной лексемы и правила заданы приоритеты и эти приоритеты различны, то выбирается действие с большим приоритетом. Больший приоритет правила вызывает свертку по нему, больший приоритет лексемы вызывает сдвиг. - Если приоритеты заданы и совпадают, то принимается во внимание заданная одновременно с приоритетом ассоци- ативность: в случае левой ассоциативности используется свертка, в случае правой - сдвиг. Отсутствие свойства ассоциативности (директива %nonassoc) в данном случае указывает на ошибку во входном тексте и анализатор воспримет вызвавшую данный конфликт лексему как ошибоч- ную. - Если не задан приоритет входной лексемы и/или приоритет правила, то действует принцип разрешения конфликтов по умолчанию, в результате чего выбирается сдвиг. Пример грамматики константного выражения, уточненной задани- ем приоритетов: %left '+' '-' %left '*' '/' %% expr: CONST | expr '+' expr | expr '-' expr | expr '*' expr | expr '/' expr; 28 9. СТРУКТУРА ИНФОРМАЦИОННОГО ВХОДНОГО ФАЙЛА y.output Основную часть данного файла составляет описание состо- яний построенного грамматичсекого анализатора. Информация о каждом состоянии приводится в следующем порядке: - Перечень соответствующих данному состоянию конфигураций грамматики (конфигурация характеризуется определенным грамматичсеким правилом и позицией в его правой части, достигнутой к данному моменту разбора). Каждая конфигу- рация представляется правилом с отменной с помощью сим- вола подчеркивания "-" распознанной частью (позицией конфигурации). Например, конфигурация: expr: expr +_expr соответствует распознанной при разборе строки по указанному правилу последовательности символов expr+. - Действия анализатора при вводе в качестве очередного просматриваемого символа каждой из лексем. Различные виды действий указываются следующим образом: <лексема> сдвиг <номер состояния> - сдвиг при вводе данной лексе- мы в состояние с указанным номером; <лексема> свертка <номер правила> - свертка при вводе лексемы по правилу с указанным номером; <лексема> error - выдача сообщения об ошибке во входных данных ("синтаксическая ошибка") и возврат из процедуры грамматического анализа с кодом 1 (дальнейший разбор невозможен); <лексема> accept - возврат из процедуры грамматического анализа с кодом 0 (успешное завершение разбора) Последняя из строк, опи- сывающих действия анализатора, содержит вместо указания лексемы символ "." и сообщает действие, выполняемое анализатором для всех лексем, не перечисленных в данном состоянии. Часто эта строка имеет вид: и указывает, что все перечисленные лексемы в данном состоянии являются недопустимыми. - Перечень переходов для данного состояния. Каждый пере- ход задается строкой <имя терминала> переход <номер состояния>, сообщающей, в какое состояние перейдет ана- лизатор после свертки указанного нетерминала, если его распознавание было начато из данного состояния. Кроме того, описанию состояния может предшествовать информа- ция о конфликтах обнаруженных YACC для этого состояния и разрешенных по принципУ умолчания. Информация о конфликте содержит тип конфликта (св/св или сдв/св), конкурирующие действия анализатора (при этом для сдвига указывается номер состояния, для свертки - номер прави- ла) и лексему, при появлении которой возникает данный конфликт. Узнать, какое из возможных действий будет вы- полнено анализатором, можно из опиания самого состо- яния. Пример описания состояния: 29 8:Конфликт сдв/св (сдвиг 5,свертка 2) при + Состояние 8 a:a_+a a:a+a_ (2) + сдвиг 5 . свертка 2 Состоянию 8 здесь соответствуют две различные позиции, дос- тигнутые при разборе по правилу a: a '+' a Kонфликт между сверткой по этому правилу и сдвигом в состо- яние 5 при вводе лексемы '+' разрешен в пользу сдвига. Ввод остальных лексем вызывает свертку. После описания состояния возможен ряд сообщений о несвер- нутых правилах (с указаниеМ этих правил), т.е. о правилах, свертка по которым не будет произведена ни в одном из состо- яний. Наличие таких правил с большой вероятностью свидетель- ствует о некорректности грамматики. В конце файла приводится информация статистичсекого ха- рактера о реальном и предельном количестве терминальных и нетерминальных символов, грамматических правил и состояний. Фиксируется число конфликтов каждого типа, число различных действий грамматического анализатора, занимаемый им об'ем памяти, приводятся данные об использовании внутренних струк- тур данных (множеств). 30 10. ОБРАБОТКА ОШИБОК ПРИ ГРАММАТИЧЕСКОМ РАЗБОРЕ Если входной поток не удовлетворяеит заданной грамматике, то грамматичсекий анализатор в момент ввода лексемы, дела- ющей невозможным продолжение разбора, фиксирует ошибку. Эту лексему мы в дальшейшем будем называть ошибочной лексемой. Реально ошибка может быть вызвана не только неверными вход- ными данными, но и некорректностью самого грамматического анализатора, являющейся следствием некорректной грамматики. Стандартной реакцией грамматического анализатора на ошиб- ку является выдача сообщения ("синтаксическая ошибка") и прекращение разбора. Эту реакцию можно несколько изменить, например, сделать сообщение об ошибке несколько более инфор- мативным, задав собственную процедуру yyerror. Однако, на- иболее важная задача состоит в том, чтобы заставить анализа- тор в этом случае продолжать просмотр входного потока, в частности, для выявления остальных ошибок. Применяемый YACC механизм восстановления основан на чтении и отбрасывании не- которого числа входных лексем; от пользователя требуется введение дополнительных грамматичсеких правил, указывающих, в каких конструкциях синтаксические ошибки являются допути- мыми (в отношении возможности восстановления). Одновременно эти правила определяют путь дальнейшего разбора для ошибоч- ных ситуаций. Для указания точек допустимых ошибок использу- ется зарезервированное с этой целью имя лексемы error. Пример: a: b c d ; /*1*/ a: b c error; /*2*/ d: d1 d2 d3; /*3*/ Второе правило указывает путь разбора в случае, если при распознавании нетерминала a встретится ошибка после выделе- ния элементов b и c. YACC обрабатывает правила, содержащие лексему error, так же, как все остальные правила. В результате в ряде состояний построенного анализатора оказывается предусмотренным дей- ствие для лексемы error (отличное от действия error). Будем говорить, что в этих состояниях лексема error допустима. Рассмотрим порядок работы анализатора при появлении во вход- ном потоке ошибочной лексемы (т.е. лексемы, ввод которой в данном состоянии вызывает действие error): - Фиксируется состояние ошибки; вызывается функция yyerror для выдачи сообщения. - Путем обратного просмотра пройденных состояний,начиная с данного, делается попытка найти состояние, в котором допустима лексема error. Отсутствие такого состояния говорит о невозможности восстановления, и разбор прек- ращается. - Осуществляется возврат в найденное состояние (кроме случая, когда им является непосредственно то состояние, в котором встретилась ошибка) 31 - Выполняется действие, заданное в этом состоянии для лексемы error. Очередной входной лексемой становится лексема, вызвавшАя ошибку. - Разбор продолжается, но анализатор остается в состоянии ошибки до тех пор, пока не будут успешно прочитаны и обработаны три подряд идущие лексемы. При нахождении анализатора в состоянии ошибки отличие в обработке оши- бочной лексемы заключается в том, что сообщения об ошибке не выдается, а сама лексема игнорируется. - После обработки трех допустимых лексем считается, что восстановление произошло, и анализатор выходит из сос- тояния ошибки. Итак, грамматический анализатор, встретив ошибку, пытает- ся найти ближайшую точку во входном потоке, где разрешена лексема error. При этом сначала делается попытка возврата в рамках правила, по которому шел разбор в момент появления ошибочноЙ лексемы, затем поиск распространяется на правила все более высокого уровня. В примере, приведенном в начале раздела, ввод недопустимой лексемы после того, как прочитана строка в c d1 d2 вызовет возврат к состоянию, характеризу- ющемуся конфигурациями: a: b c_d; a: b c_error; и продолжение разбора по правилу (2). Часто правила, учитывающие возможность ошибки, задаются на уровне основных структурных единиц входного текста. Нап- ример, для пропуска в тексте ошибочных операторов может быть использовано правило оператор: error; При этом восстановление из состояния ошибки произойдет после нахождения трех лексем, которые могут следовать после опера- тора, например, начинать новый оператор. Если точно распоз- нать начало оператора невозможно, то ошибочное состояние может быть подавлено преждевременно, а обработка нового опе- ратора начата с середины ошибочного, что, вероятно, приведет к повторному сообщению об ошибке (на самом деле не существу- ющей). Учитывая это, более надежного результата следует ожи- дать от правил вида: оператор: error ';' Здесь восстановление произойдет только после нахождения ';' и двух начальных лексем следующего оператора; Все лексемы после найденной ошибочной до ';' будут отброшены. С правилами, включающими лексему error, могут быть связа- ны действия. С их помощью пользователь может самостоятельно обработать ошибочную ситуацию. Кроме обычных операторов, здесь можно использовать специальные операторы yyerror и yyclearin, которые YACC на макроуровне расширяет в нужнЫе последовательности. Оператор yyerror аннулирует состояние ошибки. Таким образом, можно отменить действие принципа "трех лексем". Это помогает предотвратить маскирование новых 32 ошибок в случаях, когда конец ошибочной конструкции распоз- нается самим пользователем или однозначно определяется в правиле по меньшему числу лексем. Оператор yyclearin стирает хранимую анализатором послед- нюю входную лексему, еслм поиск нужной точки для возобновле- ния ввода обеспечивается в заданном пользователем действии. Приведем общую форму правила с восстановительным действи- ем оператор : error {resynch(); yyclearin; yyerror;} Предполагается, что пользовательская процедура resynch() просматривает входной поток до начала очередного оператора. Вызвавшая ошибку лексема, хранимая анализатором в качестве входной лексемы, стирается, после этого гасится состояние ошибки. При построении анализаторов, работающих в интерактивном режиме, для обработки ошибок рекомендуются правила вида: входная_строка : error '0 {yyerrok; printf("повторите последнюю строку 0);} входная_строка {$$=$4;} В действии, предусмотренном после ввода ошибочной строки, пользователю делается подсказка, а состояние ошибки гасится. Значением нетерминала после свертки здесь становится значе- ние повторно введенной строки. 33 11. ДИАГНОСТИКА ОШИБОК YACC выдает ряд сообщений об ошибках в случае невозмож- ности построения грамматического анализатора. В тексте сооб- щения, предваряемом заголовком "ошибка:", содержится указа- ние причины ошибки и номер просматриваемой в момент ее появ- ления строки спецификационного файла. Перечислим основные типы фиксируемых YACC ошибок: - неверно заданные флаги командной строки; - невозможность открытия входного или временных файлов; - отсутствие файла /usr/lib/yaccpar с текстом процедуры yyparse; - неверная структура спецификационного файла; - ошибки в задании директив; - синтаксические ошибки в описании грамматических правил; незавершенность комментариев, строк символов и действий; - некорректное использование псевдопеременных; - неопределенные нетерминальные символы; - нарушение количественных ограничений (по числу терми- нальных или нетерминальных символов, грамматических правил, состояний и проч.). 34 ПРИЛОЖЕНИЕ 1 Ниже приведен полный входной файл для YACC, реализующий небольшой настольный калькулятор; калькулятор имеет 26 ре- гистров, помеченных буквами от a до z, и разрешает использо- вать арифметические выражения, содержащие операции +, -, *, /, % (остаток от деления), & (побитовое и), | (побитовое или), и присваивание. Как и в Си, целые числа, начинающиеся с 0, считаются восьмеричными, все остальные - десятичными. В примере демонстрируются способы использования приорите- тов для разрешения конфликтов, а также простые операции по восстановлению из состояния ошибки. Калькулятор работает в интерактивном режиме с построчным формированием выхода. %token DIGIT LETTER /* имена лексем */ %left '|' /* задание приоритетов */ %left '&' /* операций */ %left '+' '-' %left '*' '/' '%' %left UMINUS /* установка приоритета операции унарный минус */ %{ /* oписания, используемые */ int base, regs[26]; /* в действиях */ %} %% /* начало секции правил */ list: | list stat '0 |list stat error '0 {yyerrok; } stat: expr { printf("Р,$1); } | LETTER '=' expr {regs[$1]=$3; } expr: '(' expr ')' { $$=$2; } |expr '+' expr { $$=$1+$3; } |expr '-' expr { $$=$1-$3; } |expr '*' expr { $$=$1*$3; } |expr '/' expr { $$=$1/$3; } |expr '%' expr { $$=$1%$3; } |expr '&' expr { $$=$1&$3; } |expr '|' expr { $$=$1|$3; } |'-' expr %prec UMINUS { $$= -$2; } | LETTER { $$=regs[$1]; } | number; number: DIGIT { $$=$1; base; if($1==0) base=8; } |number DIGIT {$$єse*$1+$2; } %% /* начало секции программ */ yylex() { /* программа лексического анализа для строчных латинских букв возвращает LETTER, значение yylval от 0 до 25, для цифр - DIGIT, значение yylval от 0 до 9, остальные символы возвращаются непосредственно */ 35 int c; while((c=getchar())==' '); if(c>='a'&&c<='z') { yylval=c-'a'; return(LETTER); } if(c>='0'&&c<='9') { yylval=c-'0'; return(DIGIT); } return(c); } 36 ПРИЛОЖЕНИЕ 2 Анализ и преобразование в матричную форму входных данных для задачи линейного программирования. Входная информация из обычной алгебраической формы: c1x1l...| -> min(max) a11x1]Ы...Y± am1x1mЫ...i=bm преобразуется в матричную: C: c1 c2 ... cn A: a11 a12 ... a1n ... am1 am2 ... amn B: b1 b2 ... bm Одновременно изменяются знаки коэффициентов при неизвестных в ограничениях с отрицательным свободным членом, а также знаки коэффициентов линейного функционала в случае его мак- симизации. С иллюстративной целью допускаются некоторые ва- рианты синтаксической записи. Предусмотрена возможность пов- торного задания ошибочных строк. %token число Xi оптим %% злп:функционал '0 система_ограничений {final();} | система_ограничений функционал '0 { final();} функционал: линейная_функция {stf();} /*По умолчанию - минимизация */ | оптим '('линейная_функция')' {if($1) conv(); stf();} /*в случае максимизации выполнить conv()*/ | линейная_функция '-''>' оптим {if($4) conv();stf();} линейная_функция: элем1 | линейная_функция элем ; элем: знак число Xi {stc($1*$2,$3); } | знак Xi '*' число { stc($1*$4,$2);} | знак Xi { stc($1,$2);} /* Формы записи коэффициентов*/ элем1: элем | число Xi { stc($1,$2);} | Xi '*' число { stc($3,$1);} | Xi { stc(1,$1); } знак: '+' {$$=1; } | '-' {$$= -1;} система_ограничений: ограничение '0 | система_ограничений ограничение '0 | система_ограничений error '0 {aclear();yyerrok; printf("повторите последнюю строку0);} /*В случае ошибки: стирание инф. о строке, восстановление и выдача подсказки */ ограничение: линейная_функция '=' число { stcb($3);} 37 | линейная_функция '=' знак число { if($3<0) conv(); stcb($4);} /*если bi<0, выполнить conv() */ %% #include "stdio.h" #define MAXM 100/*предельное число*/ #define MAXN 100/*ограничений и перем.*/ int c[MAXN],b[MAXM],a[MAXM+1][MAXN], neqs,nx,x[MAXN]; yylex() { /*Лексический анализатор */ char c,i; /* возвращает: */ while((c=getc(stdin))==' ');/*для целых*/ switch(c) { /*чисел - ЧИСЛО,yylval */ case'0': /*равно знач. числа;*/ case'1': /*для идент.вида xi, i=1,2,...XI*/ case'2':/*yylval равно его порядк. номеру*/ case'3':/*для max/min - ОПТИМ, yylval */ case'4': /* равно соответственно 1 или 0*/ case'5': case'6': case'7': case'8': case'9': yylval=c-'0'; while((c=getc(stdin))<='9'&&c>='0') yylval=yylval*10+c-'0'; ungetc(c,stdin); return(число); case'm': if((c=getc(stdin))=='i') yylval=0; else if(c=='a') yylval=1; else return('m'); while((c=getc(stdin))<='z'&&c>='a'); ungetc(c,stdin); return(оптим); case'X': case'x': if((c=getc(stdin))<'0' || c>'9') return('x'); yylval=0; while(c<='9'&&c>='0') {yylval=yylval*10+c-'0';c=getc(stdin);} ungetc(c,stdin); for(i=0;i