Билет №16 Восходящий синтаксический анализ.

Читайте также:

Задача восходящего анализа, как правило, сводится к нахождению правого порождения. Рассмотрим в качестве примера рассмотренный

в предыдущих разделах язык { x ^m y ⁿ |m, n > 0 }, определяемый следующими продукциями:

S -> XY

X -> xX

X -> x

Y - >yY

Y -> y

Предложение xxxyy можно сгенерировать с помощью следующего правого порождения:

S => XY => XyY => Xyy => xXyy => xxX yy => xxxyy.

В отличие от нисходящего, при восходящем синтаксическом анализе

этапы порождения определяются в противоположном порядке, то есть:

xxxyy=> xxX yy=> xXyy=> Xyy=> XyY=> XY=> S.

Применение продукции грамматики на каждом этапе предусматривает

замену правой части продукции ее левой частью, состоящей из одного символа.

При восходящем синтаксическом анализе правые части продукции

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

1) Занесение последнего считанного символа в стек - действие

переноса (SA-shift action).

2) Замена строки наверху стека посредством применения продукции грамматики - действие свертки (RA - reduce action).

Алгоритм восходящего синтаксического анализа иллюстрируется на приводимой ниже таблице.

_____________________________________________________________

Входная строка Стек Продукция Сентенциальная форма SA | RA

_____________________________________________________________

xxxyy xxxyy

x xxyy x xxxyy SA

xx xyy xx xxxyy SA

xxx yy xxx xxxyy SA

xxx yy xxX X -> x xxXyy RA

xxx yy xX X -> xX xXyy RA

xxx yy X X -> xX Xyy RA

xxxy y Xy Xyy SA

xxxyy Xyy Xyy SA

xxxyy XyY Y -> y XyY RA

xxxyy XY Y -> yY XY RA

xxxyy S S -> XY S RA

______________________________________________________________

Таблица 3.4.3 -1. Алгоритм восходящего синтаксического анализа.

Вершина стека расположена справа, а в последнем столбце показан применяемый тип операций (SA | RA). Действие переноса выполняет удаление символа и занесение его в стек. Действие свертки преду-сматривает изменения в вершине стека и в сентенциальной форме

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

В приведенной выше таблице явно указывается в какой момент производится одна из операций (SA | RA), однако из этой таблицы однозначным образом не следует критерий выбора той или иной операции. Очевидно, что необходимым условием применения операции свертки является наличие правой части некоторой продукции на вершине стэка. Однако это условие не является достаточным для применения применения операции свертки. Например, на первых этапах синтаксического разбора, иллюстрируемого на таблице 3.4.3 -1,

в стеке появляется элемент x, совпадающий с правой частью

продукции X -> x, однако перехода к операции свертки и соответствующей замены x на X не происходит. Кроме того, вершина стека может содержать например правые части более чем одной продукции и соот-ветственно возникает проблема выбора между разными операциями свертки. Говорят, что имеет место конфликт вида перенос /свертка (shift/reduce conflict), если в оказывается возможным в одно и то же время применение операции переноса и операции

свертки. Если возникает проблема выбора между разными операциями свертки, этот случай определяется как конфликт вида

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

В приведенной выше таблице символом предосмотра, определяющим применение продукции X -> x, является символ y. Для применения продукции Y -> y в качестве символа предосмотра фигурирует символ обозначающий конец строки.

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

LR(k) - грамматикой. Здесь буква L означает чтение слева (Left) направо, R - правые порождения (Rightmost), k обозначает число символов предосмотра. Соответственно, LR(k) - языком называется

язык, который можно сгенерировать LR(k) - грамматикой.

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

грамматики со следующими продукциями:

1) E -> E+T, 2) E -> T, 3)T -> T * F,4)T -> F, 5) F -> (E), 6) F ->x.

В качестве примера синтаксического разбора используем

предложение x+x+x*x. Пример анализа иллюстрируется на приводимой ниже таблице.

_____________________________________________________________

Входная строка Стек Продукция Сентенциальная форма SA | RA

_____________________________________________________________

x+x+x*x x+x+x*x

x +x+x*x x x+x+x*x SA

x +x+x*x F F -> x F+x+x*x RA

x +x+x*x T T -> F T+x+x*x RA

x +x+x*x E E ->T E+x+x*x RA

x+ x+x*x E+ E+x+x*x SA

x+x +x*x E+x E+x+x*x SA

x+x +x*x E+F F- > x E+F+x*x RA

x+x +x*x E+T T-> F E+T+x*x RA

x+x +x*x E E -> E+T E+x*x RA

x+x+ x*x E+ E+x*x SA

x+x+x *x E+x E+x*x SA

x+x+x *x E+F F- > x E+F*x RA

x+x+x *x E+T T -> F E+T*x RA

x+x+x* x E+T* E+T*x SA

x+x+x*x E+T*x E+T*x SA

x+x+x*x E+T*F F -> x E+T*F RA

x+x+x*x E+T T -> T * F E+T RA

x+x+x*x E E -> E+T E RA

_____________________________________________________________

Таблица 3.4.3 -2. Пример восходящего синтаксического анализа.

_____________________________________________________________

E T F + * () x ^

______________________________________________________________

1 S2 S5 S8 S9 S12

2 S3

3 S4 S8 S9 S12

4 R1 S6 R1 R1

5 R2 S6 R2 R2

6 S7 S9 S12

7 R3 R3 R3 R3

8 R4 R4 R4 R4

9 S10 S5 S8 S9 S12

10 S3 S11

11 R5 R5 R5 R5

12 R6 R6 R6 R6

______________________________________________________________

Таблица 3.4.3 -3. Пример заполнения таблицы синтаксического анализа.

В таблице синтаксического анализа каждому состоянию синтаксического анализатора (число состояний всегда конечное) соответствует одна строка, а каждому терминальному и нетерминальному символу грамматики соответствует один столбец. Символ ^ обозначает конец строки. Синтаксический анализ начинается с состояния 1, а входным символом является первый введенный символ. Каждый шаг анализа определяется позицией таблицы, соответствующей текущему состоянию, и входным символом. Позиция таблицы определяется одним из следующих типов.

1) Позиция переноса Sn обеспечивает выполнение операции переноса

и переход в состояние n.

2) Позиция свертки Rk обеспечивает выполнение операции свертки,

используя продукцию k.

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

индивидуального сообщения об ошибке.

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

Если предположить отсутствие ошибок, этот элемент определяет операцию переноса или свертки. В начале синтаксического анализа

анализатор находится в состоянии 1, а входной символ - это первый символ анализируемого предложения.

Пусть позиция таблицы определяет операцию переноса, тогда:

- символ, соответствующий столбцу, в котором находится данная

позиция таблицы, заносится в стек символов;

- анализатор переходит в состояние, определяемое позицией

переноса, и это состояние заносится в стек состояний;

- если входной символ является терминалом, он принимается,

и входным символом становится следующий терминал

предложения.

Пусть позиция таблицы определяет операцию свертки, тогда:

- из стека символов удаляются m -символов, а из стека состояний

удаляются m состояний, где m - число символов в правой части

продукции, фигурирующей в свертке;

- анализатор переходит в состояние, определяемое вершиной стека

состояний;

- входной символ становится символом в левой части продукции,

определенной в позиции свертки.

Ниже приводится пример анализа предложения x+x+x*x на основе использования таблицы 3.4.3 -3.

На начальном этапе имеем: