Нейтрализация ошибок в ГПП.

Ошибки: 1) отсутствие ОП

2) основа правильно выделена, но нет правил с нужной правой частью.

Для ошибок 2) делается минимальная коррекция основы, так чтобы подошло правило, «ближайшее» к выделенной основе.

Для ошибок 1) либо изменение символов

либо вставка символов во входную цепочку или в стек

либо удаление из входной цепочки или из стека

5. КОНТЕКСТНЫЙ АНАЛИЗ.

На входе: синтаксическое дерево разбора.

На выходе: атрибутное дерево программы; удаление всех нетерминалов;

Контекстный анализ состоит из 2-х этапов:

идентификация: определяются атрибуты лексем (висячих вершин);

атрибутная индукция: определяются атрибуты понятий (невисячих вершин).

В качестве атрибутов используются, например, типы переменных (операндов операций).

Идентификация.

Если лексема - const, то вид ее определяет эти атрибуты.

Если лексема - не const, то определяется тип специфическим атрибутом программы, определяющим лексему. Определяющее вхождение только в своей области определения. Правило определения области действия должно однозначно поставить в соответствие область, определяющую вхождение лексем.

Идентификация может служить источником ошибок, называемых семантическими.

Реализация идентификации идет в виде построения таблицы имен. Она содержит: имя (8 символов), ссылка на продолжение имени, тип, ссылка на атрибуты массива.

При вложенных областях имя объекта усложняется: нумеруются области и имя: номер-области.имя- переменной, С ними при трансляции связан стек. Если описание массивов динамическое, то идентификацию провести нельзя. Этот атрибут помечается, что определяется при выполнении программы.

Имеются полиморфные процедуры, выполняющиеся в зависимости от типа переменных.

5.2. Атрибутная индукция. Идет либо снизу вверх, либо сверху вниз.

+

/ \ cнизу

а * вверх

/ \

b c

Поскольку у нас *, то надо «идти на жертвы»,т.е. при преобразовании типов (в случае + можно оставить одно преобразование)

6. ГЕНЕРАЦИЯ КОДА.

6.1. Общая схема генерации.

Методы генерации зависят от выходного языка.

Рассмотрим трехадресную модель. В ней команды имеют вид

Q i AiBiCi, где Q i -код операции, Ai, Bi – операнды(их адреса), Ci - адрес результата.

Goto M~БП-М-

Генерация – это превращение атрибутного дерева в строку объектной программы.

Каждую (невисячую) вершину атрибутного дерева превратим в строку объектного кода с помощью трансдуктора (для каждой операции- свой трансдуктор).

В каком порядке обходится дерево? Управляющий алгоритм определяет обход дерева и построение строки. Просмотр происходит последовательно, без возврата.

При нисходящем разборе используют префиксную запись, при восходящем – постфиксную.

Для входной строки а:= b + c * d постфикс: cd * b + a:= или abcd *+:=, префикс::= a + b * cd.

Т.к. функции могут иметь произвольное число параметров, нужны разделители ◁, ▷ и |.

Для строки F(x,y,z) - постфикс ◁ x | y | z | F ▷, префикс ◁ F | x | y | z ▷.

Помимо трансдуктора элементарных операций необходимы обобщенные трансдукторы (метатрансдукторы) для более сложных конструкций.

6.2. Генерация выражений и операций присваивания.

Пусть у нас нет переменных с индексами и функций.

Тогда трансдуктор имеет дело с деревом, у которого корень и невисячие вершины –операции, а листья –переменные или константы.

Пример 1. Постфиксная: abc +* db -2 ­/ (кстати, инфиксная запись такова: a *(b + c)/(d - b) ­2)

/

/ \

* ­

/ \ / \

a + - 2

/ | | \

b c d b

Можно было обойтись двумя ячейками t₁,t₂,t₅ ~ t₁; t₃? t₄ ~ t₂.

Пример 2. a * b -(c - d)*(b + c)

Составим постфикс: ab * cd - bc +*- (обход слева) cb + dc -* ba *- (Обход справа)

Какой обход дерева операций использовать (слева или справа), можно узнать на этапе контекстного анализа.

Вводится характеристика вершины (сколько переменных надо для обсчета вершины v):

n (v) = if n (v ₁) = n (v ₂) then n (v ₁)+1 else max { n (v_i)}

Сначала нужно раскрывать ту вершину, у которой n (v) больше!!!

Вопрос на экзамен: проследите за порядком операндов в некоммутирующих операциях.

Пусть исполнитель – одноадресная машина, у которой есть накопитель S и команды:

L x (load = загрузка ячейки x в накопитель: x ®S)

ST x (storage = сохранение накопителя в ячейке x: S® x)

Ä x -одна из операций (сложение, вычитание, умножение, деление) SÄx®S

Команда – cdt трехадресной модели реализуется тремя командами одноадресной модели:

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

Замечания:

1) когда требуется выбрать результат предыдущей операции, в стек записывается символ S.

2) Если операция некоммутируемая, то выгоднее сначала обойти правую ветвь дерева

3) Память бывает разных видов: быстрая, оперативная и на дисках. Если быстрая память находится в регистрах, то нужно использовать их для рабочих переменных.

4) Если компьютер является стековой машиной, то это удобно для генерации.

Не нашли, что искали? Воспользуйтесь поиском: