非终端出现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 examples目录中的示例C语法确实显示了算术表达式语法的标准模型。以下摘录已大大简化，但大多数作品都是从原始作品中复制粘贴而成。（我删除了许多运算符，大多数优先级以及一些复杂的操作，例如强制转换表达式和特有的逗号运算符，这些在这里肯定是不相关的。）

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没有指数运算符，因此我添加了一个具有正确关联性且比乘法优先级高的运算符，这将用于说明。但是，您的作业可能希望它也比一元否定具有更高的优先级，而我没有这样做。因此，我不建议直接使用以上内容。

在上述模型中要注意的一件事是，每个优先级都对应一个非终结符。这些非末端使用单元生产链接到有序链中。我们可以看到以下顺序：

表达？加法表达式？multiplicative_expression吗？exponential_expression吗？一元表达式？postfix_expression？primary_expression

这确实对应于该语法的优先顺序。

语法的另一个有趣方面是，左联想算子（除幂运算以外的所有算子）都是通过左递归生成实现的，而右联想算符是通过右递归生成实现的。这不是巧合。

这是基本模型，但是值得花几分钟尝试了解它的实际工作原理，因为事实证明它很简单。让我们看一下一个乘积，并进行乘法运算，看看是否可以理解为什么它意味着幂运算的绑定更紧密，加法的绑定更不紧密：

multiplicative_expression: multiplicative_expression '*' exponential_expression

该生产说a multiplicative_expression由*一个multiplicative_expression在左边和一个exponential_expression在右边的a 组成。

现在，这意味着2 + 3 * 4 ^ 2什么？2 + 3是一个additive_expression，但是从单位生产链上我们可以看出multiplicative_expression没有生产additive_expression。因此，语法不包括与2 + 3短语左侧匹配的短语的可能性*。但是，将3（a CONSTANT，即a primary_expression）解析为乘法的左操作数是完全合法的。

同时，4 ^ 2是exponential_expression，并且我们的生产明显表明exponential_expression可以在的右侧进行匹配*。

一个类似的论证，检查加法和指数表达式的产生，将显示3 * 4 ^ 2（a multiplicative_expression）可以在+运算符的右侧，而2 + 3 * 4（an additive_expression）和3 * 4（a multiplicative_expression）都不能在指数的左侧操作员。

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

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

我希望这会有所帮助。