Вопросы Теги

Разобрать AST < O (exp (n ))?

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

На мой взгляд, распарсинг означает создание потока токенов из AST, который при повторном анализе создает такой же AST.

Таким образом, выполняется parse(unparse(AST)) = AST.

Это равнозначно поиску допустимого дерева синтаксического анализа, которое выдаст тот же AST.

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

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

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

Вопросы

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

Пример 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"]и я знаю, что корень может быть Area, я мог бы разрешить его как

Area    -> Highway  -> Car

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

Пример 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

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

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

11
задан Stefan K. 16 August 2012 в 23:58
поделиться