野牛的无用规则

Question

由于某种原因，bison拒绝了一条特定的规则，即notequal_expression，请注意，我刚刚开始学习整个概念，所以我的思路还不够成熟，输入文件：(错误是：“starting .y包含一个无用的非终端和一个无用的规则”)。

    /* Parser for StringC */

%{

/* ------------------------------------------------------------------
   Initial code (copied verbatim to the output file)
   ------------------------------------------------------------------ */

// Includes
#include <malloc.h>  // _alloca is used by the parser
#include <string.h>  // strcpy

#include "lex.h"     // the lexer

// Some yacc (bison) defines
#define YYDEBUG 1         // Generate debug code; needed for YYERROR_VERBOSE
#define YYERROR_VERBOSE // Give a more specific parse error message 

// Error-reporting function must be defined by the caller
void Error (char *format, ...);

// Forward references
void yyerror (char *msg);

%}

/* ------------------------------------------------------------------
   Yacc declarations
   ------------------------------------------------------------------ */

/* The structure for passing value between lexer and parser */
%union {
   char *str;
}

%token ERROR_TOKEN IF ELSE PRINT INPUT ASSIGN EQUAL NOTEQUAL
%token CONCAT END_STMT OPEN_PAR CLOSE_PAR
%token BEGIN_CS END_CS 
%token <str> ID STRING BOOLEAN

/*%type <type> type simple_type cast*/

%expect 1  /* shift/reduce conflict: dangling ELSE */
           /*    declaration */
%%

/* ------------------------------------------------------------------
   Yacc grammar rules
   ------------------------------------------------------------------ */

program
      : statement_list
        ;

statement_list
      : statement_list statement
      | /* empty */
      ;

statement
      : END_STMT                    {puts ("Empty statement");}
      | expression END_STMT         {puts ("Expression statement");}
      | PRINT expression END_STMT   {puts ("Print statement");}
      | INPUT identifier END_STMT   {puts ("Input statement");}
      | if_statement                {puts ("If statement");}
      | compound_statement          {puts ("Compound statement");}
      | error END_STMT              {puts ("Error statement");}
      | notequal_expression         {puts ("Not equal statement");}
      ;

/* NOTE: This rule causes an unresolvable shift/reduce conflict;
   That's why %expect 1 was added (see above) */
if_statement
      : IF OPEN_PAR expression CLOSE_PAR statement optional_else_statement
      ;

optional_else_statement
      : ELSE statement
      | /* empty */
      ;

compound_statement
      : BEGIN_CS statement_list END_CS
      ;

expression
      : equal_expression
      | OPEN_PAR expression CLOSE_PAR
      ;

equal_expression
      : expression EQUAL assign_expression
      | assign_expression
      ;

notequal_expression
      : expression NOTEQUAL assign_expression 
      | NOTEQUAL assign_expression
      ;

assign_expression
      : identifier ASSIGN assign_expression
      | concat_expression
      ;

concat_expression
      : concat_expression CONCAT simple_expression
      | simple_expression
      ;

simple_expression
      : identifier
      | string
      ;

identifier
      : ID              {}
      ;

string
      : STRING          {}
      ;

bool
      : BOOLEAN          {}
      ;

%%
/* ------------------------------------------------------------------
   Additional code (again copied verbatim to the output file)
   ------------------------------------------------------------------ */

雷克萨斯：

/* Lexical analyzer for StringC */

%{

/* ------------------------------------------------------------------
   Initial code (copied verbatim to the output file)
   ------------------------------------------------------------------ */

// Includes
#include <string.h>   // strcpy, strncpy
#include <io.h>       // isatty
#ifdef MSVC
#define  isatty _isatty  // for some reason isatty is called _isatty in VC..
#endif

#define  _LEX_CPP_   // make sure our variables get created
#include "lex.h"
#include "lexsymb.h"

extern "C" int yywrap (); // the yywrap function is declared by the caller

// Forward references
void Identifier ();
void StringConstant ();
void BoolConstant ();
void EatComment ();

//// End of inititial code
%}

/* ------------------------------------------------------------------
   Some macros (standard regular expressions)
   ------------------------------------------------------------------ */

LETTER   [a-zA-Z_]
DIGIT    [0-9]
IDENT    {LETTER}({LETTER}|{DIGIT})*
STR      \"[^\"]*\"
BOOL     \(false|true)\
WSPACE   [ \t]+


/* ------------------------------------------------------------------
   The lexer rules
   ------------------------------------------------------------------ */
%%

"if"     {return IF;}
"else"   {return ELSE;}
"print"  {return PRINT;}
"input"  {return INPUT;}
"="      {return ASSIGN;}
"=="     {return EQUAL;}
"!="     {return NOTEQUAL;}                         /* Not equal to */
"+"      {return CONCAT;}
";"      {return END_STMT;}
"("      {return OPEN_PAR;}
")"      {return CLOSE_PAR;}
"{"      {return BEGIN_CS;}
"}"      {return END_CS;}
{BOOL}   {BoolConstant ();   return BOOLEAN;}
{STR}    {StringConstant (); return STRING;}
{IDENT}  {Identifier ();     return ID;}
"//"     {EatComment();}                            /* comment:    skip */
\n       {lineno++;}                                /* newline:    count lines */
{WSPACE} {}                                         /* whitespace: (do nothing) */
.        {return ERROR_TOKEN;}                      /* other char: error, illegal token */

%%

/* ------------------------------------------------------------------
   Additional code (again copied verbatim to the output file)
   ------------------------------------------------------------------ */

// The comment-skipping function: skip to end-of-line
void EatComment()  {
    char c;

   while ((c = yyinput()) != '\n' && c != 0);
    lineno++;
}

// Pass the id name
void Identifier ()  {
   yylval.str = new char[strlen(yytext)+1];
   strcpy (yylval.str, yytext);
}

// Pass the string constant
void StringConstant()  {
   int l = strlen(yytext)-2;
   yylval.str = new char[l+1];
   strncpy (yylval.str, &yytext[1], l); yylval.str[l] = 0;
}


void BoolConstant()    {
    int l = strlen(yytext)-2;
    yylval.str = new char[l+1];
    strncpy(yylval.str, &yytext[1], l); yylval.str[l] = 0;
}

Answer 1

您确定是notequal_expression造成了这个问题吗？据我所读，没有使用的非终端和规则是

bool
      : BOOLEAN          {}
      ;

也许不是

simple_expression
      : identifier
      | string
      ;

你想要编码

simple_expression
      : identifier
      | string
      | bool
      ;

Answer 2

语法有两个问题。第一个是您已经看到的转移/减少冲突(并使用%expect 1来解决)。我更喜欢在语法中解决这个问题，而不是使用%expect 0。可以通过从ELSE列表中删除%token并添加一行来做到这一点。

%right THEN ELSE

宣布正确的结合。您的语言实际上没有THEN关键字，但这很好。然后，您可以完全删除optional_else_statement的规则，并将if_statement的规则重述如下：

if_statement
      : IF OPEN_PAR expression CLOSE_PAR statement  %prec THEN
      | IF OPEN_PAR expression CLOSE_PAR statement ELSE statement
      ;

有些人喜欢以这种方式解决这个问题，还有一些人主张采用%expect 1方法。我更喜欢这种方式，但既然有了这两种方法，你当然可以自己选择。

对于另一个问题，无用的规则肯定是这样的：

bool
      : BOOLEAN          {}
      ;

因为非终端bool不在语法的其他地方使用。这说明了野牛报告的"1条无用的非终端和1条无用的规则“。为了能够为自己识别这类东西，您可以使用

bison --report=solved -v string.y

这将创建一个string.output文件，该文件将包含一个大型但可读的报告，包括任何已解决的shift-减少错误(例如您的IF-否则构造)以及bison创建的一组完整的状态。在试图排除语法问题时，这是非常有用的。