Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 5
Текст из файла (страница 5)
В LEX действия записываются на Си. Средидействий может быть указано GOTO состояние. Выполнение этогодействия переводит анализатор в указанное состояние. Если определенонекоторое состояние анализатора, то в нем анализируются тольковыражения, помеченные меткой этого состояния. Все непомеченныедействия соответствуют состоянию по умолчанию ‘0’.Третья секция содержит вспомогательные процедуры, необходимыедля действий. Эти процедуры могут транслироваться раздельно изагружаться с лексическим анализатором.Лексический анализатор, сгенерированный LEX, взаимодействует ссинтаксическим анализатором следующим образом.
При вызове егосинтаксическим анализатором лексический анализатор посимвольно36читает остаток входа, пока не находит самый длинный префикс, которыйможет быть сопоставлен одному из регулярных выражений p i. Затем онвыполняет действие_i. Как правило, действие_i возвращает управлениесинтаксическому анализатору. Если это не так, т.е. в соответствующемдействии нет возврата, то лексический анализатор продолжает поисклексем до тех, пока действие не вернет управление синтаксическомуанализатору. Повторный поиск лексем вплоть до явной передачиуправления позволяет лексическому анализатору правильно обрабатыватьпробелы и комментарии. Синтаксическому анализатору лексическийанализатор возвращает единственное значение - тип лексемы. Дляпередачи информации о типе лексемы используется глобальнаяпеременная yylval.
Текстовое представление выделенной лексемыхранится в переменной yytext, а ее длина в переменной yylen.Пример 2.4. На рис. 2.18 приведена LEX-программа.%{ /*определения констант LT,LE,EQ,NE,GT,GE,IF,THEN,ELSE,ID,NUMBER,RELOP напримерчерез DEFINE или скалярный тип*/ %}/*регулярные определения*/delim [ \t\n]ws{delim}+letter[A-Za-z]digit[0-9]id{letter}({letter}|{digit})*number{digit}+(\.{digit}+)?(E[+\-]?{digit}+)?%%{ws}{/* действий и возврата нет */}if{return(IF);}then{return(THEN);}else{return(ELSE);}{id}{yylval=install_id(); return(ID);}{number} {yylval=install_num(); return(NUMBER);}"<"{yylval=LT; return(RELOP);}"<="{yylval=LE; return(RELOP);}"="{yylval=EQ; return(RELOP);}"<>"{yylval=NE; return(RELOP);}">"{yylval=GT; return(RELOP);}">="{yylval=GE; return(RELOP);}%%install_id(){/*процедура, которая помещает лексему,на первый символ которой указывает yytext,длина которой равна yyleng, в таблицу37символов и возвращает указатель на нее*/}install_num(){/*аналогичная процедура для размещениялексемы числа*/}Рис.
2.18.В разделе объявлений, заключенном в скобки %{ и %}, перечисленыконстанты, используемые правилами трансляции. Все, что заключено в этискобки, непосредственно копируется в программу лексическогоанализатора lex.yy.c и не рассматривается как часть регулярныхопределений или правил трансляции. То же касается и вспомогательныхпроцедур третьей секции. На рис.
2.18 это процедуры install_id иinstall_num.В секцию определений входят также некоторые регулярныеопределения. Каждое такое определение состоит из имени и регулярноговыражения, обозначаемого этим именем. Например, первое определенноеимя - это delim. Оно обозначает класс символов { \t\n}, т.е. любой из трехсимволов: пробел, табуляция или новая строка.
Второе определение разделитель, обозначаемый именем ws. Разделитель - это любаяпоследовательность одного или более символов-разделителей. Слово delimдолжно быть заключено в скобки, чтобы отличить его от образца,состоящего из пяти символов delim.В определении letter используется класс символов. Сокращение [AZa-z] означает любую из прописных букв от A до Z или строчных букв от aдо z. В пятом определении для id для группировки используются скобки,являющиеся метасимволами LEX.
Аналогично, вертикальная черта метасимвол LEX, обозначающий объединение.В последнем регулярном определении number символ '+'используется как метасимвол "одно или более вхождений", символ '?' какметасимвол "ноль или одно вхождение". Обратная черта используется длятого, чтобы придать обычный смысл символу, использующемуся в LEXкак метасимвол.
В частности, десятичная точка в определении numberобозначается как '\.', поскольку точка сама по себе представляет класс,состоящий из всех символов, за исключением символа новой строки. Вклассe символов [+\-] обратная черта перед минусом стоит потому, чтознак минус используется как символ диапазона, как в [A-Z].Если символ имеет смысл метасимвола, то придать ему обычныйсмысл можно и по-другому, заключив его в кавычки. Так, в секции правилтрансляции шесть операций отношения заключены в кавычки.Рассмотрим правила трансляции, следующие за первым %%.38Согласно первому правилу, если обнаружено ws, т.е. максимальнаяпоследовательность пробелов, табуляций и новых строк, никаких действийне производится. В частности, не осуществляется возврат всинтаксический анализатор.Согласно второму правилу, если обнаружена последовательностьбукв 'if', нужно вернуть значение IF, которое определено как целаяконстанта, понимаемая синтаксическим анализатором как лексема 'if'.Аналогично обрабатываются ключевые слова 'then' и 'else' в двух следущихправилах.В действии, связанном с правилом для id, два оператора.Переменной yylval присваивается значение, возвращаемое процедуройinstall_id.
Переменная yylval определена в программе lex.yy.c, выходе LEX,и она доступна синтаксическому анализатору. yylval хранит возвращаемоелексическое значение, поскольку второй оператор в действии, return(ID),может только возвратить код класса лексем. Функция install_id заноситидентификаторы в таблицу символов.Аналогично обрабатываются числа в следующем правиле. Впоследних шести правилах yylval используется для возврата кода операцииотношения, возвращаемое же функцией значение - это код лексемы relop.Если, например, в текущий момент лексический анализаторобрабатывает лексему 'if', то этой лексеме соответствуют два образца: 'if' и{id} и более длинной строки, соответствующей образцу, нет.
Посколькуобразец 'if' предшествует образцу для идентификатора, конфликтразрешается в пользу ключевого слова. Такая стратегия разрешенияконфликтов позволяет легко резервировать ключевые слова.Если на входе встречается '<=', то первому символу соответствуетобразец '<', но это не самый длинный образец, который соответствуетпрефиксу входа. Стратегия выбора самого длинного префикса легкоразрешает такого рода конфликты.Глава 3.
Синтаксический анализ3.1. Основные понятия и определенияПусть G=<N,T,P,S> - контекстно-свободная грамматика, где N - множествонетерминальных символов, T - множество терминальных символов, P множество правил вывода и S - аксиома. Будем говорить, что uxv39выводится за один шаг из uAv (и записывать это как uAv=>uxv), если A->x- правило вывода и u и v - произвольные строки из (N U T)*. Еслиu1=>u2=>...=>un, будем говорить, что из u1 выводится un, и записывать этокак u1=>*un. Т.е.:1) u=>*u для любой строки u,2) если u=>*v и v=>*w, то u=>*w.Аналогично, "=>+" означает выводится за один или более шагов.Если дана грамматика G с начальным символом S, отношение =>+можно использовать для определения L(G) - языка, порожденного G.Строки L(G) могут содержать только терминальные символы G. Строкатерминалов w принадлежит L(G) тогда и только тогда, когда S=>+w.Строка w называется предложением в G.Если S=>*u, где u может содержать нетерминалы, то u называетсясентенциальной формой в G.
Предложение - это сентенциальная форма, несодержащая нетерминалов.Рассмотрим выводы, в которых в любой сентенциальной форме накаждом шаге делается подстановка самого левого нетерминала. Такойвывод называется левосторонним. Если S=>*u в процессе левостороннеговывода, то u - левая сентенциальная форма. Аналогично определяетсяправосторонний вывод.Упорядоченным графом называется пара (V,E), где V обозначаетмножество вершин, а E - множество линейно упорядоченных списков дуг,каждый элемент которого имеет вид ((v,e1),(v,e2),...,(v,en)). Этот элементуказывает, что из вершины a выходят n дуг, причем первой из нихсчитается дуга, входящая в вершину e1, второй - дуга, входящая в вершинуe2, и т.д.Дерево вывода в грамматике G=<N,T,P,S> - это помеченноеупорядоченное дерево, каждая вершина которого помечена символом измножества N U T U {e}.
Если внутренняя вершина помечена символом A, аее прямые потомки - символами X1,..., Xn, то A->X1X2...Xn - правило этойграмматики.Упорядоченное помеченное дерево D называется деревом вывода(или деревом разбора) в КС-грамматике G(S)=(N,T,P,S), если выполненыследующие условия:(1) корень дерева D помечен S;(2) каждый лист помечен либо a<-T, либо e;(3) каждая внутренняя вершина помечена нетерминалом;33(4) если N - нетерминал, которым помечена внутренняя вершина иX1,...,Xn - метки ее прямых потомков в указанном порядке, то N>X1...Xk - правило из множества P.Автомат с магазинной памятью (сокращенно МП-автомат) - это семеркаP=<Q,T,Г,D,q0,Z0,F>, где(1) Q - конечное множество символов состояний, представляющихвсевозможные состояния управляющего устройства;(2) T - конечный входной алфавит;(3) Г - конечный алфавит магазинных символов;(4) D - функция переходов - отображение множества Qx(T U {e})xГ вмножество конечных подмножеств QxГ*, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
