非终端发生的JISON错误

Question

我正在为一个类编写一个JISON文件，并试图使用非终端来代替声明操作符的相联性，但是我完全不知道错误的真正含义是什么，因为这是一个类的一次赋值，而且我还没有找到在这个用例中使用非终端的惊人例子。

我的JISON代码：

/* lexical grammar */
%lex
%%

\s+                   /* skip whitespace */
[0-9]+("."[0-9]+)?\b  return 'NUMBER'
"*"                   return '*'
"/"                   return '/'
"-"                   return '-'
"+"                   return '+'
"^"                   return '^'
"!"                   return '!'
"%"                   return '%'
"("                   return '('
")"                   return ')'
"PI"                  return 'PI'
"E"                   return 'E'
<<EOF>>               return 'EOF'
.                     return 'INVALID'

/lex

%start expressions

%% /* language grammar */

expressions
   : e EOF
       { typeof console !== 'undefined' ? console.log($1) : print($1);
        return $1; }
    ;

e
    : NegExp
         {$$ = $1;}
    | MulExp
         {$$ = $1;}
    | PowExp
         {$$ = $1;}
    | UnaryExp
         {$$ = $1;}
    | RootExp
         {$$ = $1;}
    ;


RootExp
    : ’(’ RootExp ’)’
         {$$ = ’(’ + $2 + ’)’;}
| NUMBER
    {$$ = Number(yytext);}
| E
    {$$ = ’E’;}
| PI
    {$$ = ’PI’;}
;

UnaryExp
    : UnaryExp '!'
        {$$ = '(' + $1 + '!' + ')';}
    | UnaryExp '%'
        {$$ = '(' + $1 + '%' + ')';}
    | '-' UnaryExp
        {$$ = '(-' + $2 + ')';}
    ;

 NegExp
    : NegExp '+' e
        {$$ = '(' + $1 + ' + ' + $3 + ')';}
    | NegExp '-' e
        {$$ = '(' + $1 + ' - ' + $3 + ')';}
    ;

MulExp
    : MulExp '*' e
        {$$ = '(' + $1 + ' * ' + $3 + ')';}
    | MulExp '/' e
        {$$ = '(' + $1 + ' / ' + $3 + ')';}
    ;

PowExp
    : e '^' PowExp
        {$$ = '(' + $1 + ' ^ ' + $3 + ')';}
    ;

当我运行jison filename.jison时，会出现一系列错误，如：

Conflict in grammar: multiple actions possible when lookahead token is ^ in state 26
- reduce by rule: MulExp -> MulExp / e
- shift token (then go to state 13)

以及：

States with conflicts:
State 3
  e -> NegExp . #lookaheads= EOF ^ + - * /
  NegExp -> NegExp .+ e #lookaheads= EOF + - ^ / *
  NegExp -> NegExp .- e #lookaheads= EOF + - ^ / *

再说一遍，我并不是在找人帮我做家庭作业，但是我会非常感谢你给我指点该去哪里或做些什么来帮助调试。

Answer 1

这是真的；在不使用优先级声明的情况下，很难找到解决歧义的表达式语法示例。这可能是因为优先级声明(在这个特定的用例中)非常方便，而且可能比写出明确的语法更容易读。结果解析器通常也会稍微提高一些效率，因为它避免了通常的明确语法样式所造成的单元缩减链。

这种便利的另一面是，它不能帮助学生理解语法实际上是如何工作的，如果没有这种理解，就很难将优先级声明应用于不那么明确的应用程序。因此，提出这个问题的工作当然是值得的。

您可以在(某些)编程语言的规范中找到明确的表达式语法，因为明确的语法并不取决于解析器生成器用于解决解析冲突的算法的精确性质。然而，这些例子往往相当复杂，因为真正的编程语言通常有很多运算符。尽管如此，示例jison示例目录中的C语法确实显示了算术表达式语法的标准模型。下面的摘录是大大简化的，但大多数产品只是简单地复制和粘贴从原来.(我删除了许多操作符，大部分优先级别，以及一些处理诸如cast表达式和特殊逗号运算符的复杂操作，这些操作在这里肯定不相关。)

primary_expression
    : IDENTIFIER
    | CONSTANT
    | '(' expression ')'
    ;

postfix_expression
    : primary_expression
    | postfix_expression INC_OP
    | postfix_expression DEC_OP
    ;

unary_expression
    : postfix_expression
    | '-' unary_expression
    | INC_OP unary_expression
    | DEC_OP unary_expression
    ;

/* I added this for explanatory purposes. DO NOT USE IT. See the text. */
exponential_expression
    : unary_expression
    | unary_expression '^' exponential_expression    

multiplicative_expression
    : exponential_expression
    | multiplicative_expression '*' exponential_expression
    | multiplicative_expression '/' exponential_expression
    | multiplicative_expression '%' exponential_expression
    ;

additive_expression
    : multiplicative_expression
    | additive_expression '+' multiplicative_expression
    | additive_expression '-' multiplicative_expression
    ;

expression
    : additive_expression
    ;

C没有指数运算，所以我添加了一个具有正确结合性和比乘法更高优先级的运算，这将用于解释目的。但是，您的作业可能希望它比一元否定有更高的优先级，而我没有这样做。所以我不建议直接使用上面的内容。

在上面的模型中需要注意的一点是，每个优先级级别都对应于一个非终端。这些非终端被连接到一个有序链使用单位产品。我们可以看到这个序列：

表达载体( additive_expression multiplicative_expression⇒unary_expression⇒postfix_expression⇒primary_expression )

它对应于这个语法的优先顺序。

语法的另一个有趣方面是，左联想运算符(除指数运算外)都是用左递归乘积实现的，而右联想运算符则是用右递归乘积实现的。这不是巧合。

这是基本的模型，但值得花几分钟来了解它的实际工作原理，因为结果非常简单。让我们看一看乘法的一种乘积，看看我们是否能理解它为什么意味着指数结合得更紧密，加法结合得更少：

multiplicative_expression: multiplicative_expression '*' exponential_expression

这个产品是说，multiplicative_expression由左边有multiplicative_expression的*和右边的exponential_expression组成。

现在，这对2 + 3 * 4 ^ 2意味着什么？2 + 3是一个additive_expression，但是我们可以从单元产品链中看出multiplicative_expression并不生成additive_expression。因此，语法不包括2 + 3是*左侧匹配短语的可能性。然而，将3 ( CONSTANT，即primary_expression)解析为乘法的左操作数是完全合法的。

同时，4 ^ 2是一个exponential_expression，我们的产品清楚地表明exponential_expression可以在*的右边匹配。

一个类似的论点，检查加法和指数表达式的结果，将显示3 * 4 ^ 2 (一个multiplicative_expression)可以在+运算符的右边，而2 + 3 * 4 (一个additive_expression)和3 * 4 (一个multiplicative_expression)都不能在指数运算符的左边。

换句话说，这个简单的语法精确而明确地定义了表达式必须如何分解。只有一种可能的解析树：

        expression
             |
            add
             |
    +--------+----------------+
    |        |                |
    |        |              mult
    |        |                |
    |        |        +-------+---------------+
    |        |        |       |               |
    |        |        |       |             power
    |        |        |       |               |
    |        |        |       |       +-------+-------+ 
    |        |        |       |       |       |       |
   add       |      mult      |     unary     |     power
   ...       |       ...      |      ...      |      ...
    |        |        |       |       |       |       |
 primary     |     primary    |    primary    |    primary
    |        |        |       |       |       |       |
    2        +        3       *       4       ^       2

我希望这能有所帮助。