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

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

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

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

На тему

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

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

Москва 2009

Аннотация

 

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

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

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

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

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

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

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

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

Теоретическое введение

 

Теория построения трансляторов используется во многих областях, связанных с программным обеспечением. Важность этой темы можно проиллюстрировать на примере языка высокого уровня C++: для разработки программы на 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 можно изменить имена идентификаторов, и при этом не изменится смысл программы. Для терминальных символов это неверно. Набор терминальных символов всегда строго соответствует алфавиту языка, определяемого грамматикой.