Понятие грамматического разбора

Лекция 5-6. Понятие грамматического разбора Деревом вывода (деревом разбора) цепочки х в КС-грамматике G = (VT, VN, Р, S) называется упорядоченное дерево, в котором: а) корнем всегда является аксиома S; б) внутренние вершины помечены нетерминальными символами из множества VN; в) концевые вершины, которые называются листьями, помечены терминальными символами из множества VT; г) дуги дерева вывода задают отношение между двумя вершинами, что каждому правилу А  αβ в дереве соответствует поддерево с корнем А и прямыми потомками α и β (рис. 1). В силу того, что цепочка х, принадлежащая L(G), выводится из аксиомы S, корнем дерева вывода всегда является аксиома. Концевые вершины не имеют потомков и при чтении слева направо образуют цепочку, вывод которой представлен данным деревом. Концевые вершины дерева также называют кроной дерева. Рисунок 1 - Поддерево с корнем А Для понятия дерево вывода используют синонимы дерево грамматического разбора или синтаксическое дерево. Процесс построения дерева вывода называется грамматическим разбором или синтаксическим анализом. Если xL(G), то не существует вывода Sx, т.е. для цепочки х нельзя построить дерево вывода. Любой компилятор рассматривает исходный модуль как входную цепочку, выполняет его синтаксический анализ и выдает сообщение об ошибке, если не существует дерева грамматического разбора исходного модуля. Понятие сентенциальной формы. Любая цепочка, выводимая из аксиомы, называется сентенциальной формой. Например, в грамматике G с правилами S  aSb |c существует вывод: . Здесь aSb, aaSbb, aaaSbbb, aaacbbb - сентенциальные формы. Язык L(G) включает только терминальные сентенциальные формы: Стратегии грамматического разбора Методы грамматического разбора делятся на два больших класса - восходящие и нисходящие. Эти понятия соответствуют способу построения дерева грамматического разбора. При восходящей стратегии разбора дерево строится от терминальных вершин вверх к корню дерева – аксиоме. На каждом шаге разбора выполняется поиск основы, начиная с самых левых символов рассматриваемой цепочки. Найденная основа, совпадающая с правой частью какого-либо правила вывода, заменяется на нетерминальный символ, стоящий в левой части этого правила. Если грамматика содержит несколько правил с одинаковыми правыми частями, то необходимо выбрать такой нетерминальный символ, выбор которого приведет к построению дерева. Замена найденной основы на нетерминал А называется редукцией, причем правило принадлежит множеству правил вывода Р рассматриваемой грамматики. Например, в грамматике G: при восходящем разборе цепочки aacbb последовательность построения дерева представлена на рис.2. Рисунок 2 – Построение дерева при восходящем разборе При нисходящей стратегии разбора дерево строится от корня вниз к терминальным вершинам. Главной задачей при нисходящем разборе является выбор того правила для нетерминального символа А из совокупности правил которое следует применить на рассматриваемом шаге. При нисходящем разборе этой же цепочки дерево будет построено за три шага в соответствии с выводом цепочки (рис. 2.3): S  aSb aaSbb aacbb. Рисунок 3 – Построение дерева при нисходящем разборе Неоднозначные грамматики КС-грамматика G называется неоднозначной, если существует цепочка xL(G), имеющая два или более дерева вывода. Это возможно в том случае, если цепочка имеет разные выводы, порождающие разные деревья. Например, в грамматике G: цепочку х=можно вывести с использованием двух различных последовательностей правил: Соответствующие деревья вывода представлены на рис.3. Если грамматика используется для определения языка программирования, то основным требованием к ней является требование однозначности, т.е. одной цепочке языка должно соответствовать одно дерево вывода. В противном случае программист и компилятор будут по-разному понимать смысл некоторых синтаксических конструкций языка. Рисунок 4 Практическое занятие 5-6. Пример. Дана грамматика G, порождающая арифметические выражения: G: S  S+A | S–A | A A AB | A/B | B B  a | (S). Построить дерево разбора цепочки x = а – а а. Решение. Вывод цепочки в грамматике G имеет вид: S  S–A  S – A*B  S – B*B  A – B*B  B – B*B   a – a*a. Дерево вывода цепочки приведено на рис. 5. Рисунок 5 – Дерево, построенное по нисходящей стратегии Задания для самостоятельного выполнения. Используя грамматику для арифметических выражений, рассмотренную в предыдущем примере, вывести следующие выражения и построить деревья вывода по нисходящей стратегии: а) a*a + a/a - a*(a + a) б) (a+a*a - a)/a + a*a в) a * (a - a) / a + (a - a) * (a + a) г) (a - a) / a / a – a * (a - a) * a д) a * a + a / a - (a + a) * (a + a) е) (a + a) / a – a * a + a * (a - a) ж) a – a + (a + a) * (a - a) / a з) a + a / (a – a) – a * (a + a) к) (a – a) / a * a + a + (a - a) / (a - a)