Заданная грамматика может бать реализована автоматом со следующими состояниями:
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 – Управляющая таблица конечного автомата лексического анализатора
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 – множество разделительных символов [«–», «#», «(», «)», «*», «,», «/», «:», «;», «{«, «}», «+», «=»].