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

Таблицы ключевых слов и разделителей - статические, таблицы идентификаторов и констант заполняются в процессе лексического и синтаксического анализа.

Статические таблицы лексем

Синтаксический анализатор

На этапе синтаксического анализа выполняется проверка синтаксической корректности исходной программы, представленной в виде потока токенов и совокупности таблиц, и преобразование ее в некоторую внутреннюю форму, удобную в дальнейшем для генерации объектного кода.

Опишем порядок действий, выполняемых при разработке синтаксического анализатора.

Построение КС-грамматики входного языка

Для построения КС-грамматики входного языка необходимо:

1. Заменить металингвистические переменные БНФ обозначениями нетерминальных символов, используя короткие имена;

2. В качестве терминальных символов использовать токены;

.   Металингвистический символ «:=» заменить символом «à»;

.   Заменить одну металингвистическую формулу с n альтернативами на n правил грамматики с одинаковым символом в левой части правила вывода;

.   Исключить металингвистические символы [] и {}, включив в правила грамматики e-правила и рекурсивные правила.

Получившаяся грамматика должна быть грамматикой простого предшествования.

Грамматика простого предшествования

Синтаксический анализ, основанный на простом предшествовании, использует для выделения основы правовыводимой цепочки αβw три отношения предшествования (<), (=) и (>) следующим образом:

· если β - основа, то между всеми смежными символами цепочки α выполняется либо отношение (<), либо (=);

·   между последним символом цепочки α и первым символом цепочки β выполняется отношение (<);

·   между смежными символами основы выполняется отношение (=);

·   между последним символом цепочки β и первым символом цепочки w выполняется отношение (>).

Очевидно, что правый конец основы правовыводимой цепочки грамматики простого предшествования можно выделить, просматривая эту цепочку слева направо до тех пор, пока впервые не встретится отношение (>). Для нахождения левого конца основы надо просмотреть ее назад, пока не встретится отношение (<). Цепочка, заключенная между отношениями (<) и (>), будет основой. Если грамматика является обратимой, т.е. не содержит правил с одинаковой правой частью, то основу можно однозначно свернуть. Этот процесс продолжается до тех пор, пока входная цепочка не свернется к начальному символу (либо пока дальнейшие свертки окажутся невозможными).

Отношения предшествования для КС-грамматики G = (N, Σ, Р, S) определяются на множестве (N U Σ U {┴}) × (N U Σ U {ε}) следующим образом:

· X < У, если в множестве правил грамматики Р есть правило А -> αXBβ и существует вывод В =>⁺ Yγ;

·   X = Y, если в Р содержится правило вида А -> αXYβ;

·   X > а, если в Р есть правило вида А -> αBYβ и существуют выводы В =>⁺ γX и Y => аδ (если У=>° аδ, то Y= а);

·   ┴ < X для всех X, для которых S =>⁺ Хα;

· Y > ε для всех Y, для которых S =>^* αY.

КС-грамматика G = (N, Σ, P, S) называется грамматикой предшествования, если она приведенная, не содержит ε - правил и для любой пары символов из множества N U Σ выполняется не более одного отношения предшествования.

Обратимая грамматика предшествования называется грамматикой простого предшествования.

Построение грамматики по БНФ

S -> pro id; Def BOp.-> pro id; BOp.-> Def BOp.-> BOp.

-> DfL Def-> DfL-> DfC Def-> DfC-> DfT Def-> DfT-> DfV Def-> DfV

-> lab LLb-> M;-> M, LLb

-> con LCn-> Cn1; LCn-> Cn1;-> id = Pex

-> typ LTp-> Tp1; LTp-> Tp1;-> id = Typ-> id = id-> Cid. Cid-> int-> chr-> str

-> var LVr-> DV1;-> DV1; LVr-> id-> Vr1, id-> Vr1-> Vrs: id-> Vrs: int-> Vrs: chr-> Vrs: str

-> id-> nat

-> M: Op-> Op-> BOp-> O:=-> OIO-> OMn

-> beg OPs end-> Op1-> Opl-> Opl; Op1

:= -> id:= Pex

-> OIn-> OOu-> rd (Vrs)-> wr (LWr)-> Pex-> Pex, W1-> W1

-> ORu-> OGo-> OIf-> rpt Ops unt Lex-> got M-> if Lex thn Opl-> if Lex thn Opl els Opl

-> Z1 F1-> Z1-> Z2 F2-> Z2-> Z3-> not Z3-> Z4-> sme (str, str)-> Pex Sgn Pex-> (Lex)-> or Z1 F1-> or Z1-> and Z2 F2-> and Z2-> <-> >-> =-> <=-> >=-> <>

-> T1 E1-> T1-> + T1 E1-> + T1-> - T1 E1-> - T1-> * T2 E2-> * T2-> / T2 E2-> / T2-> T2 E2-> T2-> id-> Cid-> Scn-> Fun-> (Pex)

Fun -> int (Pex)-> str (Pex)-> lng (Pex)-> cnc (Pex, Pex)-> pos (Pex, Pex)-> sym (Pex, Pex)

-> - nat-> nat

-> ' Sms '-> ' '-> Sym-> Any -> Any Sym