Технологий к реализации синтаксических анализаторов и трансляторов для трансляции простых модельных языков - rita.netnado.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Технологий к реализации синтаксических анализаторов и трансляторов для трансляции - страница №1/1

ПРИЛОЖЕНИЕ

=============




1. ПРАКТИЧЕСКАЯ РАБОТА

ПО СИНТАКСИЧЕСКОМУ АНАЛИЗУ И ТPАНСЛЯЦИИ

Задание по практической работе состоит в применении современных

технологий к реализации синтаксических анализаторов и трансляторов

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

Для поддержки курса предлагается учебное программное обеспечение, включающее

1/ универсальный интерпретатор конечных автоматов Мили,

2/ универсальный интерпретатор автоматов с магазинной памятью,

3/ транслятор-интерпретатор с языка Рефал,

4/ универсальный синтаксически управляемый транслятор МИЭМ89,

5/ интерпретатор команд специальной условной трехадресной машины.

Конечные автоматы используются для контроля правильности слов

и других лексем и свертки их в токены (промежуточные знаки) для устранения незначащих пробелов и для предобработки чисел и операндов при подготовке к трансляции,

Автоматы с магазинной памятью (МП-автоматы) используются в качестве инструмента для реализации различных вариантов синтаксического анализа в виде

· нисходящего синтаксического анализатора по методу

рекурсивного спуска,

· синтаксического анализатора простого предшествования,

· анализатора операторного старшинства,

· LR(k)-анализатора.

Для трансляции входной фразы используется синтаксически управляемый транслятор МИЭМ89. На его вход загружается таблица старшинства операций и входная фраза. Транслятор генерирует команды условной трехадресной машины в формате
КОП N1 N2 N3
где КОП - код операции, N1 и N2 – имена операндов, N3 – имя

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

и другие константы.

Интерпретатор МИЭМ90 выполняет программу, сгенерированную транслятором в режиме пошаговой демонстрации.

Для интерпретации сгенерированных транслятором МИЭМ89 команд предлагается специальный описанный на языке Си интерпретатор МИЭМ90 (автор С.Ионцев). Этот интерпретатор методически документирован и может служить учебным пособием по разработке трансляторов-интерпретаторов.

Чтобы воспользоваться им, достаточно вставить конкретные

и н т е р п р е т и р у ю щ и е п р о ц е д у р ы

(в виде простых функций на Си).

ПРИМЕР ВЫПОЛЕНИЯ ЗАДАНИЯ

Вариант задания: язык арифметических выражений.

Типовая фраза:
aa92 + ( (dd1) + 2 )+ ( 66) +a+ab
Выполненное задание должно быть оформлено в виде комплекса программ, позволяющего поэтапно отслеживать процесс анализа, транс-

ляции и интерпретации любых фраз входного языка в демонстрационном режиме под управлением bat-файла.



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

на конечном автомате:


S01 -> S01;

S01A -> S02n; Метасимвол A представляет букву

S02A -> S02;

S02 -> S03;

S03 -> S03;

S03) -> S02);

S03+ -> S01+;

S01( -> S01(;

S02) -> S02);

S02Z -> S02; Метасимвол Z представляет цифру

S02+ -> S01+;

S02# -> Успех!


Здесь А обозначает любую букву, Z означает цифру,

а знак -> означает стрелку. Фраза ограничивается справа символом #
Результат работы конечного автомата

n+((n)+n)+(n)+n+n Успех!



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

КС-грамматика:


@ → @+A @ → A A → n A → (@)
Задание предусматривает построение МП-анализаторов для

рекурсивного спуска, простого предшествования и LR(k)-анализа.

Вызывается универсальный интерпретатор МП-автоматов. Команды

МП-автомата заносятся в файл pd.pgm Анализируемая фраза

находится в файле pd.in

Анализ простого предшествования символов

Алгоритм Флойда приводит к лево- и правовыдимым множествам


L(A) = {n, ( } R(A) = {n, )} L(@)={@, A, n, ( } R(@)={n, ), A}
Схемы Флойда для пар @+ +A (@ @)

дают обобщенные отношения простого предшествования

R(@)>+ +)

Строим МП-анализатор простого предшествования

(волна означает стрелку):

Первый символ:

S1n ~ S2 S1( ~ (S2

Перенос:


@S2+ ~ @+S2 +S2A ~ +AS2 (S2@ ~ S2(@

@S2) ~ @)S2 + S2( ~ +(S2 (S2@ ~ (@S2

(S2A ~ (AS2 S2n ~ (nS2 (S2( ~ ((S2

Переход:

nS2+ ~ nS3+ )S2+ ~ )S3+ AS2+ ~ AS3+

nS2) ~ nS3) )S2) ~ )S3) AS2) ~ AS3)

Свертка:

@+aS3 ~ @S2 (@)S3 ~ AS2

Концовка:

[@S2] ~ Success [@1] ~ Error

Интерпретатор команд МП-автомата требует заключения входной фразы в квадратные скобки: [S1 <фраза> ] Эта подготовка выполняется

на соответствующей модификации лексического препроцессора.

Синтаксический анализатор обрабатывает фразу [ [S1n+((n)+n)+(n)+n+n]

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

[S2+((n)+n)+(n)+n+n]

[S1((n)+n)+(n)+n+n]

[(S1(n)+n)+(n)+n+n]

[((S1n)+n)+(n)+n+n]

[((S2)+n)+(n)+n+n]

[(S2+n)+(n)+n+n]

[(S1n)+(n)+n+n]

[(S2)+(n)+n+n]

[S2+(n)+n+n]

[S1(n)+n+n]

[(S1n)+n+n]

[(S2)+n+n]

[S2+n+n]

[S1n+n]


[S2+n]

[S1n]


[S2]

Success


Лексическая подготовка трансляции
Для трансляции нужна исходная ( а не свернутая) входная фраза.

Задачи лексической подготовки:

(1) устранить незначащие пробелы;

(2) выполнить разметку входной фразы: сохранить значения

операндов, выделяя их квадратными скобками.

Лексическая подготовка выполняется на конечном автомате.

Результат лексической подготовки:

[aa92]+(([dd1])+[2])+([66])+[a]+[a6])


Трансляция

Трансляция производится на синтаксически управляемом трансляторе МИЭМ89. Транслятор выполняет анализ старшинства операций совместно с

генерацией кодов условной трехадресной машины. На входе транслятора

– таблица старшинства, приведенная выше (в файле table.dat)

– и (контрольная) фраза для трансляции (в файле trans.dat)
#[aa92]+(([dd1])+[d2])+([a6a66])+[a]+[a6]#
Результат трансляции (выдача транслятора МИЭМ89):
Syntactically Controlled Study Compilier МИЭМ-89

N of terminals was 3

Majoirity Table:
+ ( )

+ > < >


( < =

) > >
In-phrase was:

#[aa92]+(([dd1])+[d2])+([a6a66])+[a]+[a6]#

Compilation was S u c c e s s f u l

List of operands:

[dd1] [2] [var1] [var2] [var3] [aa92] [66] [var5] [var4] [a] [var6]

[a6] [var7] [var8]

The program compiled is:


No.1 () [dd1] [var1]

No.2 + [var1] [2] [var2]

No.3 () [var2] [var3]

No.4 + [aa92] [var3] [var4]

No.5 () [66] [var5]

No.6 + [var4] [var5] [var6]

No.7 + [var6] [a] [var7]

No.8 + [var7] [a6] [var8]

Интерпретация этих команд выполняется на интерпретаторе

МИЭМ90. Текст интерпретатора написан на Си и рассчитан на любые

программы, которые формирует транслятор МИЭМ89. Этот текст

модифицируется путем вставления интерпретирующих процедур для

предложенного языка, в частности, для вычисления суммы двух чисел и переноса значений при раскрытии скобок. Интерпретатор запрашивает значения переменных и выполняет вычисления.

. 2. ИНТЕРПРЕТАТОР МИЭМ90

Интерпретатор загружается интерпретирующими процедурами для

конкретного языка. В качестве примера рассмотрим язык векторных выражений. Типовая фраза этого языка:


in(x);x=a+(b+c); out(x)
Текст интерпретатора на Си
\#include \

\#include \

\#include \

\#include \

\#include \

typedef struct

\{

int K1,K2;



\} mytype;

\#define MAXNAMELEN 15 /* Максимальная длина имени переменной*/

\#define MAXMEMORY 100 /* Максимальное количество переменных*/

struct memory-element /* Формат Элемента памяти*/

\{

char name[MAXNAMELEN+1]; /* Название элемента памяти*/



mytype value; /* Значение элемента памяти*/

\} ;


/*задействован только один тип данных*/

/*{\bf в случае необходимости - добавить!} */

struct memory-element mem[MAXMEMORY]; /* Память интерпретатора*/

/* Иллюстрация к представлению памяти интерпретатора*/

/* i mem[i].name mem[i].value*/

/* 0 "[aaaa]" 12*/

/* 1 "[var1]" 0*/

/* 2 "[bb13]" 43*/

/* 3 "[var2]" 0*/

/* .................................*/

int memory-size; /* содержит число используемых переменных*/

mytype default-value={0,0}; /* Начальное значение для переменной*/

/* {\bf Прототипы функций (пример) - заменить их! } */

mytype plus(mytype op1, mytype op2); /* Сложение +*/

mytype move(mytype op1); /* Пересылка ()*/

mytype equal(mytype op2); /* Присваивание =*/

mytype semicolon(mytype op2); /* Присваивание =*/

mytype in(mytype op1);

mytype out(mytype op1);

mytype getvalue(char *name); /* Вернуть значение переменной name*/

void setvalue(char *name, mytype value);

/* Присвоить переменной name значение value*/

void initvalue(int i); /* Начальное значение для переменной*/

char kop[MAXNAMELEN+1], /* Код операции*/

nop1[MAXNAMELEN+3], /* имя операнда 1*/

nop2[MAXNAMELEN+3], /* имя операнда 2*/

nop3[MAXNAMELEN+3]; /* имя операнда 3*/

{\bf Головной модуль }

int main(void)

\{

\#define MAXLINE 132



FILE *f;

char line[MAXLINE+1]; /* Строка из файла trans.dat*/

mytype op1, op2, op3; /* Значения операндов 1, 2, 3*/

int i;


/* Открываем файл - результат работы генератора кода*/

if ( (f=fopen("trans.res","r")) == NULL )

\{

printf("Файл trans.res не найден\ n");



return 1;

\}

/* Читаем файл до списка операндов*/



do \{

fgets(line,MAXLINE,f);

printf("%s",line);

\}

while ( strncmp(line,"List of operands:",17) != 0 );



/* Инициализируем память интерпретатора*/

for (memory-size=0;;memory-size++)

\{

fgets(line,MAXLINE,f);



if (line[0] != '[') break; /* Список переменных закончился*/

sscanf(line,"\%s",mem[memory-size].name);

initvalue(memory-size);

\}

/* Пропускаем две строки*/



fgets(line,MAXLINE,f);

fgets(line,MAXLINE,f);

printf("Выполнение начинается...\ n");

/* Выбираем псевдокоманды одна за другой и интерпретируем их*/

do \{

fgets(line,MAXLINE,f);



if (line[0] == '=') break;

/* Код операции*/

sscanf(\&line[8],"\%s",kop);

printf("\%-7s ",kop);

/* Первый операнд есть всегда*/

sscanf(\&line[20],"\%s",nop1);

op1 = getvalue(nop1);

printf("\%7s=\%i,\%i ",nop1,op1.K1,op1.K2);

/* Второй операнд может отсутствовать*/

if (line[37] != ' ')

\{

sscanf(\&line[37],"\%s",nop2);



op2=getvalue(nop2);

printf("\%7s=\%i,\%i ",nop2,op2.K1,op2.K2);

\}

else


printf(" ");

/* Третий операнд есть всегда*/

sscanf(\&line[60],"\%s",nop3);

printf("\%7s=",nop3);

/* Выполнение операции*/

if (strcmp(kop,"+")==0) op3 = plus(op1,op2);

else

if (strcmp(kop,"()")==0) op3 = move(op1);



else

if (strcmp(kop,"=")==0) op3=equal(op2);

else

if (strcmp(kop,";")==0) op3=semicolon(op2);



else

if (strcmp(kop,"I()")==0) op3=in(op1);

else

if (strcmp(kop,"A()")==0) op3=out(op1);



else

\{

printf("/n Не знаю пока операции '%s'/n",kop);



printf("Готово! Нажмите Enter...");exit(3);

\}

/* Запись результата*/



setvalue(nop3,op3);

printf("\%i,\%i\ n",op3.K1,op3.K2);

\}

while ( !feof(f) );



fclose(f);

printf("Все сделано. Нажмите Enter...");

getch();return 0;

\}

/* {\bf Тела функций (пример) - заменить!} */



mytype plus(mytype op1, mytype op2)

\{

mytype pr;



pr.K1=op1.K1+op2.K1;

pr.K2=op1.K2+op2.K2;

return pr;

\}

mytype equal(mytype op2)



\{

setvalue(nop1,op2);

return (mytype)(op2);

\}

mytype move(mytype op1)



\{

return op1;

\}

mytype semicolon(mytype op2)



\{

return op2;

\}

mype in(mytype op1)



\{

printf("\ n Введите значение вектора ");

scanf("\%i \%i",\&op1.K1,\&op1.K2);

setvalue(nop1,op1);

return op1;

\}

mytype out(mytype op1)



\{ \}

mytype getvalue(char *name)

\{

int i;


for (i=0; i< memory-size; i++)

if (strcmp(mem[i].name,name)==0) return mem[i].value;

printf("nПеременная \%s не была размешена в памяти!n",name);

return default-value;

\}

void setvalue(char *name, mytype value)



\{

int i;


for (i=0; i< memory-size; i++)

if (strcmp(mem[i].name,name)==0) { mem[i].value = value; return; }

printf("\ nПеременная \%s не была размещена в памяти!\ n",name);

printf("Все! Нажмите Enter...");

getch(); exit(2);

\}


void initvalue(int i)

\{

int l;



char word[16];

FILE *ff;

char st[MAXNAMELEN];

l=strlen(mem[i].name);

if ( strncmp(mem[i].name,"[var",4) == 0 ) {return;};

if (isdigit(mem[i].name[1])!=0)

\{

memcpy(st,\&mem[i].name[1],l-2);



st[l-2]='\ x0';

mem[i].value.K1=atof(st);

mem[i].value.K2=0;

\};


\}

{\bf Конец программы на Си}


Практическая работа предусматривает ознакомление студентов

с предложенным универсальным интерпретатором МИЭМ90 и его

модификацию в соответствии с заданием. Модификация состоит в

следующем.


  1. Вводятся типы переменных, соответствующих заданию.

  1. Вводятся спецификации процедур.

  1. Программируются тела этих процедур.

  1. Транслируется и отлаживается модифицированный текст на Си.

Затем модифицированный интерпретатор используется

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

индивидуальным заданиям. .



3. ПРИМЕРЫ ЯЗЫКОВ ДЛЯ ИНДИВИДУАЛЬНЫХ ЗАДАНИЙ

Обозначения: T - алфавит языка

digits – цифры letters - буквы

Общее правило: слова и числа разделяются знаками или пробелами

(одним или более); пробелы внутри слов и чисел не допускаются.

1. Язык целочисленных выражений

Т::= {digits + - ! * ** ( ) }

Факториал ! Степень **

Показатели степеней уже степеней не содержат и имеют формат

<терм> ** <число без знака?

Типовая фраза:

7 ** (2) + ( (15 - 12)! +31) *2
2. Язык логических переменных и условий

T:: = {letters + * < & Not ( ) }

Not отделяется пробелом либо скобкой.

Типовая фраза:

(ab < (a + cc) *bb ) & Not ( p & Not qq)
3. Язык матричных выражений

T ::= { digits letters + * ( ) }

Идентификаторы - матрицы,

числа целые, знак + и для чисел и для матриц,

умножение на скаляры слева по умолчанию.

Типовая фраза:

2 a1* (b11 +02 c*c)+ (3+ (77)) a2a
4. Язык полиномов от x

T::= { x + up ( ) letters digits }

Переменные – буквы, n означает целую переменную,

степени "up" только целые и не содержат других скобок.

Типовая фраза:

ax up 3 + (a+1)4 x up( 2)+2n x up ( n+2)


5. Язык векторных выражений с коэффициентами

T::={ + . * ( ) [ ] letters digits}

Слова – векторы, числа - десятичные, числовые множители слева, коэффициенты без знака умножения

Знак + один и тот же для чисел и для векторов.

() - для чисел [] - для векторов.

Типовая фраза:

1.2 ad + [(2 + 5.0)*weight + [(11)* ccc] ]

6. Язык операций над векторами

T ::= {digits letters + * = ; ( )}

in() out() - операторы обмена (векторные),

векторные переменные – слова начинаются на букву v

числовые множители (из чисел и переменных) всегда слева.

Типовая фраза:

in (v1); vu=(a+bb)* (2 *vaa);out( 2 *vu+ v1);

7. Язык матричных выражений

T ::={letters digits + * ( ) }

Идентификаторы – матрицы, числа целые, знак + и для чисел и для матриц,

знак умножения чисел * умножение матриц на скаляры - слева по умолчанию.

Типовая фраза: 2 a1* (b11 +02 c*c)+ (3+ (1 ))* 2a2a
8. Язык скобочных структур и функций

T ::= {letters digits , ( ) + }

Примитивы – идентификаторы, Узлы – структуры в скобках либо (поименованные) - идентификаторы.

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

Типовая фраза: (bb(4+ 4) , (x,y), big(f(3)+1) (aa, f(3+ (x+1)) ,a )
Задание состоит в последовательной разработке лексических

препроцессоров, синтаксических анализаторов модельного

языка, его трансляции и интерпретации на предложенном

учебном программном обеспечении. Все эти этапы разработки

сшиваются вместе в .bat файле, обеспечивающем работу в

демонстрационном режиме.



СПИСОК ЛИТЕРАТУРЫ И ССЫЛКИ

==================================

Основная литература


  1. В.И.Сердобольский. Формальные языки. Синтаксический

анализ и трансляция. МГИЭМ, М., 2008.
2. М.Гросс, А.Лантен. Теория формальных грамматик.

М.: Мир, 1971.


3. Дж.Рейуорд-Смит. Теория формальных языков.

М.: Мир, 1986.


4. Р.Хантер. Проектирование и конструирование компиляторов.

М.: Финансы и статистика, 1984.


5. А.В.Климов, С.А.Романенко. Система программирования РЕФАЛ-2

для ЕС ЭВМ. Препринт ИПМ АН СССР, 1987.

6. Р.Ф.Гурин и С.А.Романенко. Язык программирования Рефал плюс.

М.: "Интертех", 1991.

Дополнительная литература

7. J.Earlay, Generating a recognizer for a BNF grammar,

Дж. Эрли, Эффективный алгоритм анализа контекстно-свободных

языков, в кн. Языки и автоматы, изд-во М.:Мир, 1975, стр. 47

8. A.V.Aho, J.D.Ullman, The Theory of Parsing, Translation, and

Compiling. А.В.Ахо, Дж.Ульман, Теория синтаксического анализа,

перевода и компиляции. М.: Мир, 1978

Том 1. Синтаксический анализ

Том 2. Компиляция
9. Ф.Льюис, Д. Розенкранц, Р. Стириз. Теоретические основы

построения компиляторов. М., 1979.


10. Report on the Algorithmic Language Algol-60.

by J.Green, C.Katz, et al Сообщение об алгоритмическом языке Алгол-60.

Журнал вычислительной и математической физики, 1961, 2, 308-342.

11. Donald Knuth, The Art of Computer Programming,

Д. Кнут, Искусство программирования

М.: Мир, 1976

Том 1, Основные алгоритмы.

Том 2, Получисленные алгоритмы.

Том 3, Сортировка и поиск.

Том 4, Комбинаторные алгоритмы.

Том 5, Синтаксические алгоритмы.

Том 6, Теория языков.

Том 7, Компиляторы.

12. D.Gris, Compiler gor Digital Computers

Д.Грис, Конструирование компиляторов для цифровых

вычислительных машин. М.: Мир, 1975.

13. C.К.Клини. Введение в метаматематику. АН СССР, 1957.
РЕСУРСЫ ИНТЕРНЕТ
14. В.И.Сердобольский. Формальные языки. Синтаксический

анализ и трансляция.

Адрес: http://serd-miem.narod/ru

15. Обзор по технологии построения компиляторов.

Адрес: ukman.narod.ru/book_overview.html
16. Т.М.Волосатова. Формальные языки, грамматики и автоматы.

Для технических вузов. Электронный курс.

Адрес: http://www.techno.edu.ru/db/msg/16769.html

17. В.А.Серебряков. Лекции по конструированию компиляторов.

Москва, МГУ, 1993. Глава 5. Элементы теории перевода.

Адреса: http://www.codenet.ru/progr/alg/cons/006.php

http://www.argeal.ru/arvhieve/cs/cc.html

18. Рефал. Статья в энциклопедии.

Адрес: http://ru.wikipedia.org/wiki/РЕФАЛ

19. Алгоритмический язык Рефал. Описание, реализация, версии.



Адрес: refal.msu.su

20. Рефал. Обзор и ссылки. Адрес: www.refal.net