Кафедра ЭВА
Отчет по курсовой работе
по дисциплине
«Системное Программное Обеспечение»
на тему
«Однопроходный/двухпроходный транслятор с языка математических выражений на язык деревьев вывода.
Интерпретатор языка деревьев вывода»
Москва 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 содержит символы, которые входят в алфавит языка, порождаемого грамматикой. ............