Форум за въпроси

Проект - контекстно-свободни граматики, реализация

Проект - контекстно-свободни граматики, реализация

от Христо Вригазов -
Number of replies: 1

Здравейте,

Имам въпрос относно проекта "Контекстно-свободни граматики". В условието за проекта пише, че граматиката трябва вътрешно да се представи чрез недетерминиран стеков автомат. Виждаме обаче, че трябва да проверим дали дума принадлежи на езика на граматиката два пъти -

  • функция, която проверява дали дадена дума е в езика на дадена граматика (CYK алгоритъм)
  • проверка за принадлежност на дума към езика на граматиката

Предполагам, че в първия случай трябва да направим преобразуване на граматиката в нормална формална на Чомски (т.е ще трябва да представим граматиката като множество от правила), а във втория случай - да направим пълно изчерпване при представяне на граматиката като стеков автомат. Въпросът ми е - как да се придържаме към реализацията чрез недетерминиран стеков автомат, след като все пак за някои функции ще трябва да представим граматиката и като множество от правила? Може би трябва да направим две представяния - едно със стеков автомат и едно с множества от правила, но в такъв случай няма ли да е много по-организирано да отделим стековия автомат като отделен клас, като и стековия автомат, и КСГ да имплементират интерфейс за общите им методи?

Поздрави,
Христо

In reply to Христо Вригазов

Re: Проект - контекстно-свободни граматики, реализация

от Трифон Трифонов -

Здравей, Христо,

Благодаря ти за въпроса. Точката за CYK алгоритъма е останала погрешка, би трябвало да я няма, а проверката да се прави директно чрез стековия автомат. Доколкото разбрах, CYK алгоритъма сте го реализирали на упражнения по ЕАИ, така че няма смисъл да го правите пак по СДП.

Относно това дали ще решите стековият автомат да е в отделен клас и да има две представяния: това е въпрос на ваш избор.

Поздрави,
  Т. Трифонов