Задание 1. Отчет по контрольной работе по курсу «Теория формальных языков и грамматик» Вариант __

Отчет по контрольной работе по курсу «Теория формальных языков и грамматик» Вариант __

Выполнил: _____________
гр. __________ Проверил: Кузенная Н.В.

Самара, 2015

Задание 1.

Постройте КС-грамматику для описания " пустых" процедур (заглушек, в процедурах нет раздела описания переменных и нет исполняемого кода) с исполь­зованием параметров стандартных типов CHAR, BYTE, INTEGER.

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

При построении можно пользоваться как итеративными {}, так и факультативными скобками [], для сокращения количества правил в грамматике.

Примеры правильных цепочек языка:

Пример1:

PROC pr (a, b: INTEGER; VAR b: CHAR; VAR s: BYTE); BEGIN END pr;

Пример2:

PROC Sum(a: CHAR); BEGIN END Sum;

Для первого примера постройте дерево нисходящего разбора заданной терминальной цепочки по построенной Вами КС-грамматике.

Для второго примера постройте дерево восходящего разбора (свертку) заданной терминальной цепочки по построенной Вами КС-грамматике.

РЕШЕНИЕ:

КС – грамматика:

S-> PROC < идентификатор> (Р); BEGIN END < идентификатор>;

Р-> [ VAR ] I: T | [ VAR ] I: T; P

I-> < идентификатор> | < идентификатор>, I

T-> INTEGER | BYTE | CHAR

Дерево нисходящего разбора цепочки

PROC pr (a, b: INTEGER; VAR b: CHAR; VAR s: BYTE); BEGIN END pr;

:

S

PROC < идентификатор> ( Р ); BEGIN END < идентификатор>;

pr I: T; P pr

< идентификатор>, I INTEGER VAR I: T; P

a < идентификатор> < идентификатор> CHAR VAR I: T

bb < идентификатор> BYTE

S

Свертку цепочки PROC Sum(a: CHAR); BEGIN END Sum;

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

PROC Sum (a: CHAR); BEGIN END Sum;

PROC < идентификатор> (< идентификатор >: Т); BEGIN END < идентификатор>;

PROC < идентификатор> (I: Т); BEGIN END < идентификатор>;

PROC < идентификатор> (Р); BEGIN END < идентификатор>;

S