Unparse AST <O (exp (n))? - программирование

Описание абстрактной проблемы:

Как я вижу это, unparsing означает создание потока токенов из AST, который при анализе снова дает равный AST.

Итак, parse(unparse(AST)) = AST.

Это равнозначно нахождению правильного дерева синтаксического анализа, которое создавало бы тот же АСТ.

Язык описывается контекст бесплатно S-attributed, используя вариант eBNF.

Таким образом, unparser должен найти действительный "путь" через пройденные узлы, в которых сохраняются все ограничения грамматики. Это в основном означает найти правильное распределение узлов AST для правил грамматики. Это проблема ограничения ограничений (CSP) в целом и может быть решена, например, путем синтаксического анализа, backtracking в O (exp (n)).

К счастью для синтаксического анализа, это можно сделать в O (n³), используя GLR (или лучше ограничивая грамматику). Поскольку структура AST настолько близка к структуре правил создания грамматики, я был очень удивлен, увидев реализацию, где время выполнения хуже, чем синтаксический анализ: XText использует ANTLR для синтаксического анализа и обратного отсчета для unparsing.

Вопросы

Является ли свободная от контекста грамматика S-атрибутов всем парсером и unparser, необходимо разделить или есть дополнительные ограничения, например. о методе синтаксического анализа/реализации парсера?
У меня такое ощущение, что эта проблема не O (exp (n)) вообще - может ли какой-то гений помочь мне с этим?
Является ли это в основном контекстно-зависимой грамматикой?

Пример1:

Area    returns AnyObject   -> Pedestrian | Highway
Highway returns AnyObject   -> "Foo" Car
Pedestrian  returns AnyObject   -> "Bar" Bike
Car     returns Vehicle     -> anyObjectInstance.name="Car"
Bike    returns Vehicle     -> anyObjectInstance.name="Bike"

Итак, если у меня есть AST, содержащий

AnyObject -> AnyObject -> Vehicle [name="Car"] и я знаю, что root может быть Area, я мог бы разрешить его

Area    -> Highway  -> Car

Таким образом, решение (Highway | Pedestrian) зависит от решений поддерева. Проблема ухудшается, когда лист может быть, на первый взгляд, одним из нескольких типов, но должен быть конкретным, чтобы сформировать правильный путь позже.

Пример2:

Итак, если у меня есть правила S-атрибута, возвращающие неизученные объекты, просто назначая некоторые атрибуты, например.

A -> B C   {Obj, Obj}
X -> Y Z   {Obj, Obj}
B -> "somekeyword"  {0}
Y -> "otherkeyword" {0}
C -> "C" {C}
Z -> "Z" {Z}

Итак, если AST содержит

   Obj
  /  \
"0"  "C"

Я могу отследить его до

   A
  / \
 B   C

сразу после того, как я смог разрешить "C" на C.

При прохождении AST, все ограничения, которые я могу генерировать из грамматики, удовлетворяются для обоих правил, A и X, пока я не нажму "C". Это означает, что для

A -> B | C 
B -> "map"  {MagicNumber_42}
C -> "foreach" {MagicNumber_42}

оба решения для дерева

     Obj
      |
 MagicNumber_42

и считается, что они имеют равную семантику, например. синтаксический сахар.

Дополнительная информация:

Ответ 1