Специальная математика

Вид материала

Содержание

7.11. Транслирующие грамматики
7.12. s и q - грамматики
7.13. LL(1) - грамматики.

Подобный материал:

1 ... 29 30 31 32 33 34 35 36 ... 39

7.11. Транслирующие грамматики

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

1. E  E + T. 1. E  E + T{+}.

2. E  T. 2. E  T.

3. T  T * P. 3. T  T * P{*}

4. T  P. 4. T  P.

5. P  (E). 5. P  (E).

6. P  a. 6. P  a{a}.

7. P  b. 7. P  b{b}.

8. P  c. 8. P  c{c}.

Проанализируем строку

(a + b) * c

1. E  T  T * P  P * P  (E) * P  (E + T) * P.

E  T  T * P{*}  P * P{*} 

(E) * P{*}  (E + T{+}) * P{*}  (a{a} + b{b}) * c{c}{*}

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

ab + c *

7.12. s и q - грамматики

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

Не s-грамматика :

S  aT - начинается с нетерминального. T  bT.

S  TbS

T  bT

Aналогичная s-грамматика (распознает тоже)

:

S  abR

S  bRbS

R  a

R  bR

q-грамматика отличается от s-грамматики наличием аннулирующего правила (в правой части есть пустой символ)   .

1. S  aAS

2. S  b

3. A  cAS

4. A  

Из-за аннулирующих правил для q-грамматики вводится понятие следующего символа. N(A) - множество терминальных следующих (Next) за А символов.

В данном случае за А могут следовать a или b - {a,b}.

S  aAS  aAaAS  aAaAb

E(1) = {a} - множество выбора для первого правила.

E(2) = {b}

E(3) = {c}

E(4) = N(A) = {a,b}

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

	S	A	
a	1 AS 	4  > <	
b	2 	4  > <	
c		3 AS 	
┤			+

7.13. LL(1) - грамматики.

(left - leftmost)

LL(1) - грамматики относятся к нисходящим грамматикам (сверху - вниз).

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

В LL(1) - грамматиках разворачиваются самые левые нетерминальные символы сентенциальной формы и анализируется очередной самый левый терминальный входной строки. Возможен анализ k самых левых символов входной строки, Тогда грамматику называют LL(k) - грамматикой. Но, поскольку грамматики LL(k) и LL(1) эквивалентны в плане порождаемых языков, остановимся на рассмотрении только последней.

F() - множество терминальных символов, стоящих первыми (First)) в цепочках, выводимых из строки .

N(А) - множество терминальных символов, следующих (Next) в цепочках за данным нетерминальным символом А.

Множество выбора для каждого правила формируется с учетом множества первых и множества следующих символов.

LL(1) - это такая грамматика, у которой для правил с одинаковыми левыми частями множества выбора не пересекаются.

1. S  AbB E(1) = F(AbB) = {a, b, c, e}

2. S  d E(2) = {d}

3. A  CAb E(3) = F(CAb) = {a, e}

4. A  B E(4) = F(B)  N(A) = {c}  {b} = {c, b}

5. B  cSd E(5) = F(cSd) = {c}

6. B   E(6) = F()  N(B) = {}  {b, d, ┤}

7. C  a E(7) = {a}

8. C  ed E(8) = {e}