c - YACC:查找语法中的移位/减少冲突

Question

我正在看书theory of computation并且在第2章中有一种语言PL是在YACC中实现的。该程序非常基础。有指定的语法规则，运行程序后，它会检查给定文件是否具有指定语法的语法。所有的规则都在书中给出了，我想执行它。

但是当我实现它时，我得到了移位/减少冲突代码。网上查了一下错误，发现错误是指语法歧义。我试着找到它，但找不到。 in here有一个类似的问题，用户指出这是一个警告，可以忽略，因为某些语言是模棱两可的。

问题:

• 谁能指出可能存在歧义的地方？

• 当我尝试运行如下代码时，程序无法理解它。它给出了语法错误。尽管根据我应用的语法规则，这应该被接受。我传递的语法错误吗？

  while X = 10;
  X = Y + 10;
  end;
  

我的代码:

    %start program
    %%
    LETTER : 'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G' | 'H' | 'I'
          | 'J' | 'K' | 'L' | 'M' | 'N' | 'O' | 'P' | 'Q' | 'R'
          | 'S' | 'T' | 'U' | 'V' | 'W' | 'X' | 'Y' | 'Z' 
          ;

    DIGIT : '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
         ;

    name : LETTER
         | name DIGIT
         | name LETTER
         ;


    numeral :   DIGIT 
        |   numeral DIGIT
        ;


    operation   :   '+'
                |   '-'
                |   '*'
                |   '/'
                |   '='
                |   '<'
                |   '>'
                |   '>' '='
                |   '<' '='
                ;

    expression  :   name 
            |   numeral
            |   '(' '!' expression ')'
            |   '(' expression operation expression ')'
            ;

    assignment : name '<' '-' expression
               ;

    instruction : assignment
                | 'g' 'o' 't' 'o' name
                | 's' 't' 'o' 'p'
                ;


    labelinstr : name ':' instruction ';'
               | instruction ';'
               ;

    loop : 'l' 'o' 'o' 'p' expression ';'
         |  name ':' 'l' 'o' 'o' 'p' expression ';'
         ;

    ifthen  :   'i' 'f' expression 't' 'h' 'e' 'n' ';'
            |   name ':' 'i' 'f' expression 't' 'h' 'e' 'n' ';'
            ;
    while   :   'w' 'h' 'i' 'l' 'e' ';'
            |   name ':' 'w' 'h' 'i' 'l' 'e' expression ';'
            ;


    end : 'e' 'n' 'd' ';'
        | name ':' 'e' 'n' 'd' ';'
        ;

    program : labelinstr
            | loop program end
            | while program end
            | ifthen program end
            | ifthen program end 'e' 'l' 's' 'e' ';' program end
            | program program
            ;





    %%
    #include <stdio.h>

    yylex() {
      int c;
      while ( (c=getchar()) == ' ' || c == '\n' || c == '\t') {
         printf("%c",c);}
      printf("%c",c);
      return(c);
     }

Answer 1

识别 shift/reduce 冲突的第一步是使用 -v 标志到 bison 并检查结果文件中的状态机，该状态机将具有足够的 .输出。这将告诉您哪些状态出现错误以及哪些规则导致该状态。例如，在您的程序中，我们看到两个存在移位/归约冲突的状态，状态 65 和状态 84。

状态84比较简单:

State 84

   72 program: ifthen program end .
   73        | ifthen program end . 'e' 'l' 's' 'e' ';' program end

    'e'  shift, and go to state 101

    'e'       [reduce using rule 72 (program)]
    $default  reduce using rule 72 (program)

这类似于经典的“其他悬挂”问题。通常使用像 end; 这样的语句终止符可以解决这个问题，但是你好奇地提出的语法坚持要有一个 end; 即使在 else< 的情况下也是如此 子句。所以

if (a > 3) then a <- 3; else a <- 2; end,

无效。相反，语法坚持

if (a > 3) then a <- 3; end; else a <- 2; end;

这无助于解决悬空 else 问题，因为 end 不区分带和不带 else 子句的语句，因此以下内容仍然不明确:

if (a > 3) then if (a < 7) then a <- 3; end; else a <- 7; end;

语法正确的可能性不大。我怀疑 if 产生式应该是:

        | ifthen program end
        | ifthen program 'e' 'l' 's' 'e' ';' program end

另一个问题是在状态 65 中:(这里，我省略了转换)

State 65

   74 program: program . program
   74        | program program .

这显然是模棱两可的。假设你有:

statement statement statement

这可以解析为从左到右或从右到左的绑定(bind):

[program: [program: statement] [program: [program: statement] [program: statement]]] 
[program: [program: [program: statement] [program: statement]] [program: statement]] 

粗略地说，解决方案通常是这样的:

statement: if_statement
         | loop_statement
         | ...

program: statement
       | program statement

虽然就个人而言，我可能会考虑标签。