4. Разработка синтаксического анализа.

1. Структуры данных.

1.ВХОДНЫЕ ДАННЫЕ.

1. Строка лексем, полученная на этапе лексического анализа.

2. Таблица идентификаторов, полученная на этапе лексического анализа.

3. Управляющие таблицы (см. ниже).

2. ВЫХОДНЫЕ ДАННЫЕ.

3. Таблицы, полученные из таблицы идентификаторов (см. ниже).

4. Внутренняя форма представления программы (последовательность триад).

2. Построение грамматики.

По построенным в разделе 2 БНФ построим грамматику, порождающую создаваемый язык (сохраняя нумерацию правил); при этом терминалами будут являться лексемы:

1. P -> DL DC DV begin SO end.

2. DL -> label IL ;

DL -> e

3. IL -> L

IL -> L , IL

4. L -> i

L -> z

9. DC -> const IC

DC -> e

IC -> EIC ;

IC -> EIC ; IC

10. EIC -> SI = S z

EIC -> SI = z

11. SI -> i

SI -> i , SI

12. S -> +

S -> -

13. DV -> var IV

DV -> e

IV -> EIV ;

IV -> EIV ; IV

14. EIV -> SI : T

15. T -> integer

T -> bitstring

16. SO -> O

SO -> O SO

17. O -> L : NO ;

O -> NO ;

18. NO -> begin SO end

NO -> OP

NO -> OR

NO -> OW

NO -> OG

NO -> OI

NO -> OC

19. OP -> i := E

20. E -> AE

E -> SE

21. AE -> AT

AE -> AE + AT

AE -> AE - AT

22. AT -> AM

AT -> AT * AM

AT -> AT / AM

23. AM -> ( AE )

AM -> S i

AM -> i

AM -> S z

AM -> z

AM -> LS

24. LS -> strlen ( SE )

25. SE -> STR

SE -> PS

SE -> CS

SE -> RS

26. STR -> i

STR -> ‘ sb ‘

27. PS -> strcopy ( SE , BP , QL )

28. BP -> z

29. QL -> z

30. CS -> strconc ( SE , SE )

31. RS -> strreplace ( SE , SE , SE )

32. OR -> NOR ( SI )

33. NOR -> read

NOR -> readln

34. OW -> NOW ( INF )

OW -> writeln

35. NOW -> write

NOW -> writeln

36. INF -> AE

INF -> SE

INF -> ‘ s ‘

38. OG -> goto L

39. OI -> if IE then NO else NO

OI -> if IE then NO

40. IE -> AE M AE

41. M -> =

M -> <>

M -> <

M -> >

M -> <=

M -> >=

42. OC -> repeat SO until IE

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

Приведем полученную в предыдущем пункте грамматику к грамматике слабого предшествования.

Дадим определение грамматики слабого предшествования в терминах отношений <, = и >:

пусть G=<Vt,Vn,S,R> - приведенная грамматика без e-правил; назовем G грамматикой слабого предшествования, если:

1. отношение > не пересекается с объединением отношений < и =;

2. для правил вывода A -> a X b и B -> b, где X принадлежит V, не выполняется ни X<B, ни X>B.

Поочередно выполним указанные требования.

Сначала удалим из грамматики e-правила:

1. P -> DL DC DV begin SO end.

P -> DC DV begin SO end.

P -> DL DV begin SO end.

P -> DL DC begin SO end.

P -> DL begin SO end.

P -> DC begin SO end.

P -> DV begin SO end.

P -> begin SO end.

2. DL -> label IL ;

3. IL -> L

IL -> L , IL

4. L -> i

L -> z

9. DC -> const IC

IC -> EIC ;

IC -> EIC ; IC

10. EIC -> SI = S z

EIC -> SI = z

11. SI -> i

SI -> i , SI

12. S -> +

S -> -

13. DV -> var IV

IV -> EIV ;

IV -> EIV ; IV

14. EIV -> SI : T

15. T -> integer

T -> bitstring

16. SO -> O

SO -> O SO

17. O -> L : NO ;

O -> NO ;

18. NO -> begin SO end

NO -> OP

NO -> OR

NO -> OW

NO -> OG

NO -> OI

NO -> OC

19. OP -> i := E

20. E -> AE

E -> SE

21. AE -> AT

AE -> AE + AT

AE -> AE - AT

22. AT -> AM

AT -> AT * AM

AT -> AT / AM

23. AM -> ( AE )

AM -> S i

AM -> i

AM -> S z

AM -> z

AM -> LS

24. LS -> strlen ( SE )

25. SE -> STR

SE -> PS

SE -> CS

SE -> RS

26. STR -> i

STR -> ‘ sb ‘

27. PS -> strcopy ( SE , BP , QL )

28. BP -> z

29. QL -> z

30. CS -> strconc ( SE , SE )

31. RS -> strreplace ( SE , SE , SE )

32. OR -> NOR ( SI )

33. NOR -> read

NOR -> readln

34. OW -> NOW ( INF )

OW -> writeln

35. NOW -> write

NOW -> writeln

36. INF -> AE

INF -> SE

INF -> ‘ s ‘

38. OG -> goto L

39. OI -> if IE then NO else NO

OI -> if IE then NO

40. IE -> AE M AE

41. M -> =

M -> <>

M -> <

M -> >

M -> <=

M -> >=

42. OC -> repeat SO until IE

Теперь обратимся к первому пункту определения грамматики слабого предшествования. Согласно ему, в грамматике не должны пересекаться отношение > и объединение отношений < и =, т.е. обрабатывая очередной входной символ, мы должны однозначно принять решение о переносе или свертке. В полученной же грамматике существуют 2 проблемы:

1. Нетерминал из левой части правила вывода является суффиксом правой части этого правила вывода (правила 3,9,11,13,16). В этом случае непонятно: осуществлять перенос или свертку. Решение этой проблемы: исправление таких правил вывода путем перевода в левую рекурсию.

2. Арифметические_выражения и операции_над_строками указываются в скобках (правила 23,24,27,30,31). В этом случае также непонятно: осуществлять перенос или свертку. Решение этой проблемы: введение дополнительных нетерминалов AET и SET таких, что AET -> AE и SET -> SE, и в скобках указываются именно AET и SET.

Решая проблемы (1) и (2) указанными способами, приходим к грамматике:

1. P -> DL DC DV begin SO end.

P -> DC DV begin SO end.

P -> DL DV begin SO end.

P -> DL DC begin SO end.

P -> DL begin SO end.

P -> DC begin SO end.

P -> DV begin SO end.

P -> begin SO end.

2. DL -> label IL ;

3. IL -> L

IL -> IL , L

4. L -> i

L -> z

9. DC -> const IC

IC -> EIC ;

IC -> IC EIC ;

10. EIC -> SI = S z

EIC -> SI = z

11. SI -> i

SI -> SI , i

12. S -> +

S -> -

13. DV -> var IV

IV -> EIV ;

IV -> IV EIV ;

14. EIV -> SI : T

15. T -> integer

T -> bitstring

16. SO -> O

SO -> SO O

17. O -> L : NO ;

O -> NO ;

18. NO -> begin SO end

NO -> OP

NO -> OR

NO -> OW

NO -> OG

NO -> OI

NO -> OC

19. OP -> i := E

20. E -> AE

E -> SE

21. AE -> AT

AE -> AE + AT

AE -> AE - AT

22. AT -> AM

AT -> AT * AM

AT -> AT / AM

23. AM -> ( AET )

AET -> AE

AM -> S i

AM -> i

AM -> S z

AM -> z

AM -> LS

24. LS -> strlen ( SET )

SET -> SE

25. SE -> STR

SE -> PS

SE -> CS

SE -> RS

26. STR -> i

STR -> ‘ sb ‘

27. PS -> strcopy ( SET , BP , QL )

28. BP -> z

29. QL -> z

30. CS -> strconc ( SET , SET )

31. RS -> strreplace ( SET , SET , SET )

32. OR -> NOR ( SI )

33. NOR -> read

NOR -> readln

34. OW -> NOW ( INF )

OW -> writeln

35. NOW -> write

NOW -> writeln

36. INF -> AE

INF -> SE

INF -> ‘ s ‘

38. OG -> goto L

39. OI -> if IE then NO else NO

OI -> if IE then NO

40. IE -> AE M AE

41. M -> =

M -> <>

M -> <

M -> >

M -> <=

M -> >=

42. OC -> repeat SO until IE

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

В полученной грамматике такие трудности возникают из-за неоднозначности некоторых однолитерных_разделителей. Так, символ “+” является одновременно унарным и бинарным плюсом; символ “-“ является одновременно унарным и бинарным минусом; символ “:” служит в разделе описания переменных и при использовании меток в основной программе; символ “=” служит в разделе описания констант и при использовании логических выражений в основной программе; и, наконец, символ “,” служит разделителем в списках меток, констант и идентификаторов при описании и одновременно выполняет роль разделителя в операциях со строками основной программы.

Для решения этой проблемы дополним программу лексического анализа действиями по различению указанных разделителей:

1. символ “+” явяляется бинарным, если он следует после идентификатора, целого_без_знака или закрывающей скобки, иначе он является унарным.

2. символ “-“ - аналогично символу “+”.

3. символы “:”,”=” и “,” легко распознаются, т.к. их применение зависит только от того, встречаются ли они в разделе описаний (до первого begin) или в основной программе (после первого begin).

На этапе разработки синтаксического анализа мы будем различать эти символы следующим образом:

1. унарный плюс - “+”, бинарный плюс - “++”.

2. унарный минус - “-“, бинарный минус - “—“.

3. двоеточие в разделе описаний - “:”, в основной программе - “::”.

4. равенство в разделе описаний - “=”, в основной программе - “==”.

5. запятая в разделе описаний - “,”, в основной программе - “,,”.

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

Учитывая все сказанное, грамматика принимает следующий вид (правила вывода пронумеруем теперь по порядку для дальнейшего использования):

1. P -> DL DC DV begin SO end.

2. P -> DC DV begin SO end.

3. P -> DL DV begin SO end.

4. P -> DL DC begin SO end.

5. P -> DL begin SO end.

6. P -> DC begin SO end.

7. P -> DV begin SO end.

8. P -> begin SO end.

9. DL -> label IL ;

10. IL -> i

11. IL -> IL , i

12. IL -> z

13. IL _> IL , z

14. DC -> const IC

15. IC -> EIC ;

16. IC -> IC EIC ;

17. EIC -> SI = S z

18. EIC -> SI = z

19. SI -> i

20. SI -> SI , i

21. S -> +

22. S -> -

23. DV -> var IV

24. IV -> EIV ;

25. IV -> IV EIV ;

26. EIV -> SI : T

27. T -> integer

28. T -> bitstring

29. SO -> O

30. SO -> SO O

31. O -> i :: NO ;

32. O -> z :: NO ;

33. O -> NO ;

34. NO -> begin SO end

35. NO -> OP

36. NO -> OR

37. NO -> OW

38. NO -> OG

39. NO -> OI

40. NO -> OC

41. OP -> i := E

42. E -> AE

43. E -> SE

44. AE -> AT

45. AE -> AE ++ AT

46. AE -> AE -- AT

47. AT -> AM

48. AT -> AT * AM

49. AT -> AT / AM

50. AM -> ( AET )

51. AET -> AE

52. AM -> S i

53. AM -> i

54. AM -> S z

55. AM -> z

56. AM -> LS

57. LS -> strlen ( SET )

58. SET -> SE

59. SE -> STR

60. SE -> PS

61. SE -> CS

62. SE -> RS

63. STR -> i

64. STR -> ‘ sb ‘

65. PS -> strcopy ( SET ,, BP ,, QL )

66. BP -> z

67. QL -> z

68. CS -> strconc ( SET ,, SET )

69. RS -> strreplace ( SET ,, SET ,, SET )

70. OR -> NOR ( SI )

71. NOR -> read

72. NOR -> readln

73. OW -> NOW ( INF )

74. OW -> writeln

75. NOW -> write

76. NOW -> writeln

77. INF -> AE

78. INF -> SE

79. INF -> ‘ s ‘

80. OG -> goto i

81. OG -> goto z

82. OI -> if IE then NO else NO

83. OI -> if IE then NO

84. IE -> AE M AE

85. M -> ==

86. M -> <>

87. M -> <

88. M -> >

89. M -> <=

90. M -> >=

91. OC -> repeat SO until IE

Подтверждением того, что полученная грамматика является грамматикой слабого предшествования, является корректно построенная матрица отношений.