Лексический и синтаксический анализатор языка высокого уровня

СОДЕРЖАНИЕ: Государственное образовательное учреждение высшего профессионального образования Кубанский государственный технологический университет (КубГТУ)

Государственное образовательное учреждение

высшего профессионального образования

Кубанский государственный технологический университет

(КубГТУ)

Армавирский механико-технологический институт

Кафедра внутризаводского электрооборудования и автоматики

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

по дисциплине: Теория языков программирования

на тему: «Лексический и синтаксический анализатор языка высокого уровня»

Государственное образовательное учреждение

высшего профессионального образования

Кубанский государственный технологический университет

(КубГТУ)

Армавирский механико-технологический институт

Кафедра внутризаводского электрооборудования и автоматики

Утверждаю

Заведующий кафедрой ВЭА

Проф. ____________ В.И. Куроедов

ЗАДАНИЕ

на курсовой проект

Студенту группы____________курса__________________

специальности 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 диск с готовой программой и материалами к ней, а также графическая часть, состоящая из трех листов.

СИНТАКСИС, ЛЕКСЕМА, КОНСТАНТА, АВТОМАТ – РАСПОЗНАВАТЕЛЬ, РЕГУЛЯРНОЕ МНОЖЕСТВО, ФОРМАЛЬНАЯ ГРАМАТИКА, ТЕРМИНАЛ, НЕТЕРМИНАЛ, АВТОМАТ С МАГАЗИННОЙ ПАМЯТЬЮ

Объект: лексический и синтаксический анализатор.

Цель: практическое применение теории формальных грамматик и теории автоматов для проектирования трансляторов.

Рассмотрен синтаксис заданного языка программирования, разработана грамматика регулярных множеств. Спроектированы автоматы для лексического анализа и распознавания лексем. Разработана формальная 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 Руководство пользователя

Заключение

Список используемой литературы

Приложение А. Листинг лексического анализатора

Приложение Б. Листинг синтаксического анализатора

Введение

Целью данного проекта является: практическое применение теории формальных грамматик и теории автоматов для проектирования трансляторов.

Задачи: написать транслирующую грамматику для учебного языка программирования; спроектировать и построить лексический анализатор; спроектировать и построить синтаксический анализатор.

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

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

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

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 ListKeywordTree 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 ListKeywordTree();

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 ListKeywordTree();

//если последний символ в ключ. слове

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 ListKeywordTree();

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 – номер итерации.

ПЕРВ(1) ₀	using
ПЕРВ(2) ₀	public
ПЕРВ(3) ₀	;
ПЕРВ(4) ₀
ПЕРВ(5) ₀	ID
ПЕРВ(6) ₀	.
ПЕРВ(7) ₀
ПЕРВ(8) ₀	class
ПЕРВ(9) ₀	public
ПЕРВ(10) ₀	;
ПЕРВ(11) ₀
ПЕРВ(12) ₀	uint
ПЕРВ(13) ₀	bool
ПЕРВ(14)	const
ПЕРВ(15) ₀	ID
ПЕРВ(16) ₀	(
ПЕРВ(17) ₀	,
ПЕРВ(18)	=
ПЕРВ(19) ₀
ПЕРВ(20) ₀	ID
ПЕРВ(21) ₀	,
ПЕРВ(22)	=
ПЕРВ(23) ₀
ПЕРВ(24) ₀	OPERATOR
ПЕРВ(25) ₀	;
ПЕРВ(26) ₀
ПЕРВ(27) ₀	for
ПЕРВ(28) ₀	break
ПЕРВ(29) ₀	continue
ПЕРВ(30) ₀	write
ПЕРВ(31) ₀	read
ПЕРВ(32) ₀	ID
ПЕРВ(33) ₀	=
ПЕРВ(34) ₀	*
ПЕРВ(35) ₀	/
ПЕРВ(36) ₀	(
ПЕРВ(37) ₀	ID
ПЕРВ(38)	NUM
ПЕРВ(39) ₀	+
ПЕРВ(40) ₀	-
ПЕРВ(41) ₀
ПЕРВ(42) ₀	(
ПЕРВ(43) ₀	EXPR
ПЕРВ(44) ₀
ПЕРВ(45) ₀
ПЕРВ(46) ₀	=
ПЕРВ(47) ₀

Шаг 2. Если множество первых символов содержит нетерминал В, то включить в него символы множества ПЕРВ(В), определенное на шаге 0.

ПЕРВ(1) ₁	using
ПЕРВ(2) ₁	public
ПЕРВ(3) ₁	;
ПЕРВ(4) ₁
ПЕРВ(5) ₁	ID
ПЕРВ(6) ₁	.
ПЕРВ(7) ₁
ПЕРВ(8) ₁	class
ПЕРВ(9) ₁	public
ПЕРВ(10) ₁	;
ПЕРВ(11) ₁
ПЕРВ(12) ₁	uint
ПЕРВ(13) ₁	bool
ПЕРВ(14) ₁	const
ПЕРВ(15) ₁	ID
ПЕРВ(16) ₁	(
ПЕРВ(17) ₁	,
ПЕРВ(18) ₁	=
ПЕРВ(19) ₁
ПЕРВ(20) ₁	ID
ПЕРВ(21) ₁	,
ПЕРВ(22) ₁	=
ПЕРВ(23) ₁
ПЕРВ(24) ₁	for break continue write read ID OPERATOR
ПЕРВ(25) ₁	;
ПЕРВ(26) ₁
ПЕРВ(27) ₁	for
ПЕРВ(28) ₁	break
ПЕРВ(29) ₁	continue
ПЕРВ(30) ₁	write
ПЕРВ(31) ₁	read
ПЕРВ(32) ₁	ID
ПЕРВ(33) ₁	=
ПЕРВ(34) ₁	*
ПЕРВ(35) ₁	/
ПЕРВ(36) ₁	(
ПЕРВ(37) ₁	ID
ПЕРВ(38) ₁	NUM
ПЕРВ(39) ₁	+
ПЕРВ(40) ₁	-
ПЕРВ(41) ₁
ПЕРВ(42) ₁	(
ПЕРВ(43) ₁	( ID NUM EXPR
ПЕРВ(44) ₁
ПЕРВ(45) ₁
ПЕРВ(46) ₁	=
ПЕРВ(47) ₁

Шаг 3. Если ПЕРВ(n)i+1 ПЕРВ(n)i, то i = i + 1 и перейти к шагу 2, иначе закончить.

ПЕРВ(1) ₂	using
ПЕРВ(2) ₂	public
ПЕРВ(3) ₂	;
ПЕРВ(4) ₂
ПЕРВ(5) ₂	ID
ПЕРВ(6) ₂	.
ПЕРВ(7) ₂
ПЕРВ(8) ₂	class
ПЕРВ(9) ₂	public
ПЕРВ(10) ₂	;
ПЕРВ(11) ₂
ПЕРВ(12) ₂	uint
ПЕРВ(13) ₂	bool
ПЕРВ(14) ₂	const
ПЕРВ(15) ₂	ID
ПЕРВ(16) ₂	(
ПЕРВ(17) ₂	,
ПЕРВ(18) ₂	=
ПЕРВ(19) ₂
ПЕРВ(20) ₂	ID
ПЕРВ(21) ₂	,
ПЕРВ(22) ₂	=
ПЕРВ(23) ₂
ПЕРВ(24) ₂	for break continue write read ID
ПЕРВ(25) ₂	;
ПЕРВ(26) ₂
ПЕРВ(27) ₂	for
ПЕРВ(28) ₂	break
ПЕРВ(29) ₂	continue
ПЕРВ(30) ₂	write
ПЕРВ(31) ₂	read
ПЕРВ(32) ₂	ID
ПЕРВ(33) ₂	=
ПЕРВ(34) ₂	*
ПЕРВ(35) ₂	/
ПЕРВ(36) ₂	(
ПЕРВ(37) ₂	ID
ПЕРВ(38) ₂	NUM
ПЕРВ(39) ₂	+
ПЕРВ(40) ₂	-
ПЕРВ(41) ₂
ПЕРВ(42) ₂	(
ПЕРВ(43) ₂	( ID NUM
ПЕРВ(44) ₂
ПЕРВ(45) ₂
ПЕРВ(46) ₂	=
ПЕРВ(47) ₂

Шаг 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)₀	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)₀	for break continue write read ID
ПЕРВ(NEXT_OPER)₀	;
ПЕРВ(OPERATOR)₀	for break continue write read ID
ПЕРВ(LET)₀	= * /
ПЕРВ(EXPR)₀	( ID NUM
ПЕРВ(OPERATION)₀	+ -
ПЕРВ(COND)₀	( ID NUM
ПЕРВ(RELATION)₀	=

Шаг 3. Выполнение шага 2 привело к изменению множеств ПЕРВ(А), поэтому повторим шаг 2.

Шаг 2. Если множество первых символов содержит нетерминал В, то включить в него символы множества ПЕРВ(В), i=1.

ПЕРВ(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)₁	for break continue write read ID
ПЕРВ(NEXT_OPER)₁	;
ПЕРВ(OPERATOR)₁	for break continue write read ID
ПЕРВ(LET)₁	= * /
ПЕРВ(EXPR)₁	( ID NUM
ПЕРВ(OPERATION)₁	+ -
ПЕРВ(COND)₁	( ID NUM
ПЕРВ(RELATION)₁	=

Шаг 3. Дальнейшее выполнения шага 2 не приведет к изменению множеств ПЕРВ(А), поэтому закончим.

Построение множества СЛЕД(А). Множества СЛЕД(А) строятся для всех нетрминальных символов грамматики методом последовательного приближения.

Шаг 1. Внесем во множество последующих символов СЛЕД(А) = FOLLOW(1, A) для каждого нетерминала А все символы, которые в правых частях правил встречаются непосредственно за символом А; i=0.

СЛЕД(S)₀
СЛЕД(NEXT)₀
СЛЕД(USING_LIST)₀	NEXT
СЛЕД(NEXT_USING)₀
СЛЕД(CLASS)₀	NEXT
СЛЕД(CLASS_BODY)₀	}
СЛЕД(NEXT_BODY)₀
СЛЕД(DEF)₀	NEXT_BODY
СЛЕД(DEF_LIST)₀
СЛЕД(NEXT_DEF)₀
СЛЕД(VAR_LIST)₀	)
СЛЕД(NEXT_VAR)₀
СЛЕД(OPER_LIST)₀	}
СЛЕД(NEXT_OPER)₀
СЛЕД(OPERATOR)₀	NEXT_OPER
СЛЕД(LET)₀	)
СЛЕД(EXPR)₀	VAR_LIST ; ) RELATION
СЛЕД(OPERATION)₀
СЛЕД(COND)₀	; )
СЛЕД(RELATION)₀

Шаг 2. Внесем пустую цепочку (или символ конца строки) во множество последующих символов для целевого символа S.

СЛЕД(S)₀	#
СЛЕД(NEXT)₀
СЛЕД(USING_LIST)₀	NEXT
СЛЕД(NEXT_USING)₀
СЛЕД(CLASS)₀	NEXT
СЛЕД(CLASS_BODY)₀	}
СЛЕД(NEXT_BODY)₀
СЛЕД(DEF)₀	NEXT_BODY
СЛЕД(DEF_LIST)₀
СЛЕД(NEXT_DEF)₀
СЛЕД(VAR_LIST)₀	)
СЛЕД(NEXT_VAR)₀
СЛЕД(OPER_LIST)₀	}
СЛЕД(NEXT_OPER)₀
СЛЕД(OPERATOR)₀	NEXT_OPER
СЛЕД(LET)₀	)
СЛЕД(EXPR)₀	VAR_LIST ; ) RELATION
СЛЕД(OPERATION)₀
СЛЕД(COND)₀	; )
СЛЕД(RELATION)₀

Шаг 3. Для всех нетерминальных символов A включить во множества СЛЕД(A) множества ПЕРВ(В), где B СЛЕД(A).

СЛЕД(S)₁	#
СЛЕД(NEXT)₁
СЛЕД(USING_LIST)₁	;
СЛЕД(NEXT_USING)₁
СЛЕД(CLASS)₁	;
СЛЕД(CLASS_BODY)₁	}
СЛЕД(NEXT_BODY)₁
СЛЕД(DEF)₁	;
СЛЕД(DEF_LIST)₁
СЛЕД(NEXT_DEF)₁
СЛЕД(VAR_LIST)₁	)
СЛЕД(NEXT_VAR)₁
СЛЕД(OPER_LIST)₁	}
СЛЕД(NEXT_OPER)₁
СЛЕД(OPERATOR)₁	;
СЛЕД(LET)₁	)
СЛЕД(EXPR)₁	ID ; ) =
СЛЕД(OPERATION)₁
СЛЕД(COND)₁	; )
СЛЕД(RELATION)₁

Шаг 4. Для всех нетерминальных символов A включить во множества СЛЕД(A) множества СЛЕД (В), где B СЛЕД(A), если существует правило B=e.

СЛЕД(S)₂	#
СЛЕД(NEXT)₂
СЛЕД(USING_LIST)₂	;
СЛЕД(NEXT_USING)₂
СЛЕД(CLASS)₂	;
СЛЕД(CLASS_BODY)₂	}
СЛЕД(NEXT_BODY)₂
СЛЕД(DEF)₂	;
СЛЕД(DEF_LIST)₂
СЛЕД(NEXT_DEF)₂
СЛЕД(VAR_LIST)₂	)
СЛЕД(NEXT_VAR)₂
СЛЕД(OPER_LIST)₂	}
СЛЕД(NEXT_OPER)₂
СЛЕД(OPERATOR)₂	;
СЛЕД(LET)₂	)
СЛЕД(EXPR)₂	ID ; ) =
СЛЕД(OPERATION)₂
СЛЕД(COND)₂	; )
СЛЕД(RELATION)₂

Шаг 5. Для всех нетерминальных символов A во множество СЛЕД(A) включить множества СЛЕД (В), если существует правило B=aA, a (VT VN).

СЛЕД(S)₃	#
СЛЕД(NEXT)₃	#
СЛЕД(USING_LIST)₃	;
СЛЕД(NEXT_USING)₃	;
СЛЕД(CLASS)₃	;
СЛЕД(CLASS_BODY)₃	}
СЛЕД(NEXT_BODY)₃	}
СЛЕД(DEF)₃	;
СЛЕД(DEF_LIST)₃	;
СЛЕД(NEXT_DEF)₃	;
СЛЕД(VAR_LIST)₃	)
СЛЕД(NEXT_VAR)₃	)
СЛЕД(OPER_LIST)₃	}
СЛЕД(NEXT_OPER)₃	}
СЛЕД(OPERATOR)₃	;
СЛЕД(LET)₃	)
СЛЕД(EXPR)₃	ID ; ) =
СЛЕД(OPERATION)₃	ID ; ) =
СЛЕД(COND)₃	; )
СЛЕД(RELATION)₃	; )

Шаг 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.

ВЫБОР(1)	using
ВЫБОР(2)	public
ВЫБОР(3)	;
ВЫБОР(4)	#
ВЫБОР(5)	ID
ВЫБОР(6)	.
ВЫБОР(7)	;
ВЫБОР(8)	class
ВЫБОР(9)	public
ВЫБОР(10)	;
ВЫБОР(11)	}
ВЫБОР(12)	uint
ВЫБОР(13)	bool
ВЫБОР(14)	const
ВЫБОР(15)	ID
ВЫБОР(16)	(
ВЫБОР(17)	,
ВЫБОР(18)	=
ВЫБОР(19)	;
ВЫБОР(20)	ID
ВЫБОР(21)	,
ВЫБОР(22)	=
ВЫБОР(23)	)
ВЫБОР(24)	for break continue write read ID
ВЫБОР(25)	;
ВЫБОР(26)	}
ВЫБОР(27)	for
ВЫБОР(28)	break
ВЫБОР(29)	continue
ВЫБОР(30)	write
ВЫБОР(31)	read
ВЫБОР(32)	ID
ВЫБОР(33)	=
ВЫБОР(34)	*
ВЫБОР(35)	/
ВЫБОР(36)	(
ВЫБОР(37)	ID
ВЫБОР(38)	NUM
ВЫБОР(39)	+
ВЫБОР(40)	-
ВЫБОР(41)	ID ; ) =
ВЫБОР(42)	(
ВЫБОР(43)	( ID NUM
ВЫБОР(44)
ВЫБОР(45)
ВЫБОР(46)	=
ВЫБОР(47)	; )

2.3 Построение управляющей таблицы

Для составления управляющей таблицы (таблица 4) необходимо определить множество магазинных символов, множество символов поступающих на вход автомата и определить операции МПА для каждой пары: верхний символ магазина – символ на входе автомата.

Множество магазинных символов включает все нетерминальные символы, символ дна магазина и терминальные символы за исключением тех, которые занимают в правых частях правил только первые позиции: # ( ) ; { } 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. В качестве результата лексического анализатора представлены две таблицы: таблица лексем и таблица имен. В первой отображены все распознанные лексемы и их класс. Во второй - имена переменных. На выходе синтаксического анализатора получается одна таблица, на которой показан весь процесс анализа, а именно: верхний символ магазина, символ входной лексемы и ее класс.

Рисунок 4 - Результат работы анализаторов.

Для проверки правильной работоспособности программы, допустим ошибку в коде:

public bool c, 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 с (электронный вариант)

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,ID, NEXT_USING, , , , , , , , , , , , },

/*5*/{NEXT_USING,., USING_LIST, , , , , , , , , , , , },

/*6*/{NEXT_USING,e, , , , , , , , , , , , , },

/*7*/{CLASS, CLASS, ID, {, CLASS_BODY, }, , , , , , , , , },

/*8*/{CLASS_BODY,PUBLIC, DEF, NEXT_BODY, , , , , , , , , , , },

/*9*/{NEXT_BODY, ;, CLASS_BODY, , , , , , , , , , , , },

/*10*/{NEXT_BODY, e, , , , , , , , , , , , , },

/*11*/{DEF, UINT, DEF_LIST, , , , , , , , , , , , },

/*12*/{DEF, BOOL, DEF_LIST, , , , , , , , , , , , },

/*13*/{DEF, CONST, LONG, INT, DEF_LIST, , , , , , , , , , },

/*14*/{DEF_LIST, ID, NEXT_DEF, , , , , , , , , , , , },

/*15*/{NEXT_DEF, (, VAR_LIST, ), {, OPER_LIST, }, , , , , , , , },

/*16*/{NEXT_DEF, ,, VAR_LIST, , , , , , , , , , , , },

/*17*/{NEXT_DEF, =, EXPR, NEXT_VAR, , , , , , , , , , , },

/*18*/{NEXT_DEF, e, , , , , , , , , , , , , },

/*19*/{VAR_LIST, ID, NEXT_VAR, , , , , , , , , , , , },

/*20*/{NEXT_VAR, ,, VAR_LIST, , , , , , , , , , , , },

/*21*/{NEXT_VAR, =, EXPR, NEXT_VAR, , , , , , , , , , , },

/*22*/{NEXT_VAR, e, , , , , , , , , , , , , },

/*23*/{OPER_LIST, OPERATOR, NEXT_OPER, , , , , , , , , , , , },

/*24*/{NEXT_OPER, ;, OPER_LIST, , , , , , , , , , , , },

/*25*/{NEXT_OPER, e, , , , , , , , , , , , , },

/*26*/{OPERATOR, FOR, (, ID, =, EXPR, ;, COND, ;, ID, LET, ), {, OPER_LIST, }},

/*27*/{OPERATOR, break, , , , , , , , , , , , , },

/*28*/{OPERATOR, continue, , , , , , , , , , , , , },

/*29*/{OPERATOR, WRITE, (, VAR_LIST, ), , , , , , , , , , },

/*30*/{OPERATOR, READ, (, VAR_LIST, ), , , , , , , , , , },

/*31*/{OPERATOR, ID, LET, , , , , , , , , , , , },

/*32*/{LET, =, EXPR, , , , , , , , , , , , },

/*33*/{LET, *, =, EXPR, , , , , , , , , , , },

/*34*/{LET, /, =, EXPR, , , , , , , , , , , },

/*35*/{EXPR, (, EXPR, ), OPERATION, , , , , , , , , , },

/*36*/{EXPR, ID, OPERATION, , , , , , , , , , , , },

/*37*/{EXPR, NUM, OPERATION, , , , , , , , , , , , },

/*38*/{OPERATION, +, EXPR, , , , , , , , , , , , },

/*39*/{OPERATION, -, EXPR, , , , , , , , , , , , },

/*40*/{OPERATION, e, , , , , , , , , , , , , },

/*41*/{COND, (, COND, ), RELATION, , , , , , , , , , },

/*42*/{COND, EXPR, RELATION, , , , , , , , , , , , },

/*43*/{RELATION, , COND, , , , , , , , , , , , },

/*44*/{RELATION, , COND, , , , , , , , , , , , },

/*45*/{RELATION, =, =, COND, , , , , , , , , , , },

/*46*/{RELATION, e, , , , , , , , , , , , , },

};

System.Collections.Stack SintaxStack = new System.Collections.Stack();

SintaxStack.Push(#);

SintaxStack.Push(S);

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 == S)

{

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)

{

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 == CLASS_BODY)

{

if (sLexeme == PUBLIC)

{

Replace(SintaxStack, Grammatic, 8, 2);

nLexNum++;

}

else SintaxState = SinAnalizerState.Error;

}

else if (sTopStack == CLASS)

{

if (sLexeme == CLASS)

{

Replace(SintaxStack, Grammatic, 7, 2);

nLexNum++;

}

else SintaxState = SinAnalizerState.Error;

}

else if (sTopStack == DEF_LIST)

{

if (sClass == Идентификатор)

{

Replace(SintaxStack, Grammatic, 14, 2);

nLexNum++;

}

else SintaxState = SinAnalizerState.Error;

}

else if (sTopStack == DEF)

{

if (sLexeme == UINT)

{

Replace(SintaxStack, Grammatic, 11, 2);

nLexNum++;

}

else if (sLexeme == BOOL)

{

Replace(SintaxStack, Grammatic, 12, 2);

nLexNum++;

}

else if (sLexeme == CONST)

{

Replace(SintaxStack, Grammatic, 13, 2);

nLexNum++;

}

else SintaxState = SinAnalizerState.Error;

}

else if (sTopStack == EXPR)

{

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 == LET)

{

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 == NEXT_BODY)

{

if (sLexeme == ;)

{

Replace(SintaxStack, Grammatic, 9, 2);

nLexNum++;

}

else if (sLexeme == })

{

SintaxStack.Pop();

}

else SintaxState = SinAnalizerState.Error;

}

else if (sTopStack == NEXT_DEF)

{

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 == NEXT_OPER)

{

if (sLexeme == ;)

{

Replace(SintaxStack, Grammatic, 24, 2);

nLexNum++;

}

else if (sLexeme == })

{

SintaxStack.Pop();

}

else SintaxState = SinAnalizerState.Error;

}

else if (sTopStack == NEXT_USING)

{

if (sLexeme == .)

{

Replace(SintaxStack, Grammatic, 5, 2);

nLexNum++;

}

else if (sLexeme == ;)

{

SintaxStack.Pop();

}

else SintaxState = SinAnalizerState.Error;

}

else if (sTopStack == NEXT_VAR)

{

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 == NEXT)

{

if (sLexeme == ;)

{

Replace(SintaxStack, Grammatic, 2, 2);

nLexNum++;

}

else if (sLexeme == #)

{

SintaxStack.Pop();

}

else SintaxState = SinAnalizerState.Error;

}

else if (sTopStack == OPER_LIST)

{

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 == OPERATION)

{

if (sLexeme == +)

{

Replace(SintaxStack, Grammatic, 38, 2);

nLexNum++;

}

else if (sLexeme == -)

{

Replace(SintaxStack, Grammatic, 39, 2);

nLexNum++;

}

else if ((sLexeme == )) ||

(sLexeme == ;) ||

(sLexeme == ,) ||

(sLexeme == ) ||

(sLexeme == =))

{

SintaxStack.Pop();

}

else SintaxState = SinAnalizerState.Error;

}

else if (sTopStack == OPERATOR)

{

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 == USING_LIST)

{

if (sClass == Идентификатор)

{

Replace(SintaxStack, Grammatic, 4, 2);

nLexNum++;

}

else SintaxState = SinAnalizerState.Error;

}

else if (sTopStack == COND)

{

if (sLexeme == ()

{

Replace(SintaxStack, Grammatic, 41, 2);

nLexNum++;

}

else if ((sClass == Идентификатор) ||

(sClass == Число))

{

Replace(SintaxStack, Grammatic, 42, 1);

}

else SintaxState = SinAnalizerState.Error;

}

else if (sTopStack == RELATION)

{

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 == )) ||

(sLexeme == ;))

{

SintaxStack.Pop();

}

else SintaxState = SinAnalizerState.Error;

}

else if (sTopStack == VAR_LIST)

{

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	Ошибка
R	Допустить

Множества ВЫБОР:

ВЫБОР(48)	using
ВЫБОР(49)	public
ВЫБОР(50)	;
ВЫБОР(51)	#
ВЫБОР(52)	ID
ВЫБОР(53)	.
ВЫБОР(54)	;
ВЫБОР(55)	class
ВЫБОР(56)	public
ВЫБОР(57)	;
ВЫБОР(58)	}
ВЫБОР(59)	uint
ВЫБОР(60)	bool
ВЫБОР(61)	const
ВЫБОР(62)	ID
ВЫБОР(63)	(
ВЫБОР(64)	,
ВЫБОР(65)	=
ВЫБОР(66)	;
ВЫБОР(67)	ID
ВЫБОР(68)	,
ВЫБОР(69)	=
ВЫБОР(70)	)
ВЫБОР(71)	for break continue write read ID
ВЫБОР(72)	;
ВЫБОР(73)	}
ВЫБОР(74)	for
ВЫБОР(75)	break
ВЫБОР(76)	continue
ВЫБОР(77)	write
ВЫБОР(78)	read
ВЫБОР(79)	ID
ВЫБОР(80)	=
ВЫБОР(81)	*
ВЫБОР(82)	/
ВЫБОР(83)	(
ВЫБОР(84)	ID
ВЫБОР(85)	NUM
ВЫБОР(86)	+
ВЫБОР(87)	-
ВЫБОР(88)	ID ; ) =
ВЫБОР(89)	(
ВЫБОР(90)	( ID NUM
ВЫБОР(91)
ВЫБОР(92)
ВЫБОР(93)	=
ВЫБОР(94)	; )

Формальная грамматика языка программирования:

Грамматика целевого символа:

( 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

Управляющая таблица синтаксического анализатора

(

)

;

{

}

bool

break

class

const

continue

for

int

long

NUM

public

read

using

write

(

В С

)

В С

;

В С

{

В С

}

В С

CLASS_BODY

З(9, 2) С

CLASS

З(8, 2) С

COND

З(42, 2) С

З(43, 1)

DEF_LIST

З(15, 2) С

DEF

З(13, 2) С

З(14, 2) С

EXPR

З(36, 2) С

З(37, 2) С

З(38, 2) С

LET

З(35, 2) С

З(34, 2) С

З(33, 2) С

NEXT_BODY

З(10, 2) С

NEXT_DEF

З(16, 2) С

З(17, 2) С

З(18, 2) С

NEXT_OPER

З(25, 2) С

NEXT_USING

З(6, 2) С

NEXT_VAR

З(21, 2) С

З(22, 2) С

З(3, 2) С

OPER_LIST

З(24, 1)

OPERATION

З(40, 2) С

З(39, 2) С

OPERATOR

В С

З(27, 2) С

З(32, 2) С

З(31, 2) С

З(30, 2) С

RELATION

З(45, 2) С

З(46, 2) С

З(44, 2) С

З(2, 2) С

З(1, 2) С

USING_LIST

З(5, 2) С

VAR_LIST

З(20, 2) С

В С

int

В С

long

В С

Скачать архив с текстом документа