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

Окно SAG (рис. 6) состоит из двух главных полей: левое поле – дерево разбора, правое – разбираемая цепочка.

Цепочку можно вводить в правое окно, используя клавиатуру, или открыть какой-нибудь текстовый файл, содержащий ее. Для загрузки цепочки из файла используется пункт меню Файл à Открыть.

При вводе цепочки в правое окно в левом производится ее разбор по созданной грамматике и построение дерева. Если цепочка не соответствует грамматике, в левом окне появляется надпись «цепочка не распознана» (рис.6).

Рис. 6. Анализ ошибочной цепочки

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

Рассмотрим пример разбора строки, приведенной в листинге 2 (разбор производится по грамматике, представленной в листинге 1).

Листинг 2. Строка для разбора.

int a,b;

float c,d;

После ввода этой строки в правую панель слева будет построено дерево разбора (рис. 7). На верхнем уровне дерева находится нетерминальный символ VarBlock, соответствующий всей рассматриваемой цепочке. Видно, что для каждого нетерминального символа Var, обозначающего имя переменной в программе-цепочке анализатор создал атрибут type, в котором сохранил тип переменной.

Рис. 7. Дерево разбора

Задания

1. Расширить заданную грамматику, задающую математическое выражение со скобками и операциями "+", "-", "*", "/" до атрибутной, подсчитывающей значение выражения.

Правила исходной грамматики:

exp = mulDiv '+' exp;

exp = mulDiv '-' exp;

exp = mulDiv;

mulDiv = groupOrNumber '*' mulDiv;

mulDiv = groupOrNumber '/' mulDiv;

mulDiv = groupOrNumber;

groupOrNumber = '(' exp ')';

groupOrNumber = _TEXT;

2. Написать атрибутную грамматику, описывающую объявление переменных как в языке Си. Для каждой переменной сохранить её значение в атрибуте.

Так, если есть цепочка

int a = 10;

char *b = “abc”;

То при распознавании в дереве разбора должны встретиться два узла, например, следующего вида:

VAR_DEF [ name=”a”; val = “10” ]

VAR_DEF [ name=”b”; val = “abc” ]

3. Усовершенствовать сделанную в п.2 грамматику так, чтобы стартовый символ содержал атрибут, в котором был бы сохранён список названий всех переменных.

Т.е. если есть цепочка

int a, b;

char *c, *s;

То корень дерева должен содержать атрибут

[ vars=”a b c s” ].

4. Усовершенствовать сделанную в п.3 грамматику так, чтобы можно было задавать значения по-умолчанию для переменных. Т.е. в случаях, когда значение явным образом не присвоено – задавать его равным некой константе (которая должна задаваться через наследуемый атрибут для стартового символа грамматики).

Так, если есть цепочка

char *s;

float f;

То при распознавании в дереве разбора должны встретиться узлы, например, следующего вида:

VAR_DEF [ name=”s”; val = “NULL” ]

VAR_DEF [ name=”f”; val = “0.0” ]

(Здесь “NULL” – значение по-умолчанию для переменных типа char*, a “0.0” – для переменных типа float).

5. Написать атрибутную грамматику, описывающую объявление переменных как в языке Си или Паскаль (на выбор). Для каждой переменной сохранить в атрибутах: название, тип данных и объём занимаемой памяти. Грамматика должна поддерживать объявление массивов.

Так, если есть цепочка

a[1..10]: array of integer;

b: real;

То при распознавании в дереве разбора должны встретиться два узла, например, следующего вида:

VAR_DEF [ name=”a”; type=”array of integer”; memory=”40”]

VAR_DEF [ name=”b”; type=”real”; memory=”6”]

(Здесь предполагается, что под переменную типа integer отводится 4 байта памяти.)