предусматривает построение синтаксического дерева , начиная
с предложения языка, сворачивая его до получения символа предложения . Нисходящий синтаксический анализ обладает большей степенью наглядности , чем восходящий . Однако на практике большее распространение получил восходящий синтаксический анализ , обладающий большей общностью и более совершенным аппаратом инструментальной поддержки . В ряде компиляторов сочетаются оба эти подхода .
3.4.2. Нисходящий синтаксический анализ .
Задача нисходящего анализа , как правило , сводится к нахождению левого порождения . Процесс нисходящего анализа начинается с символа предложения с последующей генерацией предложения языка .
Рассмотрим в качестве примера язык вида { x m y n |m, n > 0 } , определяемый следующими продукциями :
S -> XY
X -> xX
X -> x
Y - >yY
Y -> y
Предложение xxxyy можно сгенерировать с помощью следующего левого порождения :
S => XY => xXY => xxXY => xxxY => xxxyY => xxxyy .
Алгоритм нахождения левого порождения можно наглядно
проиллюстрировать с помощью приводимой ниже таблицы .
_________________________________________________________
Входная строка Продукция Сентенциальная форма
_________________________________________________________
xxxyy S => XY XY
xxxyy X => xX xXY
xxxyy X => xX xxXY
xxxyy X => x xxxY
xxxyy X => x xxxY
xxxyy Y => yY xxxyY
xxxyy Y => yY xxxyY
_________________________________________________________
Таблица 3.4.2 -1 . Алгоритм нахождения левого порождения .
В этой таблице знаки предложения рассматриваются по одному и используются для управленият процессом синтаксического анализа.
После генерации знак предложения подчеркивается во входной строке.
Каждому этапу синтаксического анализа соответствуют три позиции таблицы : входная строка с подчеркнутыми символами , текущая продукция , а также текущее состояние сентенциальной формы . В конце
синтаксического анализа все знаки входной строки подчеркнуты ,
а сентенциальная форма полностью совпадает с заданной строкой .
На каждом этапе первый неподчеркнутый символ определяется как входной символ и используется для разбора . Если в сентенциальной форме генерируется терминал , появляется еще один подчеркнутый символ. Принятие решений при нисходящем синтаксическом разборе
обычно основывается на символе или последовательности символов предосмотра . Под символом предосмотра здесь имеется в виду либо текущий входной символ либо символ , обозначающий признак конца строки . Существуют грамматики , поддерживающие методы
нисходящего синтаксического анализа с одним символом предосмотра . Это -так - называемые LL(1) -грамматики . Термин LL(1) означает следующее :первая буква L определяет направление чтения слева
( Left ) направо,вторая буква L определяет использование левых
( Leftmost) порождений, цифра 1- один символ предосмотра . Соответственно LL(1) - язык определяется как язык , генерируемый посредством LL(1) -грамматики .В данном пособии этот класс грамматик и языков подробно не рассматривается . Наиболее удачное и полное изложение материала по LL(1)- грамматикам и языкам можно найти в книге [ 6 ] .
3.4.3. Восходящий синтаксический анализ .
Задача восходящего анализа , как правило , сводится к нахождению правого порождения . Рассмотрим в качестве примера рассмотренный
в предыдущих разделах язык { x m y n |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
xxxyy x xxxyy SA
xxxyy xx xxxyy SA
xxxyy xxx xxxyy SA
xxxyy xxX X -> x xxXyy RA
xxxyy xX X -> xX xXyy RA
xxxyy X X -> xX Xyy RA
xxxyy 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 , а входным символом является первый введенный символ. Каждый шаг анализа определяется позицией таблицы , соответствующей текущему состоянию , и входным символом . Позиция таблицы определяется одним из следующих типов .