КафедраЭВА
Отчетпо курсовой работе
подисциплине
«СистемноеПрограммное Обеспечение»
натему
«Однопроходный/двухпроходныйтранслятор с языка математических выражений на язык деревьев вывода.
Интерпретаторязыка деревьев вывода»
Москва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 можно изменить имена идентификаторов, ипри этом не изменится смысл программы. Для терминальных символов это неверно.Набор терминальных символов всегда строго соответствует алфавиту языка,определяемого грамматикой.Принцип рекурсии в правилах грамматики
Особенность рассмотренных выше формальныхграмматик в том, что они позволяют определить бесконечное множество цепочекязыка с помощью конечного набора правил. Приведенная выше в примере грамматикадля целых десятичных чисел со знаком определяет бесконечное множество целыхчисел с помощью 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 и не могут быть отнесены к другимтипам, являются самыми сложными по структуре.
Практического применения грамматики, относящиесятолько к типу 0, не имеют.Тип 1: контекстно-зависимые (КЗ) инеукорачивающие грамматики
В этот тип входят два основных класса грамматик:
Контекстно-зависимые грамматики G (VT, VN, P, S),/>имеют правила вида:
/>, где />
Неукорачивающие грамматики G (VT, VN, P, S), /> имеют правила вида:
/>, где />
Структура правил КЗ-грамматик такова, что припостроении предложений заданного ими языка один и тот же нетерминальный символможет быть заменен на ту или иную цепочку символов в зависимости от тогоконтекста, в котором он встречается. Именно поэтому эти грамматики называют«контекстно-зависимыми». Цепочки /> и /> в правилах грамматикиобозначают контекст (/> – левыйконтекст, а /> — правый контекст), в общемслучае любая из них (или даже обе) может быть пустой. Неукорачивающиеграмматики имеют такую структуру правил, что при построении предложений языка,заданного грамматикой, любая цепочка символов может быть заменена на цепочкусимволов не меньшей длины. Отсюда и название «неукорачивающие».
Доказано, что эти два класса грамматикэквивалентны.
При построении компиляторов такие грамматики неприменяются, поскольку синтаксические конструкции языков программирования,рассматриваемые компиляторами, имеют более простую структуру и могут бытьпостроены с помощью грамматик других типов. Что касается семантическихограничений языков программирования, то с точки зрения затрат вычислительныхресурсов их выгоднее проверять другими методами, а не с помощьюконтекстно-зависимых грамматик.Тип 2: контекстно-свободные (КС) грамматики
Контекстно-свободные (КС) грамматики G (VT, VN, P,S), /> имеют правила вида:/>, где />. Такие грамматики такжеиногда называют неукорачивающими контекстно-свободными (НКС) грамматиками(видно, что в правой части правила у них должен всегда стоять как минимум одинсимвол). Существует также почти эквивалентный им класс грамматик – укорачивающиеконтекстно-свободные (УКС) грамматики G (VT, VN, P, S), />, правила которых могутиметь вид: />, где/>.
Разница между этими двумя классами грамматикзаключается лишь в том, что в УКС-грамматиках в правой части правил можетприсутствовать пустая цепочка (X), а в НКС-грамматиках – нет. Доказано, что этидва класса грамматик почти эквивалентны.
КС-грамматики широко используются при описаниисинтаксических конструкций языков программирования. Синтаксис большинстваизвестных языков программирования основан именно на КС-грамматиках.
Внутри типа КС-грамматик кроме классов НКС и УКСвыделяют еще целое множество различных классов грамматик, и все они относятся ктипу 2.Тип 3: регулярные грамматики
К типу регулярных относятся два эквивалентныхкласса грамматик: леволинейные и праволинейные.
Леволинейные грамматики G (VT, VN, P, S), />могут иметь правила двухвидов: />или />, где />.
В свою очередь, праволинейные грамматики G (VT, VN,P, S), /> могут иметь правила тоже двух видов: />или />, где/>.
Эти два класса грамматик эквивалентны и относятсяк типу регулярных грамматик.
Регулярные грамматики используются при описаниипростейших конструкций языков программирования: идентификаторов, констант,строк, комментариев и т.д. Эти грамматики исключительно просты и удобны виспользовании, поэтому в компиляторах на их основе строятся функциилексического анализа входного языка.Соотношения между типами грамматик
Типы грамматик соотносятся между собой особымобразом. Из определения типов 2 и 3 видно, что любая регулярная грамматикаявляется КС-грамматикой, но не наоборот. Также очевидно, что любая грамматикаможет быть отнесена к типу 0, поскольку он не накладывает никаких ограниченийна правила. В то же время существуют укорачивающие КС-грамматики (тип 2),которые не являются ни контекстно-зависимыми, ни неукорачивающими (тип 1),поскольку могут содержать правила вида />,недопустимые в типе 1.
Одна и та же грамматика в общем случае может бытьотнесена к нескольким классификационным типам (например, как уже было сказано,все без исключения грамматики могут быть отнесены к типу 0). Для классификацииграмматики всегда выбирают максимально возможный тип, к которому она может бытьотнесена. Сложность грамматики обратно пропорциональна номеру типа, к которомуотносится грамматика.
Трансляторы Формальное определение транслятора
Транслятор – это программа, которая переводит программу наисходном (входном) языке в эквивалентную ей программу на результирующем(выходном) языке.
С точки зрения преобразования предложенийвходного языка в эквивалентные им предложения выходного языка трансляторвыступает как переводчик.
Результатом работы транслятора будетрезультирующая программа, но только в том случае, если текст исходной программыявляется правильным – не содержит ошибок с точки зрения синтаксиса и семантикивходного языка. Если исходная программа неправильная (содержит хотя бы однуошибку), то результатом работы транслятора будет сообщение об ошибке.Этапы трансляции. Общая схема работытранслятора
На рис. 2.1 представлена общая схема работыкомпилятора. Из нее видно, что в целом процесс компиляции состоит из двухосновных этапов – анализа и синтеза. На этапе анализа выполняется распознаваниетекста исходной программы, создание и заполнение таблиц идентификаторов.Результатом его работы служит некое внутреннее представление программы,понятное компилятору. На этапе синтеза на основании внутреннего представленияпрограммы и информации, содержащейся в таблице идентификаторов, порождается текстрезультирующей программы. Результатом этого этапа является объектный код. Крометого, в составе компилятора присутствует часть, ответственная за анализ иисправление ошибок, которая при наличии ошибки в тексте исходной программыдолжна максимально полно информировать пользователя о типе ошибки и месте еевозникновения. В лучшем случае компилятор может предложить пользователю вариантисправления ошибки.
Эти этапы, в свою очередь, состоят из болеемелких этапов, называемых фазами компиляции. Состав фаз компиляции на рис. 2.1приведен в самом общем виде, их конкретная реализация и процесс взаимодействиямогут, конечно, различаться в зависимости от версии компилятора.
/>
Компилятор в целом, с точки зрения теорииформальных языков, выполняет две основные функции:
– распознавание языка исходной программы
– генерация результирующей программы назаданном языке.
Далее дается перечень основных фаз (частей)компиляции и краткое описание их функций.
Лексический анализатор (сканер) – это частькомпилятора, которая читает литеры программы на исходном языке и строит из нихслова (лексемы) исходного языка. На вход лексического анализатора поступаеттекст исходной программы, а выходная информация передается для дальнейшейобработки компилятором на этапе синтаксического разбора. С теоретической точкизрения лексический анализатор не является обязательной, необходимой частьюкомпилятора. Однако существуют причины, которые определяют его присутствиепрактически во всех компиляторах.
Синтаксический анализатор – это основная частькомпилятора на этапе анализа. Она выполняет выделение синтаксическихконструкций в тексте исходной программы, обработанном лексическим анализатором.На этой же фазе компиляции проверяется синтаксическая правильность программы.Синтаксический разбор играет роль распознавателя текста входного языкапрограммирования.
Семантический анализатор – это часть компилятора,проверяющая правильность текста исходной программы с точки зрения семантикивходного языка. Кроме непосредственно проверки семантический анализ долженвыполнять преобразования текста, требуемые семантикой входного языка (например,такие, как добавление функций неявного преобразования типов). В различныхреализациях компиляторов семантический анализ может частично входить в фазусинтаксического разбора, частично – в фазу подготовки к генерации кода.
Подготовка к генерации кода – это фаза, на которойкомпилятором выполняются предварительные действия, непосредственно связанные ссинтезом текста результирующей программы, но еще не ведущие к порождению текстана выходном языке. Обычно в эту фазу входят действия, связанные сидентификацией элементов языка, распределением памяти и т.п.
Генерация кода – это фаза, непосредственносвязанная с порождением команд, составляющих предложения выходного языка и вцелом текст результирующей программы. Это основная фаза на этапе синтезарезультирующей программы. Кроме непосредственного порождения текстарезультирующей программы генерация обычно включает в себя также оптимизацию – процесс,связанный с обработкой уже порожденного текста. Иногда оптимизацию выделяют вотдельную фазу компиляции, так как она оказывает существенное влияние накачество и эффективность результирующей программы.
Проход транслятора – процесс последовательногочтения компилятором данных из памяти, их обработки и помещёния результата впамять. В компиляторе может быть реализовано несколько проходов, напримерпроходы лексического и синтаксического анализатора. В некоторых случаях проходымогут быть объединены в один проход.Интерпретаторы
Интерпретатор – программа, воспринимающаяисходную программу на входном (исходном) языке и выполняющая ее.
Интерпретатор, также как и транслятор,анализирует текст исходной программы, но он не порождает результирующуюпрограмму, а сразу выполняет исходную в соответствии с ее смыслом, заданнымсемантикой ее языка.
Lex и Yacc/> Обзор генераторов кода
СистемыGNU/Linux поставляются с несколькими программами для написания программ.Возможно наиболее популярны:
· Flex,генератор лексического анализатора
· Bison,генератор синтаксического анализатора
· Gperf,развитый генератор хэш-функции
Этипрограммы генерируют тексты для языка C. Вы можете удивиться, почему ониреализованы в виде генераторов кода, а не в виде функций. Тому есть несколькопричин:
· Входныепараметры для этих функций являются очень сложными и их непросто выразить ввиде, корректном для C-кода.
· Этипрограммы вычисляют и генерируют много статических таблиц преобразования дляоперации, следовательно, лучше сгенерировать эти таблицы один раз передкомпиляцией, чем при каждом запуске программы.
· Многиеаспекты функционирования этих систем настраиваются произвольным кодом,помещаемым на отдельные позиции. Этот код может впоследствии использоватьпеременные и функции, являющиеся частью сгенерированной структуры, построеннойгенератором кода, без необходимости определять и извлекать все переменныевручную.
Каждоеиз этих инструментальных средств предназначено для создания конкретного типапрограмм. Bison используется для генерирования синтаксических анализаторов;Flex – для генерирования лексических анализаторов. Другие средства посвящены, восновном, автоматизации конкретных аспектов программирования.
Например,интегрирование методов доступа к базе данных в императивные языкипрограммирования часто является рутинной работой. Для ее облегчения истандартизации предназначен Embedded SQL – система метапрограммирования,используемая для простого комбинирования доступа к базе данных и C.
Хотя существует немало доступных библиотек,позволяющих обращаться к базам данных в C, использование такого генератора кодакак Embedded SQL делает комбинирование C и доступа к базе данных намного болеелегким путем объединения SQL-сущностей в C в качестве расширения языка. Многиереализации Embedded SQL, однако, в основном являются простыми специализированнымимакропроцессорами, генерирующими обычные C-программы. Тем не менее,использование Embedded SQL делает для программиста доступ к базе данных болееестественным, интуитивным и свободным от ошибок по сравнению с прямымиспользованием библиотек. При помощи Embedded SQL запутанность программированиябаз данных маскируется макроязыкомСовместное использование Lex и Yacc
До 1975 года процесс написания компиляторовзанимал очень много времени. Затем Lesk[1975] и Johnson[1975] опубликовали трудыпо lex и yacc. Эти утилиты сильноупростили написание компиляторов. Детали реализации могут быть найдены у Aho[1986]
Шаблоны кода помещаются на вход Lex. Lex читает шаблоны игенерирует Cкод для лексического анализатора или сканера.
Лексический анализатор ищет совпадение строк вовходных данных, основываясь на заданных шаблонах, и преобразует строки втокены.
Токены являются числовым представлением строкупрощающим обработку.
Когда лексический анализатор находитидентификаторы во входном потоке, они вносятся в таблицу символов. Таблицасимволов также может содержать другую информацию такую, как тип данных (целыйили вещественный) и место переменной в памяти. Все последующие ссылки наидентификаторы ссылаются на соответствующий индекс таблицы символов.
Код грамматики подаются на вход yacc. Yacc читает грамматику игенерирует Cкод для синтаксического анализатора или разборщика. Синтаксический анализаториспользует грамматические правила, которые позволяют ему анализировать токеныиз лексического анализатора и создать синтаксическое дерево. Синтаксическоедерево устанавливает иерархичскую структуру токенов. Например, оператор precedence и ассоциативности (associativity) показаны всинтаксическом дереве. Следующий шаг, генерация кода, осуществляется с помощьюобхода синтаксического дерева. Некоторые компиляторы создают машинный код,когда как некоторые – программу на языках ассемблера.
Команды для создания компилятора, bas.exe, приведены ниже:
yacc – d bas.y # createy.tab.h, y.tab.c
lex bas.l # createlex.yy.c
cc lex.yy.c y.tab.c – obas.exe# compile/link
Yacc читает грамматические описания в bas.y и генерируетсинтаксический анализатор (parser), который включает функцию yyparse, в файле y.tab.c. Файл bas.yсодержит в себеобъявления токенов. Включение опции – dведет к тому, что yacc генерирует определениядля токенов и помещает их в файл y.tab.h. Lex читает шаблоны,описанные в bas.l, включающие файл y.tab.h и генерирует лексическийанализатор, который включает функцию yylex, в файле lex.yy.c. Наконец, лексическийанализатор (lexer) и синтаксический анализатор (parser) компилируются икомпонуются вместе, образуя исполняемый файл bas.exe. Из main, мы вызываем yyparse, чтобы запуститькомпилятор. Функция yyparse автоматически вызывает yylex, чтобыполучить каждый токен.LexTheory
Первая фаза в компиляторе – чтение входногоисходного файла и его преобразование в токены. Используя регулярные выражения,мы можем специфицировать шаблоны для лексического анализа, и это позволитсгенерировать код, который позволит сканировать и найти совпадающие строки висходном коде. Каждому шаблону специфицированному в исходном коде длялексического анализа, сопоставляется ассоциированное действие. Обычно действиевозвращает токен, который представляет совпадающую строку, в последующемиспользуемую синтаксическим анализатором. Сначала просто печатаем совпавшуюстроку, если возвращается значение токена.
Далее следует представление простого шаблона,составляющего регулярное выражение, которое ищет идентификаторы. Lex читает этот шаблон исоздает Cкод для лексического анализатора, который ищет идентификаторы.
letter (letter|digit)*
Этот шаблон ищет строкусимволов, которая начинается с единичного символа, следующим за нулем илибольше символов или цифр. Этот пример хорошо иллюстрирует, операции,разрешенные а регулярных выражениях:
• повторение,представленное оператором «*» (repetition)
• чередование,представленное оператором «|» (alternation)
• объединение (concatenation)
Любое регулярное выражение может быть представленоавтоматом с конечным числом состояний (finite state automaton, FSA). Мы можем представить FSA, использующее состоянияи переходы между состояниями. Существует одно начальное состояние и одно, илибольше, конечных состояний или разрешенных состояний.
/>
На рис. 3, состояние0 – является начальным состоянием, а состояние 2 – разрешенным состоянием.Когда происходит чтение символа, осуществляется переход из одного состояния вдругое. Когда читается первый символ, осуществляется переход в состояние 1.Автомат остается в состоянии 1, пока читаются буквы (letters) или цифры (digits). Когда осуществляетсячтение иного символа, кроме буквы или символа, осуществляется переход всостояние 2, разрешенное состояние. Любой FSA может быть представлен спомощью компьютерной программы. Например, этот автомат с 3 мя состояниямипрограммируется следующим образом:
start: gotostate0
state0: read c
if c = lettergoto state1
goto state0
state1: read c
if c = lettergoto state1
if c = digitgoto state1
goto state2
state2: accept string
Это техника, используемаяlex. Регулярные выражениятранслируются с помощью lex в компьютерную программу, которая реализует FSA. Используя следующийвходной символ и текущее состояние, следующее состояние определяется с помощьюиндексирования в сгенерированной компьютером таблице состояний.
Теперь становится легко понять ограничения в lex. Например, lex не может бытьиспользован.
Таблица 1. Элементарные шаблоны (Pattern Matching Primitives)
Метасимвол (Metacharacter)
Совпадения (Matches)
. Любой символ, кроме перевода строки
\n Символ перевода строки
* 0 или более копий предшествующих выражений
+ 1 или более копий предшествующих выражений
? 0 или 1 копия предшествующих выражений
^ Начало строки
$ Конец строки
a|b
a или b
(ab)+
Одна или более копийab(группировка, grouping)
«a+b»
литерал «a+b» (C escapes still work)
[] Класс символов
Таблица 2. Примеры шаблонов выражений (Pattern Matching Examples)
Выражение (Expression)
Совпадения (Matches)
abc
abc
abc*
ab abc abcc abccc…
abc+
abc abcc abccc…
a(bc)+
abc abcbc abcbcbc…
a(bc)?
a abc
[abc]
Одно из: a, b, c
[a-z] Любой символ, a-z
[a\-z]
Одно из: a, -, z
[-az]
Одно из: -, a, z
[A-Za-z0–9]+ Один или более символов алфавита или цифр
[\t\n]+ Пробельные символы
[^ab]
Все, кроме: a, b
[a^b]
Одно из: a, ^, b
[a|b]
Одно из: a, |, b
a|b
Одно из: a, b
Регулярные выражения в lex составляются изметасимволов (Таблица 1). Примеры совпадения шаблонов показаны в таблице 2. Прииспользовании класса символов, обычные операторы теряют свое назначение.
Следующие два оператораразрешены в классе символов: дефис («–», hyphen) и циркумфлекс («^»,circumflex). При использованиимежду двумя символами дефиса, представляется диапазон символов. Циркумфлекс,при использовании его как первого символа, отрицает выражение. Если два шаблонасовпадают с некоторой строкой, используется наиболее шаблон, по которомунайдена наиболее длинная строка, в случае, если длина одинакова, используетсяпервый шаблон.
… definitions…
%%
… rules…
%%
… subroutines…
Входные данные lex делятся на 3 секции, ссимволами%%, разделяющими секции. Это проиллюстрировано в примере. Первыйпример – это наименьший возможный файл lex:
%%
Входные данные копируются выходные по одномусимволу за раз. Первый разделитель%% требуется всегда, так как всегда должнабыть секция правил. Если не специфицировать ни одного правила, тогда действиепо умолчанию – совпадение всего и копирование в выходные данные. По умолчаниюдля входных и выходных данных используются stdinи stdout, соответственно. Вотнекоторый пример, с использованием кода по умолчанию:
%%
/* Совпадение всего,кроме символа новой строки */
ECHO;
/* Совпадение символаперевода строки */
\n ECHO;
%%
intyywrap(void) {
return 1;
}
int main(void){
yylex();
return0;
}
Два шаблона специфицированы в секции правил.Каждый шаблон должен начинаться в первом столбце, то есть должен следовать запробельным символом. Опциональное действие ассоциируется с шаблоном. Действиеможет быть единичным выражением на языке C или множественным,заключенным в скобки. Все, не начинающееся с первого столбца, дословнокопируется в генерируемый C файл. Можно использовать это для спецификации комментариев вlex файле. В этом примереесть 2 выражения:
«.» и «\n» с действием ECHO, ассоциированным скаждым шаблоном. Несколько макросов и переменных определены в lex. ECHO – это макрос, которыйпишет код, совпадающий с шаблоном. Это действие по умолчанию для каждойнесовпадающей строки. Обычно ECHO определяется как
#define ECHO fwrite (yytext,yyleng, 1, yyout)
Переменная yytext – указатель на совпавшуюстроку (оканчивающийся NULL-символом), и yyleng – длина совпавшейстроки. Выражение yyout является выходным файлом и по умолчанию являетсяstdout. Функция yywrapвызывается lex, когда входные данныезакончились. Возвращает 1, если закончено, 0 если требуется дальнейшая обработка.Каждая программа на C требует main функцию. В этом случае просто вызывается yylex,
Основная точка входа для lex. Некоторые реализации lex включают копии mainи yywrap в библиотеку, устраняянеобходимость явно определять их. Поэтому первый пример, наименьшая программа lex правильно функционирует.
Name
Function
int yylex(void) Вызывается для запуска лексического анализатора, возвращает токен
char *yytext Указатель на совпавшую строку
yyleng Длина совпавшей строки
yylval Значение, ассоциируемое с токеном
int yywrap(void) Wrapup – обертка возвращает 1 – если завершена, 0 – если не завершено
FILE *yyout Выходной файл
FILE *yyin Входной файл
INITIAL Исходное условие старта
BEGIN Условие переключающее условие старта
ECHO Записать совпавшую строку
Следующийпример присоединяет слева номер линии для каждой линии в файле. Некоторыереализации lex предопределяютвычисление yylineno.Входной файл для lex – это yyin,и является по умолчанию stdin.
%{
int yylineno;
%}
%%
^(.*)\n printf («%4d\t % s», ++yylineno, yytext);
%%
int main (int argc, char *argv[]) {
yyin = fopen (argv[1], «r»);
yylex();
fclose(yyin);
}
Секции определенийсостоят из замен, кода и начальных состояний. Код в секциях определения простокопируется в начало генерируемого C файла, при этом код должен быть в скобках%{»и «%}». Замены облегчаются правилами совпадения шаблонов. Например,можно определить цифры и символы:
digit [0–9]
letter [A-Za-z]
%{
int count;
%}
%%
/* matchidentifier */
{letter} ({letter}|{digit})*count++;
%%
int main(void){
yylex();
printf («numberof identifiers =%d\n», count);
return0;
}
Пробел должен разделятьтерм и ассоциируемое выражение. Ссылки на подстановки в секциях правил окруженыскобками ({letter}), чтобы различать их с символами. Когда происходитсовпадение в секции правил, ассоциируемый C код выполняется. Вотпрограмма, которая считает количество символов, слов и линий в файле (подобнаякоманде wc в Unix):
%{
int nchar, nword,nline;
%}
%%
\n {nline++;nchar++;}
[^ \t\n]+ {nword++,nchar += yyleng;}
{nchar++;}
%%
int main(void){
yylex();
printf («%d\t %d\t % d\n», nchar, nword, nline);
return0;
}Реализация lex в Unix
Вцелом подсистема LEX для систем UNIX включает следующие файлы:
/usr/ccs/bin/lex;
lex.yy.c;
/usr/ccs/lib/lex/ncform;
/usr/lib/libl.a;
/usr/lib/libl.so.
В каталоге /usr/ccs/lib/lex имеется файл-заготовка ncform, который LEX используется для построения ЛА. Этот файлявляется уже готовой программой лексического анализа. Но в нем не определеныдействия, которые необходимо выполнять при распознавании лексем, отсутствуют исами лексемы, не сформированы рабочие массивы и т.д. С помощью команды lex файлncform достраивается. В результате мы получаем файл со стандартным именем lex.yy.c. Если LEX-программа размещена в файле program.l, то для получения ЛА с именем program необходимо выполнитьследующий набор команд:
lex program.l
cc lex.yy.c – ll – o program
Если имя входного файла для команды lex не указано, то будет использоваться файл стандартного ввода. Флаг– ll требуется для подключения /usr/ccs/lib/libl.a – библиотеки LEX. Еслинеобходимо получить самостоятельную программу, как в данном случае, подключениебиблиотеки обязательно, поскольку из нее подключается главная функция main. Впротивном случае, если имеется необходимость включить ЛА в качестве функции вдругую программу (например, в программу синтаксического анализа), этубиблиотеку необходимо вызвать уже при сборке. Тогда, если main определен ввызывающей ЛА программе, редактор связей не будет подключать раздел main избиблиотеки LEX.
Общийформат вызова команды lex:
lex [-ctvn – V – Q [y|n]] [file]
Флаги:
– c – включает фазугенерации Си-файла (устанавливается по умолчанию);
– t – поместить результат встандартный файл вывода, а не в файл lex.yy.c;
– v – вывести размерывнутренних таблиц;
– n – не выводить размерытаблиц (устанавливается по умолчанию);
– V – вывести информацию оверсии LEX в стандартный файл ошибок;
– Q – вывести (Qy) либо не выводить (Qn, устанавливается поумолчанию) информацию о версии в файл lex.yy.c.YACC – Yet Another Compiler Compiler
Грамматики для yacc описываются с помощью ФормыБэкуса-Наура (Backus Naur Form, BNF)
Эту технику была ввели John Backus и Peter Naur ииспользовали ее, чтобы описать ALGOL60. Грамматика BNF может быть использованадля описания контекстно-свободных языков. Большинство конструкций современногопрограммирования могут быть представлены в BNF.
Например, грамматика для выражения, котороеумножает и складывает числа может быть представлена следующим образом:
E -> E + E
E -> E * E
E -> id
Были специфицированы 3 правила продукции. Термы,которые могут быть с левой стороны правил продукции(lhs) продукции, такие как E(expression), являются нетерминальными символами. Термы, такие как id(identifier) являются терминальными символами (токенами, возвращаемыми lex) имогут быть только с правой стороны правил продукции(rhs).
Эта грамматика определяет, что выражение можетбыть суммой двух выражений, произведением двух выражений или идентификатором.Можно использовать эту грамматику, чтобы сгенерировать выражения:
E -> E * E (r2)
-> E * z (r3)
-> E + E * z (r1)
-> E + y * z (r3)
-> x + y * z (r3)
На каждом шаге мы расширяем терм, заменяем левуючасть продукции соответствующей правой частью. Числа справа показывают какоеправило применяется. Чтобы распознать выражение, необходима обратная операция.Кроме того, что необходимо начинать с единичного нетерминального (начальногосимвола), и генерировать выражение из грамматики. Это известно под терминомвосходящий (bottom-up) анализ и использование стека для хранения термов. Вотнекоторый пример в обратном порядке:
1. x + y * z shift
2 x. + y * z reduce(r3)
3 E. + y * z shift
4 E +. y * z shift
5 E + y. * z reduce(r3)
6 E + E. * z shift
7 E + E *. z shift
8 E + E * z. reduce(r3)
9 E + E * E. reduce(r2) emit multiply
10 E + E. reduce(r1) emit add
11 E. acceptСтруктура YACC-программы
Каждый файл спецификаций состоит из трех секций:объявления, (грамматические) правила, и программы. Секции разделяются символамидвойного процента «%%». Другими словами, полный файл спецификациивыглядит как:
описания
%%
правила
%%
программы
Секция объявлений может быть пуста. Более того,если секция программ опущена, то вторая метка «%%» также может бытьопущена; таким образом, минимальная разрешенная спецификация Yacc есть:
%%
правила
Пример простейшей программы на YACC'e:
%token name
%start e
%%
e: e '+' m | e '-' m | m;
m: m '*' t | m '/' t | t;
t: name | ' (' e ')';
%%
Секция правил содержит информацию о том, чтосимвол name является лексемой (терминалом) грамматики, а символ e – ее начальнымнетерминалом.
Грамматика записана обычным образом – идентификаторыобозначают терминалы и нетерминалы, символьные константы типа '+' '-' – терминалы.Символы: |; – принадлежат метаязыку и читаются «есть по определению», «или» и «конецправила» соответственно.Семантические действия
Каждомуправилу можно поставить в соответствие некое действие, которое будетвыполняться всякий раз, как это правило будет распознано. Действия могутвозвращать значения и могут пользоваться значениями, возвращенными предыдущимидействиями. Более того, лексический анализатор может возвращать значения длятокенов (дополнительно), если хочется. Действие – это обычный оператор языкаСи, который может выполнять ввод, вывод, вызывать подпрограммы и изменятьглобальные переменные.
Действия,состоящие из нескольких операторов, необходимо заключать в фигурные скобки.Например:
A: ' (' B ')'
{hello (1, «abc»);}
и
XXX: YYY ZZZ
{printf («a message\n»); flag = 25;}
являются грамматическими правилами с действиями.
Чтобыобеспечить связь действий с анализатором, используется спецсимвол «доллар» ($). Чтобы вернуть значение, действие обычно присваивает егопсевдопеременной $$. Например, действие,которое не делает ничего, но возвращает единицу:
{$$ = 1;}
Чтобы получить значения, возвращенные предыдущимидействиями и лексическим анализатором, действие может использоватьпсевдопеременные $1, $2 и т.д., которыесоответствуют значениям, возвращенным компонентами правой части правила, считаяслева направо. Таким образом, если правило имеет вид:
A: B C D;
то $2 соответствует значению,возвращенному нетерминалом C, a $3 – нетерминалом D. Болееконкретный пример:
expr: ' (' expr ')';
Значением, возвращаемым этим правилом, обычноявляется значение выражения в скобках, что может быть записано так:
expr: ' (' expr ')'
{$$ = $2;}
По умолчанию, значением правила считаетсязначение, возвращенное первым элементом ($1). Таким образом, еслиправило не имеет действия, Yacc автоматически добаляет его в виде $$=$1;, благодаря чему для правила вида
A: B;
обычно не требуется самому писать действие.
Ввышеприведенных примерах все действия стояли в конце правил, но иногдажелательно выполнить что-либо до того, как правило будет полностью разобрано.Для этого Yacc позволяет записывать действия не только в конце правила, но и вего середине. Значение такого действия доступно действиям, стоящим правее,через обычный механизм:
A: B
{$$ = 1;}
C
{x = $2; y = $3;}
;
В результате разбора иксу (x) присвоится значение1, а игреку (y) – значение, возвращенное нетерминалом C. Действие, стоящее всередине правила, считается за его компоненту, поэтому x=$2 присваивает X-у значение, возвращенное действием $$=1;
Длядействий, находящихся в середине правил, Yacc создает новый нетерминал и новоеправило с пустой правой частью и действие выполняется после разбора этогонового правила. На самом деле Yacc трактует последний пример как
NEW_ACT: /* empty */ /* НОВОЕ ПРАВИЛО */
{$$ = 1;}
;
A: B NEW_ACT C
{x = $2; y = $3;}
;
В большинстве приложений действия не выполняютввода / вывода, а конструируют и обрабатывают в памяти структуры данных,например дерево разбора. Такие действия проще всего выполнять вызывая подпрограммыдля создания и модификации структур данных. Предположим, что существует функцияnode, написанная так, что вызов node (L,n1, n2)создает вершину с меткой L, ветвями n1 и n2 и возвращает индекс свежесозданной вершины. Тогда дерево разбораможет строиться так:
expr: expr '+' expr
{$$ = node ('+', $1, $3);}
Программист может также определить собственныепеременные, доступные действиям. Их объявление и определение может быть сделанов секции объявлений, заключенное в символы%{и%}. Такие объявления имеют глобальную область видимости, благодарячему доступны как действиям, так и лексическому анализатору. Например:
%{
int variable = 0;
%}
Такие строчки, помещенные в раздел объявлений,объявляют переменную variable типа int и делают ее доступнойдля всех действий. Все имена внутренних переменных Yacca начинаются c двух буквy, поэтому не следует давать своим переменным имена типа yymy.Лексический анализ
Программист,использующий Yacc должен написать сам (или создать при помощи программы типаLex) внешний лексический анализатор, который будет читать символы из входногопотока (какого – это внутреннее дело лексического анализатора), обнаруживатьтерминальные символы (токены) и передавать их синтаксическому анализатору,построенному Yaccом (возможно вместе с неким значением) для дальнейшегоразбора. Лексический анализатор должен быть оформлен как функция с именем yylex, возвращающая значение типа int, которое представляетсобой тип (номер) обнаруженного во входном потоке токена. Если есть желаниевернуть еще некое значение (например номер в группе), оно может быть присвоеноглобальной, внешней (по отношению к yylex) переменной по имени yylval.
Лексическийанализатор и Yacc должны использовать одинаковые номера токенов, чтобы пониматьдруг друга. Эти номера обычно выбираются Yaccом, но могут выбираться ичеловеком. В любом случае механизм define языка Си позволяет лексическомуанализатору возвращать эти значения в символическом виде. Предположем, чтотокен по имени DIGIT был определен в секцииобъявлений спецификации Yaccа, тогда соответствующий текст лексическогоанализатора может выглядеть так:
yylex()
{
extern int yylval;
int c;
…
c = getchar();
…
switch (c) {
…
case '0':
case '1':
…
case '9':
yylval = c – '0';
return DIGIT;
…
}
…
Вышеприведенный фрагмент возвращает номер токена DIGIT и значение, равное цифре. Если при этом сам текст лексическогоанализатора был помещен в секцию программ спецификации Yacca – есть гарантия,что идентификатор DIGIT был определен номеромтокена DIGIT, причем тем самым,который ожидает Yacc.
Такоймеханизм позволяет создавать понятные, легкие в модификации лексическиеанализаторы. Единственным ограничением является запрет на использование вкачестве имени токена слов, зарезервированых или часто используемых в языке Сислов. Например, использование в качестве имен токенов таких слов как if или while, почти навернякаприведет к возникновению проблем при компиляции лексического анализатора. Кромеэтого, имя error зарезервировано длятокена, служащего делу обработки ошибок, и не должно использоваться.
Какуже было сказано, номера токенов выбираются либо Yaccом, либо человеком, ночаще Yaccом, при этом для отдельных символов (например для (или;) выбирается номер, равный ASCII коду этого символа. Длядругих токенов номера выбираются начиная с 257.
Длятого, чтобы присвоить токену (или даже литере) номер вручную, необходимо всекции объявлений после имени токена добавить положительное целое число,которое и станет номером токена или литеры, при этом необходимо позаботиться обуникальности номеров. Если токену не присвоен номер таким образом, Yaccприсваивает ему номер по своему выбору.
Потрадици, концевой маркер должен иметь номер токена, равный, либо меньший нуля,и лексический анализатор должен возвращать ноль или отрицательное число придостижении конца ввода (или файла).
Оченьнеплохим средством для создания лексических анализаторов является программаLex. Лексические анализаторы, построенные с ее помощью прекрасно гармонируют ссинтаксическими анализаторами, построенными Yaccом. Lex можно легкоиспользовать для построения полного лексического анализатора из файласпецификаций, основанного на системе регулярных выражений (в отличие от системыграмматических правил для Yacca), но, правда, существуют языки (например Фортран)не попадающие ни под какую теоретическю схему, но для них приходится писатьлексический анализатор вручную.Реализация Yacc в UnixYACC(1)
НАЗВАНИЕ
yacc– еще один компилятор компиляторов
СИНТАКСИС
yacc [-v] [-d] [-l] [-t] грамматика
ОПИСАНИЕ
Командаyacc преобразует контекстно-свободную грамматику в набор таблиц для простогоLR(1) – разбора. Грамматика может содержать неоднозначности; чтобы ихпреодолеть, используются заданные правила предшествования.
Выходнойфайл y.tab.c преобразуется C-компилятором в программу yyparse, которую нужноскомпоновать с программой лексического анализа yylex, а также с подпрограммойmain и подпрограммой обработки ошибок yyerror. Эти подпрограммы должны бытьпредоставлены пользователем; при порождении лексических анализаторов полезенlex(1).
Допустимыеопции:
-v Сгенерировать файл y.output, который содержит описание таблиц разбора с указанием конфликтных ситуаций, вызванных неоднозначностями грамматики.
-d Сгенерировать файл y.tab.h, который содержит определения #define, связывающие заданные пользователем «имена лексем» с назначенными программой yacc «кодами лексем», что позволяет использовать коды лексем в исходных файлах, отличных от y.tab.c.
-l Не вставлять в программу y.tab.c операторы #line. Рекомендуется использовать только после того, как грамматика и другие компоненты полностью отлажены.
-t При помощи средств условной компиляции в программу y.tab.c всегда вставляются отладочные операторы, однако по умолчанию компилятор их пропускает. Если указана опция – t, то при отсутствии других указаний отладочные операторы будут скомпилированы. Вне зависимости от использования опции – t компиляцией отладочных операторов управляет переменная препроцессора YYDEBUG. Если YYDEBUG имеет ненулевое значение, отладочные операторы компилируются; при нулевом значении они пропускаются. Когда программа сформирована без отладочного кода, ее размер меньше и скорость выполнения несколько выше.
ФАЙЛЫ
y.output
y.tab.c
y.tab.h Определение кодов лексем.
yacc.tmp Временный файл.
yacc.debug Временный файл.
yacc.acts Временный файл.
/usr/lib/yaccpar Прототип алгоритма разбора для
C-программ.
СМ.ТАКЖЕ
lex(1).
ДИАГНОСТИКА
Встандартный протокол направляется информация о числе конфликтных ситуаций типа «свертка-свертка»и «перенос-свертка»; более подробные сообщения содержатся в файле y.output.Аналогичным образом сообщается о продукциях, недостижимых из начального символаграмматики.
ОГРАНИЧЕНИЯ
Таккак имена файлов фиксированы, в данном каталоге в каждый момент времени можетбыть активным только один процесс yaccПостановка задачи
Реализовать:
– транслятор с языка математическихвыражений на язык деревьев вывода
– интерпретатор языка деревьев вывода
К разрабатываемым программам предъявляютсяследующие требования:
– реализация осуществляется на языке C++.
– функциональность транслятора иинтерпретатора должна быть реализована в виде класса (Класс Analyser).
Должна быть обеспечена поддержка следующей функциональности:
– вычисление математических выражений с любой степенью вложенности
– поддержка в выражениях чисел с плавающей точкой
– математические операции:
– «+», «–» (бинарный / унарный), «*», «/», «^» (возведение в степень)
– поддержка функций:
log(), exp(), sin(), cos(), tan(), acos(), asin(), atan()
– игнорирование пробелов, символов табуляции и переноса строки
– оптимизация синтаксического дерева
– объединение проходов синтаксического и лексического анализаторов в один проход. (Отсюда название «однопроходный / двухпроходный». Второй проход опциональный – это проход оптимизатора.)
– запись / чтение синтаксического дерева в файл/из файлаТрансляторГрамматика синтаксического анализатора
Грамматика описана в виде формы Бэкуса-Наура,расширенной метасимволами.Исходная грамматика
EXPR-> [|] EXPRTERM | [|] EXPRTERM | [|] TERM
TERM-> TERMFACTOR | TERMFACTOR | FACTOR
FACTOR-> FACTORPOW{} 0 | POW
POW-> | | EXPR | FUNCEXPR
FUNC-> | | | | | | |
Пояснения:
1) это пустой символ
3) {DIGIT} n – это итерация DIGIT, где n – натуральное число
4) {} 0 это отсутствие двойного возведения в степень
5) имена переменных не должны совпадать с именами функций, поддерживаемых интерпретатором.
Данная грамматика позволяет разбирать математические выражения с учетом приоритетов математических операций.Эквивалентная грамматика без левой рекурсии
EXPR-> [|] TERM MORETERMS
MORETERMS-> TERM MORETERMS | TERM MORETERMS |
TERM-> FACTOR MOREFACTORS
MOREFACTORS-> FACTOR MOREFACTORS | FACTOR MOREFACTORS |
FACTOR-> POW MOREPOWS
MOREPOWS-> POW{} 0 |
POW-> | | EXPR | FUNCEXPR
FUNC-> | | | | | | | Лексический анализатор
Лексический анализатор выделяет лексемы на основеконца строки и следующих терминальных символов, одновременно являющихсяразделителями:
+, -, *, /, ^, (,)Синтаксический анализатор
Синтаксический анализатор производит обработкупотока входных лексем методом предиктивного(предсказывающего) анализа, которыйявляется специальным видом метода рекурсивного спуска.
В данном анализаторе нетерминалам грамматикиставится в соответствие функция-обработчик. Смыслом предиктивного анализаявляется однозначное определение следующей вызываемой функции-обработчика на основетекущей лексемы.
Соответствие нетерминалов функциям-обработчикам:
POW : powNT()
FACTOR : factorNT()
TERM : termNT()
EXPR : exprNT()Взаимодействие анализаторов
В Analyser реализовано объединение проходов лексического исинтаксического анализаторов в один проход. При просмотре следующей лексемы синтаксическиманализатором вызывается функция, реализующая извлечение лексемы из входнойстроки, содержащей математическое выражение.
В данном случае это более эффективный подход сточки зрения занимаемой оперативной памяти. Если делать полный проходлексического анализатора, то в оперативной памяти, помимо входной строки сматематическим выражением, будет содержаться вектор лексем, который практическиповторяет содержимое входной строки. Поскольку синтаксическому анализатору нетребуется обозревать несколько лексем одновременно, то наличие вектора лексемне имеет смысла, значит объединение проходов анализаторов в один проходлогически обосновано.Оптимизатор
Оптимизатор делает проход по синтаксическому деревуи уменьшает количество его узлов за счет вычисления константных подвыражений слюбыми знаками и функциями, и для операций +, -, *, если подвыражения частичноявляются константными.
Если входное выражение не оптимально, содержитпеременную и требуется вычисление этого выражения на некотором множестведействительных чисел, мощность которого больше 1, то повышение скоростивыполнения программы очевидно.Алгоритм оптимизации
1) Просмотр текущего узла
2) Проверка этого узла на константность:
да:
– вычисление его значения
– освобождение памяти, выделенной дляподдерева с вершиной в этом узле
– создание нового узла, содержащеговычисленную константу
нет:
– переход к шагу 3)
3) Операция этого узла + или * (операция «–» нерассматривается, т. к. при построении синтаксического дерева бинарный «–»заменяется унарным «–». Пример: 1–2 преобразуется в 1+(-2)):
да:
– формирование векторов указателей наконстантные и неконстантные (включая не непосредственные) подузлы данного узлас той же операцией. Если встречается подузел, операция которого отличаетсяот операции данного узла, то:
– добавление указателя на этот подузел ввектор указателей на неконстантные узлы
– переход к шагу 1) для этого подузла
– вычисление результата для векторауказателей на константы
– освобождение памяти, выделенной для узлов,указатели на которые содержатся в векторе указателей на константные узлы
– построение нового поддерева на основевектора неконстант и вычисленной константы
нет:
– переход к шагу 1) для всех непосредственныхподузлов данного узлаПример оптимизации
Исходное математическое выражение:
(4^2+(2^3*2)^0.5+x*(1+2+3+4+(2*3*4*x)))+((1+2)+sin(x+1+2)) – (log (sin(x))+1)
Формат строки для синтаксического дерева в выводепрограммы имеет следующий:
()
или
() [] []
Для этой формулы неоптимизированноесинтаксическое дерево имеет вид:
Syntax Tree:(not optimized)
(0x8050da8) left=0x8050d28right=0x8050d98 op=+
(0x8050d98) right=0x8050d88op=-
(0x8050d88) left=0x8050d58right=0x8050d78 op=+
(0x8050d78)CONST=1
(0x8050d58)op=l next=0x8050d48
(0x8050d48)op=s next=0x8050d38
(0x8050d38)VAR=x
(0x8050d28) left=0x8050c38right=0x8050d18 op=+
(0x8050d18) left=0x8050c88right=0x8050d08 op=+
(0x8050d08)op=s next=0x8050cf8
(0x8050cf8) left=0x8050cc8right=0x8050ce8 op=+
(0x8050ce8)CONST=2
(0x8050cc8) left=0x8050c98right=0x8050cb8 op=+
(0x8050cb8)CONST=1
(0x8050c98)VAR=x
(0x8050c88) left=0x8050c58right=0x8050c78 op=+
(0x8050c78)CONST=2
(0x8050c58)CONST=1
(0x8050c38) left=0x8050aa8right=0x8050c28 op=+
(0x8050c28) left=0x8050ab8right=0x8050c18 op=*
(0x8050c18) left=0x8050b68right=0x8050c08 op=+
(0x8050c08) left=0x8050be8right=0x8050bf8 op=*
(0x8050bf8)VAR=x
(0x8050be8) left=0x8050bb8right=0x8050bd8 op=*
(0x8050bd8)CONST=4
(0x8050bb8) left=0x8050b88right=0x8050ba8 op=*
(0x8050ba8)CONST=3
(0x8050b88)CONST=2
(0x8050b68) left=0x8050b38right=0x8050b58 op=+
(0x8050b58)CONST=4
(0x8050b38) left=0x8050b08right=0x8050b28 op=+
(0x8050b28)CONST=3
(0x8050b08) left=0x8050ad8right=0x8050af8 op=+
(0x8050af8)CONST=2
(0x8050ad8)CONST=1
(0x8050ab8)VAR=x
(0x8050aa8) left=0x80509e8right=0x8050a98 op=+
(0x8050a98) left=0x8050a68right=0x8050a88 op=^
(0x8050a88)CONST=0.5
(0x8050a68) left=0x8050a38right=0x8050a58 op=*
(0x8050a58)CONST=2
(0x8050a38) left=0x8050a08right=0x8050a28 op=^
(0x8050a28)CONST=3
(0x8050a08)CONST=2
(0x80509e8) left=0x80509b8right=0x80509d8 op=^
(0x80509d8)CONST=2
(0x80509b8)CONST=4
nodes num: 47
Как видно из вывода, количество узлов всинтаксическом дереве равно 47.
После прохода оптимизатора дерево имеет следующийвид:
Syntax Tree:(optimized)
(0x8050da8) left=0x8050aa8right=0x8050c28 op=+
(0x8050c28) left=0x8050e08right=0x8050ab8 op=*
(0x8050ab8) VAR=x
(0x8050e08) left=0x8050b08right=0x8050c08 op=+
(0x8050c08) left=0x8050b88right=0x8050bf8 op=*
(0x8050bf8)VAR=x
(0x8050b88)CONST=24
(0x8050b08)CONST=10
(0x8050aa8) left=0x80509e8right=0x8050d08 op=+
(0x8050d08)op=s next=0x8050cf8
(0x8050cf8) left=0x8050ce8right=0x8050c98 op=+
(0x8050c98)VAR=x
(0x8050ce8)CONST=3
(0x80509e8) left=0x80509b8right=0x8050d98 op=+
(0x8050d98) right=0x8050d58op=-
(0x8050d58)op=l next=0x8050d48
(0x8050d48)op=s next=0x8050d38
(0x8050d38)VAR=x
(0x80509b8) CONST=22
nodes num: 19
Это дерево соответствует формуле:
22-log (sin(x))+sin (3+x)+x*(10+24*x)
Как видно из вывода, количество узлов всинтаксическом дереве равно 19, против 47, что приводит к повышению скоростивыполнения программы.
Сохранение синтаксического дерева в файл
Эта функциональностьдобавлена для ускорения работы с математическими выражениями. После трансляцииматематического выражения в синтаксическое дерево, есть возможность сохранитьего в том виде, в котором оно находится в оперативной памяти, в файл на жесткийдиск. Т. о. если требуется вычислить несколько математических выражений несколькораз, то их можно оттранслировать один раз, сохранить в файлы, а потом извлекатьих в виде, готовом для интерпретации, не тратя время на лексический исинтаксический анализ.
Сохранениесинтаксического дерева начинается с корня дерева и обходит дочерние узлы слева –направо с их последующим сохранением.
Аналогичнымобразом происходит извлечение дерева из файла.Интерпретатор
Интерпретаторвыполняет извлечение из файла синтаксического дерева, являющегося результатомвыполнения транслятора.
Послеизвлечения дерева интерпретатор совершает его обход. Результатом работы интерпретатораявляется число, в точности соответствующее значению математического выражения, которому,в свою очередь, эквивалентно извлеченное синтаксическое дерево.
Заключение
В работе были рассмотрены теоретические основыпостроения трансляторов.
Результатом работыявляются:
– класс Analyser, реализующий заявленнуюфункциональность
– транслятор с языка математическихвыражений на язык деревьев вывода
– интерпретатор языка деревьев вывода