Однопроходный/двухпроходный транслятор с языка математических выражений на язык деревьев вывода

Кафедра ЭВА

Отчет по курсовой работе

по дисциплине

«Системное Программное Обеспечение»

на тему

«Однопроходный/двухпроходный транслятор с языка математических выражений на язык деревьев вывода.

Интерпретатор языка деревьев вывода»

Москва 2009

Аннотация

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

- изучение принципов построения трансляторов

- написание на языке C++ класса, реализующего следующие действия над математическими выражениями:

- лексический анализ

- синтаксический анализ

- вычисление значения

- написание транслятора с языка математических выражений на язык деревьев вывода

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

Формальные грамматики

Формальное определение грамматики. Форма Бэкуса-Наура

Грамматика - это описание способа построения предложений некоторого языка. Иными словами, грамматика - это математическая система, определяющая язык. Фактически, определив грамматику языка, мы указываем правила порождения цепочек символов, принадлежащих этому языку. Таким образом, грамматика - это генератор цепочек языка.

Правило (или продукция) - это упорядоченная пара цепочек символов (?, ?). В правилах важен порядок цепочек, поэтому их чаще записывают в виде ? > ? (или ?::= ?). Такая запись читается как «? порождает ?» или «? по определению есть ?».

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

Язык, заданный грамматикой G, обозначается как L(G).

Две грамматики G и G' называются эквивалентными, если они определяют один и тот же язык: L(G) = L(G'). Две грамматики G и G' называются почти эквивалентными, если заданные ими языки различаются не более чем на пустую цепочку символов:

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

VT - множество терминальных символов или алфавит терминальных символов;

VN - множество нетерминальных символов или алфавит нетерминальных символов;

Р - множество правил (продукций) грамматики, вида , где ,

S - целевой (начальный) символ грамматики .

Алфавиты терминальных и нетерминальных символов грамматики не пересекаются: . Целевой символ грамматики - это всегда нетерминальный символ. Множество называют полным алфавитом грамматики G.

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

Во множестве правил грамматики может быть несколько правил, имеющих одинаковые левые части, вида: . Тогда эти правила объединяют вместе и записывают в виде: . Одной строке в такой записи соответствует сразу n правил.

Такую форму записи правил грамматики называют формой Бэкуса-Наура. Форма Бэкуса-Наура предусматривает, как правило, также, что нетерминальные символы берутся в угловые скобки: < >.

Пример грамматики, определяющей язык целых десятичных чисел со знаком:

С({0,1,2. 3,4.5. 6,7.8.9.-,+}, {<число>,<чс>.<цифра>}, Р,<число>)

P:

<<число> -> <чс> | +<чс> | -<чс>

<<чс> -> <цифра> | <чс><цифра>

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

Рассмотрим составляющие элементы грамматики G:

· множество терминальных символов VT содержит двенадцать элементов: десять десятичных цифр и два знака;

· множество нетерминальных символов VN содержит три элемента: символы <число>, <чс> и <цифра>;

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

· целевым символом грамматики является символ <число>.

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

Принцип рекурсии в правилах грамматики

Особенность рассмотренных выше формальных грамматик в том, что они позволяют определить бесконечное множество цепочек языка с помощью конечного набора правил. Приведенная выше в примере грамматика для целых десятичных чисел со знаком определяет бесконечное множество целых чисел с помощью 15 правил. В такой форме записи грамматики возможность пользоваться конечным набором правил достигается за счет рекурсивных правил. Рекурсия в правилах грамматики выражается в том, что один из нетерминальных символов определяется сам через себя. Рекурсия может быть непосредственной (явной) - тогда символ определяется сам через себя в одном правиле, либо косвенной (неявной) - тогда то же самое происходит через цепочку правил.

В рассмотренной выше грамматике G непосредственная рекурсия присутствует в правиле: <чс> <чс><цифра>.

Чтобы рекурсия не была бесконечной, для участвующего в ней нетерминального символа грамматики должны существовать также и другие правила, которые определяют его, минуя его самого, и позволяют избежать бесконечного рекурсивного определения (в противном случае этот символ в грамматике был бы просто не нужен). Такими правилами являются <чс><цифра> - в грамматике G.

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

Если попытаться дать определение тому, что же является числом, то начать можно с того, что любая цифра сама по себе есть число. Далее можно заметить, что любые две цифры - это тоже число, затем - три цифры и т.д. Если строить определение числа таким методом, то оно никогда не будет закончено (в математике разрядность числа ничем не ограничена). Однако можно заметить, что каждый раз, порождая новое число, мы просто дописываем цифру справа (поскольку привыкли писать слева направо) к уже написанному ряду цифр. А этот ряд цифр, начиная от одной цифры, тоже в свою очередь является числом. Тогда определение для понятия «число» можно построить таким образом: «число - это любая цифра либо другое число, к которому справа дописана любая цифра». Именно это и составляет основу правил грамматики G и отражено в правилах

<чс> <цифра> | <чс><цифра>. Другие правила в этой грамматике позволяют добавить к числу знак и дают определение понятию «цифра».

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

Задача разбора

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

Грамматики и распознаватели - два независимых метода, которые реально могут быть использованы для определения какого-либо языка. Однако при создании компилятора для некоторого языка программирования возникает задача, которая требует связать между собой эти методы задания языков. Разработчиков компиляторов интересуют, прежде всего, синтаксические конструкции языков программирования. Для этих конструкций доказано, что задача разбора для них разрешима. Более того, для них найдены формальные методы ее решения. Поскольку языки программирования не являются чисто формальными языками и несут в себе некоторый смысл (семантику), то задача разбора для создания реальных компиляторов понимается несколько шире, чем она формулируется для чисто формальных языков. Компилятор должен не просто установить принадлежность входной цепочки символов заданному языку, но и определить ее смысловую нагрузку. Для этого необходимо выявить те правила грамматики, на основании которых цепочка была построена.

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

Виды рекурсий и разбора

Правила, имеющие вид

1) T-> T * A

2) T-> A * T

Называются леворекурсивными и праворекурсивными соответственно.

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

T-> A M

M-> * A | M

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

Классификация языков и грамматик

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

Классификация грамматик по Хомскому

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

Хомский выделил четыре типа грамматик.

Тип 0: грамматики с фразовой структурой

На структуру их правил не накладывается никаких ограничений: для грамматики вида G (VT, VN, P, S), правила имеют вид: , где .

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

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