Практикум «Оптимизирующие компиляторы» (на примере GCC) (1157417), страница 17
Текст из файла (страница 17)
YACC (BISON)Программа YACC (Yet Another Compiler Compiler) предназначена дляпостроения синтаксического анализатора контекстно-свободного языка.Анализируемый язык описывается с помощью грамматики в виде, близкомформе Бэкуса-Наура (БНФ). Результатом работы YACC'a являетсяпрограмма на Си, реализующая восходящий LALR(1) распознаватель.Структура YACC-программыYACC-программа состоит из трех секций, разделенных символом %% –секции описаний, секции правил, в которой описывается грамматика, исекции программ, содержимое которой просто копируется в выходнойфайл. Пример простейшей программы на YACC'e:%token name%start e%%e : e '+' m | e '-' m | m ;m : m '*' t | m '/' t | t ;t : name | '(' e ')' ;%%Секция правил содержит информацию о том, что символ name являетсялексемой (терминалом) грамматики, а символ e – ее начальнымнетерминалом.Грамматика записана обычным образом – идентификаторы обозначаюттерминалы и нетерминалы, символьные константы типа '+' '-' – терминалы.Символы : | ; принадлежат метаязыку и читаются «есть по определению»,«или» и «конец правила» соответственно.Разрешение конфликтовПрактикум «оптимизирующие компиляторы»Написанная грамматика (она обладает свойством LALR(1)) задает языкарифметических формул, в котором приоритет '*' и '/' выше приоритета '+'и '-', а все операции левоассоциативны.
Для указания этих свойств языка вграмматику введены дополнительные нетерминалы m, и t. Другаяграмматика этого языка:e : e '+' e | e '-' e | e '*' e |e '/' e | '(' e ')' | name ;не однозначна (и, следовательно, не LALR(1)). Попытка применить YACCдляанализаданнойнеразрешеннымграмматикиконфликтамтипаприведеткмногочисленнымсдвиг/свертка(shift/reduce)впостроенном автомате. Если рассмотреть конфликты более подробно,выясняется, что в каждом случае можно однозначно выбрать междусдвигом или сверткой, основываясь на приоритетах операций и порядкевыполнения равноприоритетных операций слева направо.
(Аналогичнопростому и операторному предшествованию).YACC позволяет дополнить грамматику информацией такого рода иполучить бесконфликтный распознаватель:%token name%left '+' '-'%left '*' '/'%%e : e '+' e | e '-' e | e '*' e | e '/' e| '(' e ')' | name ;%%Предложения%left,%rightи%nonassocвсекцииописанийприписывают всем перечисленным за ними символам одинаковыйприоритет и соответствующее значение ассоциативности. (Отсутствиеассоциативности означает недопустимость выражений вида a @ b @ c)Приоритет увеличивается сверху вниз для каждого нового предложения.Практикум «оптимизирующие компиляторы»LALR(1)-конфликты сдвиг/свертка или свертка/свертка разрешаютсявыбором более приоритетного действия.
Приоритет сдвига равенприоритету считываемой лексемы. Приоритет свертки равен приоритетусамой правой лексемы в правиле, по которому производится свертка.Можно также явно указать приоритет свертки, написав %prec <лексема>справа от правила.Добавить в язык формул операцию унарного минуса, более приоритетную,чем бинарные операции, можно следующим образом:%token name%left '+' '-'%left '*' '/'%left UMIN%%e : e '+' e | e '-' e | e '*' e | e '/' e| '(' e ')' | name ;e : '-' e %prec UMIN ;%%Фиктивная лексема UMIN используется только для задания приоритетасвертки по правилу e : '-' e ;Итак, YACC разрешает конфликты (если они возникнут) по следующимправилам:• если приоритеты альтернативных действий определены и различны,то выполняется действие с большим приоритетом;• если приоритеты действий определены и одинаковы, то в случаелевой ассоциативности выбирается свертка, в случае правойассоциативности – сдвиг, если они неассоциативны – создаетсяошибочная ситуация;Практикум «оптимизирующие компиляторы»• иначе (приоритет хотя бы одной из альтернатив не специфицирован)в случае конфликта сдвиг/свертка выполняется сдвиг, а в случаеконфликта свертка/свертка – свертка по правилу, определенномувыше по тексту в описании грамматики, в обоих случаях YACCсообщает о неразрешенном конфликте в этом состоянии.Отметим, что для конфликтной грамматики с правиламиs : if '(' e ')' s| if '(' e ')' s else s;предпочтение сдвига «правильно» разрешает конфликт при разборевыраженияif( e ) if( e ) s else selse будет отнесено к ближайшему if'у, как и принято в алголоподобныхязыках.Для конфликтной грамматики арифметических формул, эти правилаприводят к вычислению выражения справа налево без учета приоритетовопераций.Семантические действияС каждым правилом грамматики может быть связано действие, котороебудет выполнено при свертке по данному правилу.
Оно записывается ввиде заключенной в фигурные скобки последовательности операторовязыка Си, расположенной после правой части соответствующего правила.stnt : IF '(' expr ')' stnt{ if_ctr++; }| WHILE '(' expr ')' stnt { while_ctr++; }| assign_st{ ass_ctr++; };В этом примере действие if_ctr++ будет выполнено после разбора всегооператора if. При необходимости выполнить семантические действия,Практикум «оптимизирующие компиляторы»например, сразу после вычисления выражения expr, можно поместить ихмежду символами правой части правила.statement: IF '(' expr { action_1 } ')'statement { action_2 } ;В этих случаях YACC автоматически преобразует грамматику, вводядополнительные нетерминалы и соответствующие им правила с пустойправойчастью.Приихсверткеибудутвыполненыдействия,расположенные между символами исходной грамматики.stnt: IF '(' expr void_1 ')' stnt { action_2 } ;void_1:{ action_2 } ;Семантический стекДля естественного обмена данными между действиями, каждый терминалили нетерминал может иметь значение.
Для доступа к нему в действияхиспользуются псевдопеременные $$ – значение левого символа правила,$<i> – значение i-ого символа правой части правила (символы нумеруютсяслева направо, начиная с 1). Другими словами, кроме обычного стекасостояний построенный YACC'ом анализатор содержит «семантический»стек, содержащий значения символов. Значения имеют тип YYSTYPE,который по умолчанию определяется как int. Действиеexpr : expr '+' expr { $$ = $1 + $3; } ;может быть использовано в интерпретаторе формул, в котором значениенетерминала «выражение» есть его вычисленное значение.Если для правила не указано никакого действия, или действие не содержитупоминания псевдопеременной $$, то значение левой части правиластановится равным значению первого символа правой части, т.
е. неявновыполняется действие { $$ = $1; }. Значение очередной лексемыкопируется из переменной int yylval, в которую его обычно заносит сканер.Различные символы грамматики могут иметь значения разных типов.Практикум «оптимизирующие компиляторы»Для этого следует определить тип YYSTYPE как union и специфицироватьтип терминалов и нетерминалов в разделе описаний. При этом будетосуществляться контроль типов при использовании псевдопеременных, аобращение к ним будет транслироваться в обращение к соответствующемуполю union.%{#define YYSTYPE yystypedef union {intintval;longlongval;nodeptr *ptrval;} yys;%{%token <intval> ICONST%token <intval> LCONST%type<ptrval> exprЕсли в качестве внутреннего представления программы используетсядерево, удобно иметь в качестве значения нетерминала указатель насоответствующий ему узел дерева.Кодировка лексем и интерфейсФайл, порождаемый YACC'ом в процессе работы, содержит таблицыLALR(1)-анализатора и Си-текст функции int yyparse( void ), реализующейинтерпретатор таблиц и семантические действия.
Для запуска парсерадостаточно вызвать эту функцию. В случае успешного разбора онавозвращает 0, в случае ошибки – 1.Для получения очередной лексемы парсер вызывает функцию int yylex(void ). Она должна возвратить код лексемы и поместить ее значение впеременную YYSTYPE yylval.Практикум «оптимизирующие компиляторы»Код лексемы – положительное целое число. Лексемам, заданным в видесимвольных констант, соответствует их код в наборе символов ЭВМ(обычно ASCII), лежащий в диапазоне 0..255. Лексемам, имеющимсимволические имена, присваиваются коды начиная с 257.Выходной файл содержит операторы #define, определяющие имена лексемкак их коды.
Если имена лексем требуются в других файлах, следуетуказать ключ -d при запуске YACC'а, и он продублирует эти определения вфайле y.tab.h. Этот файл следует включить в другие файлы программы(например, сканер), использующие коды лексем.Обработка ошибокЕсли анализируемое предложение не соответствует языку, то в некоторыймомент возникнет ошибочная ситуация, т. е. парсер окажется в состоянии,в котором не предусмотрено ни сдвига, ни свертки для полученнойошибочной лексемы. Обычная реакция парсера – вызов функции voidyyerror( const char * ) с аргументом "Syntax error" и завершение работы –возврат из функции yyparse с значением 1.
Реализация функции yyerrorвозлагается на пользователя, и он может попытаться организовать в нейвыдачу более разумной диагностики (при использовании YACC-парсераэто не является тривиальной задачей).Во многих случаях желательно как-нибудь продолжить разбор. Длявосстановления после ошибки YACC содержит следующие средства.Имеется специальная лексема с именем error, которая может употреблятьсяв грамматике.
При возникновении ошибки устанавливается флаг ошибки,вызывается функция yyerror, а затем из стека состояний удаляютсяэлементы, пока не встретится состояние, допускающее лексему error. Приобнаружении такого состояния выполняется сдвиг, соответствующийлексеме error в этом состоянии и разбор продолжается. Если приустановленном флаге ошибки снова возникает ошибочная ситуация, то дляПрактикум «оптимизирующие компиляторы»избегания многократных сообщений yyerror не вызывается, а ошибочнаялексема игнорируется. Флаг ошибки сбрасывается только после трехуспешно считанных лексем.Специальными действиями в правилах, обрабатывающих ошибочныеситуации можно более активно вмешиваться в этот процесс.yyerrok() – сбрасывает флаг ошибкиyyclearin() – удаляет просмотренную вперед ошибочную лексемуМакро YYERROR явным образом возбуждает ошибочную ситуацию.Пример:statement :....| error ';'при возникновении ошибки внутри statement продолжение разборавозможно только начиная с ';' – в результате будут пропущены все лексемыдо точки с запятой, которая затем будет свернута в нетерминал statement.Практикум «оптимизирующие компиляторы»Приложение Е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
