Практическое занятие 11. Построение ll(1)-грамматик и мп-автоматов для обработки языков, порождаемых этими грамматиками.

Цель: освоить навык построения LL(1)-грамматик и МП-автоматов для обработки языков, порождаемых этими грамматиками.

Задание 1.

Для следующей грамматики с начальным символом <S> определить является ли она LL(1)-грамматикой:

<S> → a <A> <B> b <C> <D> <S> → 

<A> → <A> <S> d <A> → 

<B> → <S> <A> c <B> → e <C>

<B> →  <C> → <S> f

<C> → <C> g <C> → 

<D> → a <B> <D> <D> → 

Рекомендуемая литература: [2], [3], конспект лекций.

Этапы выполнения.

1. Найти множество СЛЕД для каждого нетерминала.

2. Найти множество ВЫБОР для каждого правила.

3. Сделать вывод, является ли эта грамматика LL(1)-грамматикой.

Тема. Формальные методы описания перевода.

СУ-схемы перевода. Транслирующие грамматики. Понятие атрибута. Синтезированные и унаследованные атрибуты. Атрибутные транслирующие грамматики и перевод.

Практическое занятие 12. Определение атрибутов и работа с атрибутными транслирующими грамматиками.

Цель: освоить навык построения атрибутных транслирующих грамматик.

Задание 1.

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

1. обращение входной цепочки,

2. пустую цепочку,

3. саму входную цепочку,

4. цепочку 0ⁿ 1^m , где n – число нулей, а m – число единиц во входной цепочке.

Рекомендуемая литература: [3], конспект лекций.

Этапы выполнения.

Для каждого варианта:

1. Определить множество нетерминальных символов и символов действий.

2. Определить начальный нетерминал.

3. Записать правила транслирующей грамматики.

4. Продемонстрировать требуемый перевод построением соответствующей последовательности актов.

Задание 2.

Постройте транслирующую грамматику для следующих переводов:

1. {1ⁿ 0^m} в {1ⁿ 2²ⁿ}, где n>0, m>0;

2. {1ⁿ 0^m 1^m 0ⁿ} в {1^m 0^n+m}, где m>0, n>0.

Рекомендуемая литература: [3], конспект лекций.

Этапы выполнения.

Для каждого перевода:

1. Определить множество входных и выходных символов.

2. Определить множество нетерминальных символов и символов действий.

3. Определить начальный нетерминал.

4. Записать правила транслирующей грамматики.

5. Продемонстрировать требуемый перевод построением соответствующей последовательности актов.

Задание 3.

Для следующей атрибутной транслирующей грамматики:

<S>_i,s НАСЛЕДУЕМЫЙ i СИНТЕЗИРУЕМЫЙ s

Начальное значение i=3.

Атрибуты символов действия – НАСЛЕДУЕМЫЕ.

<S>_i,s → a_x {f_y } {g_z }

y  x+ i

z  y+ x

s  z

<S>_i,s → b_x {f_y } {g_z }

y  z

z  s

s  y

<S>_i,s → c_x {f_y } {g_z }

y  z + 1

z  s + 1

s  y +1

<S>_i,s → d_x <S>_j,t {f_y }

y  i+ t

j  i

s  t

<S>_i,s → e_x {h_y } <S>_j,t

y  x

j  t

s  t

построить атрибутное дерево вывода и последовательность актов (если они существуют) для каждой из следующих входных цепочек:

а).a₆ б). a₁ a₂ в). d₃ a₂

г). b₄ д). c₉ е). d₁ d₁ d₃ d₄ a₅

ж). e₂ d₁ d₂ d₃ d₄ a₅

Рекомендуемая литература: [3], конспект лекций.

Этапы выполнения.

1. Записать по заданной атрибутной транслирующей грамматике соответствующую ей транслирующую грамматику.

Для каждой входной цепочки:

2. Построить дерево вывода в соответствии с полученной транслирующей грамматикой.

3. Подписать к каждой вершине дерева соответствующие атрибуты.

4. Присвоить синтезируемым атрибутам листьев начальное значение.

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

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

7. Определить последовательность актов.