Лексический и синтаксический анализатор языка высокого уровня (стр. 4 из 7)
| СЛЕД(<S>)2 | # |
| СЛЕД(<NEXT>)2 | |
| СЛЕД(<USING_LIST>)2 | ; |
| СЛЕД(<NEXT_USING>)2 | |
| СЛЕД(<CLASS>)2 | ; |
| СЛЕД(<CLASS_BODY>)2 | } |
| СЛЕД(<NEXT_BODY>)2 | |
| СЛЕД(<DEF>)2 | ; |
| СЛЕД(<DEF_LIST>)2 | |
| СЛЕД(<NEXT_DEF>)2 | |
| СЛЕД(<VAR_LIST>)2 | ) |
| СЛЕД(<NEXT_VAR>)2 | |
| СЛЕД(<OPER_LIST>)2 | } |
| СЛЕД(<NEXT_OPER>)2 | |
| СЛЕД(<OPERATOR>)2 | ; |
| СЛЕД(<LET>)2 | ) |
| СЛЕД(<EXPR>)2 | ID ; ) < > = |
| СЛЕД(<OPERATION>)2 | |
| СЛЕД(<COND>)2 | ; ) |
| СЛЕД(<RELATION>)2 |
Шаг 5. Для всех нетерминальных символов A во множество СЛЕД(A) включить множества СЛЕД (В), если существует правило B=aA, a Î (VT È VN).
| СЛЕД(<S>)3 | # |
| СЛЕД(<NEXT>)3 | # |
| СЛЕД(<USING_LIST>)3 | ; |
| СЛЕД(<NEXT_USING>)3 | ; |
| СЛЕД(<CLASS>)3 | ; |
| СЛЕД(<CLASS_BODY>)3 | } |
| СЛЕД(<NEXT_BODY>)3 | } |
| СЛЕД(<DEF>)3 | ; |
| СЛЕД(<DEF_LIST>)3 | ; |
| СЛЕД(<NEXT_DEF>)3 | ; |
| СЛЕД(<VAR_LIST>)3 | ) |
| СЛЕД(<NEXT_VAR>)3 | ) |
| СЛЕД(<OPER_LIST>)3 | } |
| СЛЕД(<NEXT_OPER>)3 | } |
| СЛЕД(<OPERATOR>)3 | ; |
| СЛЕД(<LET>)3 | ) |
| СЛЕД(<EXPR>)3 | ID ; ) < > = |
| СЛЕД(<OPERATION>)3 | ID ; ) < > = |
| СЛЕД(<COND>)3 | ; ) |
| СЛЕД(<RELATION>)3 | ; ) |
Шаг 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;
– ДОП. – синтаксический анализ прошел успешно.
Листинг программы, реализующей данную управляющую таблицу, приведен в приложении А.
Программа выполнена в виде Windows-приложения с оконным интерфейсом (рисунок 2 в среде Microsoft Visual Studio.
Рисунок 2 - Интерфейс программы
Листинг программы на формальном языке программирования загружается из текстового файла. Результаты работы обоих анализаторов (лексического и синтаксического) отображаются в виде таблиц с помощью компоненты ListView (рисунок 3).
Рисунок 3 - Компонента ListView
Для распознавания ключевых слов используется собственная структура данных, позволяющая реализовать нагруженое дерево (структура определена в п. 2.2).
Программа состоит из нескольких процедур и функций, наиболее важными из которых являются: процедура лексического анализа и процедура синтаксического анализа. Обе они приведены в приложении А. Данные процедуры служат соответствующими обработчиками кнопок «Лексический анализ» и «Синтаксический анализ».
Обмен данными между процедурами анализаторов осуществлен с помощью компонент ListView. Лексический анализатор добавляет в компонент ListView распознанные лексемы, а по завершении анализа эти лексемы в виде таблицы передаются на вход синтаксического анализатора.
Для тестирования программы использовался следующий код на формальном языке программирования:
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 - Ошибка на этапе синтаксического анализа.