задачи (1131503)

Задачи – вариант семинариста 2002

1.

Для регулярного выражения (ab|b)*ba|ab над T = { a, b } построить эквивалентный детерминированный конечный автомат.

2.

а).

Пусть дана КС-грамматика G и цепочка w. Всегда ли существует алгоритм проверки принадлежности цепочки языку L(G)?

б).

G = ({ S, A },{ a, b },P,S), где P:

S → baaA | babA

A → e | Aa | Ab

Построить эквивалентную LL(1)- грамматику.

3.

а).

Дать определение s-атрибутной грамматики.

б).

A and ( B or not ( C and D ) and E )

Сгенерировать код на командах перехода и изобразить атрибутированное дерево.

4.

G = ({ S, A, C },{ a, b },P,S), где P:

S → b | C

C → aC | Ac

A → aA | Aa | a

а).

Является ли грамматика однозначной?

б).

Является ли грамматика приведенной?

5.

a = b [ i ] + c [ 2 ]

Сгенерировать оптимальный код методом сопоставления образцов.

6.

A * B + C * ( D + E )

Сгенерировать код с оптимальным распределением регистров и изобразить

атрибутированное дерево.

Задачи – вариант лектора на контрольной 2002

1.

Для регулярного выражения b(ba|b)*|b над T = { a, b } построить эквивалентный детерминированный конечный автомат.

2.

G = ({ S, A },{ a, b },P,S), где P:

S → ba | A

A → a | Aab | Ab

Построить эквивалентную LL(1)- грамматику.

3.

G = ({ S, A },{ a, b },P,S), где P:

S → aL | a

L → Lb | b

Построить таблицу для LR(1)- анализатора.

4.

A + B * ( C * D + E * F )

Сгенерировать код с оптимальным распределением регистров и изобразить

атрибутированное дерево.

5.

A and not ( B or C ) or ( D and E )

Сгенерировать код на командах перехода и изобразить атрибутированное дерево.

6.

a = b [ i + j + 1 ]

Сгенерировать оптимальный код методом сопоставления образцов.