Курсовая Лексический анализатор. Краткий курс лекций. Курс лекций по спецкурсу Методы трансляции
![]()
|
Построение правил подстановки ФлойдаАлгоритм построения правил подстановки Флойда для LR(1)-грамматик предполагает построение двух типов правил: помеченных S0, которые строятся для нетерминала S, если верхний терминальный символ стека определяет начало строки, которая может быть свернута в S; помеченных S1, если символ S (терминал или нетерминал) находится в следующей за вершиной позицией стека. Обозначения: L0 – множество символов S, для которых нужно построить правила S0; L0' – множество символов S, для которых уже построены правила S0; L1 – множество символов S, для которых нужно построить правила S1; L1' – множество символов S, для которых уже построены правила S1. Первоначально: L0={Z} – начальный символ грамматики; L0', L1, L1' – пустые множества. Образование S0-правил. 0.1 Если L0\L0' – пусто, то перейти к пункту 1.1. 0.2 Для символа H, принадлежащего L0\L0', построить LT'(H) – множество терминалов, с которых может начинаться разложение H. Для этого строится множество самых левых символов разложения H – L(H) и терминалы из L(H) включаются в LT'(H). 0.3 Для каждого t из LT'(H) найти множество правил грамматики: {K | K→tz}={k1,...,kr}, z – произвольная строка, и выполнить следующие действия: 0.3.1 Если r > 1, то сформировать правило подстановки Флойда │ H0 │ t │ │ │*│ t1 │ и включить t в L1. 0.3.2 Если r = 1, то в зависимости от вида правила: 0.3.2.1 K → t │ H0 │ t │ K │ │*│ K1 │ и включить K в L1; 0.3.2.2 K → tbw (b – терминал, w – произвольная строка) │ H0 │ t │ │ │*│ t1 │ и включить t в L1; 0.3.2.3 K → tGw (G – нетерминал) │ H0 │ t │ │ │*│ G0 │ и включить G в L0. 0.4 Уничтожить метку H0 во всех правилах, кроме первого. Добавить правило │ │ Образование S1-правил. 1.1 Если L1\L1' – пусто, то конец работы. 1.2 Для каждого символа X из L1\L1' выделить все правила грамматики, содержащие в правых частях символ X. 1.3 Для каждого выделенного правила G → uXv образовать правило подстановки Флойда в зависимости от вида правила грамматики: 1.3.1 Z → S┴ │ S1 │ S┴ │ Z │ Выход │ │ │ и включить S в L1; 1.3.2 G → uX │ X1 │ uX 1.3.3 G → uXt │ X1 │ uXt │ G │ │*│ G1 │ и включить G в L1; 1.3.4 G → uXUw, для каждого t из LT'(U) │ X1 │ uXt │ │ │ │ U0 │ и включить U в L0; 1.3.5 G → uXtbw (b – терминал) │ X1 │ uXt │ │ │*│ t1 │ и включить t в L1; 1.3.6 G → uXtUw │ X1 │ uXt │ │ │*│ U0 │ и включить U в L0. 1.4 Правила с символом |