lex 和 yacc 警告并且没有按预期工作

Question

Lexer.l

%{
#include "y.tab.h"
%}

%%

"define" return(TK_KEY_DEFINE); 
"as" return(TK_KEY_AS);
"is" return(TK_KEY_IS);
"if" return(TK_KEY_IF);
"then" return(TK_KEY_THEN);
"else" return(TK_KEY_ELSE);
"endif" return(TK_KEY_ENDIF);
"with" return(TK_KEY_WITH);
"DEFINE" return(TK_KEY_DEFINE_UC);
"AS" return(TK_KEY_AS_UC);
"IS" return(TK_KEY_IS_UC);
"IF" return(TK_KEY_IF_UC);
"THEN" return(TK_KEY_THEN_UC);
"ELSE" return(TK_KEY_ELSE_UC);
"ENDIF" return(TK_KEY_ENDIF_UC);
"WITH" return(TK_KEY_WITH_UC);
"+" return(TK_PLUS);
"-" return(TK_MINUS); 
"*" return(TK_MUL);
"/" return(TK_DIV);
"~" return(TK_NOT); 
"&" return(TK_AND); 
"|" return(TK_OR);
"<=" return(TK_LEQ);
"<" return(TK_LESS);
">=" return(TK_GEQ); 
">" return(TK_GT); 
"==" return(TK_EQ);
"=" return(TK_ASSIGN);
"(" return(TK_OPEN);
")" return(TK_CLOSE);
";" return(TK_SEMI);
"," return(TK_COMMA);
[[:alpha:]_][[:alnum:]_]* return(IDENTIFIER);
[+-]?[0-9]+ return(INTEGER);
[+-]?([0-9]+([.][0-9]*)?|[.][0-9]+) return(REAL); 
[[:space:]]+ ;

%%

int yywrap(void)
{
  return 1;
}

Parser.y

%{

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

  typedef struct node
  {
    struct node *left;
    struct node *right;
    char *token;
  } node;

  node *mknode(node *left, node *right, char *token);
  void printtree(node *tree);

#define YYSTYPE struct node *

%}

%start Program

%token TK_KEY_DEFINE TK_KEY_DEFINE_UC
%token TK_KEY_AS TK_KEY_AS_UC
%token TK_KEY_IS TK_KEY_IS_UC 
%token TK_KEY_IF TK_KEY_IF_UC
%token TK_KEY_THEN TK_KEY_THEN_UC
%token TK_KEY_ELSE TK_KEY_ELSE_UC
%token TK_KEY_ENDIF TK_KEY_ENDIF_UC
%token TK_KEY_WITH TK_KEY_WITH_UC
%token TK_PLUS TK_MINUS
%token TK_MUL TK_DIV
%token TK_NOT
%token TK_AND
%token TK_OR 
%token TK_LEQ TK_LESS TK_GEQ TK_GT 
%token TK_EQ
%token TK_ASSIGN 
%token TK_OPEN TK_CLOSE
%token TK_SEMI
%token TK_COMMA
%token IDENTIFIER
%token INTEGER 
%token REAL


%left   TK_PLUS  TK_MINUS
%left   TK_MUL TK_DIV
%left   TK_LEG TK_LESS TK_GEQ TK_GT 
%left   TK_AND TK_OR
%left   TK_EQ
%right  TK_NOT TK_ASSIGN

%%


Program  : Macros Statements;

Macros   :   /* empty */
         | Macro Macros
         ;

Macro    : TK_KEY_DEFINE MacroTemplate TK_KEY_AS Expression;

MacroTemplate : IDENTIFIER MT;

MT            : /*empty*/
              | TK_OPEN IdentifierList TK_CLOSE 
              ; 

IdentifierList : IDENTIFIER I;

I : /*empty*/
  | TK_COMMA IdentifierList 
  ;

Statements : /*empty*/
           | Statement Statements 
           ;

IfStmt : TK_KEY_IF Condition TK_KEY_THEN Statements TK_KEY_ELSE Statements TK_KEY_ENDIF;

Statement : AssignStmt 
          | IfStmt
          ;

AssignStmt : IDENTIFIER TK_KEY_IS Expression;



Condition : C1 C11;

C11 : /*empty*/
    | TK_OR C1 C11
    ;

C1 : C2 C22;

C22 : /*empty*/
    | TK_AND C2 C22
    ; 

C2 : C3 C33;

C33 : TK_EQ C3 C33;

C3 : C4 C44;

C44 : /*empty*/
    | TK_LESS C4 C44 
    | TK_LEQ C4 C44 
    | TK_GT C4 C44  
    | TK_GEQ C4 C44
    ;

C4 : TK_NOT C5 | C5;

C5 : INTEGER | REAL | TK_OPEN Condition TK_CLOSE;

Expression : Term EE;

EE : /*empty*/
   | TK_PLUS Term EE
   | TK_MINUS Term EE
   ;

Term : Factor TT;

TT : /*empty*/
   | TK_MUL Factor TT 
   | TK_DIV Factor TT 
   ;

Factor : IDENTIFIER | REAL | INTEGER | TK_OPEN Expression TK_CLOSE;

%%

int main (void) {return yyparse ( );}

node *mknode(node *left, node *right, char *token)
{
  /* malloc the node */
  node *newnode = (node *)malloc(sizeof(node));
  char *newstr = (char *)malloc(strlen(token)+1);
  strcpy(newstr, token);
  newnode->left = left;
  newnode->right = right;
  newnode->token = newstr;
  return(newnode);
}

void printtree(node *tree)
{
  int i;
  if (tree->left || tree->right)
    printf("(");

  printf(" %s ", tree->token);

  if (tree->left)
    printtree(tree->left);
  if (tree->right)
    printtree(tree->right);

  if (tree->left || tree->right)
    printf(")");
}

int yyerror (char *s) 
{
fprintf (stderr, "%s\n", s);
}

如果没有错误，我希望输出到解析树，如果有错误则指出。但是我收到很多警告，例如

 warning: rule useless in grammar 
 warning: nonterminal useless in grammar

我通过阅读其他类似的问题了解了这个原因，但无法自行纠正。请帮我解决这个问题。谢谢！

嗨 rici ,

非常感谢，这样我就不用担心左递归、左分解语法等问题，直接在 yacc 中使用类似下面的内容？

%% 

Program : Macros Statements;

Macros : /*empty*/ 
       |Macro Macros
       ; 

Macro : TK_KEY_DEFINE MacroTemplate TK_KEY_AS Expression;

MacroTemplate : VarTemplate
              | FunTemplate
          ;

VarTemplate : IDENTIFIER;

FunTemplate : IDENTIFIER TK_OPEN IdentifierList TK_CLOSE;

IdentifierList : IDENTIFIER TK_COMMA IdentifierList
               | IDENTIFIER
               ;

Statements : /*empty*/
           | Statement Statements 
           ;

IfStmt : TK_KEY_IF Condition TK_KEY_THEN Statements TK_KEY_ELSE Statements TK_KEY_ENDIF;

Statement : AssignStmt 
          | IfStmt
          ;

AssignStmt : IDENTIFIER TK_KEY_IS Expression;

Condition : Condition TK_AND Condition
          | Condition TK_OR Condition
          | Condition TK_LESS Condition 
          | Condition TK_LEQ Condition
          | Condition TK_GT Condition 
          | Condition TK_GEQ Condition 
      | Condition TK_EQ Condition
          | TK_NOT Condition 
          | TK_OPEN Condition TK_CLOSE
          | INTEGER
          | REAL
          ;

Expression : Expression TK_PLUS Expression
           | Expression TK_MINUS Expression 
           | Expression TK_MUL Expression 
           | Expression TK_DIV Expression 
           | TK_OPEN Expression TK_CLOSE
           | IDENTIFIER 
           | INTEGER
           | REAL
           ;

%%

是的，我注意到你的最后一点 :)

Answer 1

不像C11、C22、C44等"tail"规则可以产生%empty，C33只有一个产生:

C33 : TK_EQ C3 C33;

因为它没有非递归产生式，所以它不可能产生一个句子（仅由非终结符组成）。并且因为它是 C2 唯一作品的一部分，它是 C1 唯一作品的一部分，它是 Condition 唯一作品的一部分，它是 Condition 唯一作品的一部分=19=], none 也可以产生任何句子。不能产生任何句子的规则在技术上被描述为 "useless" 而所有规则都无用（或唯一规则无用）的非终结符是 "useless non-terminal".

还有一类无用的非终结符：那些不能由任何有用规则生成的非终结符。 C4 就是这种情况（它只能由 C3 产生，已被发现是无用的），因此 C44 和 C5 也是如此。

解决这个问题的方法应该很明显，但我想指出的是，您试图避免左递归是在给自己打结，这在使用自下而上时既不必要又适得其反解析器生成器，例如 bison/yacc。（请参阅的最后一段以获取有关此的更长时间的抱怨。）人为的产品（C33 和朋友）只会使解析树复杂化。

此外，由于您的语法没有歧义——实际上，产生式规则清楚地定义了运算符绑定强度——各种优先级声明毫无意义。（与 "useless" 不同，那不是技术术语 :-)）。优先级声明仅适用于解决此处不存在的语法歧义。

最后，我认为您应该重新检查 Condition 的语法。例如，~3 < ~4 是什么意思？为什么 x * 2 < y 无效？

lex 和 yacc 警告并且没有按预期工作

lex and yacc warning's and not working as expected

yacc

lex