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

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Однопроходный/двухпроходный транслятор с языка математических выражений на язык деревьев вывода

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

Кафедра ЭВА

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

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

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

на тему

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

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

Москва 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.-,+}