Осень 2014‎ > ‎

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

UPD: сдача задач через http://hwproj.herokuapp.com/courses/4

Задания

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

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

Реализовать программу, осуществляющую преобразование КС-грамматики к нормальной форме Хомского.
Формат вызова:
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 (эпсилон-цепочка).
  • Терминальные символы 
    • строчные латинские буквы, десятичные цифры, знаки препинания, математические операторы, различные скобки
    • '\ ' - пробел, '\n' - перенос строки, '\\' - обратный слэш
  • aij - нетерминальные или терминальные символы.
Формат файла входной цепочки:
{ASCII символы}
Пустые строки, пробелы и прочие невидимые символы игнорируются. 

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

Graphviz LR(0) автомата

Реализовать программу, осуществляющую построение детерминированного LR(0) автомата.
Формат вызова:
a.exe {файл с описанием грамматики}
Формат файла с описанием грамматики:
Аналогично заданию LL(1). Возможно явное наличие правила пополненной грамматики:
S -> N1 # 
Формат выдачи:
В случае успешного завершения .dot файл содержащий описание детерминированного LR(0) автомата:
Формат вывода:
digraph G {
  rankdir=LR;
  <nodes>
  <edges>
}
Где узлы:
node_9 [label="E -> E&bull;-T\nT -> (E&bull;)"];
Ребра:
node_9 -> node_7 [label="-"];
  • Узлы именуются как "node_<номер>".
  • Номер стартового множества допустимых ситуаций - 1, далее нумерация произвольно последовательная (2...n).
  • Узлы и рёбра упорядочены по номерам.
  • Метки узлов и рёбер - см. пример. 
  • Порядок перечисления ситуаций в множестве ситуаций соответствует порядку правил в исходной грамматике.
  • Автомат строится для грамматики на входе, вне зависимости от наличия правила пополненной грамматики. Т.е. строить дополненную грамматику не нужно. 
  • Терминальный символ '#' является допустимым.
В случае невозможности построения детерминированного LR(0) автомата:
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
      • для F# - программа в одном .fs файле. 
      • для C/C++ - *.c или *.cpp. Будут компилироваться gcc:  gcc -I. -Wall
    • тесты для задания
Ċ
Victor Polozov,
23 сент. 2014 г., 23:02
Ċ
Victor Polozov,
23 сент. 2014 г., 23:02
Ċ
Victor Polozov,
30 сент. 2014 г., 22:41
Ċ
Victor Polozov,
1 окт. 2014 г., 1:51
Ċ
Victor Polozov,
8 окт. 2014 г., 2:01
Ċ
Victor Polozov,
22 окт. 2014 г., 1:51
Ċ
Victor Polozov,
22 окт. 2014 г., 1:51
Ċ
Victor Polozov,
5 нояб. 2014 г., 1:51
Ċ
Victor Polozov,
5 нояб. 2014 г., 1:50
Ċ
Victor Polozov,
16 янв. 2015 г., 4:10
Ċ
Victor Polozov,
16 янв. 2015 г., 4:10
Ċ
Victor Polozov,
16 янв. 2015 г., 4:10
Ċ
Victor Polozov,
16 янв. 2015 г., 4:10
ċ
ll1_sample.zip
(1k)
Victor Polozov,
14 окт. 2014 г., 23:16
ċ
lr0_sample.zip
(1k)
Victor Polozov,
16 дек. 2014 г., 23:39
ċ
ncf_sample.7z
(0k)
Victor Polozov,
8 окт. 2014 г., 0:28
ċ
parsc.hs
(2k)
Victor Polozov,
16 янв. 2015 г., 4:08
Ċ
Victor Polozov,
17 дек. 2014 г., 0:01
Comments