Задания

• Задание по регулярным языкам и конечным автоматам [pdf]
• Задание по КС-языкам и магазинным автоматам [pdf]

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

Заача на LL

---

На последнем семинаре мы не успели разобраться с задачей на LL (задача №3 из первого варианта контрольной из предыдущего поста). Во-первых, никакого обмана трудящихся не произошло — мы всё делали правильно, только алгоритм удаления левой рекурсии нас не спас. Это тот случай, когда он не работает. Вообще говоря, не любая грамматика после удаления левой рекурсии и после левой факторизации становится LL(1)-грамматикой, поэтому ничего особенного в этом нет, хотя случай и удивительный.

Проблема решается следующим образом: заметим, что правило вида $A \to Ac\,|\,\varepsilon$ приписывают сколько угодно букв $c$ справа от нетерминала $A$, поэтому добавим в грамматику нетерминал $H$ с правилами $H \to cH\,|\,\varepsilon$, удалим правило $A \to Ac$ и заменим все правила вида $ X \to \alpha A \beta$, где $X \neq A$ на $ X \to \alpha AH \beta$.

Отмена занятия

---

Занятие 15-го апреля не состоится. Последний семинар состоится 22-го апреля, после него ожидаются только контрольные и обратная связь по контрольным. 

LR-конструктор

---

Мы подошли к практической части нашего курса, почти всё что было до построения анализаторов покрывалось книгой  Хопкрофта, Мотвани и Ульмана. Я рекомендую изучать алгоритмы построения анализаторов по книжке Серебрякова и по Dragon Book (Ахо, Сети, Ульман). В последней они описаны более подробно. Почему это всё работает, написано в книжке Ахо и Ульмана, но её очень сложно понять и расстояние между двумя нужными для понимания утверждениями порой достигает 100 страниц. В теории к заданиям я попытаюсь пролить свет на некоторые вещи, но это довольно трудно, и не факт что получится. Про LR-анализаторы так же написано в книжке Шеня, там есть хороший шанс понять что происходит.

 

Для проверки и более наглядного изучения есть конструктор анализаторов.  По умолчанию все нетерминалы — заглавные буквы, все терминалы — строчные. Правила записываются в виде "A -> a|B". Каждое правило, быть может с разделителями, начинается с новой строки. Пустое слово = e.

 

Если запускать программу под IE, то можно, при некоторой удаче, увидеть дерево разбора анализируемого слова. Под остальными браузерами придётся включать воображение и соединять точки.

Контрольная

---

На ближайшем семинаре будет контрольная по регулярным языкам. Она будет длиться порядка 20-30 минут, пользоваться можно любыми бумажными материалами. Задачи будут простые, но содержательные.