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

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

Задания

• 1. Преобразование грамматики к нормальной форме Хомского.

  2. Срок: до 22.10.2014

  3. Табличный LL(1) анализатор.

  4. Срок: 15.11.2014

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

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

Реализовать программу, осуществляющую преобразование КС-грамматики к нормальной форме Хомского.

Формат вызова:

a.exe {файл с описанием грамматики}

Формат файла с описанием грамматики:

N₁ -> a₁₁ a₁₂ ... a_1N1

N₂ -> a₂₁ a₂₂ ... a_2N2

...

N_m -> a_m1 a_m2 ... a_mNm

где

• Ni - нетерминальные символы (слова, начинающимися с заглавной латинской буквы).

• N1 - стартовый символ - первый нетерминал в файле.

• Количество символов в правой части соответствующего правила (N1, N2, ..., Nm) может быть равно 0 (эпсилон-цепочка).

• Терминальные символы (строчные латинские буквы, десятичные цифры, знаки препинания, различные скобки)

• aij - нетерминальные или терминальные символы.

_{Формат выдачи:}

КС-грамматика в НФХ, описывающая тот же язык:

• Если пустая цепочка принадлежит языку, добавить эпсилон правило для стартового нетерминала. Стартовый нетерминал в этом случае не должен встречаться в правых частях других правил.

• Если в результате преобразования грамматики нетерминал описывает тот же язык, то он должен сохранить имя, если язык изменяется, то нетерминал следует переименовать.

• Стартовый нетерминал - нетерминал в левой части первого правила.

• Остальные правила упорядочены лексикографически.

• В случае невозможности преобразования грамматики к НФХ (например, при удалении стартового символа), вывести FAIL

• Программа должна завершаться корректно с не пустым выводом!

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

Реализовать программу, осуществляющую построение табличного сильного LL(1) анализатора и моделирование его работы.

Формат вызова:

a.exe {файл с описанием грамматики} {файл входной цепочки}

Формат файла с описанием грамматики:

N₁ -> a₁₁ a₁₂ ... a_1N1

N₂ -> a₂₁ a₂₂ ... a_2N2

...

N_m -> a_m1 a_m2 ... a_mNm

где

• • Ni - нетерминальные символы (слова, начинающимися с заглавной латинской буквы).

• N1 - стартовый символ - первый нетерминал в файле.

• Количество символов в правой части соответствующего правила (N1, N2, ..., Nm) может быть равно 0 (эпсилон-цепочка).

• Терминальные символы

  • строчные латинские буквы, десятичные цифры, знаки препинания, математические операторы, различные скобки

  • '\ ' - пробел, '\n' - перенос строки, '\\' - обратный слэш

• aij - нетерминальные или терминальные символы.

Формат файла входной цепочки:

_{{ASCII символы}}

_{Пустые строки, пробелы и прочие невидимые символы игнорируются.}

_{Формат выдачи:}

_{В случае успешного завершения левый анализ цепочки (включая терминальные символы):}

_{N1 ai1 ai2 ai3 ... aik OK}

_{В случае обнаружения ошибки при распознавании, магазин анализа, соответствующий левому анализу максимального корректного префикса:}

N₁ a_i1 a_i2 a_i3 ... a_ik FAIL

_{В случае невозможности построения однозначного LL(1) анализатора (грамматика не является LL(1)-грамматикой):}

FAIL

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

Реализовать программу, осуществляющую построение детерминированного LR(0) автомата.

Формат вызова:

a.exe {файл с описанием грамматики}

Формат файла с описанием грамматики:

Аналогично заданию LL(1). Возможно явное наличие правила пополненной грамматики:

S -> N₁ #

_{Формат выдачи:}

_{В случае успешного завершения .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

    • тесты для задания