Разработка программы-компилятора

Синтаксический анализ производится методом рекурсивного спуска.

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

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

Множество правил грамматики реализуемого языка, записанных в форме Бэкуса-Наура, имеет следующий вид:

1. <программа>>program<имя программы>;

var<список описаний>

begin<список операторов>end.

2. <имя программы>>ИМЯ

3. <список описаний>><описание>; {<описание>; }

4. <описание>><список имён>: <тип>

5. <тип>>real

6. <список имён>>ИМЯ{, ИМЯ}

7. <список операторов>><оператор>; {<оператор>; }

8. <оператор>><присваивание> | <цикл>

9. <присваивание>>ИМЯ: =<выражение>

10. <выражение>><простое выражение>{ (=, <, <>, >, >=, <=) <простое выражение>}

11. <простое выражение>><терм>+<терм>

12. <терм>><множитель>*<множитель>

13. <множитель>>ИМЯ | КОНСТАНТА | <простое выражение>

14. <цикл>>repeat<тело цикла>until<выражение>

15. <тело цикла>><оператор>|<составной оператор>

16. <составной оператор>>begin<список операторов>end

В грамматике, помимо общепринятых, используются следующие терминальные символы: ИМЯ - идентификатор; КОНСТАНТА - 16-ричная или римская константа.

3.3.11 Функция Lex_Repeat_Until

1. Методические указания к лабораторным работам по СПО.

2. Курс лекций по дисциплине "Системное программное обеспечение".

3. А.Ю. Молчанов "Системное программное обеспечение", СПб, 2003 г.

4. Ю.Г. Карпов "Теория автоматов", СПб, 2002 г.

5. В.В. Фаронов“Delphi. Программирование на языке высокого уровня", Питер, 2004 г.

Приложение: текст программы

unit lex;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, Menus, StdCtrls, Grids;

type

TVyh = Record // Тип таблицы кодов лексем

nomer: integer; // Номер

typ: char; // Тип лексемы

Num: integer; // Номер в таблице

Lex: String; // Лексема

numstr: integer; // Номер строки

end;

TTerm = Record // тип таблицы терминальных символов

nomer: integer; // номер

Lex: String; // Лексема

razd: byte; // Разделитель?

oper: byte; // Операция?

slug: byte; // Служебное слово?

Left: integer; // Левая ветвь дерева.

Right: integer; // Правая ветвь дерева.

Way: string;

end;

TConst = Record // Тип таблицы констант

nomer: integer; // Номер

value: string; // Само значение лексемы.

Typ: string; // Тип лексемы

Width: string; // Ширина константы

Val10: string; // 10-тичный формат константы

Left: integer; // Левая ветвь дерева.

Right: integer; // Правая ветвь дерева.

Way: string;

end;

TId = Record // таблица имен

nomer: integer; // номер лексемы

lex: string; // лексема

ssylka: integer; // ссылка на элемент цепочки

end;

TForm1 = class (TForm)

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

N5: TMenuItem;

OpenDialog1: TOpenDialog;

Memo1: TMemo;

N6: TMenuItem;

StringGrid1: TStringGrid;

Label1: TLabel;

StringGrid2: TStringGrid;

Label2: TLabel;

StringGrid3: TStringGrid;

StringGrid4: TStringGrid;

Label3: TLabel;

Label4: TLabel;

Memo2: TMemo;

Label5: TLabel;

procedure N2Click (Sender: TObject);

procedure N3Click (Sender: TObject);

procedure N5Click (Sender: TObject);

procedure vyvod;

procedure Err_lex;

procedure Syntax;

procedure Err_Synt (text: string; l: integer);

function Lex_Progr: boolean;

function Lex_Prog_Name: boolean;

function Lex_Descr_List: boolean;

function Lex_descr: boolean;

function Lex_name_list: boolean;

function Lex_type: boolean;

function Lex_oper_list: boolean;

function Lex_oper: boolean;

function Lex_assign: boolean;

function Lex_Exp: boolean;

function Lex_simple_Exp: boolean;

function Lex_Term: boolean;

function Lex_mnozh: boolean;

function Lex_repeat_until: boolean;

function Lex_body: boolean;

procedure N6Click (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

const

MaxNum=100; // Максимальное число лексем

deleter= ['. ',' ',' (',') ','{','}',',','<','>','"','? ','! ','*','&','^', {'%','$',}' [','] ',': ','; ','=','-','+','/', '\',''''] ; // разделители лексем

words: Array [1. .14] of string [7] = ('program','var','then','begin','for','to','do','if','end','repeat','until','real','integer', 'else'); // Массив служебных слов

razdel: Array [1. .8] of char= (',','; ',': ',' (',') ',' [','] ','. '); // массив разделителей

operacii: Array [1. .11] of string [2] = (': =','>=','<=','<>','+','-','/','*','>','<','='); // массив операций

cifra= ['0'. '9'] ; // цифры

bukva= ['A'. 'F'] ;

var

Form1: TForm1;

FA,FName: textfile;

SA: array [1. .100] of string;

SS,Name,Constant: string;

Dlina: integer;

Code_tab: array [1. MaxNum] of TVyh; // Таблица кодов лексем

Term_tab: array [1. MaxNum] of TTerm; // Таблица терминальныз символов

Id_tab: array [1. MaxNum] of TId; // Таблица идентификаторов

Const_tab: array [1. .50] of TConst; // Таблица констант

Lexem,s,typel: string; // Лексема, Текст ошибки, Строка программы, Тип лексемы

i,j,k,l,m,n,y,String_counter,constyes,termyes,hesh, // счетчики циклов и строк

NumLex,{Число лексем}NumId,{Число идентификаторов}NumTerm,{Число терминальных символов}NumConst,{Число различных констант}

NumErr{Число ошибочных лексем}: integer;

Error,Found,Flag,Scobka: boolean; // Флаги

str16: string;

k1,kod: integer;

implementation

uses lex2;

{$R *. dfm}

procedure TForm1. N2Click (Sender: TObject);

var i: integer;

begin

OpenDialog1. Filter: ='*. txt';

if opendialog1. Execute and fileExists (openDialog1. FileName)

then

begin

Assignfile (FA, OpenDialog1. FileName);

Reset (FA);

Memo1. Lines. clear;

i: =1;

while not EOF (FA) do

begin

readln (Fa,SA [i]);

Memo1. Lines. Add (SA [i]);

i: =i+1;

end;

Closefile (FA);

end;

end;

// процедура перевода констант в десятичную форму

procedure perevod (SS: string; var Str16: string);

var ch3,ch4,ch, i: integer;

zn: string;

begin

ch: =0; // для римских констант

if (SS [2] ='X') or (SS [2] ='V') or (SS [2] ='I') then

begin

zn: =SS [1] ;

delete (SS,1,1);

while Length (SS) <>0 do

begin

if SS [1] ='X' then begin ch: =ch+10; delete (SS,1,1); end

else begin

if SS [1] ='V'then begin ch: =ch+5; delete (SS,1,1); end

else begin

if ( (SS [1] ='I') and (SS [2] ='I')) or ( (SS [1] ='I') and (SS [2] ='')) then begin ch: =ch+1; delete (SS,1,1); end

else begin

if (SS [1] ='I') and (SS [2] ='X') then begin ch: =ch+9; delete (SS,1,2); end

else begin

if (SS [1] ='I') and (SS [2] ='V') then begin ch: =ch+4; delete (SS,1,2); end;

end; end; end; end; end;

str16: =zn+IntToStr (ch);

exit;

end;

// для 16-рич. констант

If SS [3] in ['0'. '9']

then

ch3: =StrToInt (SS [3]) *16

else

if SS [3] in ['A'. 'F']

then

begin

ch3: =ord (SS [3]);

case ch3 of

65: ch3: =10*16;

66: ch3: =11*16;

67: ch3: =12*16;

68: ch3: =13*16;

69: ch3: =14*16;

70: ch3: =15*16;

end;

end;

If SS [4] in ['0'. '9']

then

ch4: =StrToInt (SS [4])

else

if SS [4] in ['A'. 'F']

then

begin

ch4: =ord (SS [4]);

case ch4 of

65: ch4: =10;

66: ch4: =11;

67: ch4: =12;

68: ch4: =13;

69: ch4: =14;

70: ch4: =15;

end;

end;

ch: =ch3+ch4;

If (SS [3] ='0') and (SS [4] ='0')

then Str16: =IntToStr (ch)

else Str16: =SS [2] +IntToStr (ch);

end;

procedure TForm1. N3Click (Sender: TObject);

begin

close;

end;

function Select_Lex (S: string; {исх. строка} var Rez: string; {лексема}N: integer {текущая позиция}): integer;

label 1;

begin // функция выбора слов из строки

k: = Length (S);

Rez: ='';

i: =N; // точка продолжения в строке

while (S [i] =' ') and (i<= k) do i: =i+1; // пропуск ' '

while not (S [i] in deleter) and (i<= k) do // накопление лексемы

begin

if s [i] ='$' then

begin

Rez: =s [i] +s [i+1] ;

i: =i+2;

end

else begin

1: Rez: =Rez+s [i] ;

i: =i+1;

end;

end;

if Rez='' then

begin

if (s [i] =': ') then

begin

if (s [i+1] ='=') then // в случае операции из двух символов

begin

Rez: =s [i] +s [i+1] ;

Select_Lex: =i+2;

end

else

begin

Rez: =s [i] ;

Select_Lex: =i+1;

end;

end else

begin

if ( (s [i] ='+') or (s [i] ='-')) and (s [i-1] =' (')

then begin

Rez: =s [i] +s [i+1] ;

i: =i+2;

goto 1;

end

else begin

Rez: =s [i] ;

Select_Lex: =i+1;

end; end;

end else Select_Lex: =i;

end;

procedure Add_Const (Curr_term: integer; str_lex: string); // Процедура добавления идентификаторов в дерево

begin

if NumConst=1 then // Если корень дерева еще не создан, то создаем его.

begin

perevod (str_lex,str16);

Const_tab [NumConst]. value: =str_lex;

Const_tab [NumConst]. nomer: =NumConst;

Const_tab [NumConst]. Val10: =str16;

Const_tab [NumConst]. Left: =0;

Const_tab [NumConst]. Right: =0;

Const_tab [NumConst]. Way: ='V';

Exit;

end;

if (CompareStr (Const_tab [Curr_term]. value,str_lex) >0) then // Если значение текущего узла дерева больше добавляемого

if Const_tab [Curr_term]. Left=0 then // если у этого элемента дерева нет левого указателя, то

begin

perevod (str_lex,str16);

Const_tab [Curr_term]. Left: =NumConst; // Создание левого элемента.

Const_tab [NumConst]. value: =str_lex;

Const_tab [NumConst]. nomer: =NumConst;

Const_tab [NumConst]. Val10: =str16;

Const_tab [NumConst]. Left: =0;

Const_tab [NumConst]. Right: =0;

Const_tab [NumConst]. Way: =Const_tab [NumConst]. Way+'L';

end else begin

Const_tab [NumConst]. Way: =Const_tab [NumConst]. Way+'L';

Add_Const (Const_tab [Curr_term]. Left,str_lex); // Если левый указатель существует, то вызываем уже функцию для левого указателя.

end;

if (CompareStr (Const_tab [Curr_term]. value,str_lex) <0) then // если у этого элемента дерева нет правого указателя, то

if Const_tab [Curr_term]. Right=0 then

begin

perevod (str_lex,str16);

Const_tab [Curr_term]. Right: =NumConst; // Создаем правый элемент.

Const_tab [NumConst]. value: =str_lex;

Const_tab [NumConst]. nomer: =NumConst;

Const_tab [NumConst]. Val10: =str16;

Const_tab [NumConst]. Left: =0;

Const_tab [NumConst]. Right: =0;

Const_tab [NumConst]. Way: =Const_tab [NumConst]. Way+'R';

end else begin

Const_tab [NumConst]. Way: =Const_tab [NumConst]. Way+'R';

Add_Const (Const_tab [Curr_term]. Right,str_lex); // Если правый указатель существует, то вызываем уже функцию для правого указателя.

end;

end;

procedure Add_Term (Curr_term: integer; str_lex: string); // Процедура добавления идентификаторов в дерево

begin

if NumTerm=1 then // Если корень дерева еще не создан, то создаем его.

begin

Term_tab [NumTerm]. lex: =str_lex;

Term_tab [NumTerm]. nomer: =NumTerm;

Term_tab [NumTerm]. Left: =0;

Term_tab [NumTerm]. Right: =0;

Term_tab [NumTerm]. Way: ='V';

Exit;

end;

if (CompareStr (Term_tab [Curr_term]. lex,str_lex) >0) then // Если значение текущего узла дерева больше добавляемого

if Term_tab [Curr_term]. Left=0 then // если у этого элемента дерева нет левого указателя, то

begin

Term_tab [Curr_term]. Left: =NumTerm; // Создание левого элемента.

Term_tab [NumTerm]. lex: =str_lex;

Страницы: 1, 2, 3