Иванова Г.С., Ничушкина Т.Н. - Основы конструирования компиляторов, страница 4

A()q := Table [q, j]Ind := Ind +1Все-циклЕсли q = «К»то Выполнить А3Вывести сообщение «Это число»иначе Вывести сообщение ДiВсе-еслиОглавление243.3Построение синтаксических анализаторовСинтаксические анализаторы регулярных языков на вход получают строку лексем.Пример. Синтаксический анализатор списка описания целых скаляров, массивов ифункций (упрощенный вариант), например: int xaf, y22[5], zrr[2][4], re[N], fun(), *g;После лексического анализа входная строка представлена в алфавите:V – идентификатор; N – целочисленная константа; служебные символы: «[ ] ( ) , ; *».Функцию переходов зададим синтаксической диаграммой (см. рисунок 7).31(45)V*[2N67]8,Рисунок 7 – Синтаксическая диаграммаПо диаграмме построим таблицу автомата (см.

таблицу 6).Таблица 6 –Таблица переходов12345678V33EEEEEENEEEEE7EE*2EEEEEEE(EE4EEEEE)EEE5EEEE[EE6EEEE6]EEEEEE8EАлгоритм распознавателя:Ind := 1q := 1Цикл-пока q ≠ «Е» и q ≠ «К»q := Table [q, Pos(S[Ind], «VN*()[];»)]Ind := Ind +1Все-циклЕсли q = «К»то Выполнить А3Оглавление,EE1E1EE1; ДругиеEEEEКEEEКEEEEEКE;К25Вывести сообщение «Это число»иначе Вывести сообщение ДiВсе-еслиОглавление26Контрольные вопросы1.

Определите, что конечный автомат. В чем особенность его использования приграмматическом разборе.Ответ.2. Какие способы описания конечных автоматов существуют? Какой способ используется при программной реализации и почему?Ответ.3. Как построить конечный автомат для лексического анализа? В чем заключается егоособенность?Ответ.4. Как построить конечный автомат для синтаксического анализа?Ответ.Оглавление274Распознавание КС-грамматик4.1 Автомат с магазинной памятьюРаспознавание КС-грамматик выполняется автоматом с магазинной памятью.

Автомат с магазинной памятью определяется семеркой:PM = (Q, Σ, Г, δ, q0, z0, F),где Q – конечное множество состояний автомата;Σ – конечный входной алфавит;Г – конечное множество магазинных символов;δ (q, ck, zj) – функция переходов;q0 ∈ Q – начальное состояние автомата;z0 ∈ Г – символ, находящийся в магазине в начальный момент,F ⊆ Q – множество заключительных (допускающих) состояний.Пример.

Синтаксический анализатор выражений.Алфавит языка записи выражений: Σ = {<Ид>, +, –, *, /, (, ), ◄, ►}. Грамматикаописывается синтаксическими диаграммами, представленными на рисунке 8.ВыражениеТерм+ТермТерм-Множ*МножМножитель/Ид(Выражение56)Рисунок 8 – Синтаксические диаграммыПодставляем диаграммы одна в другую, исключая промежуточные нетерминалыТерм и Множитель. В результате получаем полную синтаксическую диаграмму (см. рисунок 9), которая состоит из двух частей: основной и рекурсивной, что связано с наличиемрекурсивного вложения правил продукции.Оглавление2812>Выражение3К<ВыражениеX4Ид(Выражение568*)7/Y+Ид(Выражение91110Выражение-)Рисунок 9 – Синтаксическая диаграммаПо диаграмме строим таблицу автомата, которая также будет состоять из двух частей (см.

таблицу 7), которые можно объединить в одну.Таблица 7 – Таблица переходов автомата<Ид>123X45678+-*/↓S=3()►2◄↓ S =3К<Ид>4+-*/(5)↑S11 11 7 7↓ S =6↓ S =689►◄↑S4↑S11 119 ↓ S =101011 ↓ S =YY↑S↓ S =108↓ S =Y↑S↑SУсловные обозначения:К – конец разбора, E – состояние ошибки (все пустые ячейки должны содержать E),↓ Y = <состояние> – рекурсивный вызов распознавателя, справа указан номер состояния после возврата из данного вызова;↑Y – возврат из рекурсии, следующее состояние определяется значением Y,При разработке алгоритма используем следующие обозначения:Mag – стек (магазин) распознающего автомата, элементы, записываемые в стек, –терминальные и нетерминальные символы; ↓ – запись в стек, ↑ – чтение из стека;q – текущее состояние;Оглавление29Table (<Текущее состояние>, <Анализируемый символ>) – элемент таблицы (матрицы) переходов, состоящий из следующих полей: q – следующее состояние (в том числе«↓» – рекурсивный вызов, «↑» – возврат из рекурсии), S – состояние после возврата из рекурсии, если необходим рекурсивный вызов, или ∅;String – исходная строка;Ind – номер символа исходной строки.Алгоритм программы, реализующей автомат, будет выглядеть следующим образом:q:=1Ind := 1Mag :=∅Цикл-пока q ≠ «E» и q ≠ «К»q := Table [q, String[Ind]].qЕсли q = ′↓′то Mag ↓ Table [q, String[Ind]].Sq := Xиначе Если q = ′↑′то Mag ↑qиначе Ind := Ind +1Все-еслиВсе-еслиЕсли q = «К»то «Строка принята»иначе «Строка отвергнута»Все-еслиОднако построение такого автомата для сложного языка – задача не простая.

Поэтому в литературе предлагаются другие способы. Обычно выделяют подклассы грамматик,обладающих определенными свойствами, основываясь на которых можно строить конкретные распознаватели.Оглавление304.2 Синтаксические анализаторы LL(k)-грамматик. Метод рекурсивного спускаLL(k)-грамматики – это класс КС-грамматик, гарантирующих существование детерминированных нисходящих распознавателей (L – левосторонний просмотр исходной строки, L – левосторонний разбор, k – количество символов, просматриваемых для определения очередного правила). В грамматиках этого класса для однозначного выбора правилдолжны:1) отсутствовать правила с левосторонней рекурсией;2) различаться k первых символов разных правил.Реализация нисходящего разбора заключается в следующем. В исходный моментвремени в стек записывают аксиому.

Затем выбирают правило подстановки аксиомы,сравнивая k символов исходной строки с тем же количеством символов правых частейправил. Правую часть правила подставляют в стек вместо левой части. Одинаковые первые символы стека и исходной строки удаляют. Затем вновь выбирают правило подстановки уже для нетерминала, который оказался в начале стека и т. д. Количество просматриваемых символов определяется конкретными правилами грамматики.Пример. Дана грамматика записи выражений:1) <Строка> ::= <Выр>◄2) <Выр> ::= <Терм> <Слож>3) <Слож> ::= e | + <Терм> <Слож> | - <Терм><Слож>4) <Терм> ::= <Множ><Умн>5) <Умн> ::= e | *<Множ><Умн> | / <Множ><Умн>6) <Множ> ::= <Ид> | (<Выр>)В данной грамматике в тех случаях, когда есть несколько правил для нетерминалавыбор определяется одним терминальным символом, поэтому данная грамматика относится к классу LL(1).

Следовательно, для распознавания можно использовать нисходящийметод (см. таблицу 8).Оглавление31Таблица 8 – Результат распознаванияРаспознаваемая строкаСтекПравило<Ид>*(<Ид>+<Ид>)+<Ид>◄<Выр> ◄2<Ид>*(<Ид>+<Ид>)+<Ид>◄<Терм><Слож>◄4<Ид>*(<Ид>+<Ид>)+<Ид>◄<Множ><Умн><Слож>◄6а<Ид>*(<Ид>+<Ид>)+<Ид>◄<Ид><Умн><Слож>◄*(<Ид>+<Ид>)+<Ид>◄<Умн><Слож>◄*(<Ид>+<Ид>)+<Ид>◄*<Множ><Умн><Слож>◄Удалить символ(<Ид>+<Ид>)+<Ид>◄<Множ><Умн><Слож>◄6б(<Ид>+<Ид>)+<Ид>◄(<Выр>)<Умн><Слож>◄Удалить символ<Ид>+<Ид>)+<Ид>◄<Выр>)<Умн><Слож>◄2<Ид>+<Ид>)+<Ид>◄<Терм><Сложе>)<Умн><Слож>4<Ид>+<Ид>)+<Ид>◄<Множ><Умн><Слож>)<Умн><Слож>◄6а<Ид>+<Ид>)+<Ид>◄<Ид><Умн><Слож>)<Умн><Слож>◄+<Ид>)+<Ид>◄<Умн><Слож>)<Умн><Слож>◄+<Ид>)+<Ид>◄<Слож>)<Умн><Слож>◄+<Ид>)+<Ид>◄+<Терм><Слож>)<Умн><Слож>◄Удалить символ<Ид>)+<Ид>◄<Терм><Слож>)<Умн><Слож>◄4<Ид>)+<Ид>◄<Множ><Умн><Слож>)<Умн><Сложе>◄6а<Ид>)+<Ид>◄<Ид><Умн><Слож>)<Умн><Слож>◄)+<Ид>◄<Умн><Слож>)<Умн><Слож>◄5а (е))+<Ид>◄<Слож>)<Умн><Слож>◄3а (е))+<Ид>◄)<Умнож><Слож>◄+<Ид>◄<Умн><Слож>◄+<Ид>◄<Слож>◄+<Ид>◄+<Терм><Слож>◄Удалить символ<Ид>◄<Терм><Слож>◄4<Ид><Множ><Умн><Слож>◄6а<Ид><Ид><Умн><Слож>◄◄<Умн><Слож>◄5а (е)◄<Слож>◄3а (е)◄◄КонецОглавлениеУдалить символ5бУдалить символ5а (е)2аУдалить символУдалить символ5а (е)3бУдалить символ32Метод рекурсивного спуска.

Метод рекурсивного спуска основывается на синтаксических диаграммах языка. Согласно этому методу для каждого нетерминала разрабатывают рекурсивную процедуру. Основная программа вызывает процедуру аксиомы, которая вызывает процедуры нетерминалов, упомянутые в правой части аксиомы и т. д. В этиже процедуры встраивают семантическую обработку распознанных конструкций.Пример. Определим синтаксис языка описания выражений синтаксическими диаграммами (см. рисунок 10).ВыражениеТерм+ТермТерм-Множ*МножМножитель/Ид(5Выражение6)Рисунок 10 – Синтаксические диаграммы грамматики описания выраженийПо каждой диаграмме пишем рекурсивную процедуру и добавляем основную программу, вызывающую процедуру аксиомы:Функция Выражение:Boolean:R:=Терм()Цикл-пока R=true и (NextSymbol =’+’ или NextSymbol =’-’)R:=Терм()Все-циклВыражение:= RВсеФункция Терм:boolean:Множ()Цикл-пока R=true и (NextSymbol =’*’ или NextSymbol =’/’)R:=Множ()Все-циклТерм:= RВсеФункция Множ:Boolean:Если NextSymbol =’(’то R:=Выражение()Оглавление33Если NextSymbol ≠ ‘)’то Ошибка Все-еслииначе R:= Ид()Все-еслиВсеОсновная программа:R:=Выражение()Если NextSymbol ≠ ‘◄’то Ошибка ()Все-еслиКонецНиже приведен текст программы – распознавателя выражений.

Распознаватель идентификаторов построен по синтаксической диаграмме на рисунке 11:12БукваРазделительКБукваЦифраРисунок 11 – Синтаксическая диаграмма нетерминала <Идентификатор>program Compiler;{$APPTYPE CONSOLE}usesSysUtils;Type SetofChar=set of AnsiChar;Const Bukv:setofChar=['A'..'Z','a'..'z'];Const Cyfr:setofChar=['0'..'9'];Const Razd:setofChar=[' ','+','-','*','/',')'];Const TableId:array[1..2,1..4] of Byte=((2,0,0,0),(2,2,10,0));Function Culc(Var St:shortstring;Razd:setofChar):boolean;forward;Var St:shortstring; R:boolean;Procedure Error(St:shortstring); {вывод сообщений об ошибках}BeginWriteLn('Error *** ', st, ' ***');ОглавлениеEnd;34Procedure Probel(Var St:shortstring); {удаление пробелов}BeginWhile (St<>'') and (St[1]=' ') do Delete(St,1,1);End;Function Id(Var St:shortstring;Razd:setofChar):boolean;{распознаватель идентиф.}Var S:shortString;BeginProbel(St);S:='';if St[1] in Bukv thenBeginS:=S+St[1]; Delete(St,1,1);While (St<>'')and (St[1] in Bukv) or (St[1] in Cyfr) doBeginS:=S+St[1]; Delete(St,1,1);End;if (St='') or (St[1] in Razd) thenBeginId:=true;WriteLn('Identify=',S);EndelseBeginId:=false; WriteLn('Wrong symbol *',St[1],'*');End;EndelseBeginId:=false; WriteLn('Identifier waits...', St);End;End;Function Mult(Var St:shortstring;Razd:setofChar):boolean;Var R:boolean;BeginОглавление35Probel(St);if St[1]='(' thenbeginDelete(St,1,1); Probel(St);R:=Culc(St,Razd);Probel(St);if R and (St[1]=')') then Delete(St,1,1) else Error(St);endelse R:=Id(St,Razd);Mult:=R;End;Function Term(Var St:shortstring;Razd:setofChar):boolean;Var S:shortstring; R:boolean;BeginR:=Mult(St,Razd);if R thenbeginProbel(St);While ((St[1]='*') or (St[1]='/')) and R dobeginDelete(St,1,1);R:=Mult(St,Razd);end;end;Term:=R;End;Function Culc(Var St:shortstring;Razd:setofChar):boolean;Var S:shortstring; R:boolean;BeginR:=Term(St,Razd);if R thenbeginProbel(St);Оглавление36While ((St[1]='+') or (St[1]='-')) and R dobeginDelete(St,1,1);R:=Term(St,Razd);end;end;Culc:=R;End;BeginWriteln('Input Strings:'); Readln(St);R:=true;While (St<>'end') and R doBeginR:=Culc(St,Razd);if R and (length(st)=0) then Writeln('Yes') elseWriteln('No');Writeln('Input Strings:'); Readln(St);End;writeln('Input any key');readln;End.Оглавление374.3 Синтаксические анализаторы LR(k)-грамматик.