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

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

S - состояние ожидания первого символа лексемы;

I - состояние ожидания символов идентификаторов: буквы, цифры;

С - состояние ожидания символов целой части числа;

E -состояние ошибки;

R - состояние допуска лексемы.

Автомат переходит в допустимое состояние R из состояния I для идентификаторов и из состояния C для чисел.

Регулярная грамматика для заданных условий записи лексем задается следующими множествами:

Р: [P1, P2, … ,P4] - множество правил;

G: [S, I, C, E, R] - множество состояний, где S - начальный символ;

[0..9, A..Z, «-», «#», «(», «)», «*», «,», «.», «/», «:», «;», «{«, «}», «+», «=»] - множество входных символов, из них разделительные символы и уникальные лексемы [«-», «#», «(», «)», «*», «,», «/», «:», «;», «{«, «}», «+», «=»].

Символы пробел и табуляции означают конец лексемы. Эти символы не является лексемой и требуют выполнения операции «СДВИГ» над входной строкой. По символу пробел автомат допускает лексему и переходит в начальное состояние анализа следующего символа входной строки автомата.

Символы: «-», «#», «(», «)», «*», «,», «/», «:», «;», «{«, «}», «+», «=» являются одновременно разделительными знаками и началом следующей лексемы, даже если перед ними нет символа конца лексемы. Операция «СДВИГ» после этих символов не требуется, автомат допускает лексему и переходит в начальное состояние для анализа этих же символов.

Таблица 1 - Таблица переходов автомата распознавателя идентификаторов

Идентификация служебных слов реализована автоматом распознавателя: нагруженное дерево (Рисунок 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 Управляющая таблица конечного автомата лексического анализа

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

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

Для составления управляющей таблицы (таблица 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.

Листинг программы на формальном языке программирования загружается из текстового файла. Результаты работы обоих анализаторов (лексического и синтаксического) отображаются в виде таблиц с помощью компоненты ListView (рисунок 3).

Рисунок 3 - Компонента ListView

Для распознавания ключевых слов используется собственная структура данных, позволяющая реализовать нагруженое дерево (структура определена в п. 2.2).

Программа состоит из нескольких процедур и функций, наиболее важными из которых являются: процедура лексического анализа и процедура синтаксического анализа. Обе они приведены в приложении А. Данные процедуры служат соответствующими обработчиками кнопок «Лексический анализ» и «Синтаксический анализ».

Обмен данными между процедурами анализаторов осуществлен с помощью компонент ListView. Лексический анализатор добавляет в компонент ListView распознанные лексемы, а по завершении анализа эти лексемы в виде таблицы передаются на вход синтаксического анализатора.

4 Результаты тестирования

Листинг лексического анализатора

private void btnLex_Click(object sender, EventArgs e)

{

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

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;

}Приложение Б.

Листинг синтаксического анализатора