Специализни шаблонца! (udpn) wrote,
Специализни шаблонца!
udpn

Вопрос про расширяемые парсеры

Под расширяемостью я буду подразумевать, что

  1. мы можем новую грамматику построить из старой, используя некоторый набор конструкций,

  2. множество генерируемых (или принимаемых) строк новой грамматики включает в себя множество генерируемых строк старой,

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

Есть, допустим, у нас следующая грамматика (псевдокод):
g1 {
    r1 = r2*
    r2 = "a" | "b"
}
Мы хотим создать новую грамматику, используя дополнение по оператору выбора
g2 extends g1 {
    r2 = ... | "c"
}
Очевидно, g2 расширяет g1, потому что она так же принимает все строки из а и b, но теперь ещё и позволяет c.
Однако, дополнение по оператору выбора позволяет сделать и следующее:
g3 extends g1 {
    r2 = ... | "ab"
}
Теперь п.3 не исполняется, потому что вместо отдельных совпадений с "a" и "b" мы получаем совпадение с "ab".

Какой именно язык позволяет описывать изменения грамматики, чтобы расширяемость поддерживалась автоматически? Если такую проверку нельзя произвести синтаксически (чтобы нарушить расширяемость нельзя было по построению), то какие формальные методы позволяют проводить проверки подобного вида?

Edit. Для PEG и CFG автоматическая проверка расширяемости для произвольных изменений, как я понимаю, неразрешима, поскольку для этого необходимо проверять пустоту пересечения множеств строк, генерируемых аргументами оператора выбора. Собственно, поэтому про альтернативные способы и спрашиваю.
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments