Курсовая Лексический анализатор. Краткий курс лекций. Курс лекций по спецкурсу Методы трансляции

• Название: Курс лекций по спецкурсу Методы трансляции
• Анкор: Курсовая Лексический анализатор
• Дата: 29.12.2019
• Размер: 0.64 Mb.
• Имя файла: Краткий курс лекций.doc
• Тип: Курс лекций; #102547
• страница: 13 из 19

Построение правил подстановки Флойда

Алгоритм построения правил подстановки Флойда для LR(1)-грамматик предполагает построение двух типов правил:

1. 
   помеченных S₀, которые строятся для нетерминала S, если верхний терминальный символ стека определяет начало строки, которая может быть свернута в S;
   
2. 
   помеченных S₁, если символ S (терминал или нетерминал) находится в следующей за вершиной позицией стека.
   

Обозначения:

L₀ – множество символов S, для которых нужно построить правила S₀;

L₀' – множество символов S, для которых уже построены правила S₀;

L₁ – множество символов S, для которых нужно построить правила S₁;

L₁' – множество символов S, для которых уже построены правила S₁.

Первоначально: L₀={Z} – начальный символ грамматики; L₀', L₁, L₁' – пустые множества.

Образование S₀-правил.

0.1 Если L₀\L₀' – пусто, то перейти к пункту 1.1.

0.2 Для символа H, принадлежащего L₀\L₀', построить LT'(H) – множество терминалов, с которых может начинаться разложение H. Для этого строится множество самых левых символов разложения H – L(H) и терминалы из L(H) включаются в LT'(H).

0.3 Для каждого t из LT'(H) найти множество правил грамматики:

{K | K→tz}={k₁,...,k_r}, z – произвольная строка, и выполнить следующие действия:

0.3.1 Если r > 1, то сформировать правило подстановки Флойда

│ H₀ │ t │ │ │*│ t₁ │ и включить t в L₁.

0.3.2 Если r = 1, то в зависимости от вида правила:

0.3.2.1 K → t │ H₀ │ t │ K │ │*│ K₁ │ и включить K в L₁;

0.3.2.2 K → tbw (b – терминал, w – произвольная строка)

│ H₀ │ t │ │ │*│ t₁ │ и включить t в L₁;

0.3.2.3 K → tGw (G – нетерминал)

│ H₀ │ t │ │ │*│ G₀ │ и включить G в L₀.

0.4 Уничтожить метку H₀ во всех правилах, кроме первого. Добавить правило

│ │ │ │ Ошибка │ │ │. Включить H в L₀'. Перейти к пункту 0.1.

Образование S₁-правил.

1.1 Если L₁\L₁' – пусто, то конец работы.

1.2 Для каждого символа X из L₁\L₁' выделить все правила грамматики, содержащие в правых частях символ X.

1.3 Для каждого выделенного правила G → uXv образовать правило подстановки Флойда в зависимости от вида правила грамматики:

1.3.1 Z → S┴ │ S₁ │ S┴ │ Z │ Выход │ │ │ и включить S в L₁;

1.3.2 G → uX │ X₁ │ uX │ G │ │ │ G₁ │ и включить G в L₁;

1.3.3 G → uXt │ X₁ │ uXt │ G │ │*│ G₁ │ и включить G в L₁;

1.3.4 G → uXUw, для каждого t из LT'(U)

│ X₁ │ uXt │ │ │ │ U₀ │ и включить U в L₀;

1.3.5 G → uXtbw (b – терминал)

│ X₁ │ uXt │ │ │*│ t₁ │ и включить t в L₁;

1.3.6 G → uXtUw │ X₁ │ uXt │ │ │*│ U₀ │ и включить U в L₀.

1.4 Правила с символом