Книга: Системное программное обеспечение. Лабораторный практикум

Построение остовной грамматики

После того как заполнена матрица операторного предшествования, на основе исходной грамматики G можно построить остовную грамматику G'({prog,end.,if, else,begin,end,while,do,or,xor,and,not,<,>,=,<>,(,), – ,+,um,a,c,=}, {E},P',E) с правилами P':

E ? prog E end. – правило № 1

E ? E | E;E | E; – правила № 2, 3 и 4

Е ? if(E) Е else Е | if(E) Е | begin Еend | while(?)do Е | а:=Е – правила № 5-9

Е ? Е or Е | Е хог Е|Е – правила № 10, 11 и 12

Е ? Е andE | Е – правила № 13 и 14

Е ? Е<Е | Е>Е | ?=.? | Е<>Е | (Е) | not(E) – правила № 15-20

Е ? Е-Е | Е+Е | Е – правила № 21, 22 и 23

Е ? urn Е|Е – правила № 24 и 25

Е ? (_Е) | а | с – правила № 26, 27 и 28

Всего имеем 28 правил. Жирным шрифтом в грамматике и в правилах выделены терминальные символы.

При внимательном рассмотрении видно, что в остовной грамматике неразличимы правила 2, 12, 14, 23 и 25, а также правила 19 и 26. Но если первая группа правил не имеет значения, то во втором случае у распознавателя могут возникнуть проблемы, связанные с тем, что некоторые ошибочные входные цепочки он будет считать допустимыми (например оператор а:=(а or b);, который во входном языке недопустим). Это связано с тем, что круглые скобки определяют приоритет как логических, так и арифметических операций, и хотя они несут одинаковую синтаксическую нагрузку, распознаватель должен их различать, поскольку семантика этих скобок различна. Для этого дополним остовную грамматику еще одним нетерминальным символом B, который будет обозначать логические выражения. Подставив этот символ в соответствующие правила, получим новую остовную грамматику G»({prog,end.,if,else,begin,end,while,do,or,xor,and,not,<,>,=,<>,(,), – ,+,um,a,c,=}, {E,B},P», E) с правилами P»:

E ? prog E end. – правило № 1

E ? E | E;E | E; – правила № 2-4

E ? if(B) EelseE | if(B) E | begin Eend | while(B)do E | a:=E – правила № 5-9

В ? В or В | В хог В | В – правила № 10-12

В ? В and В | В – правила № 13 и 14

В ? Е<Е | Е>Е | Е=Е | Е<>Е | (В) | not(B) – правила № 15-20

Е ? Е-Е | Е+Е | Е – правила № 21-23

Е ? urn Е | Е – правила № 24 и 25

Е ? (Е) | а | с – правила № 26-28

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

Оглавление книги