программы, построенный на основе грамматики входного языка. Как правило, синтаксические конструкции языков программирования могут быть описаны с помощью КС-грамматик; реже встречаются языки, которые могут быть описаны с помощью регулярных грамматик.
Главную роль в том, как функционирует синтаксический анализатор и какой алгоритм лежит в его основе, играют принципы построения распознавателей для КС-языков. Без применения этих принципов невозможно выполнить эффективный синтаксический разбор предложений входного языка.
Проблема распознавания цепочек КС-языков
Взаимодействие лексического и синтаксического анализаторов рассматривалось в предыдущей лабораторной работе, здесь же будут рассмотрены алгоритмы, лежащие в основе синтаксического анализа. Перед синтаксическим анализатором стоят две основные задачи: проверить правильность конструкций программы, которая представляется в виде уже выделенных слов входного языка, и преобразовать ее в вид, удобный для дальнейшей семантической (смысловой) обработки и генерации кода. Одним из способов такого представления является дерево синтаксического разбора.
Основой для построения распознавателей КС-языков являются автоматы с магазинной памятью – МП-автоматы – односторонние недетерминированные распознаватели с линейно-ограниченной магазинной памятью (полная классификация распознавателей приведена в [1, 4, 3, 7]). Поэтому важно рассмотреть, как функционирует МП-автомат и как для КС-языков решается задача разбора – построение распознавателя языка на основе заданной грамматики. Далее рассмотрены технические аспекты, связанные с реализацией синтаксических анализаторов.
МП-автомат в отличие от обычного КА имеет стек (магазин), в который можно помещать специальные «магазинные» символы (обычно это терминальные и нетерминальные символы грамматики языка). Переход МП-автомата из одного состояния в другое зависит не только от входного символа, но и от одного или нескольких верхних символов стека. Таким образом, конфигурация автомата определяется тремя параметрами: состоянием автомата, текущим символом входной цепочки (положением указателя в цепочке) и содержимым стека.
При выполнении перехода МП-автомата из одной конфигурации в другую из стека удаляются верхние символы, соответствующие условию перехода, и добавляется цепочка, соответствующая правилу перехода. Первый символ цепочки становится верхушкой стека. Допускаются переходы, при которых входной символ игнорируется (и тем самым он будет входным символом при следующем переходе). Эти переходы называются ^-переходами. Если при окончании цепочки автомат находится в одном из заданных конечных состояний, а стек пуст, цепочка считается принятой (после окончания цепочки могут быть сделаны Х-переходы). Иначе цепочка символов не принимается.
МП-автомат называется недетерминированным, если при одной и той же его конфигурации возможен более чем один
