Архив‎ > ‎Осень 2013‎ > ‎

Теория автоматов и формальных языков, осень 2013

Новости

  • 01.12.2013 - выложены примеры работы для задачи 2.

Задания

  1. Преобразование грамматики к нормальной форме Хомского. 
    Срок: до 31.10.2013
  2. Табличный LL(1) анализатор.
    Срок: 30.11.2013

Преобразование грамматики к НФХ

Реализовать программу, осуществляющую преобразование КС-грамматики к нормальной форме Хомского.
Формат вызова:
a.exe {файл с описанием грамматики}
Формат файла с описанием грамматики:
N1 -> a11 a12 ... a1N1 
N2 -> a21 a22 ... a2N2 
...
Nm -> am1 am2 ... amNm 
где
  • Ni - нетерминальные символы (слова, начинающимися с заглавной латинской буквы).
  • N1 - стартовый символ - первый нетерминал в файле.
  • Количество символов в правой части соответствующего правила (N1, N2, ..., Nm) может быть равно 0 (эпсилон-цепочка).
  • Терминальные символы (строчные латинские буквы, десятичные цифры, знаки препинания, различные скобки)
  • aij - нетерминальные или терминальные символы.
Формат выдачи:
КС-грамматика в НФХ, описывающая тот же язык:
  • Если пустая цепочка принадлежит языку, добавить эпсилон правило для стартового нетерминала. Стартовый нетерминал в этом случае не должен встречаться в правых частях других правил.
  • Если в результате преобразования грамматики нетерминал описывает тот же язык, то он должен сохранить имя, если язык изменяется, то нетерминал следует переименовать.
  • Стартовый нетерминал - нетерминал в левой части первого правила.
  • Остальные правила упорядочены лексикографически.
  • В случае невозможности преобразования грамматики к НФХ (например, при удалении стартового символа), вывести FAIL

Построение табличного LL(1) анализатора

Реализовать программу, осуществляющую построение табличного LL(1) анализатора (сильного или полного) и моделирование его работы.
Формат вызова:
a.exe {файл с описанием грамматики{файл входной цепочки}
Формат файла с описанием грамматики:
N1 -> a11 a12 ... a1N1 
N2 -> a21 a22 ... a2N2 
...
Nm -> am1 am2 ... amNm 
где
  • Ni - нетерминальные символы (слова, начинающимися с заглавной латинской буквы).
  • N1 - стартовый символ - первый нетерминал в файле.
  • Количество символов в правой части соответствующего правила (N1, N2, ..., Nm) может быть равно 0 (эпсилон-цепочка).
  • Терминальные символы (строчные латинские буквы, десятичные цифры, знаки препинания, математические операторы, различные скобки)
  • aij - нетерминальные или терминальные символы.
Формат файла входной цепочки:
{ASCII символы}
Пробелы и прочие невидимые символы игнорируются. 

Формат выдачи:
В случае успешного завершения левый анализ цепочки (включая терминальные символы):
N1 ai1 ai2 ai3 ... aik OK
В случае обнаружения ошибки при распознавании, магазин анализа, соответствующий левому анализу максимально-корректного префикса:
N1 ai1 ai2 ai3 ... aik FAIL
В случае невозможности построения однозначного LL(1) анализатора (грамматика не является LL(1)-грамматикой):
FAIL

Требования к оформлению заданий

  • email на victorp@math.spbu.ru
  • префикс "[formlang]" в поле subject (+ задание или тема письма)
  • тело письма в соответствии с сетикетом: http://www.ietf.org/rfc/rfc1855.txt
  • в аттаче - архив с исходными кодами программ
  • в корне архива
    • для Java - build.xml, понимаемый инструментом Apache ant, порождающий в этой же папке запускающийся jar
    • для C# - все .cs файлы. Компляция - csc /out:a.exe *.cs
    • для C/C++ - *.c или *.cpp. Будут компилироваться gcc:  gcc -I. -Wall
  • тесты для задания
Ċ
Victor Polozov,
5 сент. 2013 г., 13:24
Ċ
Victor Polozov,
19 сент. 2013 г., 4:29
Ċ
Victor Polozov,
26 сент. 2013 г., 11:14
Ċ
Victor Polozov,
26 сент. 2013 г., 11:14
Ċ
Victor Polozov,
3 окт. 2013 г., 14:14
Ċ
Victor Polozov,
10 окт. 2013 г., 10:31
Ċ
Victor Polozov,
21 окт. 2013 г., 4:56
Ċ
Victor Polozov,
21 окт. 2013 г., 4:56
Ċ
Victor Polozov,
31 окт. 2013 г., 13:54
Ċ
Victor Polozov,
7 нояб. 2013 г., 11:52
Ċ
Victor Polozov,
5 дек. 2013 г., 3:13
Ċ
Victor Polozov,
12 дек. 2013 г., 3:34
Ċ
Victor Polozov,
5 дек. 2013 г., 3:13
Ċ
Victor Polozov,
12 дек. 2013 г., 3:36
ċ
lecture13_parsc_sample.zip
(2k)
Victor Polozov,
12 дек. 2013 г., 3:36
Ċ
Victor Polozov,
9 янв. 2014 г., 13:42
ċ
ll1_sample.zip
(1k)
Victor Polozov,
1 дек. 2013 г., 2:57
Ċ
Victor Polozov,
27 дек. 2013 г., 8:52
Comments