Jison:为AND和OR生成具有多个子节点的AST节点

Question

我正在JavaScript中生成一个简单的SQL到Mongo查询标准。我正在使用Jison来解析SQL的where子句。

下面的语法返回一个二叉树形式的AST，其中or和and是嵌套的。我想要的是获得一个AST，其中OR节点具有单个节点(平坦树)中的所有项。

/* lexical grammar */
/* http://stackoverflow.com/questions/8467150/how-to-get-abstract-syntax-tree-ast-out-of-jison-parser */
%lex
%%
s+                   /* skip whitespace */
[0-9]+("."[0-9]+)?b                return 'NUMBER'
'AND'                 return 'AND'
'OR'                  return 'OR'
'NOT'                 return 'NOT'
'BETWEEN'             return 'BETWEEN'
L?"(\.|[^\"])*"                    return 'STRING_LITERAL'
'('                   return 'LPAREN'
')'                   return 'RPAREN'
'!='                  return 'NEQ'
'>='                  return 'GE'
'<='                  return 'LE'
'='                   return 'EQ'
'>'                   return 'GT'
'<'                   return 'LT'
'IN'                  return 'IN'
'NIN'                 return 'NIN'
'+'                   return 'PLUS'
'-'                   return 'MINUS'
','                   return 'COMMA'
[_a-zA-Z][_.a-zA-Z0-9]{0,30}            return 'IDEN'
<<EOF>>               return 'EOF'
.                     return 'INVALID'
/lex
%left OR
%left AND
%right NOT
%left NEQ EQ
%left GT LE LT GE
$left PLUS MINUS
%start start
%% /* language grammar */
start
    :  search_condition EOF
        {return $1;}
    ;
search_condition
    : search_condition OR boolean_term
        {$$ = {
            'or': [ $1, $3 ]
            };
        }
    | boolean_term
    ;
boolean_term
    : boolean_factor
    | boolean_term AND boolean_factor
        {$$ = {
            'and': [ $1, $3 ]
            };
        }
    ;
boolean_factor
    : boolean_test
    ;
boolean_test
    : boolean_primary
    ;
boolean_primary
    : predicate
    | LPAREN search_condition RPAREN
        {$$ = $2}
    ;
predicate
    : comparison_predicate
    | in_predicate
    | nin_predicate
    | between_predicate
    ;
comparison_predicate
    : IDEN comp_op value_expression
        {$$ = {
            var: $1,
            op: $2,
            val: $3
            };
        }
    ;
value_expression
    : NUMBER
    | STRING_LITERAL
    ;
comp_op
    : EQ
    | NEQ
    | GT
    | GE
    | LT
    | LE
    ;
in_predicate
    : IDEN IN in_predicate_value
    {$$ = {
            in: $3
            };
        }
    ;
nin_predicate
    : IDEN NIN in_predicate_value
    {$$ = {
            nin: $3
            };
        }
    ;
in_predicate_value
    : LPAREN in_value_list RPAREN
    {$$ = [$2];}
    ;
in_value_list
    : in_value_list_element
        {$$ = []; $$.push($1); }
    | in_value_list COMMA in_value_list_element
        {$1.push($3); $$ = $1; }
    ;
in_value_list_element
    : value_expression
        {$$ = $1;}
    ;
between_predicate
    : IDEN BETWEEN value_expression AND value_expression
    {$$ = {
            between: {
                from: $3,
                to: $5
            }
            };
        }
    ;

当我解析下面的

时

var ast = parser.parse('a=1 OR b=2 OR c=3 OR d=4 ');

返回

{
  "or": [
    {
      "or": [
        {
          "or": [
            {
              "var": "a",
              "op": "=",
              "val": "1"
            },
            {
              "var": "b",
              "op": "=",
              "val": "2"
            }
          ]
        },
        {
          "var": "c",
          "op": "=",
          "val": "3"
        }
      ]
    },
    {
      "var": "d",
      "op": "=",
      "val": "4"
    }
  ]
}

但是我想让它返回

{
  "or": [
    {
      "var": "a",
      "op": "=",
      "val": "1"
    },
    {
      "var": "b",
      "op": "=",
      "val": "2"
    },
    {
      "var": "c",
      "op": "=",
      "val": "3"
    },
    {
      "var": "d",
      "op": "=",
      "val": "4"
    }
  ]
}

是否可以使用Jison?如果是这样，需要做哪些改变?

Answer 1

你只需要修复动作。

首先，按如下方式更改search_condition规则中的操作:

search_condition
    : search_condition OR boolean_term
        { $1['or'].push($3); $$ = $1; }
    | boolean_term
        { $$ = { 'or': [ $1 ] }; }
    ;

这确保search_condition总是产生or节点，即使该节点只包含一个元素。由于基本生产创建了一个(单一的)or节点，所以递归生产可以自由地附加到它上面。

如果您想摆脱退化的or节点(在search_condition不包含OR操作符的情况下)，您可以在包装器中这样做(或直接在开始生产中):

start
    :  simplified_search_condition EOF
       { return $1; }
    ;
simplified_search_condition
    :  search_condition EOF
       { $$ = $1['or'].length == 1 ? $1['or'] : $1; }
    ;