Программирование численных методов решение нелинейных уравнений итерационным методом

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

 

3.1 Исходные данные

 

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

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

 

3.2 Принципы работы лексического  анализатора

 

Лексический анализатор имеет дело с различного рода константами и идентификаторами (к последним относятся и ключевые слова). Язык констант и идентификаторов в большинстве случаев является регулярным - то есть, может быть описан с помощью регулярных (праволинейных или леволинейных) грамматик. Распознавателями для регулярных языков являются конечные автоматы. Существуют правила, с помощью которых для любой регулярной грамматики может быть построен недетерминированный конечный автомат, распознающий цепочки языка, заданного этой грамматикой.

Работа автомата выполняется по тактам. На каждом очередном такте i автомат, находясь в некотором состоянии qiÎQ, считывает очередной  символ wÎS из входной цепочки символов и изменяет свое состояние на qi+1=d(qi,w), после чего указатель в цепочке входных символов передвигается на следующий символ и начинается такт i+1. Так продолжается до тех пор, пока цепочка входных символов не закончится. Конец цепочки символов часто помечают особым символом ^. Считается также, что перед тактом 1 автомат находится в начальном состоянии q0.

Графически автомат отображается нагруженным однонаправленным графом, в котором вершины представляют состояния, дуги отображают переходы  из одного состояния в другое, а символы нагрузки (пометки) дуг соответствуют функции перехода. Если функция перехода предусматривает переход из состояния q в q’ по нескольким символам, то между ними строится одна дуга, которая помечается всеми символами, по которым происходит переход из q в q’.

 

3.3 Схема распознавателя

 

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

Начальное и конечное состояния при нормальной работе лексического анализатора совпадают (на рисунке состояние "q"). В случае ошибочной входной цепочки автомат попадает в состояние ошибки ERROR. При этом работа автомата останавливается.

Кроме того, типичными для автомата являются состояния ID (переменная) и CONSTANT (константа). Остальные состояния автомата определяются допустимыми для компилятора исходного языка лексемами.

Каждый переход в конечное состояние "q" сообщает о конце текущей входной цепочки. В этом случае производится анализ распознанной цепочки и перезапуск автомата для очередной входной цепочки символов. Заметим также, что возможна повторная обработка некоторых символов входной цепочки символов. Это необходимо в тех случаях, когда символ, приведший к переходу автомата в конечное состояние, является началом следующей цепочки символов.

 

 

3.3 Результаты

 

Программная реализация лексического анализатора представлена в виде модулей LexFSM и LexAnalyser. LexFSM – отражает работу автомата, распознающего входные цепочки символов. LexAnalyser подготавливает текст входного файла для отправки его символов модулю LexFSM по запросам последнего. Он игнорирует незначащие символы входного текста (символы табуляции, возврата каретки и т.д.). Когда LexFSM переходит в одно из конечных состояний, он передает управление модулю LexAnalyser. Тот, в свою очередь, выводит результаты работы на экран и сигнализирует в случае ошибки о строке, в которой произошла ошибка. Кроме того, если LexFSM переходит в конечное состояние "q" и таким образом распознает входную цепочку символов, он передает полученную лексему с информацией о ней модулю LexAnalyser, а тот добавляет ее в свой список лексем. По завершении обработки файла модуль LexAnalyser посылает список лексем графическому модулю LexTab, который отображает результирующий список лексем в виде таблицы.

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

Рассмотрим ниже пример обработки текстового файла:

program

begin

begine:=1;

a:=5;

repeat

if a>3 then a:=3

else i:=0

endif

until i=0

end;

end.

Результаты работы лексического анализатора кратко

представлены в таблице 1.

Таблица 1

Лексема	Тип лексемы	Номер идентификатора в таблице идентификаторов
program	Ключевое слово 'program'
begin	Ключевое слово 'begin'
begine	Переменная	1
:=	Оператор присваивания ':='
5	Константа
;	Разделитель
a	Переменная	2
:=	Оператор присваивания ':='
5	Константа
;	Разделитель
repeat	Ключевое слово 'repeat'
if	Ключевое слово 'if'
a	Переменная	2
>	Знак операции '>'
3	Константа
then	Ключевое слово 'then'
a	Переменная	2
:=	Оператор присваивания ':='
3	Константа

 

 

 

 

 

 

 

 

 

4 Построение дерева вывода

 

4.1 Исходные данные

 

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

 

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

 

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

G ({ program, end., if, then, else, endif, begin, end, repeat, until, and, or, not, <<, >>, =, <, >, <>, (, ), -, +, a, c, ;, :=}, {S, L, O, B, C, K, D, H, E, T}, 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 | repeat O until B | 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

 

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

 

 

 

 

 

Таблица 2

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, repeat, a	endif, E, end, B
L	L, O	O, ;
S	program	end.

 

Таблица 3

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	not, H, (, E, T, a, c	D, H, E, ), T, a, c
B	B, C	C, D, H, E, ), T, a, c
O	if, begin, repeat, a	endif, E, end, B
L	L, O, if, begin, repeat, a	O, ;, endif, E, end, B
S	program	end.

 

Множества крайних левых и крайних правых терминальных символов Lt(U), Rt(U) относительно всех нетерминальных символов грамматики и итоговые множества крайних левых и крайних правых терминальных символов Lt(U), Rt(U) относительно всех нетерминальных символов грамматики представлены соответственно в таблицах 4 и 5.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Таблица 4

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

 

Таблица 5

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, repeat, a	endif, end, :=, until, or, and, not, <, >, =, <>, ), >>, -, +, a, c
L	;, if, begin, repeat, a	;, endif, end, :=, until, or, and, not, <, >, =, <>, ), >>, -, +, a, c
S	program	end.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

G' ({ program, end., if, then, else, endif, begin, end, repeat, until, 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 | repeat E until 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 | (B) | E << E | E >> E

E → E – E | E + E | E

E → (E) | a | c

 

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

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

 

G' ({ program, end., if, then, else, endif, begin, end, repeat, until, and, or, not, <<, >>, =, <, >, <>, (, ), -, +, a, c, ;, :=}, {E, B}, 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 | repeat E until B | 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

 

 

 

 

 

 

 

 

4.3 Результаты

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

Рассмотрим работу синтаксического анализатора при обработке следующего файла:

program

 

(* Это 

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

*)

begin

c:= c - b +d;

repeat

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

until i= 0

end ;

end.

 

Графически результат построения дерева вывода представлен на рисунке 4.

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5 Генерация и оптимизация  объектного кода

 

5.1 Исходные данные

 

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