Математическая логика и теория алгоритмов. Стенюшкина В.А. - 103 стр.

       На рисунке 6.2 показано дерево синтаксической разборки цепочки i+i*I
для грамматики из предыдущего примера. Левостороннему выводу соответст-
вует обход сверху вниз, слева направо. Для правостороннего вывода ориента-
цию пути обхода дерева надо менять на обратную.

                                     E

                      R              +      R

                      R        R             *       F

                      F        F
                      i        i                     i




                                   Рисунок 6.2


      6.8 Магазинные автоматы

        Одной из основных задач при разборке блока синтаксического анализа
транслятора является построение алгоритма распознавания языка. Этот алго-
ритм может быть представлен распознающим устройством. Для КС-языков ис-
пользуется устройства, с магазинной памятью (МП-автоматы).
        Недетерминированным МП-автоматом называется семёрка M=< A, Q, Г,
δ,q0, Z0, F >, где А-конечный входной алфавит; Q-конечный алфавит состояний;
Г- конечное множество магазинных символов; q0∈Q – начальное состояние ав-
томата; Z0∈Г –начальный символ в магазинной памяти; F⊂Q – множество ко-
нечных состояний; δ -отображение Q×A×Г в Q×Г*.
        Магазинная память определяется правилом «первый вошел – последний
вышел». При записи нового символа содержимое магазинной памяти сдвигает-
ся в глубь на одно место, а верхнее отдается новому символу. Чтению доступен
только введенный последним символ. Он после чтения либо остается в мага-
зинной памяти, либо извлекается. Такт работы магазинной памяти-автомата
предполагает извлечение не более одного символа.
        Обработку входной цепочки магазинная память-автомат начинает в не-
котором выделенном состоянии при определенном содержимом магазинной
памяти. В каждый такт работы автомат выполняет операции трех типов: