Распознаватели констант и служебных слов

1 2 3 4 5 6 7

Заданная грамматика может бать реализована автоматом со следующими состояниями:

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

}

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

Управляющая таблица лексического анализатора для заданной выше грамматики показана в таблице 2. Листинг программы, реализующей данную управляющую таблицу, приведен в приложении А.

При составлении таблицы использовались следующие обозначения:

– первым символом указывается состояние, в которое переходит автомат при поступлении соответствующего символа;

– символ «+» означает добавление входного символа к лексеме;

– символ «>>» означает сдвиг входной строки на один символ.

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