Синтаксический анализ в языках программирования

_____________________________________________________________

 Входная строка   Стек  Продукция   Сентенциальная  форма   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 ______________________________________________________________

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

 

 

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

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

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

в стеке появляется элемент  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

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

 

 

 _____________________________________________________________

           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

______________________________________________________________

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

       состояний; 

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

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

 

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

  входная строка  стек  состояний    стек символов     сентенциальная

                                                                                             форма

     x+x+x*x               1                                                               x+x+x*x

Состояние -1, входной символ  -x , значение соответствующего элемента таблицы - S12; выполняется переход в состояние  12, в стек состояний заносится 12 , в стек символов заносится x:

 

  входная строка  стек  состояний    стек символов     сентенциальная

                                                                                             форма

  x+x+x*x                  1, 12                            x                              x+x+x*x

 

Состояние -12, входной символ  - +, значение соответствующего элемента таблицы - R6; выполняется свертка согласно продукции 6,  

 удаляется одно состояние  из  стека состояний и один символ из стека символов (так как в правой части продукции 6 имеется только один символ); входным символом становится F:

входная строка  стек состояний    стек символов     сентенциальная

                                                                                             форма

x+x+x*x                  1                                                                x+x+x*x

 

Состояние -1, входной символ  - F, значение соответствующего элемента таблицы - S8; выполняется переход в состояние  8, в стек состояний заносится 8, в стек символов заносится F:

 

  входная строка  стек  состояний    стек символов     сентенциальная

                                                                                             форма

  x+x+x*x                  1, 8                                  F                      F+x+x*x

 

Состояние -8, входной символ  - +, значение соответствующего элемента таблицы - R4; выполняется свертка согласно продукции 4,  

 удаляется одно состояние  из  стека состояний и один  символ из стека символов; входным  символом становится T:

входная строка  стек состояний    стек символов     сентенциальная

                                                                                           форма