/context-free-grammar-parser

Парсер контекстно свободной грамматики. Определяет принадлежность слова данной контекстно-свободной грамматике

Primary LanguagePython

Парсер контекстно-свободной грамматики

Аргументы

  • --grammar_file название файла с описанием правил контекстно-свободной грамматики (подробнее ниже)
  • --word_file файл со словом для проверки принадлежности языку
  • --word слово, заданное явно
  • --max_length если указан этот параметр, то скрипт генерирует и выводил на экран все слова из языка длины не более указанной. Дополнительно обязан быть только --grammar_file, остальные будут игнорироваться

Если не указан --max_length, то должны быть --word или --word_file, тогда ответом будет принадлежность указанного слова языку

Примеры использования

  • Проверяет, подходит ли слово aababb под грамматику из второго примера. Выведет, что подходит. python3 main.py --grammar_file examples/grammar2.txt --word aababb
  • Вывести все слова из первой грамматики из примера длины не более 3 python3 main.py --grammar_file examples/grammar1.txt --max_length 3
  • Пример вывода, когда слово не принадлежит грамматике python3 main.py --grammar_file examples/grammar3.txt --word 004

Алгоритм

Используется Алгоритм Эрли

Грамматика

Состоит из следующих элементов:

  1. Алфавита
  2. Набора правил
  3. Списка нетерминалов
  4. Начального нетерминала

Можно задать с помощью файла со следующими соглашениями:

  • Пробел это разделительный символ, в алфавите встречаться не может, ставится для читаемости, можно пропускать в правилах
  • Каждая строчка отражает правило
  • Первый нетерминал в списке будет считаться начальным (то есть тот, который раскрывается в первом правиле)

Каждое правило имеет вид: RULE -> abcd OTHER_RULE efg. Здесь RULE - название нетерминала, abcd efg - набор символов из алфавита

  • Нетерминал это любое количество подряд записанных заглавных букв и символ нижнего подчеркивания _, например FLOAT_NUMBER
  • ___ запрещено использовать в качестве нетерминала, так как это зарезервированный символ
  • Знак стрелочки отделяет левую часть от правой ->
  • EPSILON задается зарезервированным символом $
  • Правые части могут быть перечислены через вертикальную черту |. Пример S -> (S)|a

Примеры грамматик, задаваемых файлом

  • Правильные скобочные последовательности

    S->(S)S|$

  • Слово вида (a^n) (b^n), где n > 0

    A -> a A b | ab

  • Смотрите в папке examples

Соглашения по неймингу в коде

  • term - обычный терминал, то есть сивол из алфавита
  • nterm - нетерминал

Запуск тестов

python3 -m pytest tests

Проверка покрытия (97%)

pytest --cov-config=tests/.coveragerc --cov=. tests/

Лицензия

Данная работа является практикумом по предмету Формальные языки и трансляции (второй практикум), направление ПМИ, 2 курс МФТИ.