рекурсивный логический и/или массивный анализатор jison

Question

Я исключительно новичок в jison и сумел собрать полезный парсер запросов. Я сейчас пытаюсь создать анализатор, который можно разобрать строку типа «A == 1 и Ь == 1 и С == 1» в объект, как

{and: [ 
    {a: {eq: 1}}, 
    {b: {eq: 1}}, 
    {c: {eq: 2}} 
]} 

в то время как строка вроде «== 1 или в == 1 и с == 1" следует разобрать в объект как

{or: [ 
    {a: {eq: 1}}, 
    {and: [ 
    {b: {eq: 1}}, 
    {c: {eq: 1}} 
    ]} 
]} 

Моя грамматика выглядит так до сих пор:

%lex 

%% 
\s+  /*skip whitespace*/ 
\"(\\.|[^"])*\"   yytext = yytext.substr(1, yyleng-2); return 'STRING'; 
"=="      return '=='; 
and[^\w]     return 'and'; 
or[^\w]     return 'or'; 
[0-9]+(?:\.[0-9]+)?\b return 'NUMBER'; 
[a-zA-Z][\.a-zA-Z0-9_]* return 'SYMBOL'; 
<<EOF>>     return 'EOF'; 

/lex 

%left 'or' 
%left 'and' 
%left '==' 

%start expressions 

%% 

expressions 
    : e EOF 
    {$$ = $1;} 
    ; 

e 
    : property '==' value 
    { $$ = {}; $[$1] = {eq: $3}; } 
    | boolAnd 
    { $$ = {and: $1}} 
    | boolOr 
    { $$ = {or: $1}} 
    ; 

boolAnd 
    : boolAnd 'and' e 
    {$$ = $1; $1.push($3);} 
    | e 'and' e 
    {$$ = [$1, $3];} 
    ; 

boolOr 
    : boolOr 'or' e 
    {$$ = $1; $1.push($3);} 
    | e 'or' e 
    {$$ = [$1, $3];} 
    ; 

property 
    : SYMBOL 
    {$$ = $1;} 
    ; 

value 
    : NUMBER 
    {$$ = Number(yytext);} 
    | STRING 
    {$$ = yytext; } 
    ; 

и это дает мне следующие ошибки конфликта:

Conflict in grammar: multiple actions possible when lookahead token is and in state 4 
- reduce by rule: e -> boolAnd 
- shift token (then go to state 11) 
Conflict in grammar: multiple actions possible when lookahead token is or in state 5 
- reduce by rule: e -> boolOr 
- shift token (then go to state 12) 

States with conflicts: 
State 4 
    e -> boolAnd . #lookaheads= EOF and or 
    boolAnd -> boolAnd .and e #lookaheads= EOF and or 
State 5 
    e -> boolOr . #lookaheads= EOF and or 
    boolOr -> boolOr .or e #lookaheads= EOF or and 

Может ли кто-нибудь предложить предложение о том, что я делаю неправильно? Большое спасибо

Answer 1

С

e : boolAnd 

невозможно решить между:

boolAnd: e 'and' e 
     | boolAnd 'and' e 

что и jison жалуется. (И стоит отметить, что уменьшение boolAnd до e не похоже на то, что вы хотите. Это действительно ошибка типа, или если бы у JS были типы.)

Лично я просто использовал бинарные деревья; по моему опыту, с ними легче работать. Вы можете сделать это легко с помощью отдельных объявлений без терминалов и приоритетов.

%left 'or' 
%left 'and' 
%% 
e 
    : property '==' value 
    { $$ = {eq: [$1, $3]}; /* This seems better to me. YMMV. } 
    | e 'and' e 
    { $$ = {and: [$1, $3]}} 
    | e 'or' e 
    { $$ = {or: [$1, $3]}} 
    | '(' e ')' 
    { $$ = $2 /* You didn't have this one, but it seems useful */ } 
    ; 

Это можно сделать грамматику, которая будет обрабатывать VARIADIC операторов (то есть. Уменьшить x OP y OP z к {OP: [x, y, z]}), но это на самом деле совсем немного работы, чтобы получить это право, и это легко не уступает решение, основанное по объявлениям приоритетов. Если вы действительно не хотите различать x OP y OP z и x OP (y OP z), что необязательно в случае логических операторов, обычно проще и более общим свернуть несколько подобных двоичных операторов во втором проходе над деревом синтаксического анализа или непосредственно при создании двоичного узла , изучая типы операторов дочерних выражений.