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

Содержание 

    Введение 3

    1 Постановка задачи 4

    2 Формальная модель задачи 5

    3 Структура программы………………………………………………….....16

    3.1 Лексический анализатор 16

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

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

    3.4 Генерация ПОЛИЗа программы 22

    3.5 Интерпритация ПОЛИЗа программы 24

    4 Структурная организация данных 31

    4.1 Спецификация входной информации 31

    4.2 Спецификация выходной информации 31

    4.3 Спецификация процедур и функций 31

    5 Разработка алгоритма решения  задачи 32

    5.1 Укрупненная схема алгоритма программного средства 32

    5.2 Детальная разработка алгоритмов отдельных подзадач 33

    6 Установка и эксплуатация программного  средства 34

    7 Работа с программным средством 35

    Заключение 36

    Список  использованных источников 37

    Приложение  А – Текст программы 38 
 
 
 
 
 
 
 
 
 
 
 

 

Введение 

      Теория  формальных языков, грамматик и автоматов  составляет фундамент синтаксических методов. Основы этой теории были заложены Н. Хомским в 40–50-е годы XX столетия в связи с его лингвистическими работами, посвященными изучению естественных языков. Но уже в следующем десятилетии синтаксические методы нашли широкое практическое применение в области разработки и реализации языков программирования.

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

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

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

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

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

 
 
 
 
 

      1 Постановка задачи 

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

      1) В соответствии с номером варианта составить формальное описание модельного языка программирования с помощью:

      а) РБНФ;

      б) диаграмм Вирта;

      в) формальных грамматик.

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

      3) Составить таблицы лексем и  диаграмму состояний с действиями  для распознавания и формирования лексем языка.

      4) По диаграмме с действиями  написать функцию сканирования  текста входной программы на модельном языке.

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

      6) Реализовать синтаксический анализатор  текста программы на модельном языке методом рекурсивного спуска.

      7) Построить цепочку вывода и дерево разбора простейшей программы на модельном языке из начального символа грамматики.

      8) Дополнить синтаксический анализатор  процедурами проверки семантической правильности программы на модельном языке в соответствии с контекстными условиями вашего варианта.

      9) Распечатать пример таблиц идентификаторов  и двуместных операций.

      10) Показать динамику изменения  содержимого стека при семантическом  анализе программы на примере  одного синтаксически правильного  выражения.

      11) Записать правила вывода грамматики с действиями по переводу в ПОЛИЗ программы на модельном языке.

      12) Пополнить разработанное программное  средство процедурами, реализующими генерацию внутреннего представления введенной программы в форме ПОЛИЗа.

      13) Разработать интерпретатор ПОЛИЗа программы на модельном языке.

      14) Составить набор контрольных  примеров, демонстрирующих:

      а) все возможные типы лексических, синтаксических и семантических  ошибок в программах на модельном языке;

      б) перевод в ПОЛИЗ различных  конструкций языка;

      в) представить ход интерпретации синтаксически и семантически правильной программы с помощью таблицы. 

      2 Формальная модель  задачи 

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

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

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

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

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

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

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

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

    Формально грамматика G определяется как четверка G(V_T, V_N,P,S), где

    V_T: множество терминальных символов;

    V_N: множество нетерминальных символов;

    P: множество правил вывода

    S: начальный символ грамматики. 
 
 
 
 
 

    РБНФ  в соответствии с вариантом:

      <буква>::= A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

      <цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

     <число>::= <целое> | <действительное>

      <целое>::= <двоичное> | <восьмеричное> | <десятичное> |

                         <шестнадцатеричное>

      <двоичное>::= {/ 0 | 1 /} (B | b)

      <восьмеричное>::= {/ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 /} (O | o)

      <десятичное>::= {/ <цифра> /} [D | d]

      <шестнадцатеричное>::= <цифра> {<цифра> | A | B | C | D | E | F | a | b |

                                                   c | d | e | f} (H | h)

      <действительное>::= <числовая_строка> <порядок> |

         [<числовая_строка>] . <числовая_строка>[порядок]

      <числовая_строка>::= {/ <цифра> /}

      <порядок>::= ( E | e )[+ | -] <числовая_строка>

      <идентификатор> ::= <буква> { <буква> | <цифра> }

     <ключевое_слово> ::= or | and | not | integer | real | boolean| ass | if | then | else | for | to | do | while| read | write | true | false

      <разделитель> ::= < > | = | < | <= | > | >= | + | - | * | / | ; | : | ( | ) | { | } | , | . |

     <тип>::= integer | real | boolean

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

<оператор>::= <составной> | <присваивания> | <условный> |                      <фиксированного_цикла> | <условного_цикла> | <ввода> | <вывода>

      <составной>::= <оператор> { ( : | перевод строки) <оператор> }

      <операнд>::= <слагаемое> {<операции_группы_сложения> <операнд>}

      <выражение>::= <операнд>{<операции_группы_отношения> <операнд>}

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

     <условный>::= if <выражение> then <оператор> [ else <оператор>]

      <фиксированного_цикла>::= for <присваивания>  to <выражение> do <оператор>

      <условного_цикла>::= while <выражение>  do <оператор>

      <ввода>::= read «(»<идентификатор> {, <идентификатор> } «)»