Алгоритм нисходящего разбора. Нисходящие распознаватели

1. Задача разбора



      Разбор сентенциальной формы означает построение вывода и, возможно

   синтаксического дерева для нее. Программу разбора называют также рас-

   познавателем, так как она распознает только предложения рассматривае-

   мой грамматики. Именно это и является нашей задачей в данный момент.

   Все алгоритмы разбора, которые бутут здесь описаны называются алгори-

   тмами слева направо ввиду того, что они обрабатывают сначала самые ле-

   вые символы обрабатываемой цепочки и продвигаются по цепочке только

   тогда, когда это необходимо. Можно подобным способом определить разбор

   справа налево, но он менее естественен. Инструкции в программе выполня-

   ются слева направо, да и мы читаем слева направо.

      Различают две категории алгоритмов разбора: нисходящий (сверху вниз)

   и восходящий (снизу вверх). Их называют также разверткой и сверткой.

   ( В данном реферате будет рассмотрен процесс только нисходящего раз-

   бора. ) Соотетственно, эти термины  соответствуют и способу построения

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

   ( начального символа ) вниз к концевым узлам. Метод восходящего разбора

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

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

   предложение (1) в следующей грамматике целых чисел ( последовательностей,

   состоящих из одной и более цифр ):





               N ::= D | ND

               D ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9        (1)



    На первом шаге непосредственный вывод N => ND будет строиться так,

    как показано в первом дереве на рис. 1. На каждом последующем шаге

    самый левый нетерминал V текущей сентенциальной формы xVy заменяется

    на правую часть u правила V ::= u, в результате чего получается сле-

    дующая сентенциальная форма. Этот процесс для предложения (1) предс-

    тавлен на рис. 1. в виде пяти деревьев. Фокус в том, конечно, что

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

    цепочкой.





       N             N           N           N            N

                     |           |           |            |

                 *-------*   *-------*    *-------*   *-------*

                 |       |   |       |    |       |   |       |

                 N       D   N       D    N       D   N       D

                             |            |           |       |

                             D            D           D       5

                                          |           |

                                          3           3





       N         => N D      => D D       => 3 D      => 3 5





                Рис. 1. Нисходящий разбор и построение

                                 вывода



    2. Нисходящие разбор с возвратами



       Алгоритм нисходящего разбора строит синтаксическое дерево, как уже

    было сказано, начиная с корня, постепенно опускаясь до уровня предло-

    жения, как было показано ранее. Описание усложняется главным образом

    из-за необходимости вспомогательных операций, которые необходимы гла-

    вным образом для того, чтобы выполнять возвраты с твердой уверенностью,

    что все возможные попытки построения дерева были предприняты.

       Чтобы свести осложнеия к минимуму, давайте опишем этот алгоритм раз-

    бора образно. Вообразим, что на любом этапе разбора, в каждом узле уже

    построенной части дерева находится по одному человеку. Люди, которые

    находятся в терминальных узлах, занимают места соответственно символам

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

       Некоему человеку надлежит провести разбор предложения x. Прежде все-

    го ему необходимо отыскать вывод Z => +x, где Z - начальный символ; сле-

    довательно первым непосредственным выводом  должен будет быть вывод

    Z => y где Z ::= y - правило. Пусть для Z существуют правила



            Z ::= X  X  .. X  | Y  Y  .. Y  | Z  Z  .. Z

                   1  2     n    1  2     m    1  2     1



    Сначала человек пытается определить правило Z ::= X X .. X  . Если

                                                       1 2    n

    нельзя построить дерево, используя это правило, он делает попытку приме-

    нить второе правило Z ::= Y Y ... Y . В случае неудачи он переходит к

                               1 2     m

    следующему правилу и т.д.

         Как ему определить, правильно он выбрал непосредственный вывод

    Z => X X .. X ? Заметим, что если вывод правилен, то для некоторых

          1 2    n

    цепочек x  будет иметь место x=x x .. x , где X => *x для i=1,...,n.

             i                      1 2    n       i     i

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

    M , который должен будет найти вывод X =>*x  для любого x , такого,

     1                                    1    1             1

    что x = x ... Если сыну M  удастся найти такой вывод, он (и любой из

             1               1

    сыновей, внуков и т.д.) закрывает цепочку x  в предложении x и сообща-

                                               1

    ет своему отцу об успехе. Тогда его отец усыновит M , чтобы тот нашел

                                                       2

    вывод  X => *x , где x = x x ... и ждет ответа от него и т.д. Как толь-

            2     2           1 2

    ко сообщил об успехе сын M   ,он усыновит еще и M , чтобы тот нашел

                              i-1                    i

    вывод X => *x . Сообщение об успехе, пришедшее от сына M , означает

           i     i                                          n

    что разбор предложения закончен.

         Как быть, если сыну M  не удается найти вывод X =>*x ? В этом

                            i                         i    i

    случае M  сообщает о неудаче своему отцу; тот от него отрекается и

            i

    дает старшему брату M ,M    такое распоряжение: "Ты уже нашел вывод,

                         i  i-1

    но этот вывод неверен. Найди-ка мне другой". Если M    сумеет найти

                                                       i-1

    другой вывод, он вновь сообщит об успехе, и все продолжится по-пре-

    жнему. Если же M    сообщит о неудаче, отец отречется и от него, и

                    i-1

    тогда уже старшего брата M   , попросят предпринять еще одну попыт-

                              i-2

    ку. Если придется отречься даже от M , значит, непосредственный вы-

                                        1

    вод Z => X X .. X  был неверен, и человек, начинавший разбор, попы-

              1 2    n

    тается воспользоваться другим выводом Z => Y .. Y .

                                                1    m

         Как же действует каждый из M ? Положим, его целью является тер-

                                     1

    минал X . Входная цепочка имеет вид x=x x ..x   T.. ,где символы в

                                           1 2   i-1

    x ,x ,...,x    уже закрыты другими людьми. M  проверяет, совпадает

     1  2      i-1                              i

    ли очередной незакрытый символ T с его целью X . Если это так, он

                                                  i

    закрывает этот символ и сообщает об успехе. Если нет, сообщает об

    неудаче.

         Если цель M -  нетерминал X , то M  поступает точно так же, как

                                    1      1

    и его отец. Он начинает проверять правые части правил, относящихся к

    нетерминалу, и, если необходимо, тоже усыновляет или отрекается от

    сыновей. Есливсе его сыновья сообщают об успехе то M  в свою очередь

                                                        i

    сообщает об успехе отцу. Если отец просит M  найти другой вывод, а це-

                                               i

    лью является нетерминальный символ, то M  сообщает о неудаче, так как

                                            i

    другого такого вывода не существует. В противном случае M просит своего

                                                             i

    младшего сына найти другой вывод и реагирует на его ответ также, как и

    раньше. Если все сыновья сообщат о неудаче, он сообщит о неудаче свое-

    му отцу.

         Теперь, наверное, понятно, почему этот метод называется прогнозиру-

    ющим или целенаправленным. Используется и название "нисходящий" из-за

    способа построения синтаксического дерева. При разборе отправляются от

    начального символа и нисходят к предложению (см рис. 2)





                                   Z

                                   |

                               *---*-------*

                               |   |       |

                               F   |       T

                               |   |       |

                               T   |

                               |   |

                               F   |

                               |   |

                               i   +   i   *   i



             Рис. 2. Частичный нисходящий разбор предложения i+i*i.



         Привлекательность этого метода (и его представления) в том и сос-

    тоит, что каждый человек должен помнить лишь о своей цели, о своем от-

    це, о своих сыновьях, а также о своем месте в грамматике и выходной це-

    почке. И никому не нужны точные сведения о том, что происходит в других

    местах. Это как раз и есть то, к чему мы вообще стремимся в программиро-

    вании: в каждом сегменте программы или в подпрограмме необходимо забо-

    титься о собственной входной и выходной информации и ни о чем более.

         Для имитации усыновления и отречения сыновей в программах использу-

    ют стек типа LIFO (последний вошел - первый вышел), или, как его иногда

    называют, "магазин".

            Опишем алгоритм в более явном виде:

    Положим, во-первых, что грамматика задана списком в одномерном мас-

    сиве GRAMMAR таким образом, что каждое множество правил



                          U ::= x|y|...|z



    представлено, как Ux|y|...|z|$. То есть каждый символ занимает одну

    ячейку, за каждой правой частью следует вертикальная черта "|", а за

    последним символом следует "|$". Таким образом, грамматика



                          Z ::= E#

                          E ::= T+E|T

                          T ::= F*T|F

                          F ::= (E)|i



    будет выглядеть как



                 ZE#|$ET+E|T|$TF*T|F|$F(E)|i|$



         Каждый элемент стека соответствует человеку и состоит из пяти

    компонент



                (GOAL,i,FAT,SON,BRO)



    которые означают следующее:



         1. GOAL - цель, т.е. символ, который человек ищет. Таким обра-

    зом, в незакрытой в данный момент части предложения ему предстоит

    найти такую голову, которая приводится к GOAL, и закрыть ее. GOAL

    передается ему отцом.

         2. i - индекс в массиве GRAMMAR, указывающий на тот символ в

    правой части для GOAL, с которым человек работает в данный момент.

         3. FAT - имя отца (номер элемента стека, соответствующего от-

    цу).

         4. SON - имя самого последнего (младшего) из сыновей.

         5. BRO - имя его старшего брата.



         Нуль в любом из полей означает, что данная величина отсутствует.

    В программе значение переменной v  равно количеству участвующих в

    разборе людей (количеству элементов в стеке в текущий момент), c -

    имя (номер элемента в стеке) человека, работающего в данный момент.

    Остальные ожидают конца его работы. Индекс j относитстя к самому ле-

    вому (незакрытому) символу входной цепочки INPUT(1),...,INPUT(n).





    а)           Z           б) СТЕК   ЦЕЛЬ    i   FAT    SON    BRO

                 |

       *---------*------*         1     Z      4     0     15      0

       |                |         2     E     10     1      7      0

       E                #         3     T     20     2      4      0

       |                          4     F     28     3      5      0

    *--*------*                   5     i      0     4      0      0

    |  |      |                   6     +      0     2      0      3

    T  |      E                   7     E     12     2      8      6

    |  +      |                   8     T     18     7     12      0

    F         T                   9     F     28     8     10      0

    |         |                  10     i      0     9      0      0

    i     *---*---*              11     *      0     8      0      9

          |   |   |              12     T     20     8     13     11

          F   *   T              13     F     28    12     14      0

          |       |              14     i      0    13      0      0

          i       F              15     #      0     1      0      2

                  |

                  i



                    Рис 3. Стек после нисходящего разбора i+i*i

                а) - синтаксическое дерево б) - стек после разбора



         Поле SON используется для хранения ссылки на последнего (младше-

    го) сына. Тогда поле BRO элемента, соответствующего этому сыну, укажет

    на старшего брата. В качестве иллюстрации расмотрим изображенное на

    рис .3 а) синтаксическое дерево для предложения i+i*i вышеописанной

    грамматики. Состояние стека после окончания работы показано на рис.3 б).

    Теперь у человека 2(S (2)) есть цель E; предполагается, что он в соотве-

    тствии с синтаксическим деревом использует правило E ::= T+E. Таким

    образом, ему для того, чтобы найти символы T,+,E потребуется три сына.

    Значение поля S(2).SON=7, так что младшим сыном является человек, c

    номером 7, цель которого E. Имя среднего сына - число 6, определяется

    значением поля S(7).BRO; - цель этого сына - символ +. Имя старшего

    сына находится в поле BRO человека 6 и равно 3.

         Очевидно, что у нас имеется список сыновей каждого человека и

    элементы этого списка связаны в стеке между собой. То есть стек в его

    окончательном виде представляет собой внутреннюю форму синтаксического

    дерева.

         Рассмотрим теперь сам алгоритм нисходящего разбора. Для удобства

    чтения разделим его  на шесть поименованных частей.





    1. НАЧАЛЬНАЯ УСТАНОВКА



    S(1) := (Z,0,0,0,0); c:=1; v:=1; j:=1; переход на НОВЫЙ ЧЕЛОВЕК

    (первое усыновление. Цель усыновления - начальный символ Z.)



    2. НОВЫЙ ЧЕЛОВЕК



    IF GOAL терминал THEN          Новый человек изучает свою цель.

       IF INPUT (j)=GOAL THEN      Цель - терминал.

         BEGIN j:=j+1;             Если GOAL совпадает с символом из

         GO TO УСПЕХ;              предложения, человек закрывает этот

       ELSE GO TO НЕУДАЧА          символ и сообщает об успехе.

    i:= индекс в GRAMMAR правой    Не совпадает - сообщает об неудаче.

        части для GOAL;            Цель нового человека - нетерминал.

    GO TO ЦИКЛ                     Подготовка к просмотру правых частей

                                   в правилах для GOAL



    3. ЦИКЛ



    IF GRAMMAR(i)="|"              Просмотр правой части

    THEN IF FAT=/=0                Достигли конца правой части, поэтому

         THEN GO TO УСПЕХ          сообщаем об успехе. Если нет отца,

         ELSE STOP - предложение;  то останов - окончен разбор

                                   предложения

    IF GRAMMAR(i )="$"             Нет больше правых частей, которые

    THEN IF FAT=/=0                можно было бы попробовать, поэтому

         THEN GO TO НЕУДАЧА        сообщение о неудаче или, если нет отца

         ELSE STOP - не            остановка, не распознав предложения

         предложение;

    v:=v+1;                        GRAMMAR(i) - другая цель, которую

    S(v):=(GRAMMAR (i),0,c,0,      можно попытаться найти. Берем сына.

    SON);                          Тогда старший брат - тот, кто был до

                                   этого младшим сыном

                                   Переключить внимание на младшего сына

    SON:=v; c:=v;                  и ждать от него ответа

    GO TO НОВЫЙ ЧЕЛОВЕК



    4. УСПЕХ



    c:=FAT;                        Сообщить об успехе своему отцу. Он

    i:=i+1; GO TO ЦИКЛ             предпримет следующий шаг.



    5. НЕУДАЧА



    c:=FAT;                         Сообщить о неудаче своему отцу. Он

    v:=v-1;                         отречется от сына и попросит его

    SON:=S(SON).BRO;                старшего брата предпринять еще одну

    GO TO ЕЩЕ РАЗ                   попытку.



    6. ЕЩЕ РАЗ



    IF SON=0 THEN                   Есть ли еще сын, который может пред-

      BEGIN WHILE GRAMMAR(i)        принять еще одну попытку? Нет.

      =/="|"                        Тогда пропускается правая часть -

         DO i:=i+1;                 Это не та, которая нужна - переход к

         i:=i+1 GO TO ЦИКЛ          следующей.

         END;

    i:=i-1; c:=SON;                 Есть сын. Его просят повторить попытку

    IF GOAL нетерминал              Его цель - нетерминал, так что он по-

    THEN GO TO ЕЩЕ РАЗ              пытается еще раз добиться успеха.



    j=j-1                           Его цель терминал. Попытка не приведет

    GO TO НЕУДАЧА                   к успеху. Поэтому он открывает свой

                                    символ и сообщает о неудаче.





         Блок схема данного алгоритма приведена ниже.



                              *---------*

                              |    1    |

                              *----*----*

     *---------------------------->|            *------*

     |                             *     *----->|      |<------*

     |                    Нет     / \    |      |      |       |

     |               *-----------< 2 >   |      |      *       |

     |      Нет     / \     А     \ /    |      |  Д  / \      |

     |  *----------< 4 >    |      *     |   *-------< 9 >     |

     |  |           \ /     |      |     |   |  |     \ /      |

     |  |            *      |      |     |   |  |      *       |

     |  |            |  Да  |      | Да  |   |  |      | Нет   |

     |  |            *      |      |     |   |  |  *---*---*   |

     |  |   *---* Н / \     |      |     |   |  |  |  10   |   |

     |  |   | 6 |--< 5 >    |      *     |   |  |  *---*---*   |

     |  |   *---*   \ /     |     / \    |   |  |      |       |

     |  |            *      |  *-< 3 >   |   |  |      *       |

     |  |            | Да   |  |  \ /    |   |  |     / \  Да  |

     | *-*           |      |  |   *     |   |  |    <1 1>-----*

     *-|7|           |      |  |   *-----*   |  |     \ /

       *-*           |      |  |     Нет     |  |      *

                     |      *--|-------------*  |      | Нет

                     |         | А              |  *---*---*

                     |<--------* |              *--|  1 2  |

                 *---*---*       |                 *-------*

                 |   8   |-------*

                 *-------*



              Рис 4. Блок-схема алоритма нисходящего разбора



     1. S(1) := (Z,0,0,0,0); c:=1; v:=1;

     2. GOAL - терминал ?

     3. j:=j+1; INPUT(j)=GOAL ?

     4. GRAMMAR(i)="Конец" ?

     5. FAT =/= 0 ?

     6. STOP - Конец работы;

     7. v := v+1; S(v) := (GRAMMAR (i),0,c,0,SON);

        SON := v; c := v;

     8. c := FAT; i := i+1;

     9. SON = 0 ?

    10. Пока GRAMMAR (i) =/= "Конец":

          i := i+1,

          j:=j+1;

        i :=i -1;

        c := SON;

     11. GOAL - нетерминал ?

     12. C := FAT ; v := v-1; SON := S (SON) * BRO.







    3. Проблемы нисходящего разбора



                      Прямая левосторонняя рекурсия



         В алгориме, описанном ранее, есть один серьезный недостаток,

    который проявляется, когда цель определена с использованием левосто-

    ронней рекурсии. Если X - наша цель, а первое же правило имеет вид

    X ::= X ..., то мы незамедлительно усыновляем того, кто будет искать

    X. Он в свою очередь немедленно заведет себе сына, чтобы тот искал

    X. Таким образом, каждый будет сваливать ответственность на своего сы-

    на, и для решения задачи не хватит населения Китая.

         По этой причине правила грамматики написаны с применением право-

    сторонней рекурсии вместо более привычной левосторонней. Лучший способ

    избавиться от прямой левосторонней рекурсии - записывать правила, ис-

    пользуя итеративные и факультативные обозначения. Запишем правила



    (3.1)             E ::= E+T | T  как  E ::= T { +T }

    и

                      T ::= T*F | T/F | F  как  T ::= F { *F | /F }



         Сейчас будут сформулированы два основных принципа, на основании

    которых правила языка, включающие прямую левостороннюю рекурсию, пре-

    оьразуются в эквивалентные правила, использующие итерацию.



    (3.2 )            Факторизация. Если существуют правила вида

                      U ::= xy | xw | ... |xz, то их надо заменить на

                      U ::= x(y|w|...|z), где скобки являются метасимволами



         Допустима факторизация в более общей форме, такая как в арифметиче-

    ских выражениях. Например, если в (3.2) y=y y  и w=y w  , мы могли бы за-

                                               1 2      1 2

    менить U ::= x (y|w|...|z) на



                      U ::= x(y (y |w )|...|z).

                               1  2  2



         Заметим, что исходные правила U ::= x|xy мы преобразуем к виду

    U ::= x(y|Л), где Л - пустая цепочка. Когда бы ни использовалось по-

    добное преобразование, Л всегда помещается как последняя альтернати-

    ва, так как мы принимаем условие, что если цель - Л, то эта цель все-

    гда сопоставляется.

         Помимо того что факторизация позволяет нам исключить прямую реку-

    рсию, использование этого приема сокращает размеры грамматики и позво-

    ляет проводить разбор более эффективно. В этом мы убедимся позже.

         После факторизации (3.2) в грамматике останется не более одной пра-

    вой части с прямой левосторонней рекурсией для каждогоиз нетерминалов.

    Если такая правая часть есть, мы делаем следующее:



     (3.3)    Пусть U ::= x|y|...|z|Uv - правила, у которых осталась леворе-

              курсивная правая часть. Эти правила означают, что членом син-

              таксического класса U является x, y или z, за которыми либо ни-

              чего не следует, либо следует только v. Тогда преобразуем эти

              правила к виду U ::= (x|y| ... |z) {v}.



         Мы использовали (3.3)  чтобы сделать преобразование в (3.1),

    позволяющее избавиться от ненужных скобок заключающихся в T. В качес-

    тве другого примера преобразуем A ::= BC|BCD|Axz|Axy





       а)         Z                  б)       Z

                  |                           |

             *----*-*                   *-*-*-*-*-*-*

             |    | |                   | | | | | | |

             E    + T                   T + T + T + T

             |

          *--*-*

          |  | |

          E  + T

          |

        *-*-*

        | | |

        E + T

        |

        T



                Рис 5. Деревья, использующие рекурсию и итерацию



         Применив правило (3.2) получим A ::= BC(D|Л)|Ax(z|y); Применив

    (3.3), получим A ::= BC(D|Л){x(z|y)}. Можно избавиться от одной па-

    ры скобок, после чего получим A ::= BC(D|Л){x(z|y)}.

         После таких изменений мы, конечно, должны изменить и наш алгоритм

    нисходящего разбора. Теперь алгоритм должен уметь обрабатывать альтер-

    нативы не только в одной правой части, но и в ее подцепочках, должен

    учитывать в своей работе существование пустой цепочки Л, должен уметь

    обрабатывать итерацию.

         Использование итерации вместо рекурсии отчасти меняет и структуру

    деревьев. Таким образом, рис 3.а должен был бы походить на рис. 3.б. Но

    эти два дерева следует рассматривать как эквивалентные; операторы "плюс"

    должны заменяться слева направо.



                         Общая левосторонняя рекурсия



         Мы не решили всей проблемы левосторонней рекурсии: с прямой лево-

    сторонней рекурсией покончено, но общая левосторонняя рекурсия еще ос-

    талась. Таким образом, правила



                          U ::= Vx и V ::= Uy|v



    дают вывод U => +Uyx. Избавиться от этого не так просто, но обнаружить

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

    левосторонней рекурсией. Символ U, получившейся в результате этих пре-

    образований грамматики, может быть леворекурсивным тогда и только тогда

    когда U FIRST+ U. Как проверить это отношение, нам уже известно.



                 Представление грамматики в оперативной памяти



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

    является представление грамматики в вычислительной машине. Одно из

    возможных представлений уже использовалось ранее. Очевидно, что оно

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

    вующих каждому нетерминалу. Речь пойдет о другом представлении. Прежде

    чем начать изложение, стоит упомянуть о том что написать конструктор,

    который воспринимает грамматику, проводит любые из преобразований, о

    которых только что говорилось, проверяет не являются ли правила рекур-

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

    лее форм довольно легко.

         Для представления грамматики используется списочная структура, на-

    зываемая синтаксическим графом. Каждый узел представляет символ S из

    правой части и состоит из четырех компонент: ИМЯ, ОПРЕДЕЛЕНИЕ (ОПР),

    АЛЬТЕРНАТИВА (АЛТ) и ПРЕЕМНИК (ПРЕМ), где

         1. ИМЯ - это сам символ S в некоторой внутренней форме.

         2. ОПРЕДЕЛЕНИЕ равно 0, если S - терминал; в противном случае эта

            компонента указывает на узел соответствующий первому символу в

            перво правой части для S.

         3. АЛЬТЕРНАТИВА указывает на первый символ той альтернативы пра-

            вой части которая следует за правой частью, содержащей данный

            узел (0, если такой правой части нет). Это только для символов

            в правых частях.

         4. ПРЕЕМНИК указывает на следующий символ правой части (0, если

            такого символа нет).



         Кроме того, каждый нетерминальный символ представлен узлом, состо-

      ящим из одной компоненты, которая указывает а первый символ в первой

      правой части, относящейся к этому символу. Примером может служить

      рис. 4, на котором изображено расположения компонент узла синтаксическо-

      го графа грамматики:





                        *---------------------------*

                        |           ИМЯ             |

                        *--------*---------*--------*

                        | ОПР    |  АЛТ    |  ПРЕМ  |

                        *--------*---------*--------*



                 Рис 6. Расположение компонент узла синтаксического

                                 графа грамматики



         Подробно о синтаксических графах см. в книге Д.Гриса "Конструи-

    рование компиляторов для цифровых вычислительных машин"





                             Разбор без возвратов



         Программа разбора в компиляторе ни в коем случае не должна прибе-

    гать к возвратам. Мы должны иметь уверенность в том, что каждая пред-

    полагаемая цель верна. Это нреобходимо потому, чтонам предстоит связать

    семантику с синтаксисом, и по мере того, как мы будем прогнозировать и

    находить цели, эти символы будут обрабатываться семантически. Вот неко-

    торые примеры "обработки": 1) при обработке описаний переменных иденти-

    фикаторы помещаются в таблицу символов; 2) при обработке арифметических

    выражений проверяют, совместимы ли типы операндов.

         Если возврат произошел из-за того, что прогнозируемая цель неверна,

    придется уничтожить результаты семантической обработки, сделанной во

    время поисков этой цели. Сделать это не так -то просто, поэтому постара-

    емся провести грамматический разбор без возвратов.

         Для того, чтобы избавиться от возвратов, в компиляторах в качестве

    контекста обычно используется следующий "незакрытый" символ исходной про-

    граммы. Тогда на грамматику налагается следующее требование: если есть

    альтернативы x|y|...|z, то множества символов, которыми могут начинаться

    выводимые из x,y,..,z слова, должны быть попарно различны. То есть если

    x => *Au и y => *Bv то A =/= B. если это требование выполнено, можно

    довольно просто определить, какая из альтернатив x,y или z - наша цель.

    Заметим, что факторизация оказывает здесь большую помощь. Если есть пра-

    вило U ::= xy|xz, ео преобразование этого правила к виду U ::= x(y|z)

    помогает сделать множесва первых символов для разных альтернатив непе-

    ресекающимися.



    4. Заключение



         В данном реферате рассматривались нисходящие распознаватели,

    алгоритм нисходящего разбора и проблемы связанные с нисходящим

    разбором. Одна из первых статей, рассматривающих фиксированный ал-

    горитм нисходящего разбора, принадлежит Айронсу. Но его метод не

    являлся нисходящим разбором в чистом виде, а являлся смешением нис-

    ходящих и восходящих разборов. Алгоритм, приведенный в данном рефе-

    рате, впервые был предложен в обзоре Флойда. Он же ввел и понятия

    "отец - сын - брат". Способы избавления от возвратов описаны Унге-

    ром.



    5. Список литературы



     1. Грисс.  Конструирование  компиляторов  для  цифровых вы-

     числительных машин. М., Мир, 1975г.

     2. Ахо А., Ульман Дж. Теория синтаксического анализа, пере-

     вода и компиляции. М. Мир 1978г.

     3. Ф.Льюис,  Д.Розенкранц,  Р.Стирнз.  Теоретические основы

     проектирования компиляторов. М., Мир, 1979г.

     4. Фельдман Дж.,  Грис Д.  Системы построения трансляторов.

     Сб. Алгоритмы и алгоритмические языки, вып.5, ВЦ АН СССР, 1971г.

_