Flex/Bison mini C 编译器词法语义分析shift/reduce 冲突
Flex/Bison mini C compiler lexical and semantic analysis shift/reduce conflict
我想使用 flex 和 bison 为迷你 C 语言编写一个编译器。我的语言示例如下所示:
/* This is an example uC program. */
int fac(int n)
{
if (n < 2)
return n;
return n * fac(n - 1);
}
int sum(int n, int a[])
{
int i;
int s;
i = 0;
s = 0;
while (i < n) {
s = s + a[i];
i = i + 1;
}
return s;
}
int main(void)
{
int a[2];
a[0] = fac(5);
a[1] = 27;
return 0;
}
这是我解析这种语言的语法:
program ::= topdec_list
topdec_list ::= /empty/ | topdec topdec_list
topdec ::= vardec ";"
| funtype ident "(" formals ")" funbody
vardec ::= scalardec | arraydec
scalardec ::= typename ident
arraydec ::= typename ident "[" intconst "]"
typename ::= "int" | "char"
funtype ::= typename | "void"
funbody ::= "{" locals stmts "}" | ";"
formals ::= "void" | formal_list
formal_list ::= formaldec | formaldec "," formal_list
formaldec ::= scalardec | typename ident "[" "]"
locals ::= /empty/ | vardec ";" locals
stmts ::= /empty/ | stmt stmts
stmt ::= expr ";"
| "return" expr ";" | "return" ";"
| "while" condition stmt
| "if" condition stmt else_part
| "{" stmts "}"
| ";"
else_part ::= /empty/ | "else" stmt
condition ::= "(" expr ")"
expr ::= intconst
| ident | ident "[" expr "]"
| unop expr
| expr binop expr
| ident "(" actuals ")"
| "(" expr ")"
unop ::= "-" | "!"
binop ::= "+" | "-" | "*" | "/"
| "<" | ">" | "<=" | ">=" | "!=" | "=="
| "&&"
| "="
actuals ::= /empty/ | expr_list
expr_list ::= expr | expr "," expr_list
flex 模块工作正常并且 returns 值符合要求,但是 bison 一直给我奇怪的错误,表明我的语法错误(实际上不是)。这是我的野牛文件:
%{
#include <stdio.h>
#include <stdlib.h>
extern int yylex();
extern int yyparse();
FILE* yyin;
extern int lineNumber;
void yyerror(const char* s);
%}
%union {
int intvalue;
}
%token<intvalue> INTCONST
%token IDENT
%token CHARK
%token ELSEK
%token IFK
%token INTK
%token RETURNK
%token VOIDK
%token WHILEK
%token NOTK
%token ANDK
%token COMMAK
%token DIVIDEK
%token MULTIPLYK
%token MINUSK
%token PLUSK
%token SEMICOLONK
%token NEQUALK
%token EQUALK
%token ASSIGNMENTK
%token RECOMPARATORK
%token LECOMPARATORK
%token RCOMPARATORK
%token LCOMPARATORK
%token RPARANTESESK
%token LPARANTESESK
%token RBRACKETK
%token LBRACKETK
%token RCURLY
%token LCURLY
%right ASSIGNMENTK
%left ANDK
%left EQUALK NEQUALK
%left LCOMPARATORK RCOMPARATORK LECOMPARATORK RECOMPARATORK
%left PLUSK
%left MULTIPLYK DIVIDEK
%left MINUSK NOTK
%start program
%%
program: topdec_list
;
topdec_list: /*empty*/
| topdec topdec_list
;
topdec: vardec SEMICOLONK
| funtype IDENT LPARANTESESK formals RPARANTESESK funbody
;
vardec: scalardec
| arraydec
;
scalardec: typename IDENT
;
arraydec: typename IDENT LBRACKETK INTCONST RBRACKETK
;
typename: INTK
| CHARK
;
funtype: typename
| VOIDK
;
funbody: LCURLY locals stmts RCURLY
| SEMICOLONK
;
formals: VOIDK
| formal_list
;
formal_list: formaldec
| formaldec COMMAK formal_list
;
formaldec: scalardec
| typename IDENT LBRACKETK RBRACKETK
;
locals: /*empty*/
| vardec SEMICOLONK locals
;
stmts: /*empty*/
| stmt stmts
;
stmt: expr SEMICOLONK
| RETURNK expr SEMICOLONK
| RETURNK SEMICOLONK
| WHILEK condition stmt
| IFK condition stmt else_part
| LCURLY stmts RCURLY
| SEMICOLONK
;
else_part: /*empty*/ | ELSEK stmt
;
condition: LPARANTESESK expr RPARANTESESK
;
expr: INTCONST
| IDENT
| IDENT LBRACKETK expr RBRACKETK
| unop expr
| expr binop expr
| IDENT LPARANTESESK actuals RPARANTESESK
| LPARANTESESK expr RPARANTESESK
;
unop: MINUSK | NOTK
;
binop: PLUSK
| MINUSK
| MULTIPLYK
| DIVIDEK
| LCOMPARATORK
| RCOMPARATORK
| LECOMPARATORK
| RECOMPARATORK
| NEQUALK
| EQUALK
| ANDK
| ASSIGNMENTK
;
actuals: /*empty*/
| expr_list
;
expr_list: expr
| expr COMMAK expr_list
;
%%
int main(int argc, char **argv)
{
yyin = fopen("input.c", "r");
do
{
yyparse();
} while (!feof(yyin));
fclose(yyin);
return 0;
}
void yyerror(const char* error)
{
fprintf(stderr, "Parse error in line %d: %s\n", lineNumber, error);
}
例如对于此输入:
int i;
i = 0;
我得到一个错误,在它区分第二个 i
后立即发生了语法错误(我在我的 flex 文件中打印了标记,所以我知道它没有问题,直到它到达赋值字符)。
或者作为传递此行时的另一个示例:
int fac(int n);
我在第一个 paranteses 之后得到相同的语法错误(完全是 Parse error in line 1: syntax error
),这意味着它将第二个 int
视为语法错误,这不应该是因为我的语法看起来不错。
另外bison产生的警告如下(flex和gcc都可以):
semantic_analyzer.y: warning: 26 shift/reduce conflicts [-Wconflicts-sr]
semantic_analyzer.y:78.10-17: warning: rule useless in parser due to conflicts [-Wother]
funtype: typename
^^^^^^^^
如有任何建议或更正,我们将不胜感激 :) 在此先致谢。
int i;
i = 0;
不是有效的 C 程序,您的语法正确地拒绝了它。 (如您的语法所示,程序是一系列 声明 而 i = 10;
不是声明。)
你提到的第二个问题与 shift-reduce 冲突有关,这是由于你的语法坚持认为 int fac(int n)
中的第一个 int
必须缩减为 funtype
,而int i;
中的 int
是 typename
。在解析器需要决定是将 IDENT
移动还是将 typename
缩减为 funtype
时,它无法知道要采取哪项操作,因为它只能看到一个先行标记—— IDENT
—— 决定取决于 second 下一个先行标记(它可能是也可能不是左括号)。默认情况下,yacc/bison通过shifting解决shift-reduce冲突,也就是说int fac
不能作为topdec
的第二个产生式的前缀;因此,(
将触发错误。
我想使用 flex 和 bison 为迷你 C 语言编写一个编译器。我的语言示例如下所示:
/* This is an example uC program. */
int fac(int n)
{
if (n < 2)
return n;
return n * fac(n - 1);
}
int sum(int n, int a[])
{
int i;
int s;
i = 0;
s = 0;
while (i < n) {
s = s + a[i];
i = i + 1;
}
return s;
}
int main(void)
{
int a[2];
a[0] = fac(5);
a[1] = 27;
return 0;
}
这是我解析这种语言的语法:
program ::= topdec_list
topdec_list ::= /empty/ | topdec topdec_list
topdec ::= vardec ";"
| funtype ident "(" formals ")" funbody
vardec ::= scalardec | arraydec
scalardec ::= typename ident
arraydec ::= typename ident "[" intconst "]"
typename ::= "int" | "char"
funtype ::= typename | "void"
funbody ::= "{" locals stmts "}" | ";"
formals ::= "void" | formal_list
formal_list ::= formaldec | formaldec "," formal_list
formaldec ::= scalardec | typename ident "[" "]"
locals ::= /empty/ | vardec ";" locals
stmts ::= /empty/ | stmt stmts
stmt ::= expr ";"
| "return" expr ";" | "return" ";"
| "while" condition stmt
| "if" condition stmt else_part
| "{" stmts "}"
| ";"
else_part ::= /empty/ | "else" stmt
condition ::= "(" expr ")"
expr ::= intconst
| ident | ident "[" expr "]"
| unop expr
| expr binop expr
| ident "(" actuals ")"
| "(" expr ")"
unop ::= "-" | "!"
binop ::= "+" | "-" | "*" | "/"
| "<" | ">" | "<=" | ">=" | "!=" | "=="
| "&&"
| "="
actuals ::= /empty/ | expr_list
expr_list ::= expr | expr "," expr_list
flex 模块工作正常并且 returns 值符合要求,但是 bison 一直给我奇怪的错误,表明我的语法错误(实际上不是)。这是我的野牛文件:
%{
#include <stdio.h>
#include <stdlib.h>
extern int yylex();
extern int yyparse();
FILE* yyin;
extern int lineNumber;
void yyerror(const char* s);
%}
%union {
int intvalue;
}
%token<intvalue> INTCONST
%token IDENT
%token CHARK
%token ELSEK
%token IFK
%token INTK
%token RETURNK
%token VOIDK
%token WHILEK
%token NOTK
%token ANDK
%token COMMAK
%token DIVIDEK
%token MULTIPLYK
%token MINUSK
%token PLUSK
%token SEMICOLONK
%token NEQUALK
%token EQUALK
%token ASSIGNMENTK
%token RECOMPARATORK
%token LECOMPARATORK
%token RCOMPARATORK
%token LCOMPARATORK
%token RPARANTESESK
%token LPARANTESESK
%token RBRACKETK
%token LBRACKETK
%token RCURLY
%token LCURLY
%right ASSIGNMENTK
%left ANDK
%left EQUALK NEQUALK
%left LCOMPARATORK RCOMPARATORK LECOMPARATORK RECOMPARATORK
%left PLUSK
%left MULTIPLYK DIVIDEK
%left MINUSK NOTK
%start program
%%
program: topdec_list
;
topdec_list: /*empty*/
| topdec topdec_list
;
topdec: vardec SEMICOLONK
| funtype IDENT LPARANTESESK formals RPARANTESESK funbody
;
vardec: scalardec
| arraydec
;
scalardec: typename IDENT
;
arraydec: typename IDENT LBRACKETK INTCONST RBRACKETK
;
typename: INTK
| CHARK
;
funtype: typename
| VOIDK
;
funbody: LCURLY locals stmts RCURLY
| SEMICOLONK
;
formals: VOIDK
| formal_list
;
formal_list: formaldec
| formaldec COMMAK formal_list
;
formaldec: scalardec
| typename IDENT LBRACKETK RBRACKETK
;
locals: /*empty*/
| vardec SEMICOLONK locals
;
stmts: /*empty*/
| stmt stmts
;
stmt: expr SEMICOLONK
| RETURNK expr SEMICOLONK
| RETURNK SEMICOLONK
| WHILEK condition stmt
| IFK condition stmt else_part
| LCURLY stmts RCURLY
| SEMICOLONK
;
else_part: /*empty*/ | ELSEK stmt
;
condition: LPARANTESESK expr RPARANTESESK
;
expr: INTCONST
| IDENT
| IDENT LBRACKETK expr RBRACKETK
| unop expr
| expr binop expr
| IDENT LPARANTESESK actuals RPARANTESESK
| LPARANTESESK expr RPARANTESESK
;
unop: MINUSK | NOTK
;
binop: PLUSK
| MINUSK
| MULTIPLYK
| DIVIDEK
| LCOMPARATORK
| RCOMPARATORK
| LECOMPARATORK
| RECOMPARATORK
| NEQUALK
| EQUALK
| ANDK
| ASSIGNMENTK
;
actuals: /*empty*/
| expr_list
;
expr_list: expr
| expr COMMAK expr_list
;
%%
int main(int argc, char **argv)
{
yyin = fopen("input.c", "r");
do
{
yyparse();
} while (!feof(yyin));
fclose(yyin);
return 0;
}
void yyerror(const char* error)
{
fprintf(stderr, "Parse error in line %d: %s\n", lineNumber, error);
}
例如对于此输入:
int i;
i = 0;
我得到一个错误,在它区分第二个 i
后立即发生了语法错误(我在我的 flex 文件中打印了标记,所以我知道它没有问题,直到它到达赋值字符)。
或者作为传递此行时的另一个示例:
int fac(int n);
我在第一个 paranteses 之后得到相同的语法错误(完全是 Parse error in line 1: syntax error
),这意味着它将第二个 int
视为语法错误,这不应该是因为我的语法看起来不错。
另外bison产生的警告如下(flex和gcc都可以):
semantic_analyzer.y: warning: 26 shift/reduce conflicts [-Wconflicts-sr]
semantic_analyzer.y:78.10-17: warning: rule useless in parser due to conflicts [-Wother]
funtype: typename
^^^^^^^^
如有任何建议或更正,我们将不胜感激 :) 在此先致谢。
int i;
i = 0;
不是有效的 C 程序,您的语法正确地拒绝了它。 (如您的语法所示,程序是一系列 声明 而 i = 10;
不是声明。)
你提到的第二个问题与 shift-reduce 冲突有关,这是由于你的语法坚持认为 int fac(int n)
中的第一个 int
必须缩减为 funtype
,而int i;
中的 int
是 typename
。在解析器需要决定是将 IDENT
移动还是将 typename
缩减为 funtype
时,它无法知道要采取哪项操作,因为它只能看到一个先行标记—— IDENT
—— 决定取决于 second 下一个先行标记(它可能是也可能不是左括号)。默认情况下,yacc/bison通过shifting解决shift-reduce冲突,也就是说int fac
不能作为topdec
的第二个产生式的前缀;因此,(
将触发错误。