В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 14
Текст из файла (страница 14)
При вызове ЛА синтаксическим анализаторомон посимвольно читает остаток входа, пока не находит самый длинныйпрефикс, который может быть сопоставлен одному из регулярных выраженийp_i. Затем он выполняет действие_i. Как правило, действие_i возвращаетуправление синтаксическому анализатору. Если это не так, т. е. в соответствующем действии нет возврата, то ЛА продолжает поиск лексем до техпор, пока действие не вернет управление синтаксическому анализатору.
Повторный поиск лексем вплоть до явной передачи управления позволяет ЛАправильно обрабатывать пробелы и комментарии. Синтаксическому анализатору ЛА возвращает единственное значение — тип лексемы. Для передачиинформации о типе лексемы используется глобальная переменная yylval.Текстовое представление выделенной лексемы хранится в переменной yytext,а ее длина в переменной yylen.Пример 3.13.
LEX-программа для ЛА, обрабатывающего идентификаторы, числа, ключевые слова if, then, else и знаки логических операций:%{ /*определения констант 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,3*68Глава 3. Лексический анализдлина которой равна yylen, в таблицусимволов и возвращает указатель на нее*/}install_num(){/*аналогичная подпрограмма для размещениялексемы числа*/}В разделе объявлений, заключенном в скобки %{ и %}, перечислены константы,используемые правилами трансляции.
Все, что заключено в эти скобки, непосредственно копируется в программу ЛА lex.yy.c и не рассматривается как частьрегулярных определений или правил трансляции. То же касается и вспомогательныхподпрограмм третьей секции. В данном примере это подпрограммы install_idи install_num.В секцию определений входят также некоторые регулярные определения. Каждоетакое определение состоит из имени и регулярного выражения, обозначаемого этимименем. Например, первое определенное имя — это delim.
Оно обозначает класссимволов { \t\n\}, т. е. любой из трех символов: пробел, табуляция или новаястрока. Второе определение — разделитель, обозначаемый именем ws. Разделитель— это любая последовательность одного или более символов-разделителей.
Словоdelim должно быть заключено в скобки, чтобы отличить его от образца, состоящегоиз пяти символов delim.В определении letter используется класс символов. Сокращение [A-Za-z]обозначает любую из прописных букв от A до Z или строчных букв от a до z. В пятомопределении id для группировки используются скобки, являющиеся метасимволамиLEX. Аналогично, вертикальная черта — метасимвол LEX, обозначающий объединение.В последнем регулярном определении number символ «+» используется какметасимвол «одно или более вхождений», символ «?» как метасимвол «ноль илиодно вхождение». Обратная черта используется для того, чтобы придать обычныйсмысл символу, использующемуся в LEX как метасимвол.
В частности, десятичнаяточка в определении number обозначается как «\.», поскольку точка сама по себепредставляет класс, состоящий из всех символов, за исключением символа новойстроки. В классe символов [+\] обратная черта перед минусом стоит потому, чтознак минус используется как символ диапазона, как в [A-Z].Если символ имеет смысл метасимвола, то придать ему обычный смысл можнои по-другому, заключив его в кавычки.
Так, в секции правил трансляции шестьопераций отношения заключены в кавычки.Рассмотрим правила трансляции, следующие за первым %%. Согласно первомуправилу, если обнаружено ws, т. е. максимальная последовательность пробелов, табуляций и новых строк, никаких действий не производится. В частности, не осуществляется возврат в синтаксический анализатор.Согласно второму правилу, если обнаружена последовательность букв if, нужно вернуть значение IF, которое определено как целая константа, понимаемаясинтаксическим анализатором как лексема if. Аналогично обрабатываются ключевые слова then и else в двух следующих правилах.3.7. Конструктор лексических анализаторов LEX69В действии, связанном с правилом для id, два оператора.
Переменной yylvalприсваивается значение, возвращаемое процедурой install_id. Переменнаяyylval определена в программе lex.yy.c, выходе LEX и доступна синтаксическому анализатору. Она хранит возвращаемое лексическое значение, поскольку второйоператор в действии, return(ID), может только возвратить код класса лексем.Функция install_id заносит идентификаторы в таблицу символов.Аналогично обрабатываются числа в следующем правиле. В последних шестиправилах yylval используется для возврата кода операции отношения, возвращаемое же функцией значение — это код лексемы relop.Если, например, в текущий момент ЛА обрабатывает лексему if, то этойлексеме соответствуют два образца: if и {id}, причем более длинной строки,соответствующей образцу, нет.
Поскольку образец if предшествует образцу дляидентификатора, конфликт разрешается в пользу ключевого слова. Такая стратегияразрешения конфликтов позволяет легко резервировать ключевые слова.Если на входе встречается «<=», то первому символу соответствует образец «<»,но это не самый длинный образец, который соответствует префиксу входа. Стратегиявыбора самого длинного префикса легко разрешает такого рода конфликты.Глава 4СИНТАКСИЧЕСКИЙ АНАЛИЗ4.1. Контекстно-свободные грамматикии автоматы с магазинной памятьюПусть G = (N , T , P , S) — КС-грамматика. Введем несколько важныхпонятий и определений.Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала, называется левосторонним.Если S ⇒∗ u в процессе левостороннего вывода, то u — левая сентенциальная форма. Аналогично определим правосторонний вывод.
Обозначим шагилевого (правого) вывода ⇒ l (⇒ r ).Упорядоченным графом называется пара (V , E ), где V есть множествовершин, а E — множество линейно упорядоченных списков дуг, каждый элемент которого имеет вид ((v , v1 ), (v , v2 ), . . . , (v , vn )). Этот элемент указывает,что из вершины v выходят n дуг, причем первой из них считается дуга,входящая в вершину v1 , второй — дуга, входящая в вершину v2 , и т. д.Упорядоченным помеченным деревом называется упорядоченный граф(V , E ), основой которого является дерево и для которого определена функцияf : V → F (функция разметки), где F — некоторое множество.Упорядоченное помеченное дерево D называется деревом вывода (илидеревом разбора) цепочки w в КС-грамматике G = (N , T , P , S), если выполняются следующие условия:1) корень дерева D помечен S ;2) каждый лист помечен либо a ∈ T , либо e;3) каждая внутренняя вершина помечена нетерминалом A ∈ N ;4) если X — нетерминал, которым помечена внутренняя вершина и X1 , .
. .. . . , Xn — метки ее прямых потомков в указанном порядке, то X → X1 . . .. . . Xk — правило из множества P ;5) цепочка, составленная из выписанных слева направо меток листьев,равна w.4.1. Контекстно-свободные грамматики и автоматы с магазинной памятью71Процесс определения принадлежности данной строки языку, порождаемому данной грамматикой, и, в случае указанной принадлежности, построениядерева разбора для этой строки называется синтаксическим анализом. Можно говорить о восстановлении дерева вывода (в частности, правостороннегоили левостороннего) для строки, принадлежащей языку.
По восстановленному выводу можно строить дерево разбора.Грамматика G называется неоднозначной, если существует цепочка w,для которой имеется два или более различных деревьев вывода в G.Грамматика G называется леворекурсивной, если в ней имеется нетерминал A, такой, что для некоторой цепочки α существует вывод A ⇒ + Aα.Автомат с магазинной памятью (МП-автомат) состоит из управляющего устройства, входной ленты (входа) и так называемого магазина.Один конец магазина называется верхушкой, другой — дном. Формально этосемерка M = (Q, T , Γ, D, q0 , Z0 , F ), где:1) Q — конечное множество состояний управляющего устройства;2) T — конечный входной алфавит;3) Γ — конечный алфавит магазинных символов;4) D — отображение множества Q × (T ∪ {e}) × Γ в множество конечныхподмножеств Q × Γ∗ , называемое функцией переходов;5) q0 ∈ Q — начальное состояние управляющего устройства;6) Z0 ∈ Γ — символ, находящийся в магазине в начальный момент (начальный символ магазина);7) F ⊆ Q — множество заключительных состояний.Конфигурация МП-автомата — это тройка (q , w, u), где1) q ∈ Q — текущее состояние управляющего устройства;2) w ∈ T ∗ — непрочитанная часть входной цепочки; первый символ цепочкиw находится под входной головкой; если w = e, то считается, что всявходная лента прочитана;3) u ∈ Γ∗ — содержимое магазина; самый левый символ цепочки u считается верхним символом магазина; если u = e, то магазин считаетсяпустым.Такт работы МП-автомата M будем представлять в виде бинарногоотношения ⊢, определенного на конфигурациях.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
