Грамматический разбор. 
Построение эквивалентной праворекурсивной КС-грамматики

В КС-грамматике может быть несколько выводов, эквивалентных в том смысле, что в них применяются одни и те же правила к одинаковым в промежуточном выводе цепочкам, но в различном порядке. Например, для грамматики G с правилами вывода S > ScS|b|a возможны следующие эквивалентные выводы терминальной цепочки acb: S > ScS > Scb > acb и S > ScS > acS > acb.

Деревом вывода цепочки х в КС-грамматике G = (VT, VN, Р, S) называется упорядоченное дерево, каждая вершина которого помечена символом из множества V? VN? {е} так, что каждому правилу, А > b1b2b3 … bk, использующемуся при выводе цепочки х, в дереве вывода соответствует поддерево с корнем, А и прямыми потомками b1, b2, b3, …, bk.

В силу того, что цепочка х? L (G) выводится из аксиомы S, корнем вывода всегда является аксиома. Внутренние узлы вывода соответствуют нетерминальным символам. Концевые вершины дерева вывода — листья — это вершины, не имеющие потомков. Такие вершины соответствуют либо терминалам, либо пустым символам (е) при условии, что среди правил грамматики имеются правила с пустой правой частью. При чтении слева направо концевые вершины дерева вывода образуют цепочку х. Дерево вывода часто называют деревом грамматического разбора, или синтаксическим деревом, а процесс построения дерева вывода — грамматическим разбором (синтаксическим анализом). Одной цепочке языка может соответствовать больше одного дерева, так как эта цепочка может иметь разные выводы, порождающие разные деревья. КС-грамматика G == (VT, VN, Р, S) называется неоднозначной (неопределенной), если существует цепочка х? L (G), имеющая два или более дерева вывода.

Рассмотрим пример.

Пусть даны две КС-грамматики:

G1 = (VT, VN, Р1, S), VN = {S},.

P1={S > S+S | S | S? S | (S) | a};

G2= (VT, VN, Р2, S), VN = {S, A, B},.

P2 = {S > S + A | A | A, A > A? B | A / B | B, B > a| (S)}.

содержащие в множестве терминальных символов знаки операций, круглые скобки и символ а. Определить, являютсяли грамматики однозначными. Если какая-либо из них неоднозначна, привести пример цепочки, для которой существует два различных дерева вывода.

Решение: Грамматика G1 является неоднозначной, так как она имеет правила с правой частью, содержащей два вхождения нетерминала S и знак арифметической операции.

Построим два дерева вывода для простейшей цепочки, а + а + а:

Грамматика G2 является однозначной, так как не содержит правил с двойным вхождением нетерминального символа. Так, для цепочки, а + а + а она имеет только одно дерево вывода.

В некоторых случаях неоднозначность в грамматиках может устраняться путем эквивалентных преобразований. Однако в общем случае проблема устранения неоднозначности неразрешима. На практике от неоднозначности избавляются путем задания словесных ограничений, называемых контекстными условиями языка, которые включаются в его семантику.

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

Представление грамматики в виде графа

Дерево грамматического разбора не следует путать с представлением грамматики в виде графа. Граф грамматики в качестве вершин содержит сентенциальные формы (любые цепочки, выводимые из аксиомы).

Рассмотрим представление грамматики G в виде графа: G = (VT, VN, Р, S), в которой VT ={a, b, с}, VN = {S}, P={S > aSa | bSb | c}.