В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 21
Текст из файла (страница 21)
Если приэтом B ∈ N , то определены e-переходы в состояния [B → .ξ , b] для всехправил с участием B . Начальным состоянием будем считать [S ′ → .S , $], всесостояния — заключительные.Теорема 4.8. Определенный таким образом недерминированный конечный автомат допускает в точности активные префиксы грамматики.4.5.
Разбор снизу-вверх типа сдвиг-свертка101Д о к а з а т е л ь с т в о проводится индукцией по длине активного префикса.По недерминированному конечному автомату можно построить эквивалентный детерминированный в соответствии с алгоритмом, изложеннымв подразделе 3.4.2. Это осуществляется приведенными ниже функциямиclosure, goto и items.Алгоритм 4.11. Конструирование канонической системы множеств допустимых LR(1)-ситуаций.Вход. КС-грамматика G = (N , T , P , S).Выход. Каноническая система C множеств допустимых LR(1)-ситуацийдля грамматики G.Метод.
Выполнить для пополненной грамматики G′ процедуру items,которая использует функции closure и goto.SetOf Itemsclosure(SetOf ItemsI){do {SetOf Items J = I ;for (каждой ситуации [A → α.Bβ , a] из J ,каждого правила вывода B → γ из G′ ,каждого терминала b из F IRST (βa),такого, что [B → .γ , b] нет в J )добавить [B → .γ , b] к J ;}while (к J можно добавить новую ситуацию);return J ;}SetOfItems goto(SetOfItems I,GrammarSymbol X){/* X - символ грамматики */Пусть J = {[A → αX.β , a] | [A → α.Xβ , a] ∈ I};return closure(J );}items(Gramma G’){ /* G′ - пополненная грамматика */I0 = closure({[S ′ → .S , $]});C = {I0 };do{for (каждого множества ситуаций I изсистемы C , каждого символа грамматики X ){SetOfItems J = goto(I , X);/ C)Если (J 6= ∅)&(J ∈добавить J к системе C ;} }102Глава 4.
Синтаксический анализwhile (к C можно добавить новое множествоситуаций);}Если I — множество ситуаций, допустимых для некоторого активногопрефикса δ , то goto(I , X) — множество ситуаций, допустимых для активногопрефикса δX .Система множеств допустимых LR(1)-ситуаций для всевозможных активных префиксов пополненной грамматики называется канонической системоймножеств допустимых LR(1)-ситуаций.Работа алгоритма построения системы C множеств допустимых LR(1)ситуаций начинается с того, что в C помещается начальное множествоситуаций I0 = closure({[S ′ → .S , $]}). Затем с помощью функции gotoвычисляются новые множества ситуаций и включаются в C . По-существу,goto(I , X) — переход конечного автомата из состояния I по символу X .Рассмотрим теперь, как по системе множеств LR(1)-ситуаций строитсяLR(1)-таблица, т.
е. функции действий и переходов LR(1)-анализатора.Алгоритм 4.12. Построение LR(1)-таблицы.Вход. Каноническая система C = {I0 , I1 , . . . , In } множеств допустимыхLR(1)-ситуаций для грамматики G.Выход. Функции Action и Goto, составляющие LR(1)-таблицу для грамматики G.Метод. Для каждого состояния i функции Action[i, a] и Goto[i, X] строятся по множеству ситуаций Ii :1. Значения функции действия (Action) для состояния i определяютсяследующим образом:а) если [A → α.aβ , b] ∈ Ii (a — терминал) и goto(Ii , a)= Ij , то полагаем Action[i, a] = shift j ;б) если [A → α., a] ∈ Ii , причем A 6= S ′ , то полагаем Action[i, a] == reduce A → α;в) если [S ′ → S., $] ∈ Ii , то полагаем Action[i, $] = accept.2. Значения функции переходов для состояния i определяются следующимобразом: если goto(Ii , A) = Ij , то Goto[i, A] = j (здесь A — нетерминал).3.
Все входы в Action и Goto, не определенные шагами 2 и 3, полагаемравными error.4. Начальное состояние анализатора строится из множества, содержащегоситуацию [S ′ → .S , $].4.5. Разбор снизу-вверх типа сдвиг-свертка103LR(1)-таблица на основе функций Action и Goto, полученных в результатеработы алгоритма 4.12, называется канонической.
Работающий с ней LR(1)анализатор называется каноническим.Пример 4.14. Рассмотрим следующую грамматику, являющуюся пополненнойдля грамматики из примера 4.8:0) E ′ → E ;1) E → E + T ;2) E → T ;3) T → T ∗ F ;4) T → F ;5) F → id.Множества ситуаций и переходы по goto для этой грамматики приведенына рис. 4.7. LR(1)-таблица для этой грамматики приведена в табл. 4.3.4.5.4.
Конструктор LR(1)-анализаторов на Java. В программном приложении приведен пакет LR1, содержащий LR(1)-конструктор и анализатор.Используются следующие структуры данных:HashMap GrammarR = new HashMap();/* Набор отображений номер правила-> Левая часть, правая часть */HashMap GrammarN = new HashMap();/* Для каждого нетерминала Набор отображений номер правила ->/* правая часть */HashSet Nonterms = new HashSet(), Terminals = new HashSet();LinkedList statesList = new LinkedList();/** Список необработанных состояний; содержит номера состояний из* canonicalSystem*/HashMap canonicalSystem = new HashMap();/* Это отображение Номер состояния -> множество LR1 ситуаций */HashMap actionTable = new HashMap();/* Это отображение Номер состояния ->входной символ -> действие */HashMap gotoTable = new HashMap();/* Это отображение Номер состояния ->нетерминал -> состояние */4.5.5. Корректность построения.Теорема 4.9.
Если G = (N , T , P , S ′ ) — LR(1)-грамматика, товывод S ⇒ πr w существует титтк последовательность шагов LR(1)анализатора такова, что (I0 , w$, e) ⊢∗ (I0 SI , $, π), Action(I , $) = accept.Здесь π — цепочка номеров примененных правил правостороннего выводаи эта цепочка добавлена в порядке применения свертки (последняя слева)в конфигурацию анализатора.104Глава 4. Синтаксический анализ2Рис. 4.7Д о к а з а т е л ь с т в о . Д о с т а т о ч н о с т ь . Индукцией по l = |π|покажем, что если S ⇒ πr αx, α ∈ (N ∪ T )∗ , x ∈ T ∗ , то (I0 X1 I1 .
. .. . . Xm Im , x$, e) ⊢∗ (I0 SI , $, π), где X1 X2 ...Xm = α, I0 — начальное состояниеDF AG , Ii — состояние DF AG после прочтения X1 X2 . . . Xi (а не состояниес номером i).Базис. Пусть l = 1, т. е. π = i. Тогда S ⇒ ir αx, т. е. существует правило (i)S → αx ∈ P . Пусть x = a1 a2 ...ap . Согласно определению активных4.5. Разбор снизу-вверх типа сдвиг-свертка105префиксов и допустимых для них ситуаций:[S → α.a1 ...aj ...ap , $] ∈ Im = DF AG (α) = DF AG (X1 X2 ...Xm );[S → αa1 .a2 ...ap , $] ∈ Im = DF AG (αa1 );[S → αa1 . .
. ap−1 .ap , $] ∈ Im = DF AG (αa1 . . . ap−1 );[S → αa1 . . . ap ., $] ∈ Im = DF AG (αa1 . . . ap ) = DF AG (αx).Тогда по построению Action(Im+j−1 , aj ) = shif t Im+j , Action(Im+j , $)= reduce i. Поэтому (I0 X1 I1 . . . Xm Im , x$, e) = (I0 X1 I1 . . . Xm Im , a1 . . .. . . ap $, e) ⊢∗ (I0 X1 I1 . . . Xm Im Im+1 . .
. ap Im+p , $, e) ⊢ (I0 ST , $, i), ч. т. д.Шаг индукции. Предположим, что утверждение выполняется для l 6 n(n > 1). Покажем, что оно выполняется для l = n + 1.′Имеем S ⇒ πr α′ Aw ⇒ ir α′ βw = αx. Очевидно, что x заканчивается цепочкой w, т. е. x = zw.
Тогда: α, α′ ∈ (N ∪ T )∗ , w, x, z ∈ T ∗ , π = π ′ i; A → β ∈ P ,β = β ′ z , α = α′ β ′ .′(i)Имеющийся вывод можно представить как S ⇒ πr α′ Aw ⇒ r = α′ βw =′′′′′= α β zw. Имеем A → β = β z ∈ P , тогда α β — активный префикс α′ β ′ zw,причем DF AG (α′ β ′ ) = DF AG (α) = Im ; поэтому [A → β ′ .z , u] ∈ Im , u == F IRST (w)(либо u = $, если w = e). Пусть z = a1 .
. . ap . По построениюAction(Im , a1 ) = shif t Im+1 , . . .Action(Im+p−1 , ap ) = shif t Im+p , Im+p =DF AG (α′ β), Action(Im+p , u) = reduce I , u = F IRST (w)(либо u = $).Анализатор осуществляет следующие такты:(I0 X1 I1 . . . Xj Ij Xj+1 Ij+1 . . . Xm Im , x$, e) =(I0 X1 I1 . .
. Xj Ij Xj+1 Ij+1 . . . Xm Im , zw$, e) =(I0 X1 I1 . . . Xj Ij Xj+1 Ij+1 . . . Xm Im , a1 . . . ap w$, e) ⊢(I0 X1 I1 . . . Xj Ij Xj+1 Ij+1 . . . Xm Im a1 Im+1 , a2 . . . ap w$, e) ⊢(I0 X1 I1 . . . Xj Ij Xj+1 Ij+1 . . . Xm Im a1 Im+1 . . . ap Im+p , w$, e) =′ , w$, i) ⊢∗ (I ST , $, π ′ i) = (I SI , $, π).(I0 X1 I1 . . . Xj Ij AIj+001Последний переход обоснован предположением индукции с учетом того,′G ′′что Ij+1 = Goto(Ij , A), Ij+1 = DF A (α A), α = X1 X2 . . . Xj . В частности,π∗если α = e, т.е.
S ⇒ r x, то (I0 , x$, e) ⊢ (I0 SI , $, π).Н е о б х о д и м о с т ь . Индукцией по числу l тактов анализатора покажем, что если (I0 , w$, e) ⊢l (I0 X1 I1 . . . Xj Ij Xj+1 Ij+1 . . . Xm Im , x$, π), тоαx ⇒ πr w, α = X1 . . . Xj . . . Xm , x, w ∈ T ∗ , т. е. содержимое магазина в конкатенации с непросмотренной входной строкой представляет правосентенциальную форму, выводимую с помощью последовательности правил π .Базис.
Пусть l = 1. Если это shif t, то пусть (I0 , w$, e) == (I0 , X1 x$, e) ⊢ (I0 X1 I , x$, e), w = X1 x. Тогда X1 x ⇒ w за 0 шагов. Еслиэто шаг reduce i, то, поскольку в начальной конфигурации (I0 , w$, e)магазин пуст (состояние I0 не учитываем), основа также пуста. Значит,[A → e., u] ∈ I0 , (I0 , w$, e) ⊢ (I0 AI , w$, e), u = F IRST (w), (либо u = $), такчто Aw ⇒ (i) w.106Глава 4.
Синтаксический анализШаг. Пусть анализатор осуществляет l = n + 1 шагов. Первые n шаговдают (I0 , w$, e) ⊢n (I0 X1 I1 . . . Xj Ij Xj+1 Ij+1 . . . Xm Im , x′ $, π ′ ).′По предположению индукции X1 . . . Xj . . . Xm x′ ⇒ πr w, затем осуществляется последний шаг. Пусть это shif t. Тогда:(I0 X1 I1 . . . Xj Ij Xj+1 Ij+1 . .
. Xm Im , x′ $, π ′ ) =(I0 X1 I1 . . . Xj Ij Xj+1 Ij+1 . . . Xm Im , Xm+1 x$, π ′ ) ⊢(I0 X1 I1 . . . Xj Ij Xj+1 Ij+1 . . . Xm Im Xm+1 , x$, π ′ ).′X1 . . . Xj . . . Xm Xm+1 x ⇒ πr w,поскольку′x′ = Xm+1 x, X1 . . . Xj . . . Xm Xm+1 x = X1 Xj . . . Xm Xm+1 x′ ⇒ πr wпо предположению индукции.Пусть это reduce. За первые n шагов достигнута конфигурация (I0 X1 I1 . . .′.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
