Розробка нових алгоритмів реалізації з метою розробки інтелектуальної системи синтаксичного аналізу

 Дерево AST, показане на рисунку 4.1.1 є наслідком наступного фрагмента коду:

var x = "hello world!";

print x;

 

Рисунок 4.1.1 – Дерево AST

4.2 Розробка програмного забезпечення для інтелектуальної системи синтаксичного аналізу

 

При розробці структури компілятора  було використано принципи об'єктно-орієнтованого  програмування. Отже, за кожну фазу роботи компілятора відповідає окремий  модуль, який може бути легко замінений, не порушуючи цілісності програмного продукту. На рисунку 4.1 показано діаграму класів, які відповідають усім фазам роботи компілятора.

 

 

Рисунок 4.2.1 – Фази роботи компілятора

Основним  завданням сканера є розбивка тексту (потоку символів у вихідному  файлі) на частини (іменовані лексемами), які може обробити аналізатор. Сканер визначає які лексеми відсилаються аналізатору і, отже, може викидати те, що не визначено синтаксисом, наприклад коментарі. Що стосується мови «ОО», сканер цікавлять символи, числа, символи, що визначають операції (такі як додавання, множення, ділення), лапки для інкапсуляції рядків та крапки з комою.

Сканер  збирає в групи потоки пов'язаних символів, формуючи лексеми для аналізатора. Наприклад, потік символів "h e l l o w o r l d!" буде згрупований в одну лексему: "hello world!".

Генератор коду для компілятора «ОО» у великій  мірі покладається на бібліотеку Reflection.Emit для створення виконуваних збірок .NET.

Конструктор CodeGen,  встановлює інфраструктуру Reflection.Emit, яка необхідна перш ніж розпочати виведення коду. Для початку необхідно визначити ім’я збірки і передачі його компонувальнику збірки. Компілятор «ОО» використовує ім'я вихідного файлу, як ім'я збірки. Далі йде визначення ModuleBuilder - для визначення одного модуля воно використовує те ж ім'я, що і складання. Наступним кроком є визначення TypeBuilder на ModuleBuilder, щоб утримувати єдиний тип у збірці. Після настройки структури Reflection.Emit генератор покроково аналізує AST та генерує IL код.

 

4.3 Аналіз результатів тестування програми

 

У ході виконання курсового проекту  було проаналізовано основні підходи  щодо створення синтаксичного аналізатора.

Побудований у роботі синтаксичний аналізатор було включено до програми «Компілятор мови ОО». Ці задачі розв’язувались наявними на сьогодні методами.

Для тестування програмного продукту передамо на вхід компілятору текст програми з помилками, потім враховуючи повідомлення про помилки виправимо програму.

Текст програми з помилкою:

   var x = "hello world!"

  print x;

Запуск  програми виконується через командний  рядок, де перший параметр це назва  програми компілятора, другий – шлях до файлу з текстом програми.

Як  показано на рисунку 4 компілятор видає  повідомлення «expected EOF» – це означає, що було пропущено символ кінця строки «;».

 

Рисунок 4.3.1 – Повідомлення про помилку

Після виправлення тексту програми, він  виглядає так:

  var x = "hello world!"

  print x;

Після компілювання виправленої версії програми, в папці де знаходиться компілятор, з’явиться виконуємий файл з програмою.

Тестування  програми показало, що програмний продукт  виконує покладені на нього завдання, а саме сканування, синтаксичний аналіз та перетворення тексту програми у  виконуємий файл. Також компілятор реагує на помилки в тексті програми, видаючи текстове повідомлення користувачу.

5 ВИСНОВКИ

 

При розробці курсового проекту робота над ним була організована у п’ять  основних етапів:

1. Вибір предметної області та її аналіз і дослідження.
2. Вибір методу розв’язання задачі та розробка інтелектуального модуля.
3. Написання пояснювальної записки до курсового проекту.
4. Створення інтелектуального модуля та його вдосконалення.
5. Виправлення помилок, та внесення доповнень у пояснювальну записку.

При розробці курсового проекту найбільше  часу було витрачено на реалізацію двох основних підпунктів – це написання  пояснювальної записки та розробка інтелектуального модуля. Загалом було дотримано усіх правил написання  пояснювальної записки.

Так як на початку розробки курсового  проекту була чітко сформована мета проекту та основні задачі, то при  написанні пояснювальної записки  особливих проблем не виникало, на відміну від проектування програмного  комплексу, де проблем було значно більше.

У курсовому проекті розв’язано актуальну  задачу побудови інтелектуальної системи  синтаксичного аналізатора і  розроблено компілятор, який дозволяє  розробляти елементарні програми.

У ході виконання проекту отримано такі основні результати.

1. Визначено теоретичну постановку задачі розробки інтелектуальної системи синтаксичного аналізатора.

2. Розроблено визначення мови «ОО»  та її основних операторів.

3. Побудовано синтаксичний аналізатор  за допомогою LR – аналізу.

4. Включення синтаксичного аналізатора  до складу компілятора мови  «ОО».

Розроблений компілятор надає можливості виконувати базові арифметичні дії, має невелику систему типів і просту взаємодію  с користувачем через консоль.

 

6 РЕЗУЛЬТАТИ  НАУКОВИХ ДОСЛІДЖЕНЬ

 

УДК 519.855

В. А. Серебряков, М. П. Галочкин

Издательство: Едиториал УРСС

ISBN 5-8360-0242-8; 1/1/2001 г.

 

Основы конструирования компиляторов

4. Синтаксический  анализ

4.3 Предсказывающий разбор сверху-вниз

4.3.1 Алгоритм разбора сверху-вниз

Пусть дана КС-грамматика G = (N, T, P, S). Рассмотрим предсказывающий разбор (или разбор сверху-вниз) для грамматики G.

Основная задача предсказывающего разбора - определение правила вывода, которое нужно применить к  нетерминалу. Процесс предсказывающего разбора с точки зрения построения дерева разбора проиллюстрирован на рисунке 4.1.

Рисунок 4.1

Фрагменты недостроенного дерева соответствуют  сентенциальным формам. Вначале дерево состоит только из одной вершины, соответствующей аксиоме S. В этот момент по первому символу входной  цепочки предсказывающий анализатор должен определить правило S   X₁X₂... , которое должно быть применено к S. Затем необходимо определить правило, которое должно быть применено к X₁, и т.д., до тех пор, пока в процессе такого построения сентенциальной формы, соответствующей левому выводу, не будет применено правило Y   a... . Этот процесс затем применяется для следующего самого левого нетерминального символа сентенциальной формы.

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

Рисунок 4.2

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

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

Таблица анализа - это двумерный  массив M[A, a], где A - нетерминал, и a - терминал или символ $. Значением M[A, a] может  быть некоторое правило грамматики или элемент «ошибка».

Магазин может содержать последовательность символов грамматики с $ на дне. В начальный  момент магазин содержит только начальный  символ грамматики на верхушке и $ на дне.

Анализатор работает следующим  образом. Вначале анализатор находится  в конфигурации, в которой магазин  содержит S$, на входной ленте w$ (w - анализируемая  цепочка), выходная лента пуста. На каждом такте анализатор рассматривает X - символ на верхушке магазина и a - текущий  входной символ. Эти два символа  определяют действия анализатора. Имеются  следующие возможности.

1. Если X = a = $, анализатор останавливается,  сообщает об успешном окончании  разбора и выдает содержимое  выходной ленты.

2. Если X = a $, анализатор удаляет X из магазина и продвигает указатель входа на следующий входной символ.

3. Если X - терминал, и X a, то анализатор останавливается и сообщает о том, что входная цепочка не принадлежит языку.

4. Если X - нетерминал, анализатор заглядывает  в таблицу M[X, a]. Возможны два  случая:

• Значением M[X, a] является правило для X. В этом случае анализатор заменяет X на верхушке магазина на правую часть данного правила, а само правило помещает на выходную ленту. Указатель входа не передвигается.
• Значением M[X, a] является «ошибка». В этом случае анализатор останавливается и сообщает о том, что входная цепочка не принадлежит языку.

Работа анализатора может быть задана следующей программой:

do       {X=верхний символ магазина;        if (X - терминал || X=="$")            if (X==InSym)                {удалить X из магазина;                 InSym=очередной символ;                }            else error();        else /*X - нетерминал*/            if (M[X,InSym]=="X->Y1Y2...Yk")                {удалить X из магазина;                 поместить Yk,Yk-1,...Y1 в магазин                    (Y1 на верхушку);                 вывести правило X->Y1Y2...Yk;                }            else error(); /*вход таблицы M пуст*/       }    while (X!=$) /*магазин пуст*/

Пример 4.3. Рассмотрим грамматику арифметических выражений G = ({E, E', T, T', F}, {id, +, *, (, )}, P, E) с правилами:

	E   TE'		T' *FT'
	E'  +TE'		T'  e
	E'  e		F   (E)
	T   FT'		F   id

 

  Таблица предсказывающего анализатора для этой грамматики приведена на рисунке 4.3. Пустые клетки таблицы соответствуют элементу «ошибка».

Рисунок 4.3

При разборе входной цепочки id + id * id$ анализатор совершает последовательность шагов, изображенную на рис. 4.4. Заметим, что анализатор осуществляет в точности левый вывод. Если за уже просмотренными входными символами поместить символы грамматики в магазине, то можно получить в точности левые сентенциальные формы вывода. Дерево разбора для этой цепочки приведено на рисунке 4.5.

Рисунок 4.4

Рисунок 4.5

 

 

 

4.3.2 Функции FIRST и FOLLOW

При построении таблицы предсказывающего анализатора нам потребуются  две функции - FIRST и FOLLOW.

Пусть G = (N, T, P, S) - КС-грамматика. Для   - произвольной цепочки, состоящей из символов грамматики, определим FIRST( ) как множество терминалов, с которых начинаются строки, выводимые из  . Если    ^*e, то e также принадлежит FIRST( ).

Определим FOLLOW(A) для нетерминала A как множество терминалов a, которые  могут появиться непосредственно  справа от A в некоторой сентенциальной форме грамматики, т.е. множество  терминалов a таких, что существует вывод вида S  ^* Aa  для некоторых  ,     (N  T)^*. Заметим, что между A и a в процессе вывода могут находиться нетерминальные символы, из которых выводится e. Если A может быть самым правым символом некоторой сентенциальной формы, то $ также принадлежит FOLLOW(A).

Рассмотрим алгоритмы вычисления функции FIRST.

Алгоритм 4.3. Вычисление FIRST для символов грамматики.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Множество FIRST(X) для каждого символа X   (N   T).

Метод. Выполнить шаги 1-3:

• Если X - терминал, то положить FIRST(X) = {X}; если X - нетерминал, положить FIRST(X) =  .
• Если в P имеется правило X   e, то добавить e к FIRST(X).
• Пока ни к какому множеству FIRST(X) нельзя уже будет добавить новые элементы, выполнять:

если X - нетерминал и имеется правило  вывода X   Y ₁Y ₂...Y _k, то включить a в FIRST(X), если a   FIRST(Y _i) для некоторого i, 1   i   k, и e принадлежит всем FIRST(Y ₁), ..., FIRST(Y _i-1), то есть Y₁...Y _i-1  ^*e. Если e принадлежит FIRST(Y _j) для всех j = 1, 2, ..., k, то добавить e к FIRST(X).

Алгоритм 4.4. Вычисление FIRST для цепочки.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Множество FIRST(X₁X₂...X_n), X_i   (N   T).

Метод. Выполнить шаги 1-3:

• При помощи предыдущего алгоритма вычислить FIRST(X) для каждого X   (N   T).
• Положить FIRST(X₁X₂...X_n) =  .
• Добавить к FIRST(X₁X₂...X_n) все не e-элементы из FIRST(X₁). Добавить к нему также все не e-элементы из FIRST(X₂), если e   FIRST(X₁), не e-элементы из FIRST(X₃), если e принадлежит как FIRST(X₁), так и FIRST(X₂), и т.д. Наконец, добавить цепочку e к FIRST(X₁X₂...X_n), если e  FIRST(X_i) для всех i.