YACC 生成的解析器对重复的相同输入给出不同的输出

Question

我想使用 YACC 和 LEX 检查字符串是否与语法 a^nb^n 匹配。这是我的 LEX 和 YACC 文件，顺序相同：

Lex 文件：

  %{
   #include <stdio.h>
   #include <y.tab.h>
  %}

  %%
   a {return A;}
   b {return B;}
   . {return yytext[0];}
   \n {return NL;}
  %%
   int yywrap(void) {
      return 1;
   }

YACC 文件：

  %{
   #include <stdio.h>
   yyerror()
  {
    printf("Rejected\n");
   }    
  %}

   %token A B NL
   %start T

   %%

   T : S NL {printf("accepted\n");}
     ;
   S : A S B
     | A B
     ;

  %%

  main()
  {
    yyparse();
  }

问题是输出：

输入字符串：aabb

输出：已接受

输入字符串：aabb

输出：拒绝

当相同的输入或任何应该被接受的输入在第二次输入时被拒绝。我了解到 YACC 有一个在解析字符串时使用的堆栈。但我找不到任何相关文件。请帮忙。

Answer 1

yacc规则T是非递归的，这意味着它只匹配一个行。以下修改将观看任意数量的行（包括 none）。

T : T S NL
  | /* empty */
  ;

导致连续行被接受。

$ printf 'aabb\naabb\n' | ./a.out
accepted
accepted

Answer 2

我无法通过运行反复使用你的解析器来重现你的结果，但我可以通过在同一个运行中为解析器提供多个字符串来重现它.了解其中的区别很重要：一次执行 yyparse() 就是一次执行运行，它将尝试解析整个输入，直到词法分析器发出文件结束信号为止。 @kdhp 的回答解释了为什么您的解析器不接受同一运行中的多个字符串，并提供了一种获得您似乎想要的结果的方法。

另一种方法是真正执行多个运行s，您可以通过调整解析器和词法分析器来实现。词法分析器在看到换行符时需要报告输入结束，然后解析器根本不需要考虑换行符。

此外，在任何一种情况下所需的词法分析器都非常简单，以至于用 lex（或 flex）生成它太过分了；直接写一个合适的yylex()就简单多了。此外，通过编写自己的代码，您可以更方便地在 main() 中区分行尾和输入结束。支持所有可能出现在语法文件中的词法分析器，在 main():

之前

int end_of_input = 0;

int yylex(void) {
    int c = getc();  /* no buffering inside the lexer */

    if (c < 0) {
        end_of_input = 1;
    }
    return ((c == '\n') ? 0 : c);
}

为简单起见，假设解析器使用文字标记，在这种情况下没有特别的理由不这样做。此外，它唯一需要的规则是非终端 S （现在是开始符号）的原始规则的变体：

S : 'a' S 'b'
  | 'a' 'b'
  ;

使用该词法分析器和该规则，yyparse() 中的每个运行将最多解析一行（但可能会在行尾之前因解析错误而停止），并且 return 0 当且仅当整行被成功解析。然后你运行它在一个循环中：

int main(void)
{
    do {
        if (yyparse() == 0)) {
            puts("accepted");
        } // else yyerror() already printed "rejected"
    } while (!end_of_input);
}

最后要注意的是，如果在输入行的中间某处存在解析错误，则上述内容不会使用该行的其余部分（您的版本也不会）。如果发生错误后您想在 main() 中或通过解析器中的错误规则继续解析下一行。那当然可以做到；我把它留作练习。

YACC 生成的解析器对重复的相同输入给出不同的输出

YACC-generated parser gives different outputs for same input repeated

c

yacc

lex