Методические указания (1114907), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Таблица синтаксического анализа состоит из двух частей – функций действий синтаксического анализа action и функции переходов goto. Управляющая программа LR-анализатора функционирует следующим образом. Она определяет s_m­, текущее состояние на вершине стека, и a_i, текущий входной символ. Затем программа обращается к action[s_m, a_i], ячейке таблицы действий синтаксического анализа, определяемой состоянием s_m и символами a_i, которая может иметь одно из четырех значений:

1. перенос s, где s – состояние;

2. свертка в соответствии с продукцией A -> β;

3. допуск (accept);

4. ошибка (error);

Рис. 4.1. Модель LR-анализатора

Функция goto получает в качестве аргументов состояние и символ грамматики и возвращает новое состояние.

Конфигурация LR-анализатора представляет собой пару, первый компонент которой – содержимое стека, а второй – непросмотренная часть входного потока: (s₀X₁s₁X₂s₂…X_ms_m, a_ia_i+1…a_n$).

Следующий шаг синтаксического анализатора определяется текущим входным символом a_i и состоянием на вершине стека s_m в соответствии со значением ячейки таблицы action[s_m, a_i]. Конфигурации, получаемые после каждого из четырех типов действий следующие:

1. Если action[s_m, a_i] = “перенос s”, синтаксический анализатор выполняет перенос, переходя в конфигурацию (s₀X₁s₁X₂s₂…X_ms_ma_is, a_i+1…a_n$). Синтаксический анализатор переносит в стек текущий входной символ a_i и очередное состояние s, определяемое значением action[s_m, a_i]; текущим входным символом становится a_i+1.

2. Если action[s_m, a_i] = “свертка A -> β”, то синтаксический анализатор выполняет свертку в конфигурацию (s₀X₁s₁X₂s₂…X_m-rs_m-rAs, a_ia_i+1…a_n$), где s = goto[s_m-r, a_i], a r – длина β, правой части продукции. Здесь синтаксический анализатор вначале снимает со стека 2r символов (r символов состояний и r символов грамматики), выводя на вершину стека состояние s_m-r. Затем вносит в стек A (левую часть продукции) и s, запись из ячейки goto[s_m-r, A]. Текущий входной символ при этом не изменяется. Последовательность снимаемых со стека символов грамматики X_m-r+1…X_m всегда соответствуют β, правой части продукции свертки.

3. Если action[s_m, a_i] = “допуск”, синтаксический анализ завершается.

4. Если action[s_m, a_i] = “ошибка”, синтаксический анализатор обнаружил ошибку и вызывает подпрограмму восстановления после нее.

Полностью алгоритм LR-анализа приведен ниже. Все LR-анализаторы ведут себя одинаково; единственная разница между ними заключается в таблицах action и goto.

Вход. Входная строка w и таблица LR-анализа с функциями action и goto для грамматики G.

Выход. Если w ϵ L(G), выдается восходящий разбор для w; в противном случае выводится сообщение об ошибке.

Алгоритм. Изначально синтаксический анализатор содержит в стеке начальное состояние s₀, а во входном буфере – w$. Затем анализатор выполняет приведенный ниже алгоритм до тех пор, пока не будет достигнуто успешное завершение анализа или не обнаружена ошибка.

Установить указатель ip на первый символ w$;

repeat forever begin

Пусть s – состояние на вершине стека, а a – символ, на который указывает ip

if action[s,a] = “перенос s” then begin

Поместить в стек a, затем s’; переместить ip к следующему входному символу

end

else if action[s,a] = “свертка A -> β” then begin

Снять со стека 2*|β| символов. Пусть s’ – текущее состояние на вершине стека. Поместить в стек A, затем goto[s’,A]; вывести продукцию A -> β.

end

else if action[s,a] = “допуск” then

return

else error()

end

Пример части таблицы LR-анализа.

• Поясним обозначения в данной таблице.
  s_i означает перенос и i-е состояние на вершине стека,

• r_j означает свертку в соответствии с продукцией номер j,

• accept означает допуск входной строки,

• пустая ячейка означает ошибку,

• В части action находятся терминальные символы грамматики, в части goto, соответственно, нетерминальные.

Восстановление после ошибок при LR-анализе.

LR-анализатор обнаруживает ошибку при обращении к таблице action синтаксического анализа при нахождении там записи об ошибке (при обращении к таблице goto ошибки не выявляются).

Восстановление на уровне фразы реализуется путем проверки каждой ошибочной записи в таблице LR-анализа и принятия решения (на основе знания особенностей языка) о том, какая наиболее вероятная ошибка программиста могла привести к данной ситуации. После этого можно построить подходящую процедуру восстановления после ошибки; возможно, при этом придется изменить вершину стека и/или первые символы входного потока способом, соответствующим данной записи ошибки.

Таким образом, мы можем заполнить каждую пустую ячейку в таблице action указателем на программу обработки ошибок, которая будет выполнять некоторые действия, определенные разработчиком компилятора. Эти действия могут включать вставку символов в стек или входной поток и удаление их оттуда или изменение и перестановку входных символов, как и в случае синтаксического анализатора приоритета операторов. Как и в упомянутом случае, мы не должны допустить возможности зацикливания LR-анализатора. Стратегия, гарантирующая отсутствие зацикливания, требует либо удаления (переноса) из входного потока по меньшей мере одного символа, либо уменьшения стека или достижения конца входного потока. Снятие со стека состояния над нетерминалом следует избегать, поскольку такое изменение удаляет из стека успешно разобранную конструкцию.

Условие:

1. Определить значение функций FIRST и FOLLOW для разработанной грамматики.

2. Построить множество пунктов.

3. Построить диаграмму переходов.

4. Построить таблицу SLR анализатора c учетом вариантов восстановления после ошибок.

5. Проверить правильность построения на трех примерах (один правильный, два неправильных).

Варианты:

Пример построения таблицы SLR-анализатора:

1. Исходная грамматика для декларации функции:

• D -> i(P);

• P -> iF

• P -> ε

• F -> ,iF

• F -> ε

1. Построим функции FIRST и FOLLOW для грамматики, заданной в условии (подробнее построение этих функций описано в задаче 3).

FIRST(D) = {i} FOLLOW(D) = {$}

FIRST(P) = {i, ε} FOLLOW(P) = {)}

Характеристики

Список файлов книги