Контекстно-свободные языки. Свойства и распознаватели КС-языков. Преобразование КС-грамматик. КС-грамматики в нормальной форме, страница 9

1,2 {q,1,S,l} |¾(1) {q,1,T,S₁}

раскроем нетерминал T

3 |¾(1) {q,1,E,S₁T₁}

раскроем нетерминал E

4|¾(1) {q,1,(S),S₁T₁E₁}

первый символ – не “(”

5|¾(4) {b,1,(S),S₁T₁E₁}

выберем след. альтернативу для E

6|¾(6,1) {q,1,a,S₁T₁E₂}

первый символ совпал, сдвиг головки

7|¾(2) {q,2,l,S₁T₁E₂a}

в стеке пусто, но i¹n+1 – возврат

8|¾(3) {b,2,l,S₁T₁E₂a}

возвращаем “a”  из стека возврата в  L₁

9|¾(5) {b,1,a,S₁T₁E₂}

выберем след. альтернативу для E

10|¾(6,1) {q,1,b,S₁T₁E₃}

первый символ – не “b”

11|¾(4) {b,1,b,S₁T₁E₃}

вернем E из L₂ в  L₁ 

12|¾(6,3) {b,1,E,S₁T₁}

выберем след. альтернативу для T

13|¾(6,1) {q,1,EF,S₁T₂}

раскроем нетерминал E

14|¾(1) {q,1,(S)F,S₁T₂E₁}

первый символ – не “(”

15|¾(4) {b,1,(S)F,S₁T₂E₁}

выберем след. альтернативу для E

16|¾(6,1) {q,1,aF,S₁T₂E₂}

первый символ совпал, сдвиг головки

17|¾(2) {q,2,F,S₁T₂E₂a}

раскроем нетерминал F

18|¾(1) {q,2,*E,S₁T₂E₂aF₁}

второй символ – не “*”

19|¾(4) {b,2,*E,S₁T₂E₂aF₁}

выберем след. альтернативу для F

20|¾(6,1) {q,2,/E,S₁T₂E₂aF₂}

второй символ совпал, перепишем в L₂

21|¾(2) {q,3,E,S₁T₂E₂aF₂/}

раскроем нетерминал E

22|¾(1) {q,3,(S),S₁T₂E₂aF₂/E₁}

третий символ совпал, перепишем в L₂

23|¾(2) {q,4,S),S₁T₂E₂aF₂/E₁(}

раскроем нетерминал S

24|¾(1) {q,4,T),S₁T₂E₂aF₂/E₁(S₁}

раскроем нетерминал T

25|¾(1) {q,4,E),S₁T₂E₂aF₂/E₁(S₁T₁}

раскроем нетерминал E

26|¾(1) {q,4,(S)),S₁T₂E₂aF₂/E₁(S₁T₁E₁}

4-й символ – не “(”

27|¾(4) {b,4,(S)),S₁T₂E₂aF₂/E₁(S₁T₁E₁}

выберем след. альтернативу для E

28|¾(6,1) {q,4,a),S₁T₂E₂aF₂/E₁(S₁T₁E₂}

4-й символ совпал, переносим в L₂

29|¾(2) {q,5,),S₁T₂E₂aF₂/E₁(S₁T₁E₂a}

5-й символ не совпал

30|¾(4) {b,5,),S₁T₂E₂aF₂/E₁(S₁T₁E₂a}

в стеке L₂ – терминал, вернём его

31|¾(5) {b,4,a),S₁T₂E₂aF₂/E₁(S₁T₁E₂}

выберем след. альтернативу для E

32|¾(6,1) {q,4,b),S₁T₂E₂aF₂/E₁(S₁T₁E₃}

4-й символ не совпал

33|¾(4) {b,4,b),S₁T₂E₂aF₂/E₁(S₁T₁E₃}

нет альтернатив для E

34|¾(6,3) {b,4,E),S₁T₂E₂aF₂/E₁(S₁T₁}

выберем след. альтернативу для T

35|¾(6,1) {q,4,EF),S₁T₂E₂aF₂/E₁(S₁T₂}

раскроем нетерминал E

36|¾(1) {q,4,(S)F),S₁T₂E₂aF₂/E₁(S₁T₂E₁}

4-й символ не совпал

37|¾(4) {b,4,(S)F),S₁T₂E₂aF₂/E₁(S₁T₂E₁}

выберем след. альтернативу для E

38|¾(6,1) {q,4,aF),S₁T₂E₂aF₂/E₁(S₁T₂E₂}

4-й символ совпал

39|¾(2) {q,5,F),S₁T₂E₂aF₂/E₁(S₁T₂E₂a}

раскроем нетерминал F

40|¾(1) {q,5,*E),S₁T₂E₂aF₂/E₁(S₁T₂E₂aF₁}

5-й символ не совпал

41|¾(4) {b,5,*E),S₁T₂E₂aF₂/E₁(S₁T₂E₂aF₁}

выберем след. альтернативу для F

42|¾(6,1) {q,5,/E),S₁T₂E₂aF₂/E₁(S₁T₂E₂aF₂}

5-й символ не совпал

43|¾(4) {b,5,/E),S₁T₂E₂aF₂/E₁(S₁T₂E₂aF₂}

выберем след. альтерн. для F

44|¾(6,1) {q,5,*EF),S₁T₂E₂aF₂/E₁(S₁T₂E₂aF₃}

5-й символ не совпал

45|¾(4) {b,5,*EF),S₁T₂E₂aF₂/E₁(S₁T₂E₂aF₃}

выберем след. альтерн. для F

46|¾(6,1) {q,5,/EF),S₁T₂E₂aF₂/E₁(S₁T₂E₂aF₄}

5-й символ не совпал

47|¾(4) {b,5,/EF),S₁T₂E₂aF₂/E₁(S₁T₂E₂aF₄}

для F нет альтернативы

48|¾(6,3) {b,5,F),S₁T₂E₂aF₂/E₁(S₁T₂E₂a}

возврат по символу

49|¾(5) {b,4,aF),S₁T₂E₂aF₂/E₁(S₁T₂E₂}

выберем след. альтернативу для E

50|¾(6,1) {q,4,bF),S₁T₂E₂aF₂/E₁(S₁T₂E₃}

4-й символ не совпал

51|¾(4) {b,4,bF),S₁T₂E₂aF₂/E₁(S₁T₂E₃}

вернем E из L₂ в  L₁ 

52|¾(6,3) {b,4,EF),S₁T₂E₂aF₂/E₁(S₁T₂}

вернем T из L₂ в  L₁ 

53|¾(6,3) {b,4,T),S₁T₂E₂aF₂/E₁(S₁}

выберем след. альтернативу для S

54|¾(6,1) {q,4,TR),S₁T₂E₂aF₂/E₁(S₂}

раскроем нетерминал T

55|¾(1) {q,4,ER),S₁T₂E₂aF₂/E₁(S₂T₁}

раскроем нетерминал E

56|¾(1) {q,4,(S)R),S₁T₂E₂aF₂/E₁(S₂T₁E₁}

4-й символ не совпал

57|¾(4) {b,4,(S)R),S₁T₂E₂aF₂/E₁(S₂T₁E₁}

выберем след. альтернативу для E

58|¾(6,1) {q,4,aR),S₁T₂E₂aF₂/E₁(S₂T₁E₂}

4-й символ совпал, переносим в L₂

59|¾(2) {q,5,R),S₁T₂E₂aF₂/E₁(S₂T₁E₂a}

раскроем нетерминал R

60|¾(1) {q,5,+T),S₁T₂E₂aF₂/E₁(S₂T₁E₂aR₁}

5-й символ не совпал

61|¾(4) {b,5,+T),S₁T₂E₂aF₂/E₁(S₂T₁E₂aR₁}

выберем след. альтернативу для R

62|¾(6,1) {q,5,–T),S₁T₂E₂aF₂/E₁(S₂T₁E₂aR₂}

5-й символ совпал, переносим в L₂

63|¾(2) {q,6,T),S₁T₂E₂aF₂/E₁(S₂T₁E₂aR₂–}

раскроем нетерминал T

64|¾(1) {q,6,E),S₁T₂E₂aF₂/E₁(S₂T₁E₂aR₂–T₁}

раскроем нетерминал E

65|¾(1) {q,6,(S)),S₁T₂E₂aF₂/E₁(S₂T₁E₂aR₂–T₁E₁}

6-й символ не совпал

66|¾(4) {b,6,(S)),S₁T₂E₂aF₂/E₁(S₂T₁E₂aR₂–T₁E₁}

выберем след. альтер. для E

67|¾(6,1) {q,6,a),S₁T₂E₂aF₂/E₁(S₂T₁E₂aR₂–T₁E₂}

6-й символ не совпал

68|¾(4) {b,6,a),S₁T₂E₂aF₂/E₁(S₂T₁E₂aR₂–T₁E₂}

выберем след. альтер. для E

69|¾(6,1) {q,6,b),S₁T₂E₂aF₂/E₁(S₂T₁E₂aR₂–T₁E₃}

6-й символ совпал

70|¾(2) {q,7,),S₁T₂E₂aF₂/E₁(S₂T₁E₂aR₂–T₁E₃b}

7-й символ совпал

71|¾(2) {q,8,l,S₁T₂E₂aF₂/E₁(S₂T₁E₂aR₂–T₁E₃b)}|¾(3)

Разбор закончен  stop(+)