Алексей Молчанов - Системное программное обеспечение. Лабораторный практикум

L → Р| L;P | L;

О → if(B) О; else Р | if(B) R else Р | if(B) Р | while(B) Р | а:=Е

R → begin L end

Р → О | R

И показанный выше оператор будет выглядеть так:

if (а<0) while (а<10) а:=а+1; else а:=1;

В языках C и C++ операторным скобкам begin и end соответствуют лексемы { и }, а оператор присваивания обозначается одним символом: =. Но суть подхода этот пример иллюстрирует верно: в этих языках для условного оператора правила различны в зависимости от того, входит в него составной оператор или одиночный оператор (точка с запятой ставится перед else для одиночных операторов в отличие от языка Pascal, где этой проблемы нет, так как конфликт между then и else может быть разрешен указанным выше способом, как в табл. 5.7). Желающие могут построить для такого языка матрицу операторного предшествования и убедиться, что она строится без конфликтов.

После того как заполнена матрица операторного предшествования, на основе исходной грамматики 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

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

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

Модуль SyntSymb (листинг П3.7, приложение 3), который реализует функционирование алгоритма «сдвиг-свертка» для грамматик операторного предшествования, можно использовать, не внося в него никаких изменений, так как он не зависит от входного языка. Требуется перестроить только модуль SyntRulе, внеся в него новые правила грамматики и новую матрицу операторного предшествования. Полученный в результате программный модуль представлен в листинге П3.6 в приложении 3 (обратите внимание на функцию MakeSymbolStr, которая возвращает имена нетерминальных символов для правил остовной грамматики!).

На этом построение синтаксического распознавателя закончено. Структуры данных, используемые этим распознавателем и порождаемые в результате его работы, были рассмотрены при выполнении лабораторной работы № 3.

В качестве формы внутреннего представления программы будут использоваться триады. Преимущества и недостатки триад были рассмотрены ранее (при выполнении лабораторной работы № 4). В данном случае в пользу выбора триад говорят два определяющих фактора: