(8 оценок, среднее: 4,75 из 5)
Загрузка...
Учебная работа. Курсовая работа: Лексический и синтаксический анализатор языка высокого уровня
высшего проф образования
Кубанский муниципальный технологический институт
(КубГТУ)
Армавирский механико-технологический институт
Кафедра внутризаводского электрооборудования и автоматики
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовому проекту
по дисциплине: Теория языков программирования
на тему: «Лексический и синтаксический анализатор языка высочайшего уровня»
Государственное образовательное учреждение
высшего проф образования
Кубанский муниципальный технологический институт
(КубГТУ)
Армавирский механико-технологический институт
Кафедра внутризаводского электрооборудования и автоматики
Утверждаю
Заведующий кафедрой ВЭА
Проф. ____________ В.И. Куроедов
ЗАДАНИЕ
на курсовой проект
Студенту группы____________курса__________________
специальности 230105(2204) «Программное обеспечение вычислительной техники и автоматических систем»
Тема проекта: «Лексический и синтаксический анализатор языка высочайшего уровня»
Содержание задания: Спроектировать и выстроить лексический и синтаксический анализаторы для данного формального языка программирования. Выстроить и воплотить в лексическом анализаторе распознаватель лексем с данной структурой: нагруженное дерево (один элемент дерева хранит один знак (буковку входного алфавита) лексемы).
Учебный язык включает директиву using, функцию main(), описание переменных, констант, цикла for, операторов присваивания, арифметические операции. За базу лексики, синтаксиса и семантики учебного языка принять эталоны языка программирования С#.
Размер работы:
Объяснительная записка 35 – 40 листов
Графическая часть 2-3 листа формата А3
Рекомендуемая литература:
1. Ключко В.И. Теория вычислительных действий и структур. Учебное пособие, — КубГТУ, 1998;
2. Соколов А.П. системы программирования: теория, способы, методы: Учеб. Пособие, — М.:
деньги и статистика, 2004. – 320 с.: ил.
3. Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. — СПб.: Питер, 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 диск с готовой программкой и материалами к ней, также графическая часть, состоящая из 3-х листов.
СИНТАКСИС, ЛЕКСЕМА, КОНСТАНТА, автомат – РАСПОЗНАВАТЕЛЬ, РЕГУЛЯРНОЕ МНОЖЕСТВО, ФОРМАЛЬНАЯ ГРАМАТИКА, ТЕРМИНАЛ, НЕТЕРМИНАЛ, автомат С МАГАЗИННОЙ ПАМЯТЬЮ
Объект: лексический и синтаксический анализатор.
Цель: практическое применение теории формальных грамматик и теории автоматов для проектирования трансляторов.
Рассмотрен синтаксис данного языка программирования, разработана грамматика постоянных множеств. Спроектированы автоматы для лексического анализа и определения лексем. Разработана формальная LL(1) грамматика для данного языка программирования, спроектирован автомат с магазинной памятью для нисходящего анализа программки. Написана программка на языке высочайшего уровня Microsoft Visual C++ для лексического и синтаксического анализа текста на учебном языке программирования.
Содержание
Введение
1 синтез лексического анализатора (сканера)
1.1 Описание синтаксиса формального языка программирования
1.2 Система постоянных выражений
1.3 Распознаватели констант и служебных слов
1.4 Управляющая таблица конечного автомата лексического анализа
2 Синтез синтаксического анализатора
2.1 Описание формальной грамматики
2.2 Построение огромного количества ВЫБОР(n)
2.3 Построение управляющей таблицы
3 Описание программки
4 Результаты тестирования
5 Управление юзера
Заключение
Перечень применяемой литературы
приложение А. Листинг лексического анализатора
Приложение Б. Листинг синтаксического анализатора
Введение
Целью данного проекта является: практическое применение теории формальных грамматик и теории автоматов для проектирования трансляторов.
задачки: написать транслирующую грамматику для учебного языка программирования; спроектировать и выстроить лексический анализатор; спроектировать и выстроить синтаксический анализатор.
Входной информацией является файл, содержащий текст программки, написанной на учебном языке.
Выходной информацией являются таблицы лексем и имен, также доказательство того, что код соответствует синтаксису.
Результатом курсового проекта обязана быть программка—анализатор, состоящая из 2-ух частей: лексического анализатора, разбивающего начальный текст программки на лексемы и заполняющего таблицу имен; синтаксического анализатора, проверяющего соответствие текста данной грамматике.
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);
Так же в тексте программки могут содержаться многострочные комменты:
/* многострочный
комментарий */
Для записи идентификаторов употребляются буковкы британского языка и числа. Идентификаторы начинаются с буковкы. Целые константы записываются арабскими цифрами.
1.2
Система постоянных выражений
Для записи грамматики лексем языка применим форму Бэкуса-Наура.
Для записи идентификаторов употребляются буковкы британского языка и числа. Идентификаторы начинаются с буковкы. Синтаксис идентификаторов определяется праволинейной постоянной грамматикой:
<S> -> L <I>( 1)
<I> -> L <I>( 2)
<I> -> D <I>( 3)
<I> -> е( 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<KeywordTree> 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<KeywordTree>();
pKeywordsList.bIsWordEnd = true;
for(int i = 0; i < KeyWords.Length; i++)
{String KeyWord = KeyWords[i];
p = pKeywordsList;
for (int j = 0; j < KeyWord.Length; j++)
{if (p.pNextList.Count == 0)
{q = new KeywordTree();
q.cLetter = KeyWord[j];
q.pNextList = new List<KeywordTree>();
//если крайний знак в ключ. слове
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 < p.pNextList.Count; 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<KeywordTree>();
q.bIsWordEnd = false;
p.pNextList.Add(q);
p = q;
}}}}}
Функция идентификации служебных слов:
private bool IsKeyword(String sLexeme)
{int j, k;
KeywordTree p = pKeywordsList;
for (j = 0; j < sLexeme.Length; j++)
{if (p.pNextList.Count == 0) break;
else
{bool bIsFound = false;
for (k = 0; k < p.pNextList.Count; 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
E
Ошибка
R
S, Допустить
Spaces – огромное количество знаков пробела (сам пробел и символ табуляции);
Letters – огромное количество букв латинского алфавита [A..Z, «_»];
Digits – огромное количество арабских цифр [0..9];
Symbols – огромное количество разделительных знаков [«–», «#», «(», «)», «*», «,», «/», «:», «;», «{«, «}», «+», «=»].
2 синтез синтаксического анализатора
2.1 Описание формальной грамматики
Грамматика мотивированного знака:
( 1) <S> -> using <USING_LIST> <NEXT>
( 2) <S> -> public <CLASS> <NEXT>
( 3) <NEXT> -> ; <S>
( 4) <NEXT> -> e
Грамматика описания using:
( 5) <USING_LIST> -> ID <NEXT_USING>
( 6) <NEXT_USING> -> . <USING_LIST>
( 7) <NEXT_USING> -> e
Грамматика описания класса:
( 8) <CLASS> -> class ID { <CLASS_BODY> }
( 9) <CLASS_BODY> -> public <DEF> <NEXT_BODY>
(10) <NEXT_BODY> -> ; <CLASS_BODY>
(11) <NEXT_BODY> -> e
Грамматика описания определения полей и способов класса:
(12) <DEF> -> uint <DEF_LIST>
(13) <DEF> -> bool <DEF_LIST>
(14) <DEF> -> const long int <DEF_LIST>
(15) <DEF_LIST> -> ID <NEXT_DEF>
(16) <NEXT_DEF> -> ( <VAR_LIST> ) { <OPER_LIST> }
(17) <NEXT_DEF> -> , <VAR_LIST>
(18) <NEXT_DEF> -> = <EXPR> <VAR_LIST>
(19) <NEXT_DEF> -> e
(20) <VAR_LIST> -> ID <NEXT_VAR>
(21) <NEXT_VAR> -> , <VAR_LIST>
(22) <NEXT_VAR> -> = <EXPR> <VAR_LIST>
(23) <NEXT_VAR> -> e
Грамматика описания перечня операторов:
(24) <OPER_LIST> -> <OPERATOR> <NEXT_OPER>
(25) <NEXT_OPER> -> ; <OPER_LIST>
(26) <NEXT_OPER> -> e
Грамматика описания операторов:
(27) <OPERATOR> -> for ( ID = <EXPR> ; <COND> ; ID <LET> ) { <OPER_LIST> }
(28) <OPERATOR> -> break
(29) <OPERATOR> -> continue
(30) <OPERATOR> -> write ( <VAR_LIST> )
(31) <OPERATOR> -> read ( <VAR_LIST> )
(32) <OPERATOR> -> ID <LET>
(33) <LET> -> = <EXPR>
(34) <LET> -> * = <EXPR>
(35) <LET> -> / = <EXPR>
Грамматика описания арифметического выражения:
(36) <EXPR> -> ( <EXPR> ) <OPERATION>
(37) <EXPR> -> ID <OPERATION>
(38) <EXPR> -> NUM <OPERATION>
(39) <OPERATION> -> + <EXPR>
(40) <OPERATION> -> — <EXPR>
(41) <OPERATION> -> e
Грамматика описания условия:
(42) <COND> -> ( <COND> ) <RELATION>
(43) <COND> -> <EXPR> <RELATION>
(44) <RELATION> -> > <COND>
(45) <RELATION> -> < <COND>
(46) <RELATION> -> = = <COND>
(47) <RELATION> -> e
2.2 Построение огромного количества ВЫБОР(n)
Построение огромного количества ПЕРВ(n). Шаг 0. Для построения огромного количества ПЕРВ(n) = FIRST(1, A), где А — нетерминал в правой части n – го правила, определим огромного количества первых знаков, стоящих сначала правых частей правил, для всякого нетерминала в левой части правил.
ПЕРВ(<S>)
using public
ПЕРВ(<NEXT>)
;
ПЕРВ(<USING_LIST>)
ID
ПЕРВ(<NEXT_USING>)
.
ПЕРВ(<CLASS>)
class
ПЕРВ(<CLASS_BODY>)
public
ПЕРВ(<NEXT_BODY>)
;
ПЕРВ(<DEF>)
uint bool const
ПЕРВ(<DEF_LIST>)
ID
ПЕРВ(<NEXT_DEF>)
( , =
ПЕРВ(<VAR_LIST>)
ID
ПЕРВ(<NEXT_VAR>)
, =
ПЕРВ(<OPER_LIST>)
ПЕРВ(<NEXT_OPER>)
;
ПЕРВ(<OPERATOR>)
for break continue write read ID
ПЕРВ(<LET>)
= * /
ПЕРВ(<EXPR>)
( ID NUM
ПЕРВ(<OPERATION>)
+ —
ПЕРВ(<COND>)
(
ПЕРВ(<RELATION>)
> < =
Шаг 1. Внесем во огромное количество первых знаков ПЕРВ(n)i для всякого правила знаки, стоящие сначала правых частей правил. Индекс i = 0 – номер итерации.
0
using
0
public
0
;
0
0
ID
0
.
0
0
class
0
public
0
;
0
0
uint
0
bool
const
0
ID
0
(
0
,
=
0
0
ID
0
,
=
0
0
<OPERATOR>
0
;
0
0
for
0
break
0
continue
0
write
0
read
0
ID
0
=
0
*
0
/
0
(
0
ID
NUM
0
+
0
—
0
0
(
0
<EXPR>
0
>
0
<
0
=
0
Шаг 2. Если огромное количество первых знаков содержит нетерминал В, то включить в него знаки огромного количества ПЕРВ(В), определенное на шаге 0.
1
using
1
public
1
;
1
1
ID
1
.
1
1
class
1
public
1
;
1
1
uint
1
bool
1
const
1
ID
1
(
1
,
1
=
1
1
ID
1
,
1
=
1
1
for break continue write read ID <OPERATOR>
1
;
1
1
for
1
break
1
continue
1
write
1
read
1
ID
1
=
1
*
1
/
1
(
1
ID
1
NUM
1
+
1
—
1
1
(
1
( ID NUM <EXPR>
1
>
1
<
1
=
1
Шаг 3. Если ПЕРВ(n)i+1 ≠ ПЕРВ(n)i, то i = i + 1 и перейти к шагу 2, по другому окончить.
Шаг 2. Если огромное количество первых знаков содержит нетерминал В, то включить в него знаки огромного количества ПЕРВ(В), определенное на шаге 0.
2
using
2
public
2
;
2
2
ID
2
.
2
2
class
2
public
2
;
2
2
uint
2
bool
2
const
2
ID
2
(
2
,
2
=
2
2
ID
2
,
2
=
2
2
for break continue write read ID
2
;
2
2
for
2
break
2
continue
2
write
2
read
2
ID
2
=
2
*
2
/
2
(
2
ID
2
NUM
2
+
2
—
2
2
(
2
( ID NUM
2
>
2
<
2
=
2
Шаг 3. Если ПЕРВ(n)i+1
≠ ПЕРВ(n)i
, то i = i + 1 и перейти к шагу 2, по другому окончить.
Построение огромного количества ПЕРВ(А). Огромного количества ПЕРВ(А) нужно для определения множеств СЛЕД(А).
Шаг 1. Для построения огромного количества ПЕРВ(А) = FIRST(1, A), где А — нетерминал в правой части правил, определим огромного количества первых знаков, стоящих сначала правых частей правил, для всякого нетерминала в левой части правил.
ПЕРВ(<S>)
using public
ПЕРВ(<NEXT>)
;
ПЕРВ(<USING_LIST>)
ID
ПЕРВ(<NEXT_USING>)
.
ПЕРВ(<CLASS>)
class
ПЕРВ(<CLASS_BODY>)
public
ПЕРВ(<NEXT_BODY>)
;
ПЕРВ(<DEF>)
uint bool const
ПЕРВ(<DEF_LIST>)
ID
ПЕРВ(<NEXT_DEF>)
( , =
ПЕРВ(<VAR_LIST>)
ID
ПЕРВ(<NEXT_VAR>)
, =
ПЕРВ(<OPER_LIST>)
<OPERATOR>
ПЕРВ(<NEXT_OPER>)
;
ПЕРВ(<OPERATOR>)
for break continue write read ID
ПЕРВ(<LET>)
= * /
ПЕРВ(<EXPR>)
( ID NUM
ПЕРВ(<OPERATION>)
+ —
ПЕРВ(<COND>)
<EXPR> (
ПЕРВ(<RELATION>)
> < =
Шаг 2. Если огромное количество первых знаков содержит нетерминал В, то включить в него знаки огромного количества ПЕРВ(В), i=0.
ПЕРВ(<S>)0
using public
ПЕРВ(<NEXT>)0
;
ПЕРВ(<USING_LIST>)0
ID
ПЕРВ(<NEXT_USING>)0
.
ПЕРВ(<CLASS>)0
class
ПЕРВ(<CLASS_BODY>)0
public
ПЕРВ(<NEXT_BODY>)0
;
ПЕРВ(<DEF>)0
uint bool const
ПЕРВ(<DEF_LIST>)0
ID
ПЕРВ(<NEXT_DEF>)0
( , =
ПЕРВ(<VAR_LIST>)0
ID
ПЕРВ(<NEXT_VAR>)0
, =
ПЕРВ(<OPER_LIST>)0
for break continue write read ID
ПЕРВ(<NEXT_OPER>)0
;
ПЕРВ(<OPERATOR>)0
for break continue write read ID
ПЕРВ(<LET>)0
= * /
ПЕРВ(<EXPR>)0
( ID NUM
ПЕРВ(<OPERATION>)0
+ —
ПЕРВ(<COND>)0
( ID NUM
ПЕРВ(<RELATION>)0
> < =
Шаг 3. Выполнение шага 2 привело к изменению множеств ПЕРВ(А), потому повторим шаг 2.
Шаг 2. Если огромное количество первых знаков содержит нетерминал В, то включить в него знаки огромного количества ПЕРВ(В), i=1.
ПЕРВ(<S>)1
using public
ПЕРВ(<NEXT>)1
;
ПЕРВ(<USING_LIST>)1
ID
ПЕРВ(<NEXT_USING>)1
.
ПЕРВ(<CLASS>)1
class
ПЕРВ(<CLASS_BODY>)1
public
ПЕРВ(<NEXT_BODY>)1
;
ПЕРВ(<DEF>)1
uint bool const
ПЕРВ(<DEF_LIST>)1
ID
ПЕРВ(<NEXT_DEF>)1
( , =
ПЕРВ(<VAR_LIST>)1
ID
ПЕРВ(<NEXT_VAR>)1
, =
ПЕРВ(<OPER_LIST>)1
for break continue write read ID
ПЕРВ(<NEXT_OPER>)1
;
ПЕРВ(<OPERATOR>)1
for break continue write read ID
ПЕРВ(<LET>)1
= * /
ПЕРВ(<EXPR>)1
( ID NUM
ПЕРВ(<OPERATION>)1
+ —
ПЕРВ(<COND>)1
( ID NUM
ПЕРВ(<RELATION>)1
> < =
Шаг 3. Предстоящее выполнения шага 2 не приведет к изменению множеств ПЕРВ(А), потому закончим.
Построение огромного количества СЛЕД(А). Огромного количества СЛЕД(А) строятся для всех нетрминальных знаков грамматики способом поочередного приближения.
Шаг 1. Внесем во огромное количество следующих знаков СЛЕД(А) = FOLLOW(1, A) для всякого нетерминала А все знаки, которые в правых частях правил встречаются конкретно за эмблемой А; i=0.
СЛЕД(<S>)0
СЛЕД(<NEXT>)0
СЛЕД(<USING_LIST>)0
<NEXT>
СЛЕД(<NEXT_USING>)0
СЛЕД(<CLASS>)0
<NEXT>
СЛЕД(<CLASS_BODY>)0
}
СЛЕД(<NEXT_BODY>)0
СЛЕД(<DEF>)0
<NEXT_BODY>
СЛЕД(<DEF_LIST>)0
СЛЕД(<NEXT_DEF>)0
СЛЕД(<VAR_LIST>)0
)
СЛЕД(<NEXT_VAR>)0
СЛЕД(<OPER_LIST>)0
}
СЛЕД(<NEXT_OPER>)0
СЛЕД(<OPERATOR>)0
<NEXT_OPER>
СЛЕД(<LET>)0
)
СЛЕД(<EXPR>)0
<VAR_LIST> ; ) <RELATION>
СЛЕД(<OPERATION>)0
СЛЕД(<COND>)0
; )
СЛЕД(<RELATION>)0
Шаг 2. Внесем пустую цепочку (либо знак конца строчки) во огромное количество следующих знаков для мотивированного знака <S>.
СЛЕД(<S>)0
#
СЛЕД(<NEXT>)0
СЛЕД(<USING_LIST>)0
<NEXT>
СЛЕД(<NEXT_USING>)0
СЛЕД(<CLASS>)0
<NEXT>
СЛЕД(<CLASS_BODY>)0
}
СЛЕД(<NEXT_BODY>)0
СЛЕД(<DEF>)0
<NEXT_BODY>
СЛЕД(<DEF_LIST>)0
СЛЕД(<NEXT_DEF>)0
СЛЕД(<VAR_LIST>)0
)
СЛЕД(<NEXT_VAR>)0
СЛЕД(<OPER_LIST>)0
}
СЛЕД(<NEXT_OPER>)0
СЛЕД(<OPERATOR>)0
<NEXT_OPER>
СЛЕД(<LET>)0
)
СЛЕД(<EXPR>)0
<VAR_LIST> ; ) <RELATION>
СЛЕД(<OPERATION>)0
СЛЕД(<COND>)0
; )
СЛЕД(<RELATION>)0
Шаг 3. Для всех нетерминальных знаков A включить во огромного количества СЛЕД(A) огромного количества ПЕРВ(В), где B Î СЛЕД(A).
СЛЕД(<S>)1
#
СЛЕД(<NEXT>)1
СЛЕД(<USING_LIST>)1
;
СЛЕД(<NEXT_USING>)1
СЛЕД(<CLASS>)1
;
СЛЕД(<CLASS_BODY>)1
}
СЛЕД(<NEXT_BODY>)1
СЛЕД(<DEF>)1
;
СЛЕД(<DEF_LIST>)1
СЛЕД(<NEXT_DEF>)1
СЛЕД(<VAR_LIST>)1
)
СЛЕД(<NEXT_VAR>)1
СЛЕД(<OPER_LIST>)1
}
СЛЕД(<NEXT_OPER>)1
СЛЕД(<OPERATOR>)1
;
СЛЕД(<LET>)1
)
СЛЕД(<EXPR>)1
ID ; ) < > =
СЛЕД(<OPERATION>)1
СЛЕД(<COND>)1
; )
СЛЕД(<RELATION>)1
Шаг 4. Для всех нетерминальных знаков A включить во огромного количества СЛЕД(A) огромного количества СЛЕД (В), где B Î СЛЕД(A), если существует правило B=e.
СЛЕД(<S>)2
#
СЛЕД(<NEXT>)2
СЛЕД(<USING_LIST>)2
;
СЛЕД(<NEXT_USING>)2
СЛЕД(<CLASS>)2
;
СЛЕД(<CLASS_BODY>)2
}
СЛЕД(<NEXT_BODY>)2
СЛЕД(<DEF>)2
;
СЛЕД(<DEF_LIST>)2
СЛЕД(<NEXT_DEF>)2
СЛЕД(<VAR_LIST>)2
)
СЛЕД(<NEXT_VAR>)2
СЛЕД(<OPER_LIST>)2
}
СЛЕД(<NEXT_OPER>)2
СЛЕД(<OPERATOR>)2
;
СЛЕД(<LET>)2
)
СЛЕД(<EXPR>)2
ID ; ) < > =
СЛЕД(<OPERATION>)2
СЛЕД(<COND>)2
; )
СЛЕД(<RELATION>)2
Шаг 5. Для всех нетерминальных знаков A во огромное количество СЛЕД(A) включить огромного количества СЛЕД (В), если существует правило B=aA, a Î (VT È VN).
СЛЕД(<S>)3
#
СЛЕД(<NEXT>)3
#
СЛЕД(<USING_LIST>)3
;
СЛЕД(<NEXT_USING>)3
;
СЛЕД(<CLASS>)3
;
СЛЕД(<CLASS_BODY>)3
}
СЛЕД(<NEXT_BODY>)3
}
СЛЕД(<DEF>)3
;
СЛЕД(<DEF_LIST>)3
;
СЛЕД(<NEXT_DEF>)3
;
СЛЕД(<VAR_LIST>)3
)
СЛЕД(<NEXT_VAR>)3
)
СЛЕД(<OPER_LIST>)3
}
СЛЕД(<NEXT_OPER>)3
}
СЛЕД(<OPERATOR>)3
;
СЛЕД(<LET>)3
)
СЛЕД(<EXPR>)3
ID ; ) < > =
СЛЕД(<OPERATION>)3
ID ; ) < > =
СЛЕД(<COND>)3
; )
СЛЕД(<RELATION>)3
; )
Шаг 6 Потому что огромного количества СЛЕД(А) не поменялись на шагах 3,4,5, то закончим.
Построение огромного количества ВЫБОР(n). Для формирования множеств ВЫБОР требуется найти аннулирующие правила. Для этого из общего перечня правил исключают правила, содержащие в правых частях хотя бы один терминал. Из оставшихся правил исключают непроизводительные правила, т.е. те правила, которые не порождают цепочки терминалов. Оставшиеся правила будут аннулирующими.
Таблица 3 содержит правила, которые не содержат терминальные знаки. Слева – непроизводительные правила. Справа – аннулирующие правила.
Таблица 3 – Непроизводительные и аннулирующие правила.
Непроизводительные правила
Аннулирующие правила
(24) <OPER_LIST> -> <OPERATOR> <NEXT_OPER>
(43) <COND> -> <EXPR> <RELATION>
( 4) <NEXT> -> e
( 7) <NEXT_USING> -> e
(11) <NEXT_BODY> -> e
(19) <NEXT_DEF> -> e
(23) <NEXT_VAR> -> e
(26) <NEXT_OPER> -> e
(41) <OPERATION> -> e
(47) <RELATION> -> e
Огромного количества ВЫБОР определим на основании последующих выражений: для не аннулирующих правил — ВЫБОР(n) = ПЕРВ(n), для аннулирующих правил — ВЫБОР(n) = СЛЕД(A), где А – нетерминальный знак в левой части правила n.
using
public
;
#
ID
.
;
class
public
;
}
uint
bool
const
ID
(
,
=
;
ID
,
=
)
for break continue write read ID
;
}
for
break
continue
write
read
ID
=
*
/
(
ID
NUM
+
—
ID ; ) < > =
(
( ID NUM
>
<
=
; )
2.3 Построение управляющей таблицы
Для составления управляющей таблицы (таблица 4) нужно найти огромное количество магазинных знаков, огромное количество знаков поступающих на вход автомата и найти операции МПА для каждой пары: верхний знак магазина – знак на входе автомата.
Огромное количество магазинных знаков включает все нетерминальные знаки, знак дна магазина и терминальные знаки кроме тех, которые занимают в правых частях правил лишь 1-ые позиции: # ( ) ; { } <CLASS_BODY> <CLASS> <COND> <DEF_LIST> <DEF> <EXPR> <LET> <NEXT_BODY> <NEXT_DEF> <NEXT_OPER> <NEXT_USING> <NEXT_VAR> <NEXT> <OPER_LIST> <OPERATION> <OPERATOR> <RELATION> <S> <USING_LIST> <VAR_LIST> = decimal ID.
Огромное количество знаков входной строчки включает все терминальные знаки и знак конца строчки: – # ( ) * , . / ; { } + < = > break class const continue decimal double for ID int NUM public read using writeline.
При построении таблицы использовались последующие обозначения и сокращения:
– Выт. – вытолкнуть верхний знак из магазина;
– Сдв. – двинуть входную строчку на одну лексему;
– Зам. (n, m) – поменять верхний знак магазина на знаки правила номер n, начиная с знака m;
– ДОП. – синтаксический анализ прошел удачно.
Листинг программки, реализующей данную управляющую таблицу, приведен в приложении А.
3 Описание программки
программка выполнена в виде Windows-приложения с оконным интерфейсом (набросок 2 в среде Microsoft Visual Studio.
Набросок 2 — интерфейс программки
Листинг программки на формальном языке программирования загружается из текстового файла. Результаты работы обоих анализаторов (лексического и синтаксического) показываются в виде таблиц при помощи составляющие ListView (набросок 3).
Набросок 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 < 10; i = i + 1)
{
write(a, b, c, d, e);
a = b — (c + 2L);
d *= e — 2;
e /= 123;
break;
};
for(i = 0; i < 10; i *= 2) { continue; }
}
}
Результаты работы лексического и синтаксического анализаторов показаны на рисунке 4. В качестве результата лексического анализатора представлены две таблицы: таблица лексем и таблица имен. В первой отображены все распознанные лексемы и их класс. Во 2-ой — имена переменных. На выходе синтаксического анализатора выходит одна таблица, на которой показан весь процесс анализа, а конкретно: верхний знак магазина, знак входной лексемы и ее класс.
Набросок 4 — Итог работы анализаторов.
Для проверки правильной работоспособности программки, допустим ошибку в коде:
public bool c, 1d;
В итоге программка выдаст сообщение о ошибке на шаге лексического анализа (набросок 5).
Набросок 5 — Ошибка на шаге лексического анализа.
Для проверки синтаксического анализатора, создадим еще одну ошибку:
public const int e = 9L;
На рисунке 6 показан итог работы синтаксического анализатора.
Набросок 6 — Ошибка на шаге синтаксического анализа.
5 Управление юзера
программка запускается из файла Leks_Analizator.exe. В интерфейсе программки находятся четыре клавиши (набросок 7). При нажатии на клавишу «Загрузить пример кода» (набросок 7) юзеру будет дана возможность загрузки кода. Также код можно ввести с клавиатуры.
Набросок 7 — интерфейс программки
Набросок 8 — Диалог загрузки файла
Опосля ввода кода программки, при нажатии на клавишу «Лексический анализ», запускается процесс анализа. Результатом анализа будет строка понизу формы.
По кнопочке «Синтаксический анализ» запускается процесс анализа. Итог отображается понизу формы.
При нажатии на кнопочке «Общий анализ» будет запущен по порядку лексический анализ, а потом синтаксический анализ.
Заключение
В данном курсовом проекте была разработана программка—анализатор, состоящая из 2-ух частей: лексического анализатора, разбивающего начальный текст программки на лексемы и заполняющего таблицу имен; синтаксического анализатора, проверяющего соответствие текста данной грамматике.
В процессе выполнения курсового проекта были получены последующие результаты:
— написана грамматика для учебного языка программирования;
— спроектирован и построен лексический анализатор;
— спроектирован и построен синтаксический анализатор.
Для написания курсовой работы мною были без помощи других исследованы литературные и справочные материалами по этой теме.
Перечень применяемой литературы
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 с (электрический вариант)
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 < rSrcFile.Lines.Length; 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++;
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;
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*/{«<S>», «USING», «<USING_LIST>», «<NEXT>», «», «», «», «», «», «», «», «», «», «», «»},
/*1*/{«<S>», «PUBLIC», «<CLASS>», «<NEXT>», «», «», «», «», «», «», «», «», «», «», «»},
/*2*/{«<NEXT>», «;», «<S>», «», «», «», «», «», «», «», «», «», «», «», «»},
/*3*/{«<NEXT>», «e», «», «», «», «», «», «», «», «», «», «», «», «», «»},
/*4*/{«<USING_LIST>