Разработка лексического и синтаксического анализаторов

Оглавление введение 1.1 Структура компилятора 1.2 Стадии работы компилятора 1.3 Термины 1.4 Вывод 14 Техническое задание 2.1 Формальная грамматика для элементов объекта 18 Проектная часть 3.1 Функциональное описание. 2. Построение конечного автомата. 3.3 Определение формальной грамматики. 3.4 Построение дерева синтаксического анализа.

3.5 Синтаксические алгоритмы разбора. 3.6 Отношение предшествования 3.7 Нисходящий разбор. 31 Технологическая часть 35 Заключение 39 Листинг программы 41 ВВЕДЕНИЕ Тема курсового проектирования является разработка лексического и синтаксического анализаторов. Объектом исследования является фрагмент кода, написанного на языке программирования Visual C#. Цель проектирования – разработка программы-анализатора. Задача проектирования: Изучение методов трансляции

; Формирование и описание объекта синтаксического анализа; Построение конечного автомата; Построение таблицы переходов-выходов; Построение дерева синтаксического анализа; Построение стека для дерева синтаксического анализа; Построение формальной грамматики, левосторонней и правосторонней формальных грамматик; Построение программы анализатора для объекта. Для реализации поставленных задач было проведено исследование методов синтаксического анализа. На основе проведённого иссле

дования составлен объект, к которому будет применён синтаксический анализ. Для фрагмента построенного объекта проведено построение конечного автомата, построена таблица переходов-выходов и дерево синтаксического анализа. Результатом исследования является программа-анализатор, которая обрабатывает объект и формирует результирующий файл. Данное исследование не является исчерпывающим и может быть продолжено с применением готовых пакетов лексического анализа LEX и программы FLE

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

разработать «небольшую» программу, решающую обычно одну конкретную несложную задачу и предназначенную, чаще всего, для использования одним человеком или узкой группой людей. • Она решает одну четко поставленную задачу в хорошо известных ограничениях (не более 30000 цифр), к тому же, не очень существенную для какой-либо практической или исследовательской деятельности. • Неважно, насколько быстро она работает — на вычисление уходит не более получаса даже на устаревших компью

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

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

ход в виде архивов Надо сделать так, чтоб в индексе оставались только слова в основной грамматической форме – существительные в единственном числе и именительном падеже, глаголы в неопределенной форме. Определим 2 возможных архитектуры разбиения индексатора на два компонента. Один компонент принимает на свой вход входной текст, полностью прочитывает его и выдает на выходе список слов, из которых он состоит. Второй принимает на вход список слов, она выходе выдает его упорядоченный

вариант. Рис. 1 Диаграмма обработки входного текста АНАЛИТИЧЕСКАЯ ЧАСТЬ 1.1 Структура компилятора На начальной фазе лексического анализа входная программа, представляющая собой поток литер, разбивается на лексемы - слова в соответствии с определениями языка. Основными формализмами, лежащим в основе реализации лексических анализаторов, являются конечные автоматы и регулярные выражения. Лексический анализатор может работать в двух основных режимах: либо как подпрограмма, вызыва

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

тейшие) ошибки (недопустимые символы, неправильная запись чисел, идентификаторов и другие). Центральная задача синтаксического анализа - разбор структуры программы. Как правило, под структурой понимается дерево, соответствующее разбору в контекстно-свободной грамматике языка. В настоящее время чаще всего используется либо LL(1)-анализ (и его вариант - рекурсивный спуск), либо

LR(1)-анализ и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный спуск чаще используется при ручном программировании синтаксического анализатора, LR(1) - при использовании систем автоматического построения синтаксических анализаторов. Результатом синтаксического анализа является синтаксическое дерево со ссылками на таблицы объектов. Ошибки, связанные со структурой программы, также обнаруживаются в процессе синтаксического анализа. На этапе контекстного анализа выявляются зависимости между частя

ми программы, которые не могут быть описаны контекстно-свободным синтаксисом. Это, в основном, связи "описание-использование", в частности, анализ типов объектов, анализ областей видимости, соответствие параметров, метки и другие. В процессе контекстного анализа таблицы объектов пополняются информацией об описаниях (свойствах) объектов. Основным формализмом, используемым при контекстном анализе, является аппарат атрибутных грамматик.

Результатом контекстного анализа является атрибутированное дерево программы. Информация об объектах может быть как рассредоточена в самом дереве, так и сосредоточена в отдельных таблицах объектов. В процессе контекстного анализа также могут быть обнаружены ошибки, связанные с неправильным использованием объектов. Затем программа может быть переведена во внутреннее представление. Это делается для целей оптимизации и/или удобства генерации кода. Еще одной целью преобразования программы во внутреннее представление явл

яется желание иметь переносимый компилятор. Тогда только последняя фаза (генерация кода) является машинно-зависимой. В качестве внутреннего представления может использоваться префиксная или постфиксная запись, ориентированный граф, тройки, четверки и другие способы. Фаз оптимизации может быть несколько. Оптимизации обычно делят на машинно-зависимые и машинно-независимые, локальные и глобальные. Определенная часть машинно-зависимой оптимизации выполняется на фазе генерации кода. Глобальная оптимиз

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

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

няться. В простейшем случае однопроходного транслятора нет явной фазы генерации промежуточного представления и оптимизации, остальные фазы объединены в одну, причем нет и явно построенного синтаксического дерева. Рис. 2 «Структура взаимодействия лексического и синтаксического анализа»   1.2 Стадии работы компилятора Лексический анализатор (англ. lexical analyzer или коротко lexer) — это программа или часть программы, выполняющая лексический анализ.

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

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

окен с типом и соответственно подготовленным значением передаётся на вход синтаксического анализатора. Следующая стадия компиляции синтаксический анализ. Различаю два вида анализа: Нисходящий разбор (англ. top-down parser) — продукции грамматики раскрываются, начиная со стартового символа, до получения требуемой последовательности токенов. Восходящий разбор (англ. bottom-up parser) — продукции восстанавливаются из правых частей, начиная с токенов и

кончая стартовым символом. Метод рекурсивного спуска или нисходящий разбор — это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному LL(k) контекстно-свободной грамматикой. Это класс алгоритмов грамматического анализа, где правила формальной грамматики раскрываются, начиная со стартового символа, до получения требуемой последовательности токенов. Идея метода – для каждого нетерминального символа K строится функция, которая для любого входного слова x делает

2 вещи: – находит наибольшее начало z слова x, способное быть началом выводимого из K слова – определяет, является ли начало z выводимым из K – такая функция должна удовлетворять следующим критериям: –считывать из еще необработанного входного потока максимальное начало A, являющегося началом некоторого слова, выводимого из K –определять является ли A выводимым из K или просто невыводимым началом выводимого из

K слова В случае, если такое начало считать не удается (и корректность функции для нетерминала K доказана), то входные данные не соответствуют языку, и следует остановить разбор. Разбор заключается в вызове описанных выше функций. Если для считанного нетерминала есть составное правило, то при его разборе будут вызваны другие функции для разбора входящих в него терминалов. Дерево вызовов, начиная с самой «верхней» функции эквивалентно дереву разбора. Наиболее простой и «человечный» вариант создания анализато

ра, использующего метод рекурсивного спуска, — это непосредственное программирование по каждому правилу вывода для нетерминалов грамматики. Синтаксический LL-анализатор — нисходящий синтаксический анализатор для подмножества контекстно-свободных грамматик. Он анализирует входной поток слева направо, и строит левый вывод грамматики. Класс грамматик, для которых можно построить LL-анализатор, известен как LL-грамматики. Восходящий анализатор (bottom-up parsing) предназначен для построения дерева разбора, начиная с листьев и двигаяс

ь вверх к корню дерева разбора. Мы можем представить себе этот процесс как "свертку" исходной строки w к аксиоме грамматики. Каждый шаг свертки заключается в сопоставлении некоторой подстроки w и правой части какого-то правила грамматики и замене этой подстроки на нетерминал, являющийся левой частью правила. Если на каждом шаге подстрока выбирается правильно, то в результате мы получим правый вывод В информатике LR-анализатор — синтаксический анализатор для исходных кодов программ, написанных на

некотором языке программирования, который читает входной поток слева (Left) направо и производит наиболее правую (Right) продукцию контекстно-свободной грамматики. Используется также термин LR(k)-анализатор, где k выражает количество непрочитанных символов предпросмотра во входном потоке, на основании которых принимаются решения при анализе. Обычно k равно 1 и часто опускается. Заключительная фаза трансляции – семантический анализ, а также фаза синтеза – генерация кода (оптимизация) или интерпрет

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

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

ат много специфических моментов, касающихся особенностей проецирования традиционных объектов языков программирования на элементы архитектуры компьютера (распределение памяти под переменные, распределение регистров под промежуточные результаты и оптимизация их использования и т.п ). Конечный автомат — абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию. Существуют различные варианты зад

ания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров: где: Q — конечное множество состояний автомата; S0 — начальное состояние автомата (); F — множество заключительных (или допускающих) состояний, таких что ; Σ — допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом; δ — заданное отображение множества во множество подмножеств Q: (иногда δ назы

вают функцией переходов автомата). Автомат начинает работу в состоянии S0, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово «принимается» автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово «отвергается». Конечн

ые автоматы широко используются на практике, например в синтаксических, лексических анализаторах, и тестировании программного обеспечения на основе моделей. Диаграмма состояний (или иногда граф переходов) — графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф, вершины которого — состояния КА, ребра — переходы из одного состояния в другое, а нагрузка — символы, при которых осуществляется данный переход. Если переход из состояния S1 в S

2 может быть осуществлен при появлении одного из нескольких символов, то над дугой диаграммы (ветвью графа) должны быть надписаны все они. Таблица переходов — табличное представление функции δ. Обычно в такой таблице каждой строке соответствует одно состояние, а столбцу — один допустимый входной символ. В ячейке на пересечении строки и столбца записывается действие, которое должен выполнить автомат, если в ситуации, когда он находился в данном состоянии на входе он получил данный символ. Форм

альная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита. Различают порождающие и распознающие (или аналитические) грамматики — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит оно в язык или нет. 1.3 Термины Терминал (терминальный символ) — объект, непосредственно присутствующий в словах языка, соотве

тствующего грамматике, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»). В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII — латинские буквы, цифры и спец. символы. Нетерминал (нетерминальный символ) — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения. 1.4 Вывод Выводом назыв

ается последовательность строк, состоящих из терминалов и нетерминалов, где первой идет строка, состоящая из одного стартового нетерминала, а каждая последующая строка получена из предыдущей путем замены некоторой подстроки по одному (любому) из правил. Конечной строкой является строка, полностью состоящая из терминалов, и следовательно являющаяся словом языка. Существование вывода для некоторого слова является критерием его принадлежности к языку, определяемом

у данной грамматикой. ТЕХНИЧЕСКОЕ ЗАДАНИЕ В качестве объекта исследования берется фрагмент кода написанный на языке C#. Данный объект содержит объявление процедуры main, определение переменной целочисленного типа, и вычисление арифметических операций. Данный код выполняет простое условие – находит максимальное значение элемента из данных. void Main() { int a, b, c; int d; a = 4; b = 6; c = -3; if (b < a && c < a) { d = a; } else if (a < b && c < b) { d = b; } else if (c < a &&a

mp; b < a) { d = c; } } Для разбора данного объекта проведем следующие стадии компиляции: – лексический анализ; – синтаксический анализ; Для лексического анализа необходимо: – разработать конечный автомат для арифметической операции; – по конечному автомату составим таблицы переходов и выходов. Для синтаксического анализа необходимо: – разработать формальный язык; – по данному формальному языку разработать правила для арифметических операций. Для грамматики: –построить дерево синтаксического анализа;

–стек. Для разбора грамматик будем использовать: – левосторонний разбор; – правосторонний разбор. Объект исследования разделить на: – лексемы; – присвоить идентификатор каждой лексеме; – определить ее тип. Для арифметических операций необходимо определить: – свойства арифметических операций; – приоритеты арифметических операций; – составить грамматику для арифметических операций; – определить правила построения выражений. Разработать программу для анализа входного объекта. Программное обеспечение дол

жно выполнять следующие функции: ¬– считать из входного файла объект; – проанализировать данный объект; – создать выходной файл содержащий результат работы анализатора. Входной файл содержит объект анализа данный объект представлен в виде фрагмента кода. Выходной файл содержит лексемы входного объект, их тип и идентификаторы. Точкой входа приложения служит структура «void Main()». Тип данных то некоторый класс объектов данных вместе с набором операций для создания и работы с ними.

Существуют три спецификации типа данных: атрибуты, значения и операции. Переменная – это объект данных, который явным образом определен и именован в программе. В данной программе использовались простые переменные – именованный элементарный объект данных. Все объекты в C# принадлежат к классу Object . Операция присваивания «=» – это операция связывания объекта данных со значением. «Int» (Integer), т.е. объявлена переменная целочисленного типа, которая занимает в п

амяти 4 байта. Это наиболее распространенный элементарный тип. Ключевые слова – это имена, имеющие особое значение только в определенном контексте. В данной программе ключевым словом выступает условный оператор «if». Условный оператор «IF» Это одновариантный условный оператор. Семантика выполнения заключена в следующем: вычисляется логическое выражение, если же выражение истинно, выполняется первый оператор, если оно ложно, оператор не выполняется и управление переходит к следующему оператору. Оператор «E

LSE IF» в большинстве языков программирования таков, что оператор, следующий за ключевым словом «else» всегда относится к ближайшему предшествующему оператору. В данной программе использовалась логическое выражение «И», которая на языке программирования C# имеет вид «&&» Main Функция void Int Определители (Типы) A B C D Локальные Переменные 4 6 -3 Локальные Константы If else if Ключевые слова (Условия) < && =

Операторы ; { } () Разделители 2.1 Формальная грамматика для элементов объекта N= { T, R, Z, E , F , O, X, D} T = {<, >, = =, <=, => } R :: Z Z :: Z<E | Z>E | E F :: E = = Z | E != Z | Z E :: a | (Z) O :: if (D)OX X :: else O | e оператор if с else и без него D :: e множество (алфавит) терминальных символов T; множество (алфавит) нетерминальных символов

N; начальный нетерминальный символ R из множества N; Теперь приведем формальное определение КА в терминах дискретной математики и теории множеств. Конечный автомат определяется шестью компонентами A = { I,O,S,S0,P,D } • множество (алфавит) входных символов I={Ii}; • множество (алфавит) выходных символов O={Oj}; • множество состояний автомата

S={Sk}; • начальное состояние S0; • функция переходов P(S,I) ® S , ставящая в соответствие каждой паре «состояние - входной символ» новое состояние; • функция выходов D(S,I) ® O , ставящая в соответствие каждой паре «состояние - входной символ» выходной символ. Опишем, как выглядит работа такой системы: • КА является дискретной системой, работающей по тактам (шагам), в каждом из которых он получает на вход один из символов входного алфавита; •

Последовательность символов на входе КА образует входную цепочку; • На каждом шаге КА находится в одном из возможных состояний, которое называется текущим. Текущее состояние – единственная характеристика внутреннего описания КА, которая меняется при его работе (изменяемая память). Все остальные элементы его описания являются статическими (т.е. в любой реализации представляют собой постоянную память); • Шаг работы КА состоит в переходе из текущего состояния в новое состояние при получени

и на вход очередного символа входной цепочки. Этот переход определяется функцией переходов; • Результат работы КА заключается в записи в выходную цепочку символов, генерируемых функцией выходов КА. Т.е. параллельно с переходом в новое состояние формируется выходной символ, определяемый парой «текущее состояние – входной символ». Выходной символ может быть и пустым; Работа КА заключается в преобразовании входной цепочки символов в выходную. Закон этого преобразования определяет поведение КА.

Задача проектирования КА состоит в создании КА, обеспечивающем заданные правила преобразования цепочек. Очевидно, что отсутствие у КА внутренней памяти ограничивает его возможности по преобразованию цепочек (общепринятый термин - моделирующая способность). С другой стороны, эти же ограничения позволяют решать в общем случае многие проблемы (термин – алгоритмическая разрешимость, т.е. принципиальная возможность разработать соответствующий алгоритм). Хотя автоматы и можно представить в традиционной для алгоритма техн

ологии блок-схем (управляющие КА так и строятся на основе разметки блок-схемы алгоритма), наиболее удобной формой их представления для человека является графическая - диаграмма состояний-переходов, а для программирования и формальных преобразований – табличная. Основные элементы диаграммы состояний – переходов: • Состояние представляет собой окружность, содержащую номер или наименование состояния; • Направленная дуга, соединяющая состояния Sk и Sm, определяется значениями функций переходов и действий: если Sm=P(Sk,Ii) и

On=D(Sk,Ii), то имеется переход КА из Sk в Sm , который обозначается дугой, соединяющей эти вершины. Дуга подписывается парой символов Ii/On . Это означает, что переход по дуге при поступлении на вход символа Ii сопровождается формированием выходного символа On. Если поведение какого-либо объекта можно описать набором предложений вида: «Находясь в состоянии A, при получении сигнала S объект переходит в состояние B и при этом выполняет действие

D», то такая система будет представлять собой конечный автомат. P ; &#949; S0 1 0 S1 2 2 P ; &#949; S0 1 0 S1 2 2 P > < S0 1 0 S1 2 2 S2 1 0 D I F S0 E e S1 e Z S2 Z e P I F S0 1 0 S1 2 2 S2 1 0 D I F S0 X e S1 e X S2 O e Анализируя приведенный здесь пример диаграммы состояний-переходов и вид преобразования цепочек, м

ожно сделать вывод о поведении автомата и сущности выполняемых им преобразований. Нетрудно заметить, что получая входные цепочки, содержащие символы a и b в произвольном порядке, КА формирует аналогичные цепочки более регулярного вида. Так, из подряд идущих символов b он оставляет один, а в последовательности символов a оставляет все нечетные, кроме первого. N= { T, R, Z, E , F, O, X, D} T = { <, >, = =, <=, => }

R :: Z Z :: Z<E | Z>E | E F :: E = = Z | E != Z | Z E :: a | (Z) O :: if (D)OX X :: else O | e D :: e R ® Z ПРОЕКТНАЯ ЧАСТЬ 3.1 Функциональное описание. Для арифметических операций определим их свойства и приоритеты. Арифметические операции. «+»-плюс- арифметическая операция сложения двух и более чисел a+b, приоритет операции 2. «-»-минус - арифметическая операция вычитания двух и более чисел a-b, приоритет операции 2.

«*»-умножение – арифметическая операция умножения двух и более чисел a*b, приоритет операции 1. «/»-деление – арифметическая операция деления одного числа на другое a/b, приоритет операции 1. Объявление переменных: Переменная в традиционных (императивных) языках программирования — поименованная либо адресуемая иным способом область памяти, имя или адрес которой можно использовать для осуществления доступа к данным, находящимся в переменной (по данному адресу).

Определим набор лексем языка, обозначим тип каждой лексемы, опишем каждую лексему. Лексема Тип лексемы Описание void, int Идентификатор Определители, определяют тип переменных функций. main Идентификатор Ключевая лексема определяет начало программы. ( ) { } ; Разделители. Разделяют предложения на лексемы. Натуральное число Константа Последовательность символов, состоящая только из цифр и не начинающаяся с нуля. If else Системная ле

ксема Логические операции. = Системная лексема Оператор присвоения. Идентификатор Последовательность символов, состоящая из букв и цифр, не начинающаяся с цифры. 3.2. Построение конечного автомата. Для определения входной строки разработаем конечный автомат. Рис 4. Граф конечного автомата. Входная строка анализа d = a if b<a & c<a d = b if a<b & c <b d = c if c<a & b<a По графу конечного автомата построим таблицы переходов и выходов. Т

аблица переходов. P a b c d & S0 1 0 0 0 0 S1 0 2 0 0 0 S2 0 0 3 0 0 S3 0 0 0 4 0 S4 - - - - Выход Таблица выходов. D a b c d & S0 < – – – - S1 – if – – - S2 – – < – - S3 – – – if - S4 – – – – Выход 3.3 Определение формальной грамматики. Определим для арифметических операций формальную грамматику. Терминальный алфавит: T={'0 1 2 3 4 5 6 7 8 9 + * / ( ) ’<’}.

Нетерминальный алфавит: { ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА } Правила грамматики. ФОРМУЛА::ФОРМУЛА ЗНАК ФОРМУЛА формула есть две формулы, соединенные знаком ФОРМУЛА::ЧИСЛО формула есть число ФОРМУЛА::( ФОРМУЛА ) формула есть формула в скобках ЗНАК::< > = ! знак есть меньше или больше или равно или не равно ЧИСЛО::ЦИФРА число есть цифра ЧИСЛО::ЧИСЛО ЦИФРА число есть число и цифра

ЦИФРА::0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 цифра есть 0 или 1 или 9 Определим множество: – «ФОРМУЛА» как F; –«ЧИСЛО» как C; – «ЦИФРА» как E; – «ЗНАК» как K; Правила формальной грамматики арифметической операций построим следующим образом. F=C<K F=C>K F=K=C Построим формальную грамматику для выражения d=c if a<b & b<c. Z::U#

U::F F::a<b F::b<c F::d 3.4 Построение дерева синтаксического анализа. Дерево разбора арифметических действий: b<a & c<a a<b & c <b c<a & b<a &#8195; Дерево формального разбора грамматики. По дереву синтаксического разбора построим стек. 18 A 13 17 E 12 16 T 11 15 ) 9 14 Z 10 13 ( 9 12 E 8 11 A 10 10 E 9 9 = 9 8 Z 8 7 F 6 6 a 6 5 E 4 4 < 5

3 Z 4 2 T 2 1 Z 1 0 R 0 Правила формальной грамматике для объявления переменных: Z::U# цепочки вида:int_a,aa[],a00; U::T_S определение начинается с типа данных U::e S::aX список начинается с идентификатора X::aX продолжение идентификатора X::0X X::M идентификатор заканчивается X::[]Mпосле идентификатора может быть [] M::,S продолжение списка M::;U завершение списка, начало следующего T::int 3.5 Синтаксические алгоритмы разбора. Определим формальную грамматику для восходящего разбор

а: Z:E# E:TM E:if FE E:else FE M:<TM M:>TM M: T:FG G:==FG G:!=FG G: F:(E) F:aY F:c Y:[E] Y:(L Y: L:) L:EN) N: N:,EN Определение формальной грамматики арифметических операций: Z:E# select:(4 6 -3 E:TM select:(4 6 -3 M:<TM select:< M:>TM select:> M: select:#)] T:FG select:(a b c d G:==FG select:== G:!=FG select:!= G: select:-+#)] F:(E) select:(

F:4Y select:4 F:6Y select:6 F:-3 select:-3 Y:[E] select:[ Y:(L select:( Y: select:*/-+#)] L:) select:) L:EN) select:(4 6 -3 N: select:) NTS::ZEMTGFYLN ; множество не терминальных символов TS::#-+*/()abcd[] ; множество терминальных символов Последовательность действий магазинного автомата (МА) (состояние стека и входной строки, номер применяемого правила); stack input rule E# b<a E:TM TM# c<a T:FG FG

M# a<b F:1Y cbYGM# c<b POP symbol:1 YGM# c<a Y: GM# b<a G: M# d=a# M:+TM dbTM# d=b# POP symbol:+ TM# d=c# T:FG 4FGM# a=4# F:2Y 6YGM# b=6# POP symbol:2 -3YGM# c=-3# Y: dGM# d# POP symbol:3 GM# # G: M# # M: # # 3.6 Отношение предшествования Построить отношение предшествования – перечислить отношения предшествования, с

ледующие их каждого правила, заполнить таблицу предшествования, указав около каждого элемента отношения номер правила, из которого оно следует. Z first= a(4 last= )]4FZ E first= b(6 last= )]6FE T first= c(-3 last= )]-3FT F first= d( last= )] # L first= last= ; 3.7 Нисходящий разбор. Формальная грамматика для нисходящий разбора: Z:E# E:E<T E:E>T E:T T:T==F T:T!=F T:F F:d F:a F:b F:c

F:a[E] F:4 F:6 F:-3 L:LE, NTS::ZETFL TS::#-+*/a()[]123, Управляющая таблица для LL-анализатора D # - + * / 1 2 3 # == < < < != < < < < < < < > < < < 1 > > > > > 2 > > > > > 3 > > > > > F > > > > > T > > > = = E = = = < < < Рис 6 Работа программы Для выбранного правильного предложения записать последовательность действий магазин

ного автомата (МА) (состояние стека и входной строки, действие – перенос или свертка с номером правила, по которому она производится); reduce rule stack input >E|+ F:1 F +4# >F|+ T:F T +6# >T|+ E:T E -3# < E {a b c}|d# == E==d { a b c}|d# != F:2 E!=d { a b c}|d # >if E<F|* T:F E+T d# >else E>F|* E+T* !d# >E+

T|# E:E+T E # =# E# >E#| Z:E# Z Понятно, что любая задача преобразования цепочек символов в рамках любой грамматики может быть решена путем полного перебора всех возможных вариантов подстановок, что влечет за собой экспоненциальную (показательную) трудоемкость решения задачи, не приемлемую в реальных условиях. Любой человек, использующий транслятор, в праве ожидать, что последний не слишком уменьшает скорость работы при росте объема транслируемой программы (то есть трудоемкость близка к линейн

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

атикой - системой терминальных и нетерминальных символов и множеством правил. Анализируемая программа представляется в такой грамматике предложением языка. Задача синтаксического анализа - определить, является ли это предложение правильным и построить для него последовательность непосредственных выводов из начального символа Z, или синтаксическое дерево. Сам процесс построения дерева, равно и синтаксического анализа может быть как нисходящим, т.е. от в

ершины-предка к вершинам-потомкам с заменой левых частей правил на правые и наоборот, восходящим. В этом же контексте объясняется понятие синтаксической ошибки. Если на каком-то этапе построения синтаксического дерева встречается недопустимая или тупиковая ситуация, то построенная последовательность терминальных символов соответствует синтаксически правильной части программы, а очередной «незакрытый» терминальный символ локализуется как синтаксическая ошибка. ТЕХНОЛОГИЧЕСКАЯ

ЧАСТЬ Входными данными является файл входных данных, содержащий объект анализа. Объект построчно загружается в оперативную память. Каждая строка анализируется с помощью смоделированного программным путем конечного автомата. Конечный автомат разбивает строку на элементарные лексемы, определяет тип лексемы, и идентификатор лексемы. Входные данные: – входной файл, хранящий объект исследования; – набор лексем входного языка; После выполнения анализа программа генерирует выходной файл содержащий лексемы объекта, идент

ификатор каждой лексемы, тип лексемы. Анализатор самостоятельно определяет имена переменных, и далее при анализе определяет данный идентификатор как системную лексему. Лексема записана в файл в виде: <ЛЕКСЕМА>:<КОД ЛЕКСЕМЫ>:<ТИП ЛЕКСЕМЫ> Лексемы в файле находятся в прямой последовательности лексем объекта. Работа проводилась на языке C# вместе с .NET Framework версии 4.0 Программа написана на интерфейсе Windows

Forms. Windows Forms — название интерфейса программирования приложений (API), отвечающего за графический интерфейс пользователя и являющегося частью Microsoft .NET Framework. Данный интерфейс упрощает доступ к элементам интерфейса Microsoft Windows за счет создания обертки для существующего Win32 API в управляемом коде. Рис. 7 Главное меню программы Рис. 8 Работы программы (функция GO RE

AD) Рис. 9 Меню “О программе” Рис 10 Входной файл input.txt Рис 11 Выходной файл output.txt ЗАКЛЮЧЕНИЕ В ходе курсового проектирования выполнена разработка программы – анализатора фрагмента кода на языке C#. В первой части выполнено исследование методов лексического и синтаксического анализа. Показана методология построения конечного автомата, синтаксического дерева, формальной грамматики, левостороннего и правостороннего разбор. На основании проведенного исследована составлено

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

в. Составлена формальная грамматика, построено синтаксическое дерево, проведены нисходящие и восходящие разборы, составлены соответствующие таблицы магазинных автоматов. В третьей части дано описание программы – анализатор. Описаны выходной и выходной файл программы, алгоритм работы программы, составлена инструкция по работе с программой. Та ким образом в ходе работы показано применение методов лексического, синтаксического и семантического анализов. Список литературы [1] Т. Кормен,

Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 1999. [2] И. Соммервилл. Инженерия программного обеспечения. М.: Вильямс, 2002. [3] Е. А. Жоголев. Лекции по технологии программирования: Учебное пособие. М.: Издательский отдел факультета ВМиК МГУ, 2001. [4] Г. Буч. Объектно-ориентированный анализ и проектирование с примерами приложений на

C++. Второе издание. М.: Бином, СПб.: Невский диалект, 2000. [5] F. Buschmann, R. Meunier, H. Rohnert, P. Sommerlad, M. Stal. Pattern-Oriented Software Architecture. Wiley, 2002. [6] Э. Дж. Брауде. Технология разработки программного обеспечения. СПб.: Питер, 2004. ЛИСТИНГ ПРОГРАММЫ using System; using System.Windows.Forms; using System.IO; namespace Kursach { public partial class Form1 :

Form { public Form1() { InitializeComponent(); } private static string iPath = @"L:ТРПОinput.txt"; private static string OPath = @"L:ТРПОoutput.txt"; string[] function = { "MAIN" }; string[] type = { "VOID", "INT" }; string[] localPerem = { "A", "B", "C", "D" }; string[] localCons = { "4", "6", "-3" }; string[] key

Words = { "IF", "ELSE IF", "ELSE"}; string[] operators = { "<", "&&", "=" }; string[] razdel = { ";", "{", "}", "(", ")", "," }; StreamReader sR = new StreamReader(iPath); StreamWriter sW = new StreamWriter(OPath); private void ReadString() { listBox2.

Items.Clear(); listBox3.Items.Clear(); //создаем переменную для значения введенного текста string temp = ""; try { //проверка конца файла while (sR.EndOfStream == true) { //ВЫВОДИМ SR НА ЛИСТБОКС for (int i = 0; i < sR.ToString().Length; i++) { temp += sR.ReadLine() + " "; } char[] razdelitel = {' '}; string[] ll = temp.Split(razdelitel); foreach (string s in ll) { listBox

2.Items.Add(s); //вывод форматированного результата listBox3.Items.Add( proverka(s.ToUpper())); //вывод ответа на эту шнягу sW.WriteLine(s + " " + proverka(s.ToUpper())); } } sR.Close();//закрываем StreamReader sW.Close(); } catch { MessageBox.Show("Ошибка чтения!"); return; } } public string proverka(string vvod) { string res = ""; for (int i = 0; i<function.Length; i++) { if (vvod == function[i]) res += "

Функция"; } for (int i = 0; i < type.Length; i++) { if (vvod == type[i]) res += "Определители (Типы)"; } for (int i = 0; i < localPerem.Length; i++) { if (vvod == localPerem[i]) res = "Локальные Переменные"; } for (int i = 0; i < localCons.Length; i++) { if (vvod == localCons[i]) res += "

Локальные Константы"; } for (int i = 0; i < keyWords.Length; i++) { if (vvod == keyWords[i]) res += "Ключевые слова (Условия)"; } for (int i = 0; i < operators.Length; i++) { if (vvod == operators[i]) res += "Операторы"; } for (int i = 0; i < razdel.Length; i++) { if (vvod == razdel[i]) res += "Разделители"; } return res; } private void button1_Click(object sender,

EventArgs e) { ReadString(); } } }