Практическое занятие 8. Построение мп-трансляторов.

Цель: освоить навык построения МП-трансляторов и организации перевода символьных цепочек.

Задание 1.

Постройте не примитивные МП-трансляторы, которые будут выполнять следующие переводы:

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.

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

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

Для каждого множества:

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

2. Построить управляющую таблицу МП-автомата, определив:

   • множества входных, выходных и магазинных символов,

   • правила переходов и выходов,

   • формат вывода.

3. Показать последовательность конфигураций построенного автомата при распознавании и переводе указанной цепочки.

Тема. Нисходящие методы синтаксического анализа.

Алгоритм нисходящего разбора. S-грамматика. Q-грамматика.

Практическое занятие 9. Построение s-грамматик и мп-автоматов для обработки языков, порождаемых этими грамматиками.

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

Задание 1.

Для каждого из следующих языков построить S-грамматику и соответствующий нисходящий МП-распознаватель:

1. {1 ⁿ m 0 ⁿ | n ≥ 0}

2. {w m w ^r | w  {0,1}^*}, где верхний индекс r обозначает запись цепочки в обратном порядке, например, w=00101, тогда w ^r = 10100.

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

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

Для каждого языка:

1. Указать цепочку длины, большей 3, принадлежащую этому языку.

2. Описать S-грамматику, порождающую данный язык.

3. Построить управляющую таблицу МП-автомата, определив

   • множества входных и магазинных символов,

   • правила переходов и выходов.

4. Показать последовательность конфигураций построенного автомата при распознавании указанной цепочки.

Практическое занятие 10. Построение q-грамматик и мп-автоматов для обработки языков, порождаемых этими грамматиками.

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

Задание 1.

Определить, является ли следующая грамматика с начальным символом <S> Q-грамматикой:

<S> → a <A> <B>

<S> → b <A>

<S> → 

<A> → a <A>b

<A> → 

<B> → b <B>

<B> → c

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

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

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

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

3. Определить, является ли эта грамматика Q-грамматикой.

Задание 2.

Для каждого из следующих языков построить Q-грамматику и соответствующий нисходящий МП-распознаватель:

1. {1 ⁿ 0 ⁿ | n ≥ 0}

2. {1 ⁿ 0 ^m | m ≥ n > 0}

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

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

Для каждого языка:

1. Указать цепочку длины, большей 3, принадлежащую этому языку.

2. Описать Q -грамматику, порождающую данный язык.

3. Определить для каждого нетерминала, стоящего в левой части -правила, множество СЛЕД.

4. Построить управляющую таблицу МП-автомата, определив

   • множества входных и магазинных символов,

   • правила переходов и выходов.

5. Показать последовательность конфигураций построенного автомата при распознавании указанной цепочки.

Задание 3.

Для следующей грамматики (с начальным нетерминалом <S>) построить управляющую таблицу МП-автомата, который распознает сверху вниз порождаемый грамматикой язык:

<S> → a <A> b <B> b <S>

<S> → 

<A> → a <B><C>

<A> → b <A>

<B> → a <B>

<B> → 

<C> → c <c>

<C> → 

Изобразить в виде последовательности конфигураций, как автомат, соответствующий этой грамматике, распознает цепочки: aaabab, aabbaabb.

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

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

1. Определить для каждого нетерминала, стоящего в левой части -правила, множество СЛЕД.

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

3. Построить управляющую таблицу МП-автомата, определив

   • множества входных и магазинных символов,

   • правила переходов и выходов для Q-грамматики.

4. Показать последовательность конфигураций построенного автомата при распознавании цепочек: aaabab, aabbaabb.

Тема. Алгоритмы синтаксического анализа для LL(k)-грамматик.

Определение LL(k)-грамматики. Алгоритм разбора для LL(1)-грамматик. Метод рекурсивного спуска.