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

Новости

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

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

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) анализатора (сильного или полного) и моделирование его работы.

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

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

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

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

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

...

N_m -> a_m1 a_m2 ... a_mNm

где

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

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

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

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

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

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

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

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

N₁ a_i1 a_i2 a_i3 ... a_ik 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
тесты для задания