Задание к расчетно-графической работе по дисциплине

“Теория формальных языков и компиляторов”

 

Вариант N

Цель работы: практическое применение теоретических основ проектирования трансляторов с языков программирования; освоение средств автоматизации построения трансляторов; разработка элементов транслятора для учебного языка.

 

 I. Содержание работы

 

1.      Разработать описание лексики, синтаксиса и семантики заданного варианта языка. Написать простую тестовую программу (программы), содержащую все заданные элементы и конструкции языка. Вручную выполнить интерпретацию программы. Эту программу (программы) использовать впоследствии для проверки элементов разрабатываемого транслятора.

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

3.      Разработать формальную грамматику класса LL(1) или не выше, чем LALR(1), определяющую синтаксис заданного языка. Используя пакет Вебтранслаб, построить автоматную реализацию нисходящего синтаксического акцептора, проверить его работоспособность.

4.      Разработать расширение синтаксического акцептора (по собственному выбору – нисходящего или восходящего) для преобразования последовательности лексем в постфиксную запись или в абстрактное синтаксическое дерево.

5.      Оформить (в электронном виде) расчетно-пояснительную записку следующего содержания:

-        данное задание;

-        оглавление;

-        введение;

-        описание заданного варианта языка;

-        тестовая программа (программы);

-        система регулярных выражений ( п.2 ) и ее описание

-        управляющая таблица (или ГСП) лексического акцептора, ее описание.

-        формальная грамматика ( п. 3 ) и ее описание;

-        управляющая таблица синтаксического акцептора, ее описание.

-        примеры результатов работы акцепторов с тестовыми примерами; объяснение и анализ этих результатов;

-        алгоритм расширения синтаксического акцептора для формирования ПФЗ, его описание, примеры результатов преобразования с пояснениями;

-        заключение.

 

II. Варианты заданий на разработку учебного языка,.

Лексика, синтаксис и семантика учебного языка близки к языкам типа C и С++. Любые конструкции, не оговоренные явно в задании, можно заимствовать из этих языков или определять самостоятельно.

 

Структура программы на учебном языке:

         <Последовательность операторов описания данных или ничего>

         <Имя функции>(<список аргументов>) {

                  <Последовательность операторов описания данных или ничего>

                  <Последовательность выполняемых операторов>

            }

 

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

 

Последовательность операторов описания данных состоит из одной или нескольких записей вида:

<описатель> <список идентификаторов> ;

где

- <описатель> - ключевое слово согласно п. II.2.

- <список идентификаторов> - один или несколько идентификаторов, разделенных запятыми.

Имя функции - идентификатор.

Последовательность выполняемых операторов - один или несколько следующих в произвольном порядке операторов присваивания (II.3), условных операторов (II.4), операторов цикла (II.5) или блоков (блок - последовательность операторов, заключенная в ограничители блока, например - фигурные скобки).

 

Обозначения, используемые ниже:

[...]             – необязательная часть

              – часть, повторяющаяся произвольное количество раз

< >             – описание конструкции:

<Б>|<Ц>|<пБ>|<пЦ>|<пБЦ> – одна буква | одна цифра | непустая последовательность букв | непустая последовательность цифр | возможно пустая последовательность букв и/или цифр

<И>                                         Идентификатор

<К>                                         – Константа

<В>                                         произвольное Выражение

<ЛВ>                                       – Логическое Выражение

<О>                                         – одиночный Оператор

<ОБ>                                      – Оператор или Блок)

Расшифровка цифр варианта задания:

II.1      Идентификаторы и константы

Вариант:

1

2

3

4

Идентификаторы

<пБ><пЦ>

<Б><Ц><пБ>

$<пБЦ>

<Б><пЦ>_

Константы

целые, в том числе 16-ричные

вещественные

символьные

целые, в том числе 4-ричные

вещественные

символьные

целые, в том числе двоичные

вещественные

символьные

целые, в том числе 8-ричные

вещественные

символьные

 

II.2      Объявления примитивных типов (целое, вещественное, символьное, булево):

Вариант:

1

2

3

4

 

number

real

symbol

integer

single

char

long

double

sign

no

float

letter

 

II.3      Оператор присваивания:

Вариант:

1

2

3

4

 

<И> := <В>;

<И> let <В>;

<И> ~ <В> ;

 <И> = <В> ;

 

II.4      Условный оператор:

В-т:

1

2

3

4

 

when<ЛВ> then <ОБ> [ other <ОБ> ]

? (<ЛВ>) @<ОБ>  [ @ <ОБ> ]

if (<ЛВ>) <ОБ>  [ ifnot<ОБ>]

by <ЛВ> do <ОБ> [ else <ОБ> ]

 

II.5      Оператор цикла:

В-т:

1

2

3

4

 

for <И> from <К> [step < К >] to<К> exec <ОБ>

cycle([<О>];[<ЛВ>];[<О>]) <ОБ>

till (<ЛВ>)   repeat <ОБ>

loop( [<O>] ) <ОБ> while(<ЛВ>)