6.3 Нерекурсивный предиктивный анализ

Нерекурсивный предиктивный синтаксический анализатор можно построить с помо­щью явного использования стека. Основная проблема предиктивного анализа заключается в определении продукции, которую следу­ет применить к нетерминалу. Нерекурсивный синтаксический анализатор, представлен­ный на рис. 28, ищет необходимую для анализа продукцию в таблице разбора.

Рис. 28. Модель нерекурсивного предиктивного синтаксического анализатора

Предиктивный синтаксический анализатор включает в себя:

управляющую программу, входной буфер, стек, таблицу разбора и выходной поток. Входной буфер содержит анализируемую строку с маркером ее правого конца — специальным символом. Стек содержит последовательность символов грамматики с символом $ на дне. Изначально стек содержит стартовый символ грамматики непосредственно над символом $. Таблица разбора представляет собой двухмерный массив М[А, а], где А — нетерминал, а а — терминал или символ $.

Синтаксический анализатор управляется программой, которая работает следующим образом. Программа рассматривает X — символ на вершине стека, и а, текущий входной символ. Эти два символа определяют действия синтаксического анализатора. Имеется три варианта:

1. Если Х=а=$, синтаксический анализатор прекращает работу и сообщает об успешном завершении разбора.

2. Если Х=а≠$, синтаксический анализатор снимает со стека X и перемещает указатель входного потока к следующему символу.

3. Если X представляет собой нетерминал, программа рассматривает запись M[Х, а] таблицы разбора М. Эта запись представляет собой либо X-продукцию грамматики, либо запись об ошибке. Если, например, М[Х, а] = {X → UVW}, синтаксический анализатор замещает X на вершине стека на WVU (с U на вершине стека). В качестве выхода синтаксический анализатор просто выводит использованную продукцию. Если M[Х, а] = error, синтаксический анализатор вызывает программу восстановления после ошибки.

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

6.4 Множества first и follow

При построении предиктивного синтаксического анализатора необходимо построить два множества связанные с грамматикой G, — FIRST и FOLLOW, которые обеспечивают заполнение таблицы предиктивного анализа грамматики G. Если α — произвольная строка символов грамматики, то определим FIRST(a) как множество терминалов, с которых начинаются строки, выводимые из а. Если а λ, то λ входит в FIRST(a).

FOLLOW(A) для нетерминала А определяется как множество терминалов а, которые могут располагаться непосредственно справа от А в некоторой сентенциальной форме, т.е. множество терминалов а, таких, что существуют порождения вида SαAaβ для некоторых α и β. В процессе приведения между А и а могут появиться символы, но они порождают λ и в конечном счете исчезают. Если А может оказаться крайним справа символом некоторой сентенциальной формы, то $ входит в FOLLOW(A).

FIRST(X) для всех символов грамматики X вычисляется с применением следующих правил до тех пор, пока ни к одному из множеств FIRST не смогут быть добавлены ни терминалы, ни λ.

1. Если X— терминал, то FIRST(X)={X}.

2. Если имеется продукция X→ λ, добавим λ к FIRST(X).

3. Если X нетерминал и имеется продукция X → Y₁Y₂...Y_k, то поместим а в FIRST(X), если для некоторого i а є FlRST(Y_i) и λ входит во все множества FIRST(Y₁)… FIRST(Y_i-1), т.е. Y₁…Y_i-1 λ. Если λ имеется во всех FIRST(Y_i), i = l, k, то добавляем λ к FIRST(X). Например, все, что находится во множестве FIRST(Y_i), есть и в множе­стве FIRST(X). Если Y₁ не порождает λ, то больше мы ничего не добавляем к FIRST(X), но если Y₁ λ, то к FIRST(X) добавляем FIRST(Y₂) и т.д.

FIRST для любой строки Х₁Х₂...Х_n вычисляется следующим образом. Добавим к FIRST(Х₁Х₂...Х_n) все не-λ символы из FIRST(X₁). Добавим также все не λ- символы из FIRST(X₂), если λ є FIRST(X₁), все не λ - символы из FIRST(X₃), если λ имеется как в FIRST(X₁), так и в FIRST(X₂) и т.д. И наконец, добавим λ к FIRST(Х₁Х₂...Х_n), если для всех i FIRST(X_i) содержит λ.

FOLLOW(A) для всех нетерминалов А вычисляется с применением следую­щих правил до тех пор, пока ни к одному множеству FOLLOW нельзя будет добавить ни одного символа.

1. Поместим $ в FOLLOW(S), где S — стартовый символ, а $ — правый ограничитель входного потока.

2. Если имеется продукция А → αBβ, то все элементы множества FIRST(β), кроме λ , помещаются в множество FOLLOW(B).

3. Если имеется продукция А → αB, или A → αBβ, где FIRST(β) содержит λ (т.е. β=> λ), то все элементы из множества FOLLOW(A) помещаются в множество FOLLOW(B) [3].

Пример 16

Для грамматики арифметических выражений

E → TE’

E’ → +TE’| λ

T → FT’

T’ → *FT’| λ

F → (E) | id

множества будут иметь вид:

FIRST(E) = FIRST(T) = FIRST(F) = {(,id}

FIRST(E’) = {+, λ }

FIRST(T’) = {*, λ }

FOLLOW(E) = FOLLOW(E’) = {), $}

FOLLOW(T) = FOLLOW(T’) = {+, ), $}

FOLLOW(F) = {+,*, ),$}

Например, id и левая скобка добавляются к FIRST(F) по правилу (3) в опреде­лении FIRST, поскольку FIRST(id)={id}, и к FIRST('(')={(} по правилу (1). По пра­вилу (3) с i=1 из продукции Т → FT' следует, что id и левая скобка входят и в FIRST(T). В соответствии с правилом (2) λ входит в FIRST(E’).

Для вычисления множеств FOLLOW помещаем $ в FOLLOW(E) в соответствии с правилом (1) для вычисления FOLLOW. По правилу (2), примененному к продукции F→(E), правая скобка также входит в множество FOLLOW(E). В соответствии с прави­лом (3), примененным к продукции Е→ТЕ', $ и правая скобка входят в FOLLOW(E'). Поскольку Е' λ, эти же символы входят и в FOLLOW(T). Из продукции Е→ТЕ' со­гласно правилу (2), следует, что все, что имеется в множестве FIRST(E’) (за исключением λ), должно входить в множество FOLLOW(T). В это же множество входит также $.