Разработка распознавателя модельного языка программирования

1.1. ПОСТАНОВКА ЗАДАЧИ

1. Цель

Целью данной работы является:

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

1. Требования

Разработать распознаватель модельного языка программирования согласно заданной формальной грамматике.

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

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

Конфигурацией распознавателя является:

• состояние УУ; - содержимое входной ленты;
• положение читающей головки;
• содержимое дополнительной памяти (стека).

Трансляция исходного текста программы происходит в несколько этапов.

Основными этапами являются следующие:

• лексический анализ;
• синтаксический анализ;
• семантический анализ;
• генерация целевого кода.

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

Синтаксический анализатор строится на базе контекстно-свободных (КС) грамматик. Задача синтаксического анализатора – провести разбор программы и сопоставить его с формальным описание языка.

Семантический анализ позволяет учесть особенности языка программирования, которые не могут быть описаны правилами КС-грамматики. К таким особенностям относятся:

• обработка описаний;
• анализ выражений;
• проверка правильности операторов.

Обработки описаний помогают убедиться, что каждая переменная в программе описана и при этом только один раз.

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

Этапы синтаксического и семантического анализа обычно можно объединить.

1. Порядок выполнения

1. В соответствии с номером варианта составить описание модельного языка программирования в виде правил вывода формальной грамматики;
2. Составить таблицу лексем и нарисовать диаграмму состояний для распознавания и формирования лексем языка;
3. Разработать процедуру лексического анализа исходного текста программы на языке высокого уровня;
4. Разработать процедуру синтаксического анализа исходного текста методом рекурсивного спуска на языке высокого уровня;
5. Построить программный продукт, читающий текст программы, написанной на модельном языке, в виде консольного приложения;
6. Протестировать работу программного продукта с помощи серии тестов, демонстрирующих все основные особенности модельного языка программирования, включая возможные лексические и синтаксические ошибки.

2. ГРАММАТИКА ЯЗЫКА

Согласно        индивидуальному        варианту        задания        на        курсовую        работу грамматика языка включает следующие синтаксические конструкции:

1. <операции_группы_отношения>::= <> | = | < | <= | > | >=
2. <операции_группы_сложения>::= + | - | or
3. <операции_группы_умножения>::= * | / | and
4. <унарная_операция>::= not
5. <программа>::= program var <описание> begin <оператор>{;

        <оператор>} end.

1. <описание>::= {<идентификатор> {, <идентификатор> } : <тип>;}

7. <тип>::= % | ! | $

1. <оператор>::=        <составной>|<присваивания>        |<условный>        |<цикла>

|<ввода> |<вывода>

1. <составной>::= «[» <оператор> { ( : | перевод строки) <оператор> }«]»

10. <присваивания>::= <идентификатор> as <выражение>