Государственное образовательное учреждение
высшего профессионального образования
Кубанский государственный технологический университет
(КубГТУ)
Армавирский механико-технологический институт
Кафедра внутризаводского электрооборудования и автоматики
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовому проекту
по дисциплине: Теория языков программирования
на тему: «Лексический и синтаксический анализатор языка высокого уровня»
Государственное образовательное учреждение
высшего профессионального образования
Кубанский государственный технологический университет
(КубГТУ)
Армавирский механико-технологический институт
Кафедра внутризаводского электрооборудования и автоматики
Утверждаю
Заведующий кафедрой ВЭА
Проф. ____________ В.И. Куроедов
ЗАДАНИЕ
на курсовой проект
Студенту группы____________курса__________________
специальности 230105(2204) «Программное обеспечение вычислительной техники и автоматизированных систем»
Тема проекта: «Лексический и синтаксический анализатор языка высокого уровня»
Содержание задания: Спроектировать и построить лексический и синтаксический анализаторы для заданного формального языка программирования. Построить и реализовать в лексическом анализаторе распознаватель лексем с заданной структурой: нагруженное дерево (один элемент дерева хранит один символ (букву входного алфавита) лексемы).
Учебный язык включает директиву using, функцию main(), описание переменных, констант, цикла for, операторов присваивания, арифметические операции. За основу лексики, синтаксиса и семантики учебного языка принять стандарты языка программирования С#.
Объем работы:
Пояснительная записка 35 – 40 листов
Графическая часть 2-3 листа формата А3
Рекомендуемая литература:
Ключко В.И. Теория вычислительных процессов и структур. Учебное пособие, -КубГТУ, 1998;
2. Соколов А.П. Системы программирования: теория, методы, алгоритмы: Учеб. Пособие, — М.:
Финансы и статистика, 2004. – 320 с.: ил.
Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. — СПб.: Питер, 2001. — 736 с.
Срок выполнения проекта:
с «___»____________ «___»_____________20___ г.
Срок защиты «___»____________ 20___ г.
Дата выдачи задания «___»_____________20___ г.
Дата сдача проекта на кафедру «___»_____________20___ г.
Руководитель канд. техн. наук, доцент _____________________
Задание принял студент______________________________
Нормативные ссылки
ГОСТ Р ИСО 9001-2001 Системы менеджмента качества. Требования.
ГОСТ 7.1-2003 СИБИД. Библиографическая запись. Библиографическое описание. Общие требования и правила составления.
ГОСТ 19.101-77 ЕСПД. Виды программ и программных документов.
ГОСТ 19.102-77 ЕСПД. Стадии разработки.
ГОСТ 19.103-77 ЕСПД. Обозначение программ и программных документов.
ГОСТ 19.105-78 ЕСПД. Общие требования к программным документам
ГОСТ 19.202-78 ЕСПД. Спецификация. Требования к содержанию и оформлению.
ГОСТ 19.404-79 ЕСПД. Пояснительная записка Требования к содержанию и оформлению.
ГОСТ 19.701-90 ЕСПД. Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения.
Реферат
Пояснительная записка к курсовому проекту содержит 37 листов, 8 рисунков, 3 таблицы, 9 литературных источников, 2 приложения. К пояснительной записке прилагается 1 диск с готовой программой и материалами к ней, а также графическая часть, состоящая из трех листов.
СИНТАКСИС, ЛЕКСЕМА, КОНСТАНТА, АВТОМАТ – РАСПОЗНАВАТЕЛЬ, РЕГУЛЯРНОЕ МНОЖЕСТВО, ФОРМАЛЬНАЯ ГРАМАТИКА, ТЕРМИНАЛ, НЕТЕРМИНАЛ, АВТОМАТ С МАГАЗИННОЙ ПАМЯТЬЮ
Объект: лексический и синтаксический анализатор.
Цель: практическое применение теории формальных грамматик и теории автоматов для проектирования трансляторов.
Рассмотрен синтаксис заданного языка программирования, разработана грамматика регулярных множеств. Спроектированы автоматы для лексического анализа и распознавания лексем. Разработана формальная LL(1) грамматика для заданного языка программирования, спроектирован автомат с магазинной памятью для нисходящего анализа программы. Написана программа на языке высокого уровня Microsoft Visual C++ для лексического и синтаксического анализа текста на учебном языке программирования.
Содержание
Введение
1 Синтез лексического анализатора (сканера)
1.1 Описание синтаксиса формального языка программирования
1.2 Система регулярных выражений
1.3 Распознаватели констант и служебных слов
1.4 Управляющая таблица конечного автомата лексического анализа--PAGE_BREAK--
2 Синтез синтаксического анализатора
2.1 Описание формальной грамматики
2.2 Построение множества ВЫБОР(n)
2.3 Построение управляющей таблицы
3 Описание программы
4 Результаты тестирования
5 Руководство пользователя
Заключение
Список используемой литературы
Приложение А. Листинг лексического анализатора
Приложение Б. Листинг синтаксического анализатора
Введение
Целью данного проекта является: практическое применение теории формальных грамматик и теории автоматов для проектирования трансляторов.
Задачи: написать транслирующую грамматику для учебного языка программирования; спроектировать и построить лексический анализатор; спроектировать и построить синтаксический анализатор.
Входной информацией является файл, содержащий текст программы, написанной на учебном языке.
Выходной информацией являются таблицы лексем и имен, а также подтверждение того, что код соответствует синтаксису.
Результатом курсового проекта должна быть программа-анализатор, состоящая из двух частей: лексического анализатора, разбивающего исходный текст программы на лексемы и заполняющего таблицу имен; синтаксического анализатора, проверяющего соответствие текста заданной грамматике.
1 Синтез лексического анализатора (сканера)
1.1 Описание синтаксиса формального языка программирования
Директива using позволяет в текущем пространстве имен использовать типы данных, определенные в другом пространстве имен. Синтаксис:
using System.Text;
В данном случае лексема using является ключевым словом.
С помощью ключевого слова class определяются классы. Например:
public class TestClass
{
// Определение полей и методов класса
}
Ключевое слово public определяет уровень доступности класса.
Поля класса определяются как переменные:
public class TestClass
{
public uint a, b = 35, i;
public bool c, d;
public const long int e = 9L;
}
Для каждого поля прописывается модификатор доступа (public) и тип поля (double, int или decimal).
Методы класса определяются так же, как и обычные функции:
public class TestClass
{
public int Main(Param1, Param2)
{ }
}
Как и для полей класса, для методов задается модификатор доступа и тип возвращаемого значения метода.
Тело метода класса согласно учебному языку может содержать:
–определение цикла со счетчиком:
for (; ; )
{ }
–вызовы процедур:
write ();
read ();
–операторы присваивания:
a = ;
d *= ;
f /= ;
–арифметические выражения, содержащие бинарные операции:
a = b — (c + d); продолжение
--PAGE_BREAK--
Так же в тексте программы могут содержаться многострочные комментарии:
/* многострочный
комментарий */
Для записи идентификаторов используются буквы английского языка и цифры. Идентификаторы начинаются с буквы. Целые константы записываются арабскими цифрами.
1.2 Система регулярных выражений
Для записи грамматики лексем языка применим форму Бэкуса-Наура.
Для записи идентификаторов используются буквы английского языка и цифры. Идентификаторы начинаются с буквы. Синтаксис идентификаторов определяется праволинейной регулярной грамматикой:
-> L ( 1)
-> L ( 2)
-> D ( 3)
-> е( 4)
где L — буква множества (A..Z), D — цифра множества (0..9), е — пустая цепочка или символ окончания лексемы.
Целые константы записываются арабскими цифрами.
Праволинейная грамматика целого числа:
→ +|-
→ н
→ н|е
1.3 Распознаватели констант и служебных слов
Заданная грамматика может бать реализована автоматом со следующими состояниями:
S — состояние ожидания первого символа лексемы;
I — состояние ожидания символов идентификаторов: буквы, цифры;
С — состояние ожидания символов целой части числа;
E -состояние ошибки;
R — состояние допуска лексемы.
Автомат переходит в допустимое состояние R из состояния I для идентификаторов и из состояния C для чисел.
Регулярная грамматика для заданных условий записи лексем задается следующими множествами:
Р: [P1, P2, … ,P4] – множество правил;
G: [S, I, C, E, R] – множество состояний, где S – начальный символ;
[0..9, A..Z, «–», «#», «(», «)», «*», «,», «.», «/», «:», «;», «{«, «}», «+», «=»] – множество входных символов, из них разделительные символы и уникальные лексемы [«–», «#», «(», «)», «*», «,», «/», «:», «;», «{«, «}», «+», «=»].
Символы пробел и табуляции означают конец лексемы. Эти символы не является лексемой и требуют выполнения операции «СДВИГ» над входной строкой. По символу пробел автомат допускает лексему и переходит в начальное состояние анализа следующего символа входной строки автомата.
Символы: «–», «#», «(», «)», «*», «,», «/», «:», «;», «{«, «}», «+», «=» являются одновременно разделительными знаками и началом следующей лексемы, даже если перед ними нет символа конца лексемы. Операция «СДВИГ» после этих символов не требуется, автомат допускает лексему и переходит в начальное состояние для анализа этих же символов.
Таблица 1 – Таблица переходов автомата распознавателя идентификаторов
L
D
e
S
I
E
S
Нач. состояние
I
I
I
R
E
Ошибка
R
Допустить
Идентификация служебных слов реализована автоматом распознавателя: нагруженное дерево (Рисунок 1). Множествослужебныхслов: BREAK CLASS CONST CONTINUE LONG INT BOOL FOR UINT PUBLIC READ USING WRITE.
Рисунок 1 – Нагруженное дерево (часть)
Структура данных для формирования нагруженного дерева:
protected struct KeywordTree
{
public bool bIsWordEnd;
public char cLetter;
public List pNextList;
}
KeywordTree pKeywordsList;
Процедура заполнения нагруженного дерева:
private void Form1_Load(object sender, EventArgs e)
{String[] KeyWords = {«BREAK», «CLASS», «CONST», «CONTINUE», «LONG», «BOOL», «FOR»,
«INT», «UINT», «PUBLIC», «READ», «USING», «WRITE»};
KeywordTree p, q;
pKeywordsList = new KeywordTree();
pKeywordsList.cLetter = '#';
pKeywordsList.pNextList = new List();
pKeywordsList.bIsWordEnd = true;
for(int i = 0; i продолжение
--PAGE_BREAK--
{String KeyWord = KeyWords[i];
p = pKeywordsList;
for (int j = 0; j
{if (p.pNextList.Count == 0)
{q = new KeywordTree();
q.cLetter = KeyWord[j];
q.pNextList = new List();
//если последний символ в ключ. слове
q.bIsWordEnd = (j + 1 == KeyWord.Length)? (q.bIsWordEnd =
true): (q.bIsWordEnd = false);
p.pNextList.Add(q);
p = q;
}
else
{bool bIsAlready = false;
for (int k = 0; k
if (p.pNextList[k].cLetter == KeyWord[j])
{bIsAlready = true;
p = p.pNextList[k];
break;
}
if (bIsAlready == false)
{q = new KeywordTree();
q.cLetter = KeyWord[j];
q.pNextList = new List();
q.bIsWordEnd = false;
p.pNextList.Add(q);
p = q;
}}}}}
Функция идентификации служебных слов:
private bool IsKeyword(String sLexeme)
{int j, k;
KeywordTree p = pKeywordsList;
for (j = 0; j
{if (p.pNextList.Count == 0) break;
else
{bool bIsFound = false;
for (k = 0; k
if (p.pNextList[k].cLetter == sLexeme[j])
{bIsFound = true;
p = p.pNextList[k];
break;
}
if (!bIsFound) break;
}}
return ((j == sLexeme.Length) && (p.bIsWordEnd));
}
1.4 Управляющая таблица конечного автомата лексического анализа
Управляющая таблица лексического анализатора для заданной выше грамматики показана в таблице 2. Листинг программы, реализующей данную управляющую таблицу, приведен в приложении А.
При составлении таблицы использовались следующие обозначения:
– первым символом указывается состояние, в которое переходит автомат при поступлении соответствующего символа;
– символ «+» означает добавление входного символа к лексеме;
– символ «>>» означает сдвиг входной строки на один символ.
Таблица 2 – Управляющая таблица конечного автомата лексического анализатора
Spaces
Letters
Digits
Symbols
S
S, >>
I, +, >>
C, +, >>
R, +, >>
C
R
E
C, +, >>
R
I
R
I, +, >>
I, +, >>
R продолжение
--PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK--
const
ID
(
,
=
;
ID
,
=
)
for break continue write read ID
;
}
for
break
continue
write
read
ID
=
*
/
(
ID
NUM
+
-
ID; ) =
(
( ID NUM
>
=
; )
2.3 Построение управляющей таблицы
Для составления управляющей таблицы (таблица 4) необходимо определить множество магазинных символов, множество символов поступающих на вход автомата и определить операции МПА для каждой пары: верхний символ магазина – символ на входе автомата.
Множество магазинных символов включает все нетерминальные символы, символ дна магазина и терминальные символы за исключением тех, которые занимают в правых частях правил только первые позиции: # ( ); { } = decimal ID.
Множество символов входной строки включает все терминальные символы и символ конца строки: – # ( ) *,. /; { } + break class const continue decimal double for ID int NUM public read using writeline.
При построении таблицы использовались следующие обозначения и сокращения:
– Выт. – вытолкнуть верхний символ из магазина;
– Сдв. – сдвинуть входную строку на одну лексему;
– Зам. (n, m) – заменить верхний символ магазина на символы правила номер n, начиная с символа m;
– ДОП. – синтаксический анализ прошел успешно.
Листинг программы, реализующей данную управляющую таблицу, приведен в приложении А.
3 Описание программы
Программа выполнена в виде Windows-приложения с оконным интерфейсом (рисунок 2 в среде MicrosoftVisualStudio.
/>
Рисунок 2 — Интерфейс программы
Листинг программы на формальном языке программирования загружается из текстового файла. Результаты работы обоих анализаторов (лексического и синтаксического) отображаются в виде таблиц с помощью компоненты ListView(рисунок 3).
/> продолжение
--PAGE_BREAK--
Рисунок 3 — Компонента ListView
Для распознавания ключевых слов используется собственная структура данных, позволяющая реализовать нагруженое дерево (структура определена в п. 2.2).
Программа состоит из нескольких процедур и функций, наиболее важными из которых являются: процедура лексического анализа и процедура синтаксического анализа. Обе они приведены в приложении А. Данные процедуры служат соответствующими обработчиками кнопок «Лексический анализ» и «Синтаксический анализ».
Обмен данными между процедурами анализаторов осуществлен с помощью компонент ListView. Лексический анализатор добавляет в компонент ListView распознанные лексемы, а по завершении анализа эти лексемы в виде таблицы передаются на вход синтаксического анализатора.
4 Результаты тестирования
Для тестирования программы использовался следующий код на формальном языке программирования:
using System.Text;
/* многострочный
комменатрий */
public class TestClass
{
public uint a, b = 35, i;
public bool c, d;
public const long int e = 9L;
public uint Main(Param1, Param2)
{
read(a, b);
for(i = 0; i
{
write(a, b, c, d, e);
a = b — (c + 2L);
d *= e — 2;
e /= 123;
break;
};
for(i = 0; i
}
}
Результаты работы лексического и синтаксического анализаторов показаны на рисунке 4. В качестве результата лексического анализатора представлены две таблицы: таблица лексем и таблица имен. В первой отображены все распознанные лексемы и их класс. Во второй — имена переменных. На выходе синтаксического анализатора получается одна таблица, на которой показан весь процесс анализа, а именно: верхний символ магазина, символ входной лексемы и ее класс.
/>
Рисунок 4 — Результат работы анализаторов.
Для проверки правильной работоспособности программы, допустим ошибку в коде:
publicboolc, 1d;
В результате программа выдаст сообщение об ошибке на этапе лексического анализа (рисунок 5).
/>
Рисунок 5 — Ошибка на этапе лексического анализа.
Для проверки синтаксического анализатора, сделаем еще одну ошибку:
public const int e = 9L;
На рисунке 6 показан результат работы синтаксического анализатора.
/>
Рисунок 6 — Ошибка на этапе синтаксического анализа.
5 Руководство пользователя
Программа запускается из файла Leks_Analizator.exe. В интерфейсе программы присутствуют четыре кнопки (рисунок 7). При нажатии на кнопку «Загрузить пример кода» (рисунок 7) пользователю будет дана возможность загрузки кода. Также код можно ввести с клавиатуры.
/>
Рисунок 7 — Интерфейс программы
/>
Рисунок 8 — Диалог загрузки файла
После ввода кода программы, при нажатии на кнопку «Лексический анализ», запускается процесс анализа. Результатом анализа будет строчка внизу формы.
По кнопке «Синтаксический анализ» запускается процесс анализа. Результат отображается внизу формы.
При нажатии на кнопке «Общий анализ» будет запущен по порядку лексический анализ, а затем синтаксический анализ.
Заключение
В данном курсовом проекте была разработана программа-анализатор, состоящая из двух частей: лексического анализатора, разбивающего исходный текст программы на лексемы и заполняющего таблицу имен; синтаксического анализатора, проверяющего соответствие текста заданной грамматике.
В ходе выполнения курсового проекта были получены следующие результаты:
написана грамматика для учебного языка программирования;
спроектирован и построен лексический анализатор;
спроектирован и построен синтаксический анализатор.
Для написания курсовой работы мною были самостоятельно изучены литературные и справочные материалами по данной теме.
Список используемой литературы
1. Ключко В.И. Теория вычислительных процессов и структур. Учебное пособие, -КубГТУ, 1998.
2. Теория вычислительных процессов и структур. Методические указания к курсовой работе для студентов специальности 220400. Составитель проф. В.И.Ключко. -КубГТУ,1997. -27 с.
3. Соколов А.П. Системы программирования: теория, методы, алгоритмы: Учеб. Пособие, — М.: Финансы и статистика, 2004. – 320 с.: ил.
4. Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. – СПб.: Питер, 2001. – 736 с.
5. Ахо А, Сети Р., Ульман Д. Компиляторы: принципы, технологии инструменты.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003. – 768 с.: ил. ISBN5-8459-0189-8(рус), ББК 32.973.26.-018.2.75
6. Вольфенгаген В.Э. Конструкции языков программирования. Приемы описания. — М.: АО «Центр ЮрИнфоР», 2001.-276 с.
7. Карпов В.Э. Теория компиляторов. Учебное пособие — Московский государственный институт электроники и математики. М., 2001. – 79 с (электронный вариант) продолжение
--PAGE_BREAK--
8. Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman. Compilers Principles, Techniques, and Tools. 2000. (электронный вариант).
9. Серебряков В.А. Лекции по конструированию компиляторов. Москва, 1993 (электронный вариант).
Приложение А
Листинг лексического анализатора
private void btnLex_Click(object sender, EventArgs e)
{
char[] Letters={'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'G',
'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
'U', 'V', 'W', 'X', 'Y', 'Z', '_'};
char[] Digits={'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
char[] Symbols={',', ';', '(', ')', '=', '', '{', '}', '.', '+', '-', '*', '/'};
char[] Spaces={' ', char.Parse(Char.ConvertFromUtf32(9))};
LexAnalizerState CommentState = LexAnalizerState.Start;
lvLexTable.Items.Clear();
lvIdTable.Items.Clear();
lLexProgress.Text = «Лексический анализ завершен успешно!»;
lLexProgress.ForeColor = Color.Blue;
lLexProgress.Visible = false;
for (int nNumStr = 0; nNumStr
{
String sSrcLine = rSrcFile.Lines[nNumStr].ToUpper();
if (String.IsNullOrEmpty(sSrcLine)) continue;
int nSrcSymbol = 0;
String sLexeme = "", sClass = "";
LexAnalizerState LexState = CommentState;
while(LexState != LexAnalizerState.Stop)
{
switch(LexState)
{
case LexAnalizerState.Start:
{
if (sSrcLine[nSrcSymbol] == '/')
{
sLexeme += sSrcLine[nSrcSymbol];
nSrcSymbol++;
LexState = LexAnalizerState.Comment;
}
else if (Array.IndexOf(Spaces, sSrcLine[nSrcSymbol]) != -1)
{
nSrcSymbol++;
LexState = (nSrcSymbol == sSrcLine.Length)?
(LexAnalizerState.Stop):(LexAnalizerState.Start);
}
else if (Array.IndexOf(Letters, sSrcLine[nSrcSymbol]) != -1)
{
LexState = LexAnalizerState.Identify;
}
else if (Array.IndexOf(Symbols, sSrcLine[nSrcSymbol]) != -1)
{
sLexeme += sSrcLine[nSrcSymbol];
sClass = «Символ»;
nSrcSymbol++;
LexState = LexAnalizerState.Ready;
}
else if (Array.IndexOf(Digits, sSrcLine[nSrcSymbol]) != -1)
{
sLexeme += sSrcLine[nSrcSymbol];
nSrcSymbol++;
LexState = LexAnalizerState.Num;
}
else LexState = LexAnalizerState.Error;
}
break;
case LexAnalizerState.Comment:
{
if (sSrcLine[nSrcSymbol] == '*')
{
sLexeme = "";
sClass = "";
nSrcSymbol++;
LexState = (nSrcSymbol == sSrcLine.Length)?
(LexAnalizerState.Stop):(LexAnalizerState.CommentStart);
CommentState = LexAnalizerState.CommentStart;
}
else
{
LexState = LexAnalizerState.Ready;
CommentState = LexAnalizerState.Start;
sClass = «Символ»;
}
}
break;
case LexAnalizerState.CommentStart:
{
if (sSrcLine[nSrcSymbol] == '*')
{
nSrcSymbol++; продолжение
--PAGE_BREAK--
LexState = (nSrcSymbol == sSrcLine.Length)?
(LexAnalizerState.Stop):(LexAnalizerState.CommentEnd);
CommentState = LexAnalizerState.CommentEnd;
}
else
{
nSrcSymbol++;
LexState = (nSrcSymbol == sSrcLine.Length)?
(LexAnalizerState.Stop):(LexAnalizerState.CommentStart);
}
}
break;
case LexAnalizerState.CommentEnd:
{
if (sSrcLine[nSrcSymbol] == '/')
{
nSrcSymbol++;
LexState = (nSrcSymbol == sSrcLine.Length)?
(LexAnalizerState.Stop):(LexAnalizerState.Start);
CommentState = LexAnalizerState.Start;
}
else
{
nSrcSymbol++;
LexState = (nSrcSymbol == sSrcLine.Length)?
(LexAnalizerState.Stop):(LexAnalizerState.CommentStart);
CommentState = LexAnalizerState.CommentStart;
}
}
break;
case LexAnalizerState.Identify:
{
if ((Array.IndexOf(Digits, sSrcLine[nSrcSymbol]) != -1)
|| (Array.IndexOf(Letters, sSrcLine[nSrcSymbol]) != -1))
{
sLexeme += sSrcLine[nSrcSymbol];
nSrcSymbol++;
LexState = (nSrcSymbol == sSrcLine.Length)?
(LexAnalizerState.Ready):(LexAnalizerState.Identify);
}
else if ((Array.IndexOf(Spaces, sSrcLine[nSrcSymbol]) != -1)
|| (Array.IndexOf(Symbols, sSrcLine[nSrcSymbol]) != -1))
{
LexState = LexAnalizerState.Ready;
}
else LexState = LexAnalizerState.Error;
sClass = «Идентификатор»;
}
break;
case LexAnalizerState.Num:
{
if (Array.IndexOf(Digits, sSrcLine[nSrcSymbol]) != -1)
{
sLexeme += sSrcLine[nSrcSymbol];
nSrcSymbol++;
LexState = (nSrcSymbol == sSrcLine.Length)?
(LexAnalizerState.Ready):(LexAnalizerState.Num);
}
else if (sSrcLine[nSrcSymbol] == 'L')
{
sLexeme += sSrcLine[nSrcSymbol];
nSrcSymbol++;
LexState = LexAnalizerState.Ready;
}
else if ((Array.IndexOf(Spaces, sSrcLine[nSrcSymbol]) != -1)
|| (Array.IndexOf(Symbols, sSrcLine[nSrcSymbol]) != -1))
{
LexState = LexAnalizerState.Ready;
}
else LexState = LexAnalizerState.Error;
sClass = «Число»;
}
break;
case LexAnalizerState.Ready:
{
sClass = (IsKeyword(sLexeme) == true)?(«Ключевое слово»):(sClass);
if (sClass == «Идентификатор») AddId(sLexeme);
AddLexeme(sLexeme, sClass);
sLexeme = "";
LexState = (nSrcSymbol == sSrcLine.Length)?
(LexAnalizerState.Stop):(LexAnalizerState.Start);
}
break;
case LexAnalizerState.Error:
{
lLexProgress.Text = «ОШИБКА! Неизвестный символ (» +
(nNumStr + 1).ToString() + ", " + (nSrcSymbol + 1).ToString() +
"): \"" + sSrcLine[nSrcSymbol].ToString() + "\"";
lLexProgress.ForeColor = Color.Red; продолжение
--PAGE_BREAK--
LexState = LexAnalizerState.Stop;
}
break;
}
}
}
AddLexeme("#", «Конец»);
lLexProgress.Visible = true;
btnSintax.Enabled = true;
синтаксическийАнализToolStripMenuItem.Enabled = true;
}
Приложение Б.
Листинг синтаксического анализатора
private void btnSintax_Click(object sender, EventArgs e)
{
string[,] Grammatic = {
/*0*/{"", «USING», "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*1*/{"", «PUBLIC», "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*2*/{"", ";", "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*3*/{"", «e», "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*4*/{"",«ID», "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*5*/{"",".", "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*6*/{"",«e», "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*7*/{"", «CLASS», «ID», "{", "", "}", "", "", "", "", "", "", "", "", ""},
/*8*/{"",«PUBLIC», "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*9*/{"", ";", "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*10*/{"", «e», "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*11*/{"", «UINT», "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*12*/{"", «BOOL», "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*13*/{"", «CONST», «LONG», «INT», "", "", "", "", "", "", "", "", "", "", ""},
/*14*/{"", «ID», "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*15*/{"", "(", "", ")", "{", "", "}", "", "", "", "", "", "", "", ""},
/*16*/{"", ",", "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*17*/{"", "=", "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*18*/{"", «e», "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*19*/{"", «ID», "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*20*/{"", ",", "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*21*/{"", "=", "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*22*/{"", «e», "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*23*/{"", "", "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*24*/{"", ";", "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*25*/{"", «e», "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*26*/{"", «FOR», "(", «ID», "=", "", ";", "", ";", «ID», "", ")", "{", "", "}"},
/*27*/{"", «break», "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*28*/{"", «continue», "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*29*/{"", «WRITE», "(", "", ")", "", "", "", "", "", "", "", "", "", ""},
/*30*/{"", «READ», "(", "", ")", "", "", "", "", "", "", "", "", "", ""},
/*31*/{"", «ID», "", "", "", "", "", "", "", "", "", "", "", "", ""}, продолжение
--PAGE_BREAK--
/*32*/{"", "=", "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*33*/{"", "*", "=", "", "", "", "", "", "", "", "", "", "", "", ""},
/*34*/{"", "/", "=", "", "", "", "", "", "", "", "", "", "", "", ""},
/*35*/{"", "(", "", ")", "", "", "", "", "", "", "", "", "", "", ""},
/*36*/{"", «ID», "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*37*/{"", «NUM», "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*38*/{"", "+", "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*39*/{"", "-", "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*40*/{"", «e», "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*41*/{"", "(", "", ")", "", "", "", "", "", "", "", "", "", "", ""},
/*42*/{"", "", "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*43*/{"", ">", "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*44*/{"", "", "", "", "", "", "", "", "", "", "", "", "", ""},
/*45*/{"", "=", "=", "", "", "", "", "", "", "", "", "", "", "", ""},
/*46*/{"", «e», "", "", "", "", "", "", "", "", "", "", "", "", ""},
};
System.Collections.Stack SintaxStack = new System.Collections.Stack();
SintaxStack.Push("#");
SintaxStack.Push("");
String sTopStack, sLexeme, sClass;
SinAnalizerState SintaxState = SinAnalizerState.InProcess;
lSinProgress.Visible = false;
lvSinTable.Items.Clear();
int nLexNum = 0;
while (SintaxState == SinAnalizerState.InProcess)
{
sTopStack = (String) SintaxStack.Peek();
sLexeme = lvLexTable.Items[nLexNum].SubItems[0].Text;
sClass = lvLexTable.Items[nLexNum].SubItems[1].Text;
String[] subItems = {sTopStack, sLexeme, sClass};
lvSinTable.Items.Add(new ListViewItem(subItems));
if (sTopStack == "#")
{
SintaxState = (sLexeme == "#")?(SinAnalizerState.Accept):(SinAnalizerState.Error);
}
else if (sTopStack == "")
{
if (sLexeme == "#")
{
SintaxStack.Pop();
}
else if (sLexeme == «PUBLIC»)
{
Replace(SintaxStack, Grammatic, 1, 2);
nLexNum++;
}
else if (sLexeme == «USING»)
{
Replace(SintaxStack, Grammatic, 0, 2);
nLexNum++;
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == «LONG»)
{
if (sLexeme == «LONG»)
{
SintaxStack.Pop();
nLexNum++;
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == «INT»)
{
if (sLexeme == «INT»)
{ продолжение
--PAGE_BREAK--
SintaxStack.Pop();
nLexNum++;
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "(")
{
if (sLexeme == "(")
{
SintaxStack.Pop();
nLexNum++;
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == ")")
{
if (sLexeme == ")")
{
SintaxStack.Pop();
nLexNum++;
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == ";")
{
if (sLexeme == ";")
{
SintaxStack.Pop();
nLexNum++;
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "{")
{
if (sLexeme == "{")
{
SintaxStack.Pop();
nLexNum++;
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "}")
{
if (sLexeme == "}")
{
SintaxStack.Pop();
nLexNum++;
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "")
{
if (sLexeme == «PUBLIC»)
{
Replace(SintaxStack, Grammatic, 8, 2);
nLexNum++;
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "")
{
if (sLexeme == «CLASS»)
{
Replace(SintaxStack, Grammatic, 7, 2);
nLexNum++;
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "")
{
if (sClass == «Идентификатор»)
{
Replace(SintaxStack, Grammatic, 14, 2);
nLexNum++;
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "")
{
if (sLexeme == «UINT»)
{
Replace(SintaxStack, Grammatic, 11, 2);
nLexNum++;
}
else if (sLexeme == «BOOL»)
{ продолжение
--PAGE_BREAK--
Replace(SintaxStack, Grammatic, 12, 2);
nLexNum++;
}
else if (sLexeme == «CONST»)
{
Replace(SintaxStack, Grammatic, 13, 2);
nLexNum++;
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "")
{
if (sLexeme == "(")
{
Replace(SintaxStack, Grammatic, 35, 2);
nLexNum++;
}
else if (sClass == «Идентификатор»)
{
Replace(SintaxStack, Grammatic, 36, 2);
nLexNum++;
}
else if (sClass == «Число»)
{
Replace(SintaxStack, Grammatic, 37, 2);
nLexNum++;
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "")
{
if (sLexeme == "/")
{
Replace(SintaxStack, Grammatic, 34, 2);
nLexNum++;
}
else if (sLexeme == "*")
{
Replace(SintaxStack, Grammatic, 33, 2);
nLexNum++;
}
else if (sLexeme == "=")
{
Replace(SintaxStack, Grammatic, 32, 2);
nLexNum++;
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "")
{
if (sLexeme == ";")
{
Replace(SintaxStack, Grammatic, 9, 2);
nLexNum++;
}
else if (sLexeme == "}")
{
SintaxStack.Pop();
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "")
{
if (sLexeme == "(")
{
Replace(SintaxStack, Grammatic, 15, 2);
nLexNum++;
}
else if (sLexeme == ",")
{
Replace(SintaxStack, Grammatic, 16, 2);
nLexNum++;
}
else if (sLexeme == "=")
{
Replace(SintaxStack, Grammatic, 17, 2);
nLexNum++;
}
else if (sLexeme == ";")
{
SintaxStack.Pop();
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "")
{ продолжение
--PAGE_BREAK--
if (sLexeme == ";")
{
Replace(SintaxStack, Grammatic, 24, 2);
nLexNum++;
}
else if (sLexeme == "}")
{
SintaxStack.Pop();
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "")
{
if (sLexeme == ".")
{
Replace(SintaxStack, Grammatic, 5, 2);
nLexNum++;
}
else if (sLexeme == ";")
{
SintaxStack.Pop();
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "")
{
if (sLexeme == ",")
{
Replace(SintaxStack, Grammatic, 20, 2);
nLexNum++;
}
else if (sLexeme == "=")
{
Replace(SintaxStack, Grammatic, 21, 2);
nLexNum++;
}
else if ((sLexeme == ")") || (sLexeme == ";"))
{
SintaxStack.Pop();
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "")
{
if (sLexeme == ";")
{
Replace(SintaxStack, Grammatic, 2, 2);
nLexNum++;
}
else if (sLexeme == "#")
{
SintaxStack.Pop();
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "")
{
if ((sLexeme == «FOR») ||
(sLexeme == «CONTINUE») ||
(sLexeme == «BREAK») ||
(sLexeme == «READ») ||
(sLexeme == «WRITE») ||
(sClass == «Идентификатор»))
{
Replace(SintaxStack, Grammatic, 23, 1);
}
else if (sLexeme == "}")
{
SintaxStack.Pop();
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "")
{
if (sLexeme == "+")
{
Replace(SintaxStack, Grammatic, 38, 2);
nLexNum++;
}
else if (sLexeme == "-")
{
Replace(SintaxStack, Grammatic, 39, 2);
nLexNum++;
}
else if ((sLexeme == ")") || продолжение
--PAGE_BREAK--
(sLexeme == ";") ||
(sLexeme == ",") ||
(sLexeme == ">") ||
(sLexeme == "
(sLexeme == "="))
{
SintaxStack.Pop();
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "")
{
if (sLexeme == «FOR»)
{
Replace(SintaxStack, Grammatic, 26, 2);
nLexNum++;
}
else if (sLexeme == «BREAK»)
{
SintaxStack.Pop();
nLexNum++;
}
else if (sLexeme == «CONTINUE»)
{
SintaxStack.Pop();
nLexNum++;
}
else if (sLexeme == «READ»)
{
Replace(SintaxStack, Grammatic, 30, 2);
nLexNum++;
}
else if (sLexeme == «WRITE»)
{
Replace(SintaxStack, Grammatic, 29, 2);
nLexNum++;
}
else if (sClass == «Идентификатор»)
{
Replace(SintaxStack, Grammatic, 31, 2);
nLexNum++;
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "")
{
if (sClass == «Идентификатор»)
{
Replace(SintaxStack, Grammatic, 4, 2);
nLexNum++;
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "")
{
if (sLexeme == "(")
{
Replace(SintaxStack, Grammatic, 41, 2);
nLexNum++;
}
else if ((sClass == «Идентификатор») ||
(sClass == «Число»))
{
Replace(SintaxStack, Grammatic, 42, 1);
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "")
{
if (sLexeme == ">")
{
Replace(SintaxStack, Grammatic, 43, 2);
nLexNum++;
}
else if (sLexeme == "
{
Replace(SintaxStack, Grammatic, 44, 2);
nLexNum++;
}
else if (sLexeme == "=")
{
Replace(SintaxStack, Grammatic, 45, 2);
nLexNum++;
}
else if ((sLexeme == ")") || продолжение
--PAGE_BREAK--
(sLexeme == ";"))
{
SintaxStack.Pop();
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "")
{
if (sClass == «Идентификатор»)
{
Replace(SintaxStack, Grammatic, 19, 2);
nLexNum++;
}
else if (sLexeme == ";")
{
SintaxStack.Pop();
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == "=")
{
if (sLexeme == "=")
{
SintaxStack.Pop();
nLexNum++;
}
else SintaxState = SinAnalizerState.Error;
}
else if (sTopStack == «ID»)
{
if (sClass == «Идентификатор»)
{
SintaxStack.Pop();
nLexNum++;
}
else SintaxState = SinAnalizerState.Error;
}
else SintaxState = SinAnalizerState.Error;
if (SintaxState == SinAnalizerState.Error)
{
lSinProgress.Text = «ОШИБКА! Неправильный синтаксис»;
lSinProgress.ForeColor = Color.Red;
}
else if (SintaxState == SinAnalizerState.Accept)
{
lSinProgress.Text = «Синтаксический анализ завершен успешно!»;
lSinProgress.ForeColor = Color.Blue;
}
}
lSinProgress.Visible = true;
btnSintax.Enabled = false;
синтаксическийАнализToolStripMenuItem.Enabled = false;
}
Цель данного проекта: практическое применение теории формальных грамматик и теории автоматов для проектирования трансляторов.
Постановка задания: Спроектировать и построить лексический и синтаксический анализаторы для заданного формального языка программирования. Построить и реализовать в лексическом анализаторе распознаватель лексем с заданной структурой: Нагруженное дерево (один элемент дерева хранит один символ (букву входного алфавита) лексемы).
Учебный язык включает директиву using, функцию main(), описание переменных, констант, массива переменной длины, операторов присваивания, арифметические операции. За основу лексики, синтаксиса и семантики учебного языка принять стандарты языка программирования С#.
Рассмотренная регулярная грамматика может быть реализована автоматом с множеством состояний G: [S, I, C, E, R], где
S — состояние ожидания первого символа лексемы;
I — состояние ожидания символов идентификаторов: буквы, цифры;
С — состояние ожидания символов целой части числа;
E -состояние ошибки;
R — состояние допуска лексемы.
Автомат переходит в допустимое состояние R из состояний S, I, C по символу конца лексемы — пробел или разделительного знака. Автомат определен множеством перечисленных состояний, множеством правил [1, 2, …, 47] и множеством входных символов [00..9, A..Z, «–», «#», «(», «)», «*», «,», «.», «/», «:», «;», «{«, «}», «+», «=»], из которых символы подмножества [«–», «#», «(», «)», «*», «,», «/», «:», «;», «{«, «}», «+», «=»] являются одновременно разделительными символами и уникальными лексемами. Таблица переходов автомата распознавателя идентификаторов представлена ниже на таблице.
L
D
e
S
I
E
S
Нач. состояние
I
I
I
R
E продолжение
--PAGE_BREAK----PAGE_BREAK--
; )
--PAGE_BREAK--
public
read
using
write
#
Д
(
В С
)
В С
;
В С
{
В С
}
В С
З(9, 2) С
З(8, 2) С
З(42, 2) С
З(43, 1)
З(43, 1)
З(15, 2) С
З(13, 2) С
З(14, 2) С
З(36, 2) С
З(37, 2) С
З(38, 2) С
З(35, 2) С
З(34, 2) С
З(33, 2) С
З(10, 2) С
В
З(16, 2) С
З(17, 2) С
В
З(18, 2) С
З(25, 2) С
В
З(6, 2) С
В
В
З(21, 2) С
В
З(22, 2) С
В
З(3, 2) С
В
З(24, 1)
З(24, 1)
З(24, 1)
З(24, 1)
З(24, 1)
З(24, 1)
З(40, 2) С
В
В
З(39, 2) С
В
В
В
В С
В С
З(27, 2) С
З(32, 2) С
З(31, 2) С
З(30, 2) С
В
В
З(45, 2) С
З(46, 2) С
З(44, 2) С
В
З(2, 2) С
З(1, 2) С
З(5, 2) С
В
З(20, 2) С
=
В С
ID
В С
int
В С
long
В С
продолжение
--PAGE_BREAK--