Распознавание цепочек КС-языков




Краткие теоретические сведения

По иерархии грамматик Хомского выделяют 4 основные группы языков (и описывающих их грамматик). При этом наибольший интерес представляют регулярные и контексно-свободные (КС) грамматики и языки. Они используются при описании синтаксиса языков программирования. С помощью регулярных грамматик можно описать лексемы языка - идентификаторы, константы, служебные слова и прочие. На основе КС-грамматик строятся более крупные синтаксические конструкции - описания типов и переменных, арифметические и логические выражения, управляющие операторы, и, наконец, полностью вся программа на исходном языке.

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

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

Распознавание цепочек КС-языков

Класс КС-языков допускает распознавание с помощью недетерминированного конечного автомата со стековой (или магазинной) памятью - МП-автомата. Контекстно-зависимые языки - последний класс языков, которые можно эффективно распознавать с помощью ЭВМ. Они допускаются двусторонними недетерминированными линейно ограниченными автоматами. Для цепочек языка без ограничений, в общем случае, требуется универсальный вычислитель (машина Тьюринга, машина с неограниченным числом регистров и т.п.). Контекстно-зависимые языки и языки без ограничений при создании структур языков программирования не используются.

МП-автомат в отличие от обычного КА имеет стек (магазин), в который можно помещать специальные "магазинные" символы (обычно это терминальные и нетерминальные символы грамматики языка). Переход из одного состояния в другое зависит не только от входного символа, но и от одного или нескольких верхних символов стека. Таким образом, конфигурация автомата определяется тремя параметрами: состоянием автомата, текущим символом входной цепочки (положением указателя в цепочке) и содержимым стека.

При выполнении перехода из стека удаляются верхние символы, соответствующие условию перехода, и добавляется цепочка, соответствующая правилу перехода. Первый символ цепочки становится верхушкой стека. Допускаются переходы, при которых входной символ игнорируется (и, тем самым, он будет входным символом при следующем переходе). Эти переходы называются l-переходами. МП-автомат называется недетерминированным, если при одной и той же его конфигурации возможен более чем один переход. Если при окончании цепочки автомат находится в одном из заданных конечных состояний, а стек пуст, цепочка считается принятой (после окончания цепочки могут быть сделаны l-переходы). Иначе цепочка символов не принимается.

По КС-грамматике G (VN, VT, P,S), V = VT È VN можно построить недетерминированный МП-автомат, который допускает цепочки языка этой грамматики. Он имеет только одно состояние и следующий набор переходов:

· l(A)¸(a) - для каждого правила грамматики A®a Î P, где AÎ VN, aÎ V *;

· а(а)¸() - для каждого терминала аÎ VT;

Здесь в круглых скобках показано содержимое верхушки стека. Перед скобками стоит очередной символ входной цепочки или символ l для l-перехода, а символ ¸ разделяет состояния автомата до и после выполнения перехода (показывает такт работы автомата). В начале работы автомата в стеке лежит символ SÎ VN, в конце работы автомата стек должен быть пуст.

Можно построить и другой автомат, который также содержит одно состояние и имеет следующие переходы:

· а()¸(а) - для каждого терминала аÎ VT;

· l(a)¸(A) - для каждого правила грамматики A®a Î P, где AÎ VN, aÎ V *;

В таком варианте в начале разбора стек автомата пуст. Тогда в конце разбора допустимой цепочки в стеке должен остаться символ SÎ VN.

По недетерминированному МП-автомату всегда можно построить КС-грамматику. Таким образом, класс КС-языков и класс языков, допускаемых МП-автоматами, эквивалентны.

Не каждый КС-язык допускает разбор с помощью детерминированного МП-автомата. Недетерминированные МП-автоматы могут распознавать более широкий класс языков, чем детерминированные - в этом их отличие от обычных КА. Интерес для реализации компиляторов представляют детерминированные КС-языки - собственное подмножество КС-языков, допускающее распознавание с помощью детерминированных МП-автоматов.

Два (недетерминированных) МП-автомата, построенных выше для произвольной КС-грамматики определяют два класса методов разбора КС-языков: сверху вниз и снизу вверх.

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

Во втором случае детерминированный разбор удобно формализовать в терминах "сдвиг" (перенос символа из входной цепочки в магазин) и "свертка" (применение к вершине магазина какого-либо правила грамматики). При просмотре входной цепочки слева направо при этом будут получаться правые выводы. Проблема в этом случае состоит в выборе между сдвигом и сверткой и в выборе правила для свертки.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-27 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: