Министерство образования Российской Федерации.
Федеральное государственное общеобразовательное учреждение высшегопрофессионального образования
«Чувашский государственный университет имени И.Н. Ульянова»
Алатырский филиал
Курсовая работа
По предмету: «Теория вычислительных процессов и структур»
На тему: «Проектирование компилятора»
Выполнил студент
группы АФТ 61-05
Федин А. В.
Научный руководитель:
Пичугин В.Н.
Алатырь 2009
Задание вариант №9
компилятор идентификатор лексический анализатор
/>
/>
Задание №2
Входной язык содержит арифметические выражения, разделенныесимволом; (точка с запятой). Арифметические выражения состоят изидентификаторов, шестнадцатеричных чисел, знака присваивания (:=), знаковопераций +, -, *, / и круглых скобок.
Содержание
Введение
1 Организация таблиц идентификаторов
1.1 Назначение таблиц идентификаторов
1.2 Принципы организации таблиц идентификаторов
1.3 Простейшие методы построения таблиц идентификаторов
1.4 Метод простого рехэшированияс помощью произведения
2 Проектирование лексического анализатора
2.1 Назначение лексического анализатора
2.2 Таблица лексем и содержащаяся в нейинформации
2.3 Построение лексических анализаторов(сканеров)
Заключение
Список использованной литературы
Приложение 1
Приложение 2
Приложение 3
Введение
Компилятор – программный модуль, задачейкоторого является перевод программы, написанной на одном из языковпрограммирования (исходный язык) в программу на язык ассемблера или языкмашинных команд.
Большинство компиляторов переводятпрограмму с некоторого высокоуровневого языка программирования в машинный код,который может быть непосредственно выполнен компьютером.
Целью данной курсовой работы являетсяизучение составных частей, основных принципов построения и функционированиякомпиляторов, практическое освоение методов построения составных частейкомпилятора для заданного входного языка.
Курсовая работа заключается в созданииотдельных частей компилятора заданного языка.
В первой части работы ставится задачаразработать программу, которая получает на входе набор идентификаторов,организует таблицу по заданному методу и позволяет осуществить многократныйпоиск идентификатора в этой таблице. Программа должна сообщать среднее числоколлизий и среднее количество сравнений, выполняемых для поиска идентификатора.
Во второй части работы требуетсяразработать программу, которая выполняет лексический анализ входного текста позаданной грамматике и порождает таблицу лексем с указанием их типов и значений.
1 Организация таблицидентификаторов 1.1 Назначение таблиц идентификаторов
При выполнении семантического анализа,генерации кода и оптимизации результирующей программы компилятор долженоперировать характеристиками основных элементов исходной программы — переменных, констант, функций и других лексических единиц входного языка. Этихарактеристики могут быть получены компилятором на этапе синтаксическогоанализа входной программы (чаще всего при анализе структуры блоков описанийпеременных и констант), а также дополнены на этапе подготовки к генерации кода(например при распределении памяти).
Набор характеристик, соответствующийкаждому элементу исходной программы, зависит от типа этого элемента, от егосмысла (семантики) и, соответственно, от той роли, которую он исполняет висходной и результирующей программах. В каждом конкретном случае этот наборхарактеристик может быть свой в зависимости от синтаксиса и семантики входногоязыка, от архитектуры целевой вычислительной системы и от структурыкомпилятора. Но есть типовые характеристики, которые чаще всего присущи тем илииным элементам исходной программы. Например для переменной — это ее тип и адресячейки памяти, для константы — ее значение, для функции — количество и типыформальных аргументов, тип возвращаемого результата, адрес вызова кода функции.
Главной характеристикой любого элементаисходной программы является его имя. Именно с именами переменных, констант,функций и других элементов входного языка оперирует разработчик программы — поэтому и компилятор должен уметь анализировать эти элементы по их именам.
Имя каждого элемента должно бытьуникальным. Многие современные языки программирования допускают совпадения(неуникальность) имен переменных, и функций в зависимости от их областивидимости и других условий исходной программы.
Таким образом, задача компиляторазаключается в том, чтобы хранить некоторую информацию, связанную с каждымэлементом исходной программы, и иметь доступ к этой информации по имениэлемента. Для решения этой задачи компилятор организует специальные хранилищаданных, называемые таблицами идентификаторов, или таблицами символов. Таблицаидентификаторов состоит из набора полей данных (записей), каждое из которыхможет соответствовать одному элементу исходной программы. Запись содержит всюнеобходимую компилятору информацию о данном элементе и может пополняться помере работы компилятора. Количество записей зависит от способа организациитаблицы идентификаторов, но в любом случае их не может быть меньше, чемэлементов в исходной программе. В принципе, компилятор может работать не содной, а с несколькими таблицами идентификаторов — их количество и структуразависят от реализации компилятора. 1.2 Принципы организации таблиц идентификаторов
Компилятор пополняет записи в таблицеидентификаторов по мере анализа исходной программы и обнаружения в ней новыхэлементов, требующих размещения в таблице. Поиск информации в таблицевыполняется всякий раз, когда компилятору необходимы сведения о том или иномэлементе программы. Причем следует заметить, что поиск элемента в таблице будетвыполняться компилятором существенно чаще, чем помещение в нее новых элементов.Так происходит потому, что описания новых элементов в исходной программе, какправило, встречаются гораздо реже, чем эти элементы используются. Кроме того,каждому добавлению элемента в таблицу идентификаторов в любом случае будет предшествоватьоперация поиска — чтобы убедиться, что такого элемента в таблице нет.
На каждую операцию поиска элемента втаблице компилятор будет затрачивать время, и поскольку количество элементов висходной программе велико (от единиц до сотен тысяч в зависимости от объемапрограммы), это время будет существенно влиять на общее время компиляции.Поэтому таблицы идентификаторов должны быть организованы таким образом, чтобыкомпилятор имел возможность максимально быстро выполнять поиск нужной емузаписи таблицы по имени элемента, с которым связана эта запись.
Можно выделить следующие способыорганизации таблиц идентификаторов:
□ простые и упорядоченные списки;
□ бинарное дерево;
□ хэш — адресация срехэшированием;
□ хэш — адресация по методуцепочек;
□ комбинация хэш — адресации еесписком или бинарным деревом.
Далее будет дано краткое описание способаорганизации таблиц идентификаторов при помощи простого списка. 1.3 Простейшие методы построения таблиц идентификаторов
В простейшем случае таблицаидентификаторов представляет собой линейный неупорядоченный список, или массив,каждая ячейка которого содержит данные о соответствующем элементе таблицы.Размещение новых элементов в такой таблице выполняется путем записи информациив очередную ячейку массива или списка по мере обнаружения новых элементов висходной программе.
Поиск нужного элемента в таблице будет вэтом случае выполняться путём последовательного перебора всех элементов исравнения их имени с именем искомого элемента, пока не будет найден элемент стаким же именем. Тогда если за единицу времени принять время, затрачиваемоекомпилятором на сравнение двух строк (в современных вычислительных системахтакое сравнение чаще всего выполняется одной командой), то для таблицы,содержащей N элементов, в среднем будет выполнено N/2 сравнений.
Время, требуемое на добавление новогоэлемента в таблицу (Тд), не зависит от числа элементов в таблице (N). Но если Nвелико, то поиск потребует значительных затрат времени. Время поиска (Ти) втакой таблице можно оценить как Ти = O(N). Поскольку именно поиск в таблицеидентификаторов является наиболее часто выполняемой компилятором операцией,такой способ организации таблиц идентификаторов является неэффективным. Онприменим только для самых простых компиляторов, работающих с небольшимипрограммами.
Поиск может быть выполнен болееэффективно, если элементы таблицы отсортированы (упорядочены) естественнымобразом. Поскольку поиск осуществляется по имени, наиболее естественнымрешением будет расположить элементы таблицы в прямом или обратном алфавитномпорядке. Эффективным методом поиска в упорядоченном списке из N элементовявляется бинарный, или логарифмический; поиск.
Алгоритм логарифмического поисказаключается в следующем: искомый символ сравнивается с элементом (N+ 1)/2 всередине таблицы; если этот элемент не является искомым, то мы должныпросмотреть только блок элементов, пронумерованных от 1 до (N+ 1)/2 — 1, илиблок элементов от (N+ 1)/2 + 1 до N в зависимости от того, меньше или большеискомый элемент того, с которым его сравнили. Затем процесс повторяется наднужным блоком в два раза меньшего размера. Так продолжается до тех пор, покалибо искомый элемент не будет найден, либо алгоритм не дойдет до очередногоблока, содержащего один или два элемента (с которыми можно выполнить прямоесравнение искомого элемента).
Так как на каждом шаге число элементов,которые могут содержать искомый элемент, сокращается в два раза, максимальноечисло сравнений равно 1 + log2 N. Тогда время поиска элемента в таблицеидентификаторов можно оценить как Тп = O(log2 N). Для сравнения: при N=128бинарный поиск требует самое большее 8 сравнений, а поиск в неупорядоченнойтаблице — в среднем 64 сравнения. Метод называют «бинарным поиском», посколькуна каждом шаге объем рассматриваемой информации сокращается в два раза, а«логарифмическим» — поскольку время, затрачиваемое на поиск нужного элемента вмассиве, имеет логарифмическую зависимость от общего количества элементов внем.
Недостатком логарифмического поискаявляется требование упорядочивания таблицы идентификаторов. Так как массивинформации, в котором выполняется поиск, должен быть упорядочен, время егозаполнения уже будет зависеть от числа элементов в массиве. Таблицаидентификаторов зачастую просматривается компилятором еще до того, как оназаполнена, поэтому требуется, чтобы условие упорядоченности выполнялось на всехэтапах обращения к ней. Следовательно, для построения такой таблицы можнопользоваться только алгоритмом прямого упорядоченного включения элементов.
Если пользоваться стандартнымиалгоритмами, применяемыми для организации упорядоченных массивов данных, тосреднее время, необходимое на помещение всех элементов в таблицу, можно оценитьследующим образом:
Тд = O(N*log2 N) + k*O(N^2).
Здесь k — некоторый коэффициент,отражающий соотношение между временами, затрачиваемыми компьютером навыполнение операции сравнения и операции переноса данных.
При организации логарифмического поискав таблице идентификаторов обеспечивается существенное сокращение времени поисканужного элемента за счет увеличения времени на помещение нового элемента втаблицу. Поскольку добавление новых элементов в таблицу идентификаторовпроисходит существенно реже, чем обращение к ним, этот метод следует признатьболее эффективным, чем метод организации неупорядоченной таблицы. Однако вреальных компиляторах этот метод непосредственно также не используется,поскольку существуют более эффективные методы./> 1.4 Метод простого рехэширования с помощью произведения.
Для организации таблицы идентификаторов пометоду рехэширования с помощью произведения необходимо определить всехэш-функции /> длявсех /> Чащевсего функции /> определяют как некоторуюмодификацию хэш-функции h. Например, самым простым методом вычисления функции /> является ееорганизация в виде
/>
где /> — некоторое вычисляемое целоечисло, а />—максимальное значение из области значений хэш-функции h. В даннойработе положим />. Тогда получаем формулу
/>
В этом случае при совпадении значенийхэш-функции для каких-либо элементов поиск свободной ячейки в таблиценачинается последовательно от текущей позиции, заданной хэш-функцией />.
Блок-схема метода простого рехэшированияпредставлена на рисунке 1.1.
/>
Рис. 1.1 – Блок-схема метода простого рехэширования с помощьюпроизведения
а) – Блок-схема алгоритмапростого рехэширования с помощью произведения; б) – Блок-схема функциипоиска идентификатора;
в) – Блок-схема функциидобавления идентификатора
2 Проектированиелексического анализатора 2.1 Назначение лексического анализатора
Лексический анализатор (или сканер) –это часть-компилятора, которая читает литеры программы на исходном языке истроит из них слова (лексемы) исходного языка. На вход лексического анализаторапоступает текст исходной программы, а выходная информация передается длядальнейшей обработки компилятором на этапе синтаксического анализа и разбора.
Лексема (лексическая единица языка) –это структурная единица языка, которая состоит из элементарных символов языка ине содержит в своем составе других структурных единиц языка. Лексемами языковпрограммирования являются идентификаторы, константы, ключевые слова языка,знаки операций и т. п. Состав возможных лексем каждого конкретного языкапрограммирования определяется синтаксисом этого языка.
С теоретической точки зрения лексическийанализатор не является обязательной, необходимой частью компилятора. Егофункции могут выполняться на этапе синтаксического анализа. Однако существуетнесколько причин, исходя из которых в состав практически всех компилятороввключают лексический анализ.
Это следующие причины:
— упрощается работа с текстом исходнойпрограммы на этапе синтаксического разбора и сокращается объем обрабатываемойинформации, так как лексический анализатор структурирует поступающий на входисходный текст программы и удаляет всю незначащую информацию;
— для выделения в тексте и разборалексем возможно применять простую, эффективную и хорошо проработаннуютеоретически технику анализа, в то время как на этапе синтаксического анализаконструкций исходного языка используются достаточно сложные алгоритмы разбора;
— лексический анализатор отделяет сложныйпо конструкции синтаксический анализатор от работы непосредственно с текстомисходной программы, структура которого может варьироваться в зависимости отверсии входного языка — при такой конструкции компилятора при переходе от однойверсии языка к другой достаточно только перестроить относительно простойлексический анализатор.
Функции, выполняемые лексическиманализатором, и состав лексем, которые он выделяет в тексте исходной программы,могут меняться в зависимости от версии компилятора. В основном лексическиеанализаторы выполняют исключение из текста исходной программы комментариев инезначащих пробелов, а также выделение лексем следующих типов: идентификаторов,строковых, символьных и числовых констант, знаков операций, разделителей иключевых (служебных) слов входного языка.
В большинстве компиляторов лексический исинтаксический анализаторы — это взаимосвязанные части. Где провести границумежду лексическим и синтаксическим анализом, какие конструкции анализироватьсканером, а какие – синтаксическим распознавателем, решает разработчиккомпилятора. Как правило, любой анализ стремятся выполнить на этапелексического разбора входной программы, если он может быть там выполнен.Возможности лексического анализатора ограничены по сравнению с синтаксическиманализатором, так как в его основе лежат более простые механизмы. 2.2 Таблица лексем и содержащаяся в ней информация
Результатом работы лексическогоанализатора является перечень всех найденных в тексте исходной программы лексемс учетом характеристик каждой лексемы. Этот перечень лексем можно представить ввиде таблицы, называемой таблицей лексем. Каждой лексеме в таблице лексемсоответствует некий уникальный условный код, зависящий от типа лексемы, идополнительная служебная информация. Таблица лексем в каждой строке должнасодержать информацию о виде лексемы, ее типе и, возможно, значении. Обычноструктуры данных, служащие для организации такой таблицы, имеют два поля:первое — тип лексемы, второе — указатель на информацию о лексеме.
Кроме того, информация о некоторых типахлексем, найденных в исходной программе, должна помешаться в таблицуидентификаторов (или в одну из таблиц идентификаторов, если компиляторпредусматривает различные таблицы идентификаторов для различных типов лексем).
Не следует путать таблицу лексем итаблицу идентификаторов — это две принципиально разные таблицы, обрабатываемыелексическим анализатором.
Таблица лексем фактически содержит весьтекст исходной программы, обработанный лексическим анализатором. В нее входятвсе возможные типы лексем, кроме того, любая лексема может встречаться в нейлюбое количество раз. Таблица идентификаторов содержит только определенные типылексем – идентификаторы и константы. В нее не попадают такие лексемы, какключевые (служебные) слова входного языка, знаки операций и разделители. Крометого, каждая лексема (идентификатор или константа) может встречаться в таблице идентификаторовтолько один раз. Также можно отметить, что лексемы в таблице лексем обязательнорасполагаются в том же порядке, что и в исходной программе (порядок лексем вней не меняется), а в таблице идентификаторов лексемы располагаются в любомпорядке так, чтобы обеспечить удобство поиска.2.3 Построение лексическиханализаторов (сканеров)
Лексический анализатор имеет дело стакими объектами, как различного рода константы и идентификаторы (к последнимотносятся и ключевые слова). Язык описания констант и идентификаторов вбольшинстве случаев является регулярным, то есть может быть описан с помощьюрегулярных грамматик. Распознавателями для регулярных языков являются конечныеавтоматы (КА). Существуют правила, с помощью которых для любой регулярнойграмматики может быть построен КА, распознающий цепочки языка, заданного этойграмматикой.
Любой КА может быть задан с помощью пятипараметров: M(Q,∑,δ,qo,F),
где:
Q — конечное множество состоянийавтомата;
∑ — конечное множество допустимыхвходных символов (входной алфавит КА);
δ — заданное отображение множестваQ*∑ во множество подмножеств P(Q)δ: Q*∑→ P(Q) (иногдаδ называют функцией переходов автомата);
q0 Q — начальное состояние автомата;
F Q. — множество заключительныхсостояний автомата.
Другим способом описания КА являетсяграф переходов – графическое представление множества состояний и функциипереходов КА. Граф переходов КА – это нагруженный однонаправленный граф, вкотором вершины представляют состояния КА, дуги отображают переходы из одногосостояния в другое, а символы нагрузки (пометки) дуг соответствуют функцииперехода КА. Если функция перехода КА предусматривает переход из состояния q вq' по нескольким символам, то между ними строится одна дуга, которая помечаетсявсеми символами, по которым происходит переход из q в q'.
Недетерминированный КА неудобен дляанализа цепочек, так как в нем могут встречаться состояния, допускающиенеоднозначность, то есть такие, из которых выходит две или более дуги,помеченные одним и тем же символом. Очевидно, что программирование работытакого КА — нетривиальная задача. Для простого программированияфункционирования КА M(Q,∑,δ,qo,F)он должен быть детерминированным — в каждом из возможных состояний этого КА длялюбого входного символа функция перехода должна содержать не более одногосостояния.
Доказано, что любой недетерминированныйКА может быть преобразован в детерминированный КА так, чтобы их языки совпадали(говорят, что эти КА эквивалентны).
Кроме преобразования в детерминированныйКА любой КА может быть минимизирован — для него может быть построенэквивалентный ему детерминированный КА с минимально возможным количествомсостояний.
Можно написать функцию, отражающуюфункционирование любого детерминированного КА. Чтобы запрограммировать такуюфункцию, достаточно иметь переменную, которая бы отображала текущее состояниеКА, а переходы из одного состояния в другое на основе символов входной цепочкимогут быть построены с помощью операторов выбора. Работа функции должнапродолжаться до тех пор, пока не будет достигнут конец входной цепочки. Длявычисления результата функции необходимо по ее завершении проанализироватьсостояние КА. Если это одно из конечных состояний, то функция выполнена успешнои входная цепочка принимается, если нет, то входная цепочка не принадлежитзаданному языку.
Однако в общем случае задачалексического анализатора шире, чем просто проверка цепочки символов лексемы насоответствие ее входному языку. Он должен правильно определить конец лексемы(об этом было сказано выше) и выполнить те или иные действия по запоминаниюраспознанной лексемы (занесение ее в таблицу лексем). Набор выполняемыхдействий определяется реализацией компилятора. Обычно эти действия выполняютсясразу же при обнаружении конца распознаваемой лексемы.
Во входном тексте лексемы не ограниченыспециальными символами. Определение границ лексем — это выделение тех строк вобщем потоке входных символов, для которых надо выполнять распознавание. Еслиграницы лексем всегда определяются (а выше было принято именно такое соглашение), то их можно определить по заданнымтерминальным символам и по символам начала следующей лексемы. Терминальныесимволы — это пробелы, знаки операций, символы комментариев, а такжеразделители (запятые, точки е запятой и др.). Набор таких терминальных символовможет варьироваться в зависимости от входного языка. Важно отметить, что знакиопераций сами также являются лексемами и необходимо не пропустить их прираспознавании текста.
Таким образом, алгоритм работыпростейшего сканера можно описать так:
□ просматривается входной потоксимволов программы на исходном языке до обнаружения очередного символа,ограничивающего лексему;
□ для выбранной части входногопотока выполняется функция распознавания лексемы;
□ при успешном распознаванииинформация о выделенной лексеме заносится в таблицу лексем, и алгоритмвозвращается к первому этапу;
□ при неуспешном распознаваниивыдается сообщение об ошибке, а дальнейшие действия зависят от реализациисканера: либо его выполнение прекращается, либо делается попытка распознатьследующую лексему (идет возврат к первому этапу алгоритма).
Работа программы-сканера продолжается дотех пор, пока не будут просмотрены все символы программы на исходном языке извходного потока.
Заключение
В результате выполнения курсовой работыдля заданного входного языка были построены отдельные части компилятора.
В первой части работы была разработанапрограмма, которая получает на входе набор идентификаторов, организует таблицуидентификаторов методом упорядоченного списка и методом простого рехэшированияс помощью произведения, позволяет осуществить многократный поиск идентификаторав этих таблицах.
Во второй части работы была написанапрограмма, которая выполняет лексический анализ входного текста и порождаеттаблицу лексем с указанием их типов и значений.
Отдельные части компилятора, разработанныев данной курсовой работе, дают представление о технике и методах, лежащих воснове построения компиляторов.
Список использованной литературы
1. Кампапиец Р.II. Манькоп Е.В., Филатов Н.Е. Системноепрограммирование. Основы построения трансляторов: Учеб. пособие для высших исредних учебных заведений. – СПб.: КОРОНА Принт, 2000. – 256 с.
2. Системное программное обеспечение: Учебник для вузов/ А.Ю.Молчанов- СПб.: Питер, 2003.- 396 с.
3. trubetskoy1.narod.ru/index.html
Приложение 1
Задание:
Организовать таблицу идентификатором с помощью простогорехеширования с помощью произведения.
Кодпрограммы:
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics,Controls, Forms,
Dialogs, ComCtrls, StdCtrls, ExtCtrls, Grids;
type
TForm1 = class(TForm)
OpenDialog1: TOpenDialog;
Panel1: TPanel;
GroupBox1: TGroupBox;
Button1: TButton;
Memo2: TMemo;
Button2: TButton;
Edit1: TEdit;
GroupBox2: TGroupBox;
StringGrid1: TStringGrid;
Label1: TLabel;
procedure Button1Click(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure Button2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
const
hash_min=Ord('0')+Ord('0')+Ord('0');
HASH_MAX= Ord('z')+Ord('z')+Ord('z');
REHASH1 = 127;
REHASH2 =223;
var
Form1: TForm1;
lengtM:integer;
sName:string ;
Find,NumSTR:integer;
implementation
function VarHash(const sName:string):longint;
var
i:integer;
begin
for i:=1 to length(sname) do
begin
Result:=(Ord(sName[i])+Ord(sName[(Length(sName)+i) div 2]) *i{HASH_MIN}) mod (HASH_MAX — HASH_MIN+i) + HASH_MiN;
if Result
end;
end;
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
var
fName,str:string;
i:integer;
begin
form1.OpenDialog1.Execute;
fname:=form1.OpenDialog1.FileName;
form1.Memo2.Lines.loadfromfile(fName);
form1.StringGrid1.RowCount:=memo2.Lines.Count+1;
NumSTR:=memo2.Lines.Count+1;
for i:=0 to NumSTR do
begin
//Заполнение таблицы идентификаторов
str:=memo2.Lines.Strings[i];
form1.StringGrid1.Cells[2,i+1]:=(str);
stringgrid1.Cells[0,i+1]:=inttostr(i);
stringgrid1.Cells[1,i+1]:=Inttostr(VarHash(str));
end;
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
with stringgrid1 do
begin
ColCount:=3;
RowCount:=3;
cells[0,0]:='#Функции';
stringgrid1.ColWidths[1]:=110;
cells[1,0]:='Значение Функции';
stringgrid1.ColWidths[2]:=100;
cells[2,0]:='Строка';
end;
end;
procedure TForm1.Button2Click(Sender: TObject);
var i,n:integer;
begin
find:=0;
n:=VArHAsh(form1.Edit1.Text);
begin
for i:=1 to numstr do
if (strtoint(stringgrid1.Cells[1,i])=n) and(edit1.Text=stringgrid1.Cells[2,i])
then
begin
Find:=Find+1;
form1.Label1.Caption:='Найдено Элементов — '+inttostr(Find);
showmessage('Элемент '+stringgrid1.Cells[2,i]+' найден'+chr(13)+'Найдено Элементов — '+inttostr(Find));
end;
end;
end;
end.
Результат выполнения:
/>
Приложение 2
Задание:
Организовать таблицу идентификатором с помощью бинарного дерева.
Код программы:
Результат выполнения:
/>
Приложение 3
Задание:
Создать лексический анализатор арифметических выражений.
Кодпрограммы:
unit Program2;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics,Controls, Forms,
Dialogs, StdCtrls, XPMan, ComCtrls, Buttons, Grids;
type
TForm1 = class(TForm)
Memo1: TMemo;
Button1: TButton;
ListBox1: TListBox;
Button2: TButton;
PageControl1: TPageControl;
TabSheet1: TTabSheet;
TabSheet2: TTabSheet;
GroupBox1: TGroupBox;
Edit1: TEdit;
Button3: TButton;
Button4: TButton;
OpenDialog1: TOpenDialog;
Button5: TButton;
Button6: TButton;
StringGrid1: TStringGrid;
StringGrid2: TStringGrid;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
procedure Button5Click(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure Button6Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
//====================================
function StringToWords(T: string; Mode: Short; List: Tstrings =nil): integer;
var
i, z: integer;
s: string;
c: Char;
procedure Check;
begin
if (s > '') and (List nil) then
begin
List.Add(S);
z := z + 1;
end
else if (s > '') and (List = nil) then z := z + 1;
s := '';
end;
begin
i := 0;
z := 0;
s := '';
if t > '' then
begin
while i
begin
c := t[i];
case Mode of
0: {русские и английские слова}
if (c in ['a'..'z']) or (c in ['A'..'Z']) or (c in ['а'..'я']) or
(c in ['А'..'Я']) and (c ' ') then
s := s + c
else
Check;
1: {только русские слова}
if (c in ['а'..'я']) or (c in ['А'..'Я']) and (c ' ') then
s := s + c
else
Check;
2: {только английские слова}
if (c in ['a'..'z']) or (c in ['A'..'Z']) or (c in ['0'..'9']) or
(c in ['+','-','*','/']) or (c in[':','=','(',')','.','_',';','%']) and (c ' ') then
s := s + c
else
Check;
end;
i := i + 1;
end;
end;
result := z;
end;
//====================================
procedure TForm1.Button1Click(Sender: TObject);
var i, j, v: Integer;
c: Char;
begin
for i := 0 to Memo1.Lines.Count — 1 do
begin
StringToWords(Memo1.Lines.Strings[i], 2, ListBox1.Items);
end;
v := 1;
for i := 0 to ListBox1.Items.Count — 1 do
for j := 0 to StringGrid2.RowCount — 1 do
begin
if ListBox1.Items.Strings[i] = StringGrid2.Cells[0,j] then
begin
StringGrid1.RowCount := StringGrid1.RowCount + 1;
StringGrid1.Cells[0,v] := IntToStr(v);
StringGrid1.Cells[1,v] := StringGrid2.Cells[0,j];
StringGrid1.Cells[2,v] := StringGrid2.Cells[1,j];
v := v + 1;
Break;
end
else if j = StringGrid2.RowCount — 1 then
begin
StringGrid1.RowCount := StringGrid1.RowCount + 1;
StringGrid1.Cells[0,v] := IntToStr(v);
StringGrid1.Cells[1,v] := ListBox1.Items.Strings[i];
c := ListBox1.Items.Strings[i][1];
if (c in ['0'..'9']) then
StringGrid1.Cells[2,v] := 'Числовое значение'
else if ((c in ['%'])) then StringGrid1.Cells[2,v] := 'Символьная константа'
else StringGrid1.Cells[2,v] := 'Переменная';
v := v + 1;
end;
end;
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
Memo1.Clear;
ListBox1.Clear;
end;
procedure TForm1.Button3Click(Sender: TObject);
begin
if OpenDialog1.Execute then
begin
Memo1.Lines.LoadFromFile(OpenDialog1.FileName);
Edit1.Text := OpenDialog1.FileName;
end;
end;
procedure TForm1.Button4Click(Sender: TObject);
begin
if FileExists(Edit1.Text) then
Memo1.Lines.LoadFromFile(Edit1.Text)
else MessageBox(Handle, 'Файл не найден.', 'Внимание',MB_ICONINFORMATION);
end;
procedure TForm1.Button5Click(Sender: TObject);
begin
if Button5.Caption = '>' then
begin
Form1.Width := 854;
Button5.Caption := '
end
else
begin
Form1.Width := 680;
Button5.Caption := '>';
end;
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
StringGrid1.Cells[0,0] := '№ п/п';
StringGrid1.Cells[1,0] := 'Лексема';
StringGrid1.Cells[2,0] := 'Значение';
StringGrid2.Cells[0,0] := '+';
StringGrid2.Cells[1,0] := 'Операция сложения';
StringGrid2.Cells[0,1] := '-';
StringGrid2.Cells[1,1] := 'Операция вычитания';
StringGrid2.Cells[0,2] := '*';
StringGrid2.Cells[1,2] := 'Операция умножения';
StringGrid2.Cells[0,3] := '/';
StringGrid2.Cells[1,3] := 'Операция деления';
StringGrid2.Cells[0,4] := '(';
StringGrid2.Cells[1,4] := 'Открывающая скобка';
StringGrid2.Cells[0,5] := ')';
StringGrid2.Cells[1,5] := 'Закрывающая скобка';
StringGrid2.Cells[0,6] := ':-';
StringGrid2.Cells[1,6] := 'Операция присваивания';
StringGrid2.Cells[0,6] := ';';
StringGrid2.Cells[1,6] := 'Разделитель';
end;
procedure TForm1.Button6Click(Sender: TObject);
var i: Integer;
begin
for i := 1 to StringGrid1.RowCount — 1 do
StringGrid1.Rows[i].Clear;
StringGrid1.RowCount := 2;
end;
end.
Результат выполнения:
/>
/>