Проблема с пустыми узлами синтаксического дерева в примере с Spirit Qi MiniC

Question

Проблема с пустыми узлами синтаксического дерева в примере с Spirit Qi MiniC

Уважаемые эксперты Spirit Qi.

Я поиграл с примером MiniC в Spirit Qi и заметил проблему с "пустыми" узлами AST в грамматике выражения. Он будет генерировать узлы "выражения", которые снова содержат только один операнд типа "выражение".

Я думаю, что проблема связана с рекурсивными определениями правил для приоритета оператора:

// expression.hpp
    qi::rule<Iterator, ast::expression(), skipper<Iterator> >
        expr, equality_expr, relational_expr,
        logical_or_expr, logical_and_expr,
        additive_expr, multiplicative_expr
        ;

// expression_def.hpp
    expr =
        logical_or_expr.alias()
        ;

    logical_or_expr =
            logical_and_expr
        >> *(logical_or_op > logical_and_expr)
        ;

    logical_and_expr =
            equality_expr
        >> *(logical_and_op > equality_expr)
        ;

// ast.hpp

typedef boost::variant<
        nil
      , bool
      , unsigned int
      , identifier
      , boost::recursive_wrapper<unary>
      , boost::recursive_wrapper<function_call>
      , boost::recursive_wrapper<expression>
    >
operand;
/*...*/
struct expression
{
    operand first;
    std::list<operation> rest;
};

Когда логический_ори_экспресс возвращается в логический_и_экспресс, логический_и_экспресс возвращает выражение (). Из-за атрибута распространения является Spirit, затем logic_or_expr назначает это выражение "первому" члену его выражения.

Я думаю, что именно это генерирует все эти "пустые" узлы выражения. Я нахожу это, однако, противным и хотел бы избавиться от них, но пока не добился успеха. Кто-нибудь нашел достойное решение для этого раньше?

Я думаю, что это было бы как-то возможно, если бы выражение состояло из двоичных операций и унарных операций. В этом случае также будет иметь преимущество сохранение операции и операндов в одной структуре (псевдокод):

struct binary_op
{
    optype type;
    operand op1;
    operand op2;
}

struct unary_op
{
    optype type;
    operand op1;
}

struct eval_op
{
    operand op1;
}

typedef boost::variant<binary_op,
                       unary_op,
                       eval_op>
expression;

typedef boost::variant<int,
                       bool,
                       boost::recursive_wrapper<expression> >
operand;

Тем не менее, я полагаю, что все еще столкнулся бы с этой проблемой "пустых узлов" после того, как разыграл ее на бумаге. Кажется, я гоняюсь за собственным хвостом.

У кого-нибудь есть идеи как подойти к этому вопросу?

РЕДАКТИРОВАТЬ

a > b

Будем разбирать на:

    expression (from logical_or_op) // Empty expression (forward only)
(rest)  -/  \- (first) expression (from logical_and_op) // Empty expression (forward only)
            (rest)  -/  \- (first) expression (from equality_op) // Empty expression (forward only)
                    (rest)  -/ \- (first) expression (from relational_op) // "Correct" expression
                            (first) a   -/      \- (rest)
                                                    [0] operator_: op_greater
                                                        operand_: b

Желаемый результат будет:

            expression (from relational_op)
(first) a   -/      \- (rest)
                        [0] operator_: op_greater
                            operand_: b

EDIT2

Я загрузил модифицированную версию mini-c, которая печатает сгенерированное дерево выражений для выражения:

Ссылка на сайт

Если вы посмотрите на включенный файл A.avxh, он содержит выражение для разбора. Установите точку останова в main.cpp в строке 67 и наблюдайте, как часто она туда входит.

3

c++ parsing expression boost-spirit boost-spirit-qi

Источник

user1641845 31 окт '13 в 13:02

1 ответ

Решение

Другие вопросы по тегам c++ parsing expression boost-spirit boost-spirit-qi

user85371 31 окт '13 в 19:29 2013-10-31 19:29 · Accepted Answer · 2013-10-31 19:29

Это потому что все правила выставляют "сырые" ast::expression и это фиксированный тип.

В данном примере это был выбор простоты:

Делая все узлы выражений одного типа, код посещения дерева может быть простым и единообразным.
Все правила имеют одинаковую "подпись" и следуют одному и тому же шаблону. Это легко рассуждать.
В этом конкретном примере (mini_c) фаза кода поколения выигрывает от наследования той же простоты.

Обычный способ иметь более гибкий AST, который более точно следует семантике, - это сделать expression вариант вместо этого: таким образом, каждое выражение может напрямую содержать фактический "конкретный" тип подвыражения вместо "пробираться" через промежуточные уровни типов узлов, просто чтобы имитировать структуру грамматики вместо семантики.

Я думаю, что у меня есть несколько примеров таких предложений и соответствующих грамматик на этом сайте, посмотрим, смогу ли я связать один позже.
^{На самом деле, я думаю, что} typedef variant<...> statement ^{в том же примере (} ast.hpp ^{) не плохой пример такого подхода.}
Соответствующие ссылки:
Boost:: анализатор выражений духа
Boost::spirit, как анализировать и вызывать функциональные выражения на языке C++, на этот вопрос я ответил, предоставив полнофункциональный синтаксический анализатор выражений (с вычислением "встроенной функции"), двумя способами:
Подход "наворотов" с полным AST (напоминает то, что мы делаем здесь с примерами выражений mini_c)
"Прагматичный" подход, который оценивает на лету, используя только семантические действия - обратите внимание, что это оптимально для хранения, но имеет некоторые недостатки, о которых я расскажу в этом посте

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

Я собираюсь посмотреть, что я могу придумать в следующий час.

Я только что переработал грамматику, чтобы она не привела к такой глубокой вложенности.

Во-первых, давайте сократим тест до отдельного тестового стенда, который просто анализирует выражения и показывает, как простое выражение ("42") разбирает глубоко вложенный AST: http://coliru.stacked-crooked.com/a/5467ca41b0ac1d03
```
<expr>
  ...
  <success></success>
  <attributes>[[[[[[[42, []], []], []], []], []], []]]</attributes>
</expr>
```
Далее, давайте удалим корневую проблему: грамматика возвращает инвариантный тип (ast::expression) который является слишком тяжелым во многих случаях. Вместо этого мы хотели бы вернуть ast::operand (который является вариантом, и может содержать то же самое ast::expression узел): http://coliru.stacked-crooked.com/a/00e43b1f61db018c
Наконец, мы бы хотели, чтобы все правила также стали вариантами и возвращали либо expression если есть трейлинг-операции, или просто одинокий operand в другом случае в псевдокоде:
```
logical_or_expr = 
      (logical_and_expr >> +(logical_or_op > logical_and_expr)
    | logical_and_expr
    ;
```
_{Обратите внимание на тонкое использование, если} +(...) _вместо *(...) _{поручить хотя бы одну завершающую операцию logic_or}
Теперь Духу нужно будет рассказать, как назначить первую ветку operand приписывать. qi::attr_cast<ast::expression>(...) должно было быть здесь, но, к сожалению, я столкнулся с неопределенным поведением (это заняло больше всего времени). Я остановился на более подробном решении:
```
_logical_or_expr = logical_and_expr    >> +(logical_or_op     > logical_and_expr) ;
logical_or_expr  = _logical_or_expr | logical_and_expr;
```
Как вы, вероятно, видите, это то же самое, но с первой веткой, извлеченной в отдельное правило, поэтому мы можем просто объявить правила, чтобы предоставить нужные атрибуты:
```
qi::rule<It, ast::operand(),    Skipper> logical_or_expr;
qi::rule<It, ast::expression(), Skipper> _logical_or_expr;
```
Действительно, выполнение этого для каждого уровня приоритета подвыражений приводит к следующему:
```
_logical_or_expr     = logical_and_expr    >> +(logical_or_op     > logical_and_expr) ;
_multiplicative_expr = unary_expr          >> *(multiplicative_op > unary_expr) ;
_additive_expr       = multiplicative_expr >> +(additive_op       > multiplicative_expr) ;
_relational_expr     = additive_expr       >> +(relational_op     > additive_expr) ;
_equality_expr       = relational_expr     >> +(equality_op       > relational_expr) ;
_logical_and_expr    = equality_expr       >> +(logical_and_op    > equality_expr) ;

logical_or_expr     = _logical_or_expr     | logical_and_expr        ;
logical_and_expr    = _logical_and_expr    | equality_expr           ;
equality_expr       = _equality_expr       | relational_expr         ;
relational_expr     = _relational_expr     | additive_expr           ;
additive_expr       = _additive_expr       | multiplicative_expr     ;
multiplicative_expr = _multiplicative_expr | attr_cast<ast::operand, ast::operand> (unary_expr) ;
```

Конечный результат здесь: http://coliru.stacked-crooked.com/a/8539757bb02fca34 (к сожалению, это слишком много для Coliru), и он печатает:

<expr>
  ...
  </logical_or_expr>
  <success></success>
  <attributes>[[42, []]]</attributes>
</expr>

CAVEAT Обратите внимание, что эта адаптация НЕ сделает парсер более эффективным! Фактически, это просто приведет к большому количеству возвратов (результат отладки насчитывает 925 строк вместо 45 в шаге 1 (!!)).

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