Магазинные автоматы
Расмотренный выше метод рекурсивного спуска является нв значительной степени неформальным и , соответственно, не может быть непосредственно применен к заданной грамматике. Все остальные мететоы СА ориентированы именно на формальный подход к построению транслятора. Имея грамматику определенного вида , можно формально построить анализатор.
Известный нам формализм - конечные автоматы (КА), используемый на этапе лексического анализа, не подходит для синтаксиса. Прежде всего по той причине, что грамматики дают возможность построения вложенных (рекурсивных) цепочек, анализ которых для КА оказывается непосильным. Интуитивно мы можем догадываться, что если речь идет о вложенности и рекурсии, то обязательно должен присутствовать стек. И действительно, если обычный КА дополнить стеком, то полученная формальная система может служить базой для создания синтаксического анализатора. Такой КА со стеком называется МАГАЗИННЫМ АВТОМАТОМ (МА). Полуформально его можно определить так:
входная строка I, текущий символ в строке (I)
магазин (стек) M, символ в вершине стека (M)
операция записи в стек заданной строки push(M,”…”). Строка помещается в стек, начиная с последнего символа, то есть первый символ оказывается в вершине стека;
операция выталкивания символа из стека pop(M);
операция проверки “стек пуст” M=0;
операция проверки наличия очередного символа в строке “строка пуста” I=0;
операция перехода к следующему символу в строке next(I) ;
S = {Si}, множество состояний КА;
описание поведения МА заключается в том, что для каждой комбинации (Si, (I), (M)) - состояния КА, входного символа и символа в вершине стека задается новое состояние перехода Sj и одна или несколько перечисленных выше операций.
Далее будут рассмотрены несколько видов грамматик, для каждой из которых будет определена методика (алгоритм) построения МА, который будет распознавать предложения этой грамматики. Речь будет идти о нисходящем разборе, грамматики будут рассматриваться в порядке возрастания их сложности.
