Все-если

Однако построение такого автомата для сложного языка – задача не простая. Поэтому в литературе предлагаются другие способы. Обычно выделяют подклассы грамматик, обладающих определенными свойствами, основываясь на которых можно строить конкретные распознаватели.

2.5.2 Синтаксические анализаторы LL(k) -грамматик. Метод рекурсивного спуска

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

1) отсутствовать правила с левосторонней рекурсией;

2) различаться k первых символов разных правил.

Реализация нисходящего разбора заключается в следующем. В исходный момент времени в стек записывают аксиому. Затем выбирают правило подстановки аксиомы, сравнивая k символов исходной строки с тем же количеством символов правых частей правил. Правую часть правила подставляют в стек вместо левой части. Одинаковые первые символы стека и исходной строки удаляют. Затем вновь выбирают правило подстановки уже для нетерминала, который оказался в начале стека и т. д. Количество просматриваемых символов определяется конкретными правилами грамматики.

Пример. Дана грамматика записи выражений:

1) <Строка>::= <Выр>◄

2) <Выр>::= <Терм> <Слож>

3) <Слож>::= e | + <Терм> <Слож> | - <Терм><Слож>

4) <Терм>::= <Множ><Умн>

5) <Умн>::= e | *<Множ><Умн> | / <Множ><Умн>

6) <Множ>::= <Ид> | (<Выр>)

В данной грамматике в тех случаях, когда есть несколько правил для нетерминала выбор определяется одним терминальным символом, поэтому данная грамматика относится к классу LL (1). Следовательно, для распознавания можно использовать нисходящий метод (см. таблицу 9).

Таблица 9 – Результат распознавания

Метод рекурсивного спуска. Метод рекурсивного спуска основывается на синтаксических диаграммах языка. Согласно этому методу для каждого нетерминала разрабатывают рекурсивную процедуру. Основная программа вызывает процедуру аксиомы, которая вызывает процедуры нетерминалов, упомянутые в правой части аксиомы и т. д. В эти же процедуры встраивают семантическую обработку распознанных конструкций.

Пример. Определим синтаксис языка описания выражений синтаксическими диаграммами (см. рисунок 10).

Рисунок 10 – Синтаксические диаграммы грамматики описания выражений

По каждой диаграмме пишем рекурсивную процедуру и добавляем основную программу, вызывающую процедуру аксиомы:

Функция Выражение:Boolean:

R:=Терм()

Цикл-пока R=true и (NextSymbol =’+’ или NextSymbol =’-’)

R:=Терм()

Все-цикл

Выражение:= R

Все

Функция Терм:boolean:

Множ()

Цикл-пока R=true и (NextSymbol =’*’ или NextSymbol =’/’)

R:=Множ()

Все-цикл

Терм:= R

Все

Функция Множ:Boolean:

Если NextSymbol =’(’

то R:=Выражение()

Если NextSymbol ¹ ‘)’то Ошибка Все-если

иначе R:= Ид()

Все-если

Все

Основная программа:

R:=Выражение()

Если NextSymbol ¹ ‘◄’то Ошибка ()Все-если

Конец

Ниже приведен текст программы – распознавателя выражений. Распознаватель идентификаторов построен по синтаксической диаграмме на рисунке 11:

Рисунок 11 – Синтаксическая диаграмма нетерминала <Идентификатор>

Program ex;

Type SetofChar=set of Char;

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:string;Razd:setofChar):boolean; forward;

Var St:string; R:boolean;

Procedure Error (St:string); {вывод сообщений об ошибках}

Begin WriteLn('Error *** ', st, ' ***'); End;

Procedure Probel (Var St:string); {удаление пробелов}

Begin While (St<>'') and (St[1]=' ') do Delete(St,1,1); End;

Function Id (Var St:string;Razd:setofChar):boolean; {распознаватель идентиф.}

Var S:String;

Begin

Probel(St);

S:='';

if St[1] in Bukv then

Begin

S:=S+St[1]; Delete(St,1,1);

While (St<>'') and (St[1] in Bukv) or (St[1] in Cyfr) do

Begin

S:=S+St[1]; Delete(St,1,1);

End;

if (St='') or (St[1] in Razd) then

Begin

Id:=true; WriteLn('Identify=',S);

End

else

Begin

Id:=false; WriteLn('Wrong symbol *',St[1],'*');

End;

End

else

Begin

Id:=false; WriteLn('Identifier waits...', St);

End;

End;

Function Mult (Var St:string;Razd:setofChar):boolean;

Var R:boolean;

Begin

Probel(St);

if St[1]='(' then

begin

Delete(St,1,1); Probel(St);

R:=Culc(St,Razd);

Probel(St);

if R and (St[1]=')') then Delete(St,1,1) else Error(St);

end

else R:=Id(St,Razd);

Mult:=R;

End;

Function Term (Var St:string;Razd:setofChar):boolean;

Var S:string; R:boolean;

Begin

R:=Mult(St,Razd);

if R then

begin

Probel(St);

While ((St[1]='*') or (St[1]='/')) and R do

begin

Delete(St,1,1);

R:=Mult(St,Razd);

end;

end;

Term:=R;

End;

Function Culc (Var St:string;Razd:setofChar):boolean;

Var S:string; R:boolean;

Begin

R:=Term(St,Razd);

if R then

begin

Probel(St);

While ((St[1]='+') or (St[1]='-')) and R do

begin

Delete(St,1,1);

R:=Term(St,Razd);

end;

end;

Culc:=R;

End;

Begin

Writeln('Input Strings:'); Readln(St);

R:=true;

While (St<>'end') and R do

Begin

R:=Culc(St,Razd);

if R then Writeln('Yes') else Writeln('No');

Writeln('Input Strings:'); Readln(St);

End;

End.

2.5.3 Синтаксические анализаторы LR(k) -грамматик. Грамматики предшествования

LR(k) -грамматики – это класс КС-грамматик, гарантирующих существование детерминированных восходящих распознавателей (L – левосторонний просмотр, R – правосторонний разбор, k – количество символов, просматриваемых для однозначного определения следующего правила). В грамматиках этого класса отсутствуют правила с правосторонней рекурсией, и обеспечивается однозначное выделение основы. К этому классу, например, относятся грамматики с операторным предшествованием, простым предшествованием и расширенным предшествованием, обеспечивающие еще более простые алгоритмы распознавания.

При восходящем разборе стек используют для накопления основы. Автомат при этом выполняет две основные операции: свертку и перенос. Свертка выполняется, когда в стеке накоплена вся основа, и заключается в ее замене на левую часть соответствующего правила. Перенос выполняется в процессе накопления основы и заключается в сохранении в стеке очередного распознаваемого символа сентенциальной формы. Основная проблема метода заключается в нахождении способа выделения очередной основы. Проще всего основу выделить для грамматик, получивших название «грамматики предшествования». Рассмотрим эти грамматики.

Если два символа α, β Î V расположены рядом в сентенциальной форме, то между ними возможны следующие отношения, названные отношениями предшествования:

1) α принадлежит основе, а β – нет, т. е. α – конец основы: α ×> β;

2) β принадлежит основе, а α – нет, т. е. β – начало основы: α <× β;

3) α и β принадлежит одной основе, т. е. α =× β;

4) α и β не могут находиться рядом в сентенциальной форме (ошибка).

Грамматикой с предшествованием называется грамматика, в которой существует однозначное отношение предшествования между соседними символами. Это отношение позволяет просто определить очередную основу, т. е. момент выполнения каждой свертки.

Различают:

1) грамматики с простым предшествованием, для которых α, β Î V;

2) грамматики с операторным предшествованием, для которых α, β Î V_Т; т. е. отношение предшествования определено для терминальных символов и не зависит от нетерминальных символов, расположенных между ними;

3) грамматики со слабым предшествованием, для которых отношение предшествования не однозначно – оно требует выполнения специальных проверок.

Пример. Грамматика описания арифметических выражений, представленная ниже, относится к классу грамматик с операторным предшествованием:

<Выражение>::= <Терм> | < Терм > + <Выражение> | <Терм> - <Выражение>

<Терм>::= <Множитель> | <Множитель>* <Терм> | <Множитель> / <Терм>

<Множитель>::= (<Выражение>) | <Идентификатор>

Отношения предшествования терминалов (знаков операций), полученные с учетом приоритетов операций, сведены в таблицу 10.

Таблица 10 – Таблица предшествования

Обозначения:

? – ошибка;

< - начало основы;

> -конец основы;

= - принадлежат одной основе;

►- начало выражения;

◄ - конец выражения.

В соответствие с этой таблицей при разборе выражения:

►d+c*(a+b) ◄

содержимое стека будет выглядеть следующим образом:

Поиск по сайту: