Проектирование лексического анализатора

 

Для программной реализации построения дерева вывода требуется написать программу, которая выполняет лексический анализ входного текста в соответствии с заданием, порождает таблицу лексем и выполняет синтаксический разбор текста по заданной грамматике с построением дерева разбора. Текст на входном языке задается в виде  символьного (текстового) файла. Программа должна выдавать сообщения о наличие во входном тексте ошибок.

 

3.2 Синтаксический анализатор

 

Исходная грамматика:

G ({ program, end., if, then, else, endif, begin, end, for, downto, do, and, or, not, <<, >>, =, <, >, <>, (, ), -, +, a, c, ;, :=}, {S, L, O, B, C, K, D, H, E, T, M}, P, S)

S → program L end.

L → O | O ; O | L ;

O → if B then O else O endif | if B then O endif | begin L end | for M downto E do O| M

M → a:= E

B → B or C | C

C → C and D | D

D → not D | H

H → E < E | E > E | E = E | E <> E | (B) | E << E | E >> E

E → E – T | E + T | T

T → (E) | a | c

 

Где a это переменная а с констата

Множества крайних левых  и крайних правых нетерминальных символов L(U), R(U) представлены в таблице 1.

 

 

Таблица 1

U	L(U)	R(U)
T	(, a, c	), a, c
E	E, T	T
H	(, E	E, )
D	not, H	D, H
C	C, D	D
B	B, C	C
O	if, begin, for, M	endif, end, O, M
M	a	E
L	L, O	O, ;
S	program	end.

 

В таблице 2 описаны результирующие множества крайних левых и крайних правых нетерминальных символов L(U), R(U).

Таблица 2

U	L(U)	R(U)
T	(, a, c	), a, c
E	E, T, (, a, c	T, ), a, c
H	E, T, (, a, c	E, ), T, a, c
D	not, H, E, T, (, a, c	D, H, E, ), T, a, c
C	C, D, not, H, E, T, (, a, c	D, H, E, ), T, a, c
B	B, C, D, not, H, E, T, (, a, c	C, D, H, E, ), T, a, c
O	if, begin, for, M, a	endif, end, O, M, E, T, ), a, c
M	a	E, T, ), a, c
L	L, O, if, begin, for, M, a	O, ;, endif, end, M, E, T, ), a, c
S	program	end.

 

Множества крайних левых  и крайних правых терминальных символов L_t(U), R_t(U) представлены в таблице 3.

 

 

 

 

 

 

 

Таблица 3

U	Lt(U)	Rt(U)
T	(, a, c	), a, c
E	-, +	-, +
H	<, >, =, <>, (, <<, >>	<, >, =, <>, ), <<, >>
D	not	not
C	and	and
B	or	or
O	if, begin, for	endif, end, do
M	a	:=
L	;	;
S	program	end.

 

Итоговые множества  крайних левых и крайних правых терминальных символов L_t(U), R_t(U) относительно всех нетерминальных символов грамматики представлены в таблице 4

 

Таблица 4

U	Lt(U)	Rt(U)
T	(, a, c	), a, c
E	-, +, (, a, c	-, +, ), a, c
H	<, >, =, <>, (, <<, >>, -, +, a, c	<, >, =, <>, ), <<, >>, -, +, a, c
D	not, <, >, =, <>, (, <<, >>, -, +, a, c	not, <, >, =, <>, ), <<, >>, -, +, a, c
C	and, not, <, >, =, <>, (, <<, >>, -, +, a, c	and, not, <, >, =, <>, ), <<, >>, -, +, a, c
B	or, and, not, <, >, =, <>, (, <<, >>, -, +, a, c	or, and, not, <, >, =, <>, ), <<, >>, -, +, a, c
O	if, begin, for, a	endif, end, do, :=, -, +, ), a, c
M	a	:=, -, +, ), a, c
L	;, if, begin, for, a	;, endif, end, do, :=, -, +, ), a, c
S	program	end.

 

 

Матрица операторного предшествования  представлена в виде таблицы, в приложении Б.

 

 

 

 

 

 

 

 

Остовная грамматика, полученная на основе исходной грамматики:

 

G' ({ program, end., if, then, else, endif, begin, end, for, downto, do, and, or, not, <<, >>, =, <, >, <>, (, ), -, +, a, c, ;, :=}, {E}, P', S)

E → program E end.

E → E | E ; E | E ;

E → if E then E else E endif | if E then E endif | begin E end | for E downto E do E | E

E → a:=E

E → E or E | E

E → E and E | E

E → not E | E

E → E < E | E > E | E = E | E <> E | (E) | E << E | E >> E

E → E – E | E + E | E

E → (E) | a | c

 

Для различия скобок, определяющих соответственно приоритет арифметических и логических операций, дополним остовную грамматику дополгительным нетерминальным символом B, который будет обозначать логические выражения.

Преобразованная остовная грамматика примет следующий вид:

 

G' ({ program, end., if, then, else, endif, begin, end, for, downto, do, and, or, not, <<, >>, =, <, >, <>, (, ), -, +, a, c, ;, :=}, {E}, P', S)

E → program E end.

E → E | E ; E | E ;

E → if B then E else E endif | if B then E endif | begin E end | for E downto E do E | E

E → a:=E

B → B or B | B

B → B and B | B

B → not B | B

B → E < E | E > E | E = E | E <> E | (B) | E << E | E >> E

E → E – E | E + E | E

E → (E) | a | c

 

Ошибки при синтаксическом аналие возникают при несоблюдений правил грамматики. Например “ if a>c else a-1 ten a+1” вызовет синтаксическую ошибку.

 

3.3 Результаты

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

Пусть на вход подается следующий  текстовый файл:

program

 

(* Это  

комментарий *  (* *

*)

begin

a:=11010111;

 

for i:=10101 downto 0 do

begin

a:=a+1;

end;  

if a>0    then a  :=11   else i:=0 endif

end ;

end.

Результаты работы синтаксического  анализатора представлены на рисунке 5.

Рисунок 5 – Результат построения дерева вывода

 

Исходный текст программы  приведен в приложении B.

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

В процессе выполнения курсовой работы была разработана программа, реализующая компилятор заданного подмножества языка Паскаль с незначительными модификациями. Для ее разработки использовалась среда Microsoft Visual Studio .NET 2003 с дополнительно интегрированной библиотекой классов Trolltech Qt v4.0.1.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список использованных источников

 

 

1. Системное программное  обеспечение: Учебник для вузов/  А.Ю. Молчанов- СПб.: Питер, 2003.- 396 с.

2. Системное программное  обеспечение. Лабораторный практикум/  А.Ю. Молчанов- СПб.: Питер, 2005.- 284 с.

3. Разработка графического  интерфейса с помощью библиотеки Qt3/ Дж. Бланшетт, М. Саммерфелд, 2003.

4. http://www.fi.ru/~mill/ Личная страничка А.Ю. Молчанова.