Лексический и синтаксический анализатор языка высокого уровня (стр. 2 из 7)
Символы: «–», «#», «(», «)», «*», «,», «/», «:», «;», «{«, «}», «+», «=» являются одновременно разделительными знаками и началом следующей лексемы, даже если перед ними нет символа конца лексемы. Операция «СДВИГ» после этих символов не требуется, автомат допускает лексему и переходит в начальное состояние для анализа этих же символов.
Таблица 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 – номер итерации.
| ПЕРВ(1) 0 | using |
| ПЕРВ(2)0 | public |
| ПЕРВ(3) 0 | ; |
| ПЕРВ(4)0 | |
| ПЕРВ(5) 0 | ID |
| ПЕРВ(6)0 | . |
| ПЕРВ(7) 0 | |
| ПЕРВ(8)0 | class |
| ПЕРВ(9)0 | public |
| ПЕРВ(10) 0 | ; |
| ПЕРВ(11) 0 | |
| ПЕРВ(12) 0 | uint |
| ПЕРВ(13) 0 | bool |
| ПЕРВ(14) | const |
| ПЕРВ(15) 0 | ID |
| ПЕРВ(16) 0 | ( |
| ПЕРВ(17) 0 | , |
| ПЕРВ(18) | = |
| ПЕРВ(19) 0 | |
| ПЕРВ(20) 0 | ID |
| ПЕРВ(21) 0 | , |
| ПЕРВ(22) | = |
| ПЕРВ(23) 0 | |
| ПЕРВ(24) 0 | <OPERATOR> |
| ПЕРВ(25) 0 | ; |
| ПЕРВ(26) 0 | |
| ПЕРВ(27) 0 | for |
| ПЕРВ(28) 0 | break |
| ПЕРВ(29) 0 | continue |
| ПЕРВ(30) 0 | write |
| ПЕРВ(31) 0 | read |
| ПЕРВ(32) 0 | ID |
| ПЕРВ(33) 0 | = |
| ПЕРВ(34) 0 | * |
| ПЕРВ(35) 0 | / |
| ПЕРВ(36) 0 | ( |
| ПЕРВ(37) 0 | ID |
| ПЕРВ(38) | NUM |
| ПЕРВ(39) 0 | + |
| ПЕРВ(40) 0 | - |
| ПЕРВ(41) 0 | |
| ПЕРВ(42) 0 | ( |
| ПЕРВ(43) 0 | <EXPR> |
| ПЕРВ(44) 0 | > |
| ПЕРВ(45) 0 | < |
| ПЕРВ(46) 0 | = |
| ПЕРВ(47) 0 |
Шаг 2. Если множество первых символов содержит нетерминал В, то включить в него символы множества ПЕРВ(В), определенное на шаге 0.
| ПЕРВ(1) 1 | using |
| ПЕРВ(2)1 | public |
| ПЕРВ(3) 1 | ; |
| ПЕРВ(4)1 | |
| ПЕРВ(5) 1 | ID |
| ПЕРВ(6)1 | . |
| ПЕРВ(7) 1 | |
| ПЕРВ(8)1 | class |
| ПЕРВ(9)1 | public |
| ПЕРВ(10) 1 | ; |
| ПЕРВ(11) 1 | |
| ПЕРВ(12) 1 | uint |
| ПЕРВ(13) 1 | bool |
| ПЕРВ(14) 1 | const |
| ПЕРВ(15) 1 | ID |
| ПЕРВ(16) 1 | ( |
| ПЕРВ(17) 1 | , |
| ПЕРВ(18) 1 | = |
| ПЕРВ(19) 1 | |
| ПЕРВ(20) 1 | ID |
| ПЕРВ(21) 1 | , |
| ПЕРВ(22) 1 | = |
| ПЕРВ(23) 1 | |
| ПЕРВ(24) 1 | for break continue write read ID <OPERATOR> |
| ПЕРВ(25) 1 | ; |
| ПЕРВ(26) 1 | |
| ПЕРВ(27) 1 | for |
| ПЕРВ(28) 1 | break |
| ПЕРВ(29) 1 | continue |
| ПЕРВ(30) 1 | write |
| ПЕРВ(31) 1 | read |
| ПЕРВ(32) 1 | ID |
| ПЕРВ(33) 1 | = |
| ПЕРВ(34) 1 | * |
| ПЕРВ(35) 1 | / |
| ПЕРВ(36) 1 | ( |
| ПЕРВ(37) 1 | ID |
| ПЕРВ(38) 1 | NUM |
| ПЕРВ(39) 1 | + |
| ПЕРВ(40) 1 | - |
| ПЕРВ(41) 1 | |
| ПЕРВ(42) 1 | ( |
| ПЕРВ(43) 1 | ( ID NUM <EXPR> |
| ПЕРВ(44) 1 | > |
| ПЕРВ(45) 1 | < |
| ПЕРВ(46) 1 | = |
| ПЕРВ(47) 1 |
Шаг 3. Если ПЕРВ(n)i+1 ≠ ПЕРВ(n)i, то i = i + 1 и перейти к шагу 2, иначе закончить.