Пример 2.8

Разбор цепочек

Пример 2.7

Примеры грамматик и языков различных типов.

1) Грамматика G1=({a, b},{A, B, C, D, F, S}, P1, S), где

P1={ S ® aaCFD, F ® AFB | AB, AB ® bBA, Ab ® bA, AD ® D, Cb ® bC,

CB ® C, bCD ® e};

L1(G1) = {a² b| n ³ 1} – это язык типа 0.

2) Грамматика G2=({0, 1}, {А, В, S}, P2 , S), где

Р2={S ® ASB | AB, AB ® BA, A ® 0, B ® 1}

L2(G2)={цепочки из 0 и 1 с одинаковым числом 0 и 1} – это язык типа 1.

3) Грамматика G3=({a, b, c}, {Q, S}, { S ® aQb | accb, Q ® cSc}, S);

L3(G3) = {(ac)ⁿ (cb)ⁿ | n > 0} - это язык типа 2.

4) Грамматика G4=({a, b, ^}, {А, В, S}, P4, S);

P4={ S ® A^ | B^, A ® a | Ba, B ® b | Bb | Ab }

L4(G4) = {w ^ | w Î {a,b}⁺, где нет двух рядом стоящих а} - язык типа 3.

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

С практической точки зрения наибольший интерес представляет разбор поконтекстно-свободным (КС и УКС) грамматикам. Их порождающей мощности достаточно для описания большей части синтаксической структуры языков программирования, для различных подклассов КС-грамматик имеются хорошо разработанные практически приемлемые способы решения задачи разбора.

Рассмотрим основные понятия и определения, связанные с разбором по КС-грамматике.

Вывод цепочки b Î (VT)^* из S Î VN в КС-грамматике G = (VT, VN, P, S), называетсялевым(левосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей путем замены самого левого нетерминала.

Вывод цепочки b Î (VT)^* из S Î VN в КС-грамматике G = (VT, VN, P, S), называетсяправым(правосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей путем замены самого правого нетерминала.

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

Для цепочки a+b+a в грамматике

G = ({a,b}, {S,T}, {S ® T | T+S; T ® a|b}, S)

можно построить следующие выводы:

1) S®T+S®T+T+S®T+T+T®a+T+T®a+b+T®a+b+a

2) S®T+S®a+S®a+T+S®a+b+S®a+b+T®a+b+a

3) S®T+S®T+T+S®T+T+T®T+T+a®T+b+a®a+b+a

Здесь вывод (2) - левосторонний, вывод (3) - правосторонний, а вывод (1) не является ни левосторонним, ни правосторонним, но все эти выводы являются эквивалентными в указанном выше смысле.

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

Дерево называется деревом вывода(или деревом разбора)в КС-грамматике G = {VT, VN, P, S), если выполнены следующие условия:

1) каждая вершина дерева помечена символом из множества (VN È VT È e), при этом корень дерева помечен символом S; листья - символами из (VT È e);

2) если вершина дерева помечена символом A Î VN, а ее непосредственные потомки - символами a₁, a₂, ... , a_n, где каждое a_i Î (VT È VN), то A ® a₁a₂...a_n - правило вывода в этой грамматике;

3) если вершина дерева помечена символом A Î VN, а ее единственный непосредственный потомок помечен символом e, то A ® e - правило вывода в этой грамматике.

Дерево вывода в примере 2.8. для цепочки a+b+a в грамматике G представлено на рис. 2.3:

Рис. 2.3. Дерево вывода

КС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка a Î L(G), для которой может быть построено два или более различных деревьев вывода.

Это утверждение эквивалентно тому, что цепочка a имеет два или более разных левосторонних (или правосторонних) выводов.

В противном случае грамматика называется однозначной.