Курсовая ТЯП. КР. Теория автоматов и формальных языков

• Название: Теория автоматов и формальных языков
• Анкор: Курсовая ТЯП
• Дата: 03.02.2023
• Размер: 0.99 Mb.
• Имя файла: КР.pdf
• Тип: Методические указания; #919155
• страница: 3 из 5

2.4 Синтаксический анализатор программы
Задача синтаксического анализатора (СиА) - провести разбор текста програм- мы, сопоставив его с эталоном, данным в описании языка. Для синтаксического раз- бора используются контекстно-свободные грамматики (КС-грамматики).
Один из эффективных методов синтаксического анализа – метод рекурсивного спуска. В основе метода рекурсивного спуска лежит левосторонний разбор строки языка. Исходной сентенциальной формой является начальный символ грамматики, а целевой – заданная строка языка. На каждом шаге разбора правило грамматики применяется к самому левому нетерминалу сентенции. Данный процесс соответ- ствует построению дерева разбора цепочки сверху вниз (от корня к листьям).
Пример 2.8. Дана грамматика
)
,
},
,
,
{
},
,
,
,
({
S
P
B
A
S
c
b
a
G

с правилами
bA
B
cA
A
a
A
AB
S
P





)
4
;
)
3
;
)
2
;
)
1
:
. Требуется выполнить анализ строки cabca

Левосторонний вывод цепочки имеет вид:







cabca
cabcA
cabA
caB
cAB
AB
S
Нисходящее дерево разбора цепочки представлено на рисунке 2.6.
Метод рекурсивного спуска реализует разбор цепочки сверху вниз следую- щим образом. Для каждого нетерминального символа грамматики создается своя процедура, носящая его имя. Задача этой процедуры – начиная с указанного места

29 исходной цепочки, найти подцепочку, которая выводится из этого нетерминала. Ес- ли такую подцепочку считать не удается, то процедура завершает свою работу вы- зовом процедуры обработки ошибок, которая выдает сообщение о том, что цепочка не принадлежит языку грамматики и останавливает разбор. Если подцепочку уда- лось найти, то работа процедуры считается нормально завершенной и осуществля- ется возврат в точку вызова. Тело каждой такой процедуры составляется непосред- ственно по правилам вывода соответствующего нетерминала, при этом терминалы распознаются самой процедурой, а нетерминалам соответствуют вызовы процедур, носящих их имена.
Рисунок 2.6 – Дерево нисходящего разбора цепочки cabca

Пример 2.9. Построим синтаксический анализатор методом рекурсивного спуска для грамматики G из примера 2.8.
Введем следующие обозначения:
1) СH – текущий символ исходной строки;
2) gc – процедура считывания очередного символа исходной строки в пере- менную СH;
3) Err - процедура обработки ошибок, возвращающая по коду соответствую- щее сообщение об ошибке.
С учетом введенных обозначений, процедуры синтаксического разбора будут иметь вид.

30
void S
{A; B;
if (CH !=

}

) ERR;
}
void A
{if (CH==

a

) gc;
else if(CH==

c

){gc; A;}
else Err;
}
void B
{if (CH==

b

)
{
gc; B;
}
else Err;
}
Теорема 2.1. Достаточные условия применимости метода рекурсивного
спуска
Метод рекурсивного спуска применим к грамматике, если правила вывода грамматики имеют один из следующих видов:
1) A


, где


(T

N)
*
, и это единственное правило вывода для этого нетер- минала;
2) A

a
1

1
|a
2

2
| … | a
n

n
, где a
i

T для каждого i=1, 2,…, n; a
i

a
j
для i

j,

i

(T

N)
*
, т.е. если для нетерминала А несколько правил вывода, то они должны начинаться с терминалов, причем эти терминалы должны быть различными.
Данные требования являются достаточными, но не являются необходимыми.
Можно применить эквивалентные преобразования КС-грамматик, которые способ- ствуют приведению грамматики к требуемому виду, но не гарантируют его дости- жения.
При описании синтаксиса языков программирования часто встречаются пра- вила, которые задают последовательность однотипных конструкций, отделенных друг от друга каким-либо разделителем. Общий вид таких правил:
L

a | a, L или в РБНФ <L> ::= a {, a}.

31
Формально здесь не выполняются условия метода рекурсивного спуска, т.к. две альтернативы начинаются одинаковыми терминальными символами. Но если принять соглашения, что в подобных ситуациях выбирается самая длинная подцепочка, выводимая из нетерминала
L, то разбор становится детерминированным, и метод рекурсивного спуска будет применим к данному правилу грамматики. Соответствующая правилу процедура будет иметь вид:
void L
{ if (CH != ‘a’) Err;
else gc;
while (CH = =’,’ )
{ gc;
if (CH != ’a’ ) Err;
else gc;
}
}
Пример 2.10. Построим синтаксический анализатор методом рекурсивного спуска для модельного языка М.
Вход – файл лексем в числовом представлении.
Выход – заключение о синтаксической правильности программы или сообщение об имеющихся ошибках.
Введем обозначения:
1) LEX – переменная, содержащая текущую лексему, считанную из файла лексем;
2) gl – процедура считывания очередной лексемы из файла лексем в переменную LEX;
3) EQ(S) – логическая функция, проверяющая, является ли текущая лексема
LEX лексемой для S;
4) ID – логическая функция, проверяющая, является ли LEX идентификатором;
5) NUM - логическая функция, проверяющая, является ли LEX числом.

32 6) err_proc(numb_error)– процедура, обрабатывающая ошибку с номером
numb_error.
Процедуры проверки выполнения правил, описывающих язык М и составляющие синтаксический анализатор, будут иметь следующий вид:
1)для правила PR

{BODY}
void PR()
{ gl();
if (EQ("{")) {gl(); BODY();
if (EQ("}") = = 0) err_proc(3);}
else err_proc(2);
}
2) для правила BODY

(DESCR | OPER) {; (DESCR | OPER)}
void BODY()
{ if (EQ("%") || EQ("#") || EQ("$") ) DESCR ();
else if(ID() || EQ(“if”) || EQ(“[”) || EQ(“while”) || EQ(“for”
|| EQ(“read”) || EQ(“write”) ) OPER();
else err_proc(31);
while(EQ(";") ) {gl;
if (EQ("%") || EQ("#") || EQ("$") ) DESCR ();
else if (ID() || EQ(“if”) || EQ(“[”) || EQ(“while”)
|| EQ(“for”) || EQ(“read”) || EQ(“write”) ) OPER();
else err_proc(31);
}
}
3) для правила DESCR

(% | # | $) ID
1
void DESCR()
{ if (EQ("%") ) {gl(); ID
1
();}
else if (EQ("#") ) {gl(); ID1();}
else if (EQ("$") ) {gl(); ID1();}
}

33 4) для правила ID
1

ID {, ID}
void ID1()
{if (ID() ){gl();
while(EQ(",") ) {gl(); if (ID() ) gl();
else err_proc(18);
}
}
else err_proc(19);
}
5) для правила FACT

ID | NUM | LOG | not FACT | (COMPARE)
void FACT()
{if (ID() || NUM() || EQ("true") || EQ("false") ) gl();
else if (EQ("not") ){gl(); FACT();}
else if (EQ("(") ){gl(); COMPARE();
if(EQ(")") ) gl();
else err_proc(16);
}
else err_proc(17);
}
Аналогично составляются оставшиеся процедуры.
2.5 Семантический анализатор программы
В ходе семантического анализа проверяются отдельные правила записи ис- ходных программ, которые не описываются КС-грамматикой. Эти правила носят контекстно-зависимый характер, их называют семантическими соглашениями или контекстными условиями.

34
Рассмотрим пример построения семантического анализатора (СеА) для про- граммы на модельном языке М. Соблюдение контекстных условий для языка М предполагает три типа проверок:
1) обработка описаний;
2) анализ выражений;
3) проверка правильности операторов.
В оптимизированном варианте СиА и СеА совмещены и осуществляются па- раллельно. Поэтому процедуры СеА будем внедрять в ранее разработанные проце- дуры СиА.
Вход: файл лексем в числовом представлении.
Выход: заключение о семантической правильности программы или о типе об- наруженной семантической ошибки.
Обработка описаний
Задача обработки описаний - проверить, все ли переменные программы опи- саны правильно и только один раз. Эта задача решается следующим образом.
Таблица идентификаторов, введенная на этапе лексического анализа, расши- ряется, приобретая вид таблицы 2.1. Описание таблицы идентификаторов будет иметь вид:
Struct Tabid
{char id[1024], typid[4];
bool descrid, nb;
double nd;
int ni, addrid;
};
typedef struct Tabid tabid;
tabid mTI[s_stack];
Таблица 2.1 – Таблица идентификаторов на этапе СеА
Номер Идентификатор
Описан
Тип
Адрес
1
K
1
%
…
2
Sum
0
…
…

35
Поле «описан» таблицы на этапе лексического анализа заполняется нулем, а при правильном описании переменных на этапе семантического анализа заменяется единицей.
При выполнении процедуры ID1 вводится стековая переменная-массив, в ко- торую заносится контрольное число 0. По мере успешного выполнения процедуры
ID1 в стек заносятся номера считываемых из файла лексем, под которыми они запи- саны в таблице идентификаторов. Как только при считывании, следующая лексема не «,» из стека извлекаются записанные номера и по ним в таблице идентификато- ров проставляется 1 в поле «описан» (к этому моменту там должен быть 0). Если очередная лексема будет «%», «#» или «$», то попутно в таблице идентификаторов поле «тип» заполняется соответствующим типом.
Пример 2.11. Пусть фрагмент описания на модельном языке имеет вид: % k,
sum … Тогда соответствующий фрагмент файла лексем: (2, 3) (4, 1) (2, 6)
(4, 2)…Содержимое стека при выполнении процедуры DESCR представлено на ри- сунке 2.7.
Рисунок 2.7 – Содержимое стека при выполнении процедуры DESCR
Для реализации обработки описаний введем следующие обозначения пере- менных и процедур:
1) LEX – переменная, хранящая значение очередной лексемы, представляющая собой структуру с 2 полями, т.е. для лексемы (n, k) LEX.n_tabl=n, LEX.leksema=k;
2) gl – процедура считывания очередной лексемы в переменную LEX;
3) inst(l) - процедура записи в стек числа l;
4) outst(l) – процедура вывод из стека числа l;
5) instl – процедура записи в стек номера, под которым лексема хранится в таблице идентификаторов, т.е. inst(LEX);
6) dec(t) - процедура вывода всех чисел из стека и вызова процедуры decid(l, t);
7) decid(l, t) – процедура проверки и заполнения поля «описан» и «тип» табли- цы идентификаторов для лексемы с номером l и типа t.
0 1
2

36
Процедуры dec и decid имеют вид:
void decid (… l,... t)
{ if(mTI[l].descrid==1) err_proc(20);
else {mTI[l].descrid=1; strcpy(mTI[l].typid, t);}
}
void dec(... t)
{ char l[s_stack];
outst(l);
while l[0] != 0
{ strcpy(stack, l);
decid(look(4)-1, t);
outst(l);
}
}
Правила и процедуры DESCR и ID1 с учетом семантических проверок прини- мают вид:
DESCR

( % <deс(“%”)> | # <deс(“#”)> | $<dec(“$”)> ) ID
1
void D
{ if(EQ("%") ){gl(); ID1(); dec("%");}
else if(EQ("#") ){gl(); ID1(); dec("#");}
else if(EQ("$") ){gl(); ID1(); dec("$");}
}
ID
1

<inst(0)> I > {, I <instl> }
void ID1()
{ inst(0);
if (ID() ){instl(); gl();
while(EQ(",") ){gl(); if(ID() ){instl(); gl();}
else err_proc(18); }
}
else err_proc(19);}

37
Анализ выражений
Задача анализа выражений - проверить описаны ли переменные, встречающи- еся в выражениях, и соответствуют ли типы операндов друг другу и типу операции.
Эти задачи решаются следующим образом. Вводится таблица двуместных операций (таблица 2.2) и стек, в который в соответствии с разбором выражения E заносятся типы операндов и знак операции. После семантической проверки в стеке остается только тип результата операции. В результате разбора всего выражения в стеке остается тип этого выражения.
Таблица 2.2 – Фрагмент таблицы двуместных операций TOP
Операция
Тип 1
Тип 2
Тип результата
+
>
…
%
%
…
%
%
…
%
$
…
Для реализации анализа выражений введем следующие обозначения процедур и функций:
1) checkid - процедура, которая для лексемы LEX, являющейся идентификато- ром, проверяет по таблице идентификаторов TI, описан ли он, и, если описан, то по- мещает его тип в стек;
2) checkop – процедура, выводящая из стека типы операндов и знак операции, вызывающая процедуру gettype(op, t1, t2, t), проверяющая соответствие типов и за- писывающая в стек тип результата операции;
3) gettype(ор, t1, t2, t) – функция, которая по таблице операций TOP для опера- ции ор выдает тип t результата и типы t1, t2 операндов. Возвращает false, если опе- рация не найдена;
4) checknot – процедура проверки типа для одноместной операции «not».
5) check_type(type) – логическая функция, проверяющая соответствие типа в верхушке стека типу type.
Перечисленные процедуры имеют следующий вид:
void checkid()

38
{char k[s_stack];
strcpy(k, tbl[lex.n_tabl][lex.leksema-1].c_str() );
if (mTI[lex.leksema-1].descrid==0) err_proc(21);
inst(mTI[lex.leksema-1].typid);
}
void checkop()
{outst(top2); outst(op); outst(top1);
strcpy(t1, top1); strcpy(t2, top2);
if (gettype(op, t1, t2, t) = = 0) err_proc(22);
inst(t);
}
void checknot()
{char t[s_stack];
outst(t);
if (strcmp(t,"$")!=0 ) err_proc(23);
inst(t);
}
bool check_type(type)
{ if (strcmp(stack,”%”) = = 0) return true;
i=look(4);
if (i>0) return strcmp(type, mTI[i].typid) = = 0;
return 0;
}
Правила, описывающие выражения языка М, расширенные процедурами се- мантического анализа, принимают вид.
COMPARE

ADD {( > | >= | <= | < | <> | = )<instl> COMPARE <checkop>}
ADD

MULT {(+ | - | or) <instl> ADD <checkop>}
MULT

FACT {( * | / | and) <instl> MULT <checkop>}
FACT

ID <checkid> | NUM <inst(“%”)> | NUM <inst(“#”)> |
NUM <inst(“$”)> | LOG <inst(‘$’)>| not FACT <checknot>| (COMPARE)

39
Пример 2.12. Дано выражение a+5*b. Дерево разбора выражения и динамика содержимого стека представлены на рисунке 2.8.
Рисунок 2.8 – Анализ выражения a+5*b
Данные задачи решаются путем включения в правило OPER ранее рассмот- ренной процедуры checkid, а также новых процедур eqtype и eqbool, имеющих сле- дующий вид:
void eqtype()
{outst(t2); outst(t1);
if (strcmp(t1,"#") = = 0 && strcmp(t2,"%") = = 0) 1;
else if (strcmp(t1, t2)!=0) err_proc(24);}
void eqbool()

40
{outst(t);
if(strcmp(t,"$")!=0) err_proc(25);}
Правило OPER с учетом процедур СеА примет вид:
OPER

[OPER
1
] | ID as COMPARE <eqtype> |
if COMPARE <eqbool> then OPER |
if COMPARE <eqbool> then OPER else OPER |
while COMPARE <egbool> do OPER |
for ID <checkid> <checktype(“%”)> as COMPARE <eqtype> to
COMPARE <check_type(“%”)> do OPER |
write (EXPR) | read (ID
1
)