И.А. Волкова, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции, страница 2

Ab  bA

AD  D

Cb  bC

CB  C

bCD  

2) Язык типа 1: L(G) = { aⁿ bⁿ cⁿ, n >= 1}

G: S  aSBC | abC

CB  BC

bB  bb

bC  bc

cC  cc

3) Язык типа 2: L(G) = {(ac)ⁿ (cb)ⁿ | n > 0}

G: S  aQb | accb

Q  cSc

4) Язык типа 3: L(G) = {  |   {a,b}⁺, где нет двух рядом стоящих а}

G: S  A | B

A  a | Ba

B  b | Bb | Ab

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

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

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

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

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

Определение: вывод цепочки   (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   ) , при этом корень дерева помечен символом S; листья - символами из (VT  );

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

(3) если вершина дерева помечена символом A  VN, а ее единственный непосредственный потомок помечен символом , то A   - правило вывода в этой грамматике.

Пример дерева вывода для цепочки a+b+a в грамматике G:

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

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

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

Определение: язык, порождаемый грамматикой, называется неоднозначным, если он не может быть порожден никакой однозначной грамматикой.

Пример неоднозначной грамматики:

G = ({if, then, else, a, b}, {S}, P, S),

где P = {S  if b then S else S | if b then S | a}.

В этой грамматике для цепочки if b then if b then a else a можно построить два различных дерева вывода.

Однако это не означает, что язык L(G) обязательно неоднозначный. Определенная нами неоднозначность - это свойство грамматики, а не языка, т.е. для некоторых неоднозначных грамматик существуют эквивалентные им однозначные грамматики.

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

В приведенном выше примере разные деревья вывода предполагают соответствие else разным then. Если договориться, что else должно соответствовать ближайшему к нему then, и подправить грамматику G, то неоднозначность будет устранена:

S  if b then S | if b then S’ else S | a

S’  if b then S’ else S’ | a

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

Однако можно указать некоторые виды правил вывода, которые приводят к неоднозначности:

1. A  AA | 

2. A  AA | 

3. A  A | A | 

4. A  A | AA | 

Пример неоднозначного КС-языка:

L = {aⁱ b^j c^k | i = j или j = k}.

Интуитивно это объясняется тем, что цепочки с i = j должны порождаться группой правил вывода, отличных от правил, порождающих цепочки с j = k. Но тогда, по крайней мере, некоторые из цепочек с i = j = k будут порождаться обеими группами правил и, следовательно, будут иметь по два разных дерева вывода. Доказательство того, что КС-язык L неоднозначный, приведен в [3, стр. 235-236].

Одна из грамматик, порождающих L, такова:

S  AB | DC

A  aA | 

B  bBc | 

C  cC | 

D  aDb | 

Очевидно, что она неоднозначна.

Дерево вывода можно строить нисходящим либо восходящим способом.

При нисходящем разборе дерево вывода формируется от корня к листьям; на каждом шаге для вершины, помеченной нетерминальным символом, пытаются найти такое правило вывода, чтобы имеющиеся в нем терминальные символы “проектировались” на символы исходной цепочки.

Метод восходящего разбора заключается в том, что исходную цепочку пытаются “свернуть” к начальному символу S; на каждом шаге ищут подцепочку, которая совпадает с правой частью какого-либо правила вывода; если такая подцепочка находится, то она заменяется нетерминалом из левой части этого правила.

Если грамматика однозначная, то при любом способе построения будет получено одно и то же дерево разбора.

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

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

Определение: символ x  (VT  VN) называется недостижимым в грамматике G = (VT, VN, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики.

Алгоритм удаления недостижимых символов:

Вход: КС-грамматика G = (VT, VN, P, S)

Выход: КС-грамматика G’ = (VT’, VN’, P’, S), не содержащая недостижимых символов, для которой L(G) = L(G’).

Метод:

1. V₀ = {S}; i = 1.

2. V_i = {x | x  (VT  VN), в P есть Ax и AV_i-1, ,(VTVN)^}  V_i-1.

3. Если V_i  V_i-1, то i = i + 1 и переходим к шагу 2, иначе VN’ = V_i  VN;
   VT’ = V_i  VT; P’ состоит из правил множества P, содержащих только символы из Vi; G’ = (VT’, VN’, P’, S).

Определение: символ A  VN называется бесплодным в грамматике
G = (VT, VN, P, S), если множество {   VT^* | A  } пусто.

Алгоритм удаления бесплодных символов:

Вход: КС-грамматика G = (VT, VN, P, S).

Выход: КС-грамматика G’ = (VT, VN’, P’, S), не содержащая бесплодных символов, для которой L(G) = L(G’).

Метод:

Рекурсивно строим множества N₀, N₁, ...

1. N₀ = , i = 1.

2. N_i = {A | (A  )  P и   (N_i-1  VT)^*}  N_i-1.

3. Если N_i  N_i-1, то i = i + 1 и переходим к шагу 2, иначе VN’ = N_i; P’ состоит из правил множества P, содержащих только символы из VN’  VT; G’ = (VT, VN’, P’, S).

Определение: КС-грамматика G называется приведенной, если в ней нет недостижимых и бесплодных символов.

Алгоритм приведения грамматики:

1. обнаруживаются и удаляются все бесплодные нетерминалы.

2. обнаруживаются и удаляются все недостижимые символы.

Удаление символов сопровождается удалением правил вывода, содержащих эти символы.

Замечание: если в этом алгоритме переставить шаги (1) и (2), то не всегда результатом будет приведенная грамматика.

Для описания синтаксиса языков программирования стараются использовать однозначные приведенные КС-грамматики.

Задачи.

1. Дана грамматика. Построить вывод заданной цепочки.

a) S  T | T+S | T-S b) S  aSBC | abC

T  F | F*T CB  BC

F  a | b bB  bb

Цепочка a-b*a+b bC  bc

cC  cc

Цепочка aaabbbccc

2. Построить все сентенциальные формы для грамматики с правилами:

S  A+B | B+A

A  a

B  b

3. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка?

a) S  APA b) S  aQb | 

P  + | - Q  cSc

A  a | b

c) S  1B d) S  A | SA | SB

B  B0 | 1 A  a

B  b

1. Построить грамматику, порождающую язык :

1. L = { aⁿ b^m | n, m >= 1}

2. L = { ccc | , ,  - любые цепочки из a и b}

3. L = { a₁ a₂ ... a_n a_n ... a₂ a₁ | a_i = 0 или 1, n >= 1}

4. L = { aⁿ b^m | n  m ; n, m >= 0}

5. L = { цепочки из 0 и 1 с неравным числом 0 и 1}

6. L = {  |   {a,b}⁺}

7. L = {  |   {0,1}⁺ и содержит равное количество 0 и 1, причем любая подцепочка, взятая с левого конца, содержит единиц не меньше, чем нулей}.

8. L = { (a^2m b^m)ⁿ | m >= 1, n >= 0}

9. L = {  | n >= 1}

10. L = { | n >= 1}

11. L = { | n >= 1}

5. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка?

a) S  a | Ba b) S  Ab

B  Bb | b A  Aa | ba

c) S  0A1 | 01 d) S  AB

0A  00A1 AB  BA

A  01 A  a

B  b

*e) S  A | B *f) S  0A | 1S

A  aAb | 0 A  0A | 1B

B  aBbb | 1 B  0B | 1B | 

*g) S  0S | S0 | D *h) S  0A | 1S | 

D  DD | 1A |  A  1A | 0B

A  0B |  B  0S | 1B

B  0A | 0

*i) S  SS | A *j) S  AB

A  a | bb A  a | cA

B  bA

*k) S  aBA |  *l) S  Ab | c

B  bSA A  Ba

AA  c B  cS

6. Эквивалентны ли грамматики с правилами :

а) S  AB и S  AS | SB | AB

A  a | Aa A  a

B  b | Bb B  b

b) S  aSL | aL и S  aSBc | abc

L  Kc cB  Bc

cK  Kc bB  bb

K  b

7. Построить КС-грамматику, эквивалентную грамматике с правилами:

а) S  aAb b) S  AB | ABS

aA  aaAb AB  BA

A   BA  AB

A  a

B  b

8. Построить регулярную грамматику, эквивалентную грамматике с правилами:

а) S  A | AS b) S  A.A

A  a | bb A  B | BA

B  0 | 1

9. Доказать, что грамматика с правилами:

S  aSBC | abC

CB  BC

bB  bb

bC  bc

cC  cc

порождает язык L = {aⁿ bⁿ cⁿ | n >= 1}. Для этого показать, что в данной грамматике

1. выводится любая цепочка вида aⁿ bⁿ cⁿ (n >= 1) и

2. не выводятся никакие другие цепочки.

10. Дана грамматика с правилами:

a) S  S0 | S1 | D0 | D1 b) S  if B then S | B = E

D  H. E  B | B + E

H  0 | 1 | H0 | H1 B  a | b

Построить восходящим и нисходящим методами дерево вывода для цепочки:

a) 10.1001 b) if a then b = a+b+b

11. Определить тип грамматики. Описать язык, порождаемый этой грамматикой. Написать для этого языка КС-грамматику.

S  P

P  1P1 | 0P0 | T

T  021 | 120R

R1  0R

R0  1