Создание выражений из этой грамматики с рекурсивным спуском - PullRequest
Новая
       34

Создание выражений из этой грамматики с рекурсивным спуском

0 голосов
/ 24 сентября 2010

У меня есть простая грамматика.На самом деле, грамматика, которую я использую, является более сложной, но это наименьшее подмножество, иллюстрирующее мой вопрос. 

Expr ::= Value Suffix
       | "(" Expr ")" Suffix

Suffix ::= "->" Expr
         | "<-" Expr
         | Expr
         | epsilon

Value соответствует идентификаторам, строкам, числам и так далее.Правило Suffix предназначено для устранения левой рекурсии.Это соответствует выражениям, таким как: 

a -> b (c -> (d) (e))

То есть график, где a обращается к b и результату (c -> (d) (e)), а c к d и e.Я пытаюсь создать абстрактное синтаксическое дерево для этих выражений, но я сталкиваюсь с трудностями, потому что все операторы могут принимать любое количество операндов на каждой стороне.Я бы предпочел сохранить логику для создания AST в методах синтаксического анализа рекурсивного спуска, так как это избавляет от необходимости дублировать логику извлечения выражения.Моя текущая стратегия такова:

  1. Если появляется Value, нажмите его на выходе.

  2. Если From илиTo Появится:

    1. Вывести разделитель.

    2. Получить следующее Expr.

    3. Создание узла Link.

    4. Вставка первого набора операндов с выхода в Link до появления разделителя.

    5. Сотрите обнаруженный разделитель.

    6. Вставьте второй набор операндов в Link до разделителя.

    7. Нажмите Linkк выводу.

Если я выполню это без выполнения шагов 2.3–2.7, я получу список значений и разделителей.Для приведенного выше выражения a -> b (c -> (d) (e)) результат должен быть следующим: 

A sep_1 B sep_2 C sep_3 D E

Применение правила To приведет к получению: 

A sep_1 B sep_2 (link from C to {D, E})

И впоследствии: 

(link from A to {B, (link from C to {D, E})})

Важно отметить, что sep_2, крайне важный для разграничения левых операндов второго ->, не появляется, поэтому синтаксический анализатор считает, что выражение действительно было записано: 

a -> (b c -> (d) (e))

Чтобы решить эту проблему с моей текущей стратегией, мне нужен способ создать разделитель между смежными выражениями, но только если текущее выражение является выражением From или To, заключенным в скобки.Если это возможно, то я просто не вижу этого, и ответ должен быть простым.Однако, если есть лучший способ сделать это, пожалуйста, дайте мне знать!

1 Ответ

1 голос
/ 24 сентября 2010

Я не пытался проанализировать его подробно, но: «From или To выражение , заключенное в скобки », начинает звучать очень похоже на «контекстно-зависимую», что может привести к рекурсивному спускуне справиться напрямую.Чтобы избежать зависимости от контекста, вам, вероятно, понадобится отдельная продукция для From или To в скобках против From или To без скобок.

Редактировать: Хотя это может быть слишкомпоздно делать что-то хорошее, если мое понимание того, что вы хотите сопоставить, верное, я думаю, что напишу это примерно так: 

Graph := 
       | List Sep Graph
       ;

Sep := "->"
     | "<-"
     ;

List :=
      | Value List
      ;

Value := Number 
      | Identifier 
      | String 
      | '(' Graph ')'
      ;

Трудно быть уверенным, но я думаю, что это должно быть вПо крайней мере, будьте близки к соответствию (только) нужным входам, и это должно позволить достаточно легко сгенерировать AST, который правильно отражает входные данные.

...