Теория и реализация языков программирования




Конструирование LR(1)-таблицы


Рассмотрим алгоритм конструирования таблицы, управляющей LR(1) - анализатором.

Пусть G = (N, T, P, S) - КС-грамматика. Пополненной грамматикой для данной грамматики G называется КС- Состояния Action Goto


Рис. 4.7. 


Рис. 4.8. 

грамматика

G' = (N \cup \{S'\}, T, P \cup \{S' \rightarrow S\}, S');

то есть эквивалентная грамматика, в которой введен новый начальный символ S' и новое правило вывода S'

S.

Это дополнительное правило вводится для того, чтобы определить, когда анализатор должен остановить разбор и зафиксировать допуск входа. Таким образом, допуск имеет место тогда и только тогда, когда анализатор готов осуществить свертку по правилу S'

S.

LR(1)-ситуацией называется пара [A

.?, a], где A
? - правило грамматики, a - терминал или правый концевой маркер $. Вторая компонента ситуации называется аванцепочкой.

Будем говорить, что LR(1)-ситуация [A

.?, a] допустима для активного префикса +, если существует вывод
S \Rightarrow^*_r \gamma A w \Rightarrow_r \gamma \alpha \beta w
, где + = ?
и либо a - первый символ w, либо w = e и a = $.

Будем говорить, что ситуация допустима, если она допустима для какого-либо активного префикса.

Пример 4.11. Дана грамматика G = ({S, B}, {a, b}, P, S) с правилами

S

BB

B

aB | b

Существует правосторонний вывод

S \Rightrarrow^*_r aaBab \Rightrarrow_r aaaBab
. Легко видеть, что ситуация [B
a.B, a] допустима для активного префикса + = aaa, если в определении выше положить ? = aa, A = B, w = ab,
= a, ? = B. Существует также правосторонний вывод
S \Rightarrow^*_r BaB \Rightarrow_r BaaB
. Поэтому для активного префикса Baa допустима ситуация [B
a.B, $].

Центральная идея метода заключается в том, что по грамматике строится детерминированный конечный автомат, распознающий активные префиксы. Для этого ситуации группируются во множества, которые и образуют состояния автомата. Ситуации можно рассматривать как состояния недетерминированного конечного автомата, распознающего активные префиксы, а их группировка на самом деле есть процесс построения детерминированного конечного автомата из недетерминированного.

Анализатор, работающий слева-направо по типу сдвиг- свертка, должен уметь распознавать основы на верхушке магазина. Состояние автомата после прочтения содержимого магазина и текущий входной символ определяют очередное действие автомата.


Содержание  Назад  Вперед