yacc语法分析minipascal_用Yacc实现语法分析器-4-编译原理

用Yacc实现语法分析器

一、实验目的

掌握语法分析器的构造原理，掌握Yacc的编程方法。

二、实验内容

用Yacc编写一个语法分析程序，使之与词法分析器结合，能够根据语言的上下文无关文法，识别输入的单词序列是否文法的句子。

program      → block

block→   { stmts}

stmts     →　stmt stmts | e

stmt       →   id= expr ;

|      if ( bool ) stmt

|      if (bool) stmtelsestmt

|      while (bool) stmt

|      do stmtwhile (bool) ;

|      break ;

|      block

bool→ expr < expr

|     expr <= expr

|     expr > expr

|     expr >= expr

|     expr

expr      → expr+term

|     expr-term

|     term

term      → term*factor

|   term/factor

|     factor

factor     → ( expr) | id| num

三、实验步骤及结果

实验环境：unix

实验结果：按归约的先后顺序显示每次归约时所使用的产生式。

部分代码：

用于产生flex输入的代码

View Code

Test.l:[a-zA-Z_][a-zA-Z_0-9]* {returnID;}

[0-9]+.[0-9]+ {returnREAL;}

[0-9]+ {returnNUM;}"||" {returnOR;}"&&" {returnAND;}"|" {return '|';}"&" {return '&';}"<=" {returnLE;}"=" {returnGE;}">" {return '>';}"!=" {returnNE;}"=" { return '=';}"==" {returnEQ;}"+" {return '+';}"-" {return '-';}"*" {return '*';}"/" {return '/';}"(" {return '(';}")" {return ')';}";" {return ';';}"{" {return '{';}"}" {return '}';}"[" {return '['; }"]" {return ']';}

Test.y:rel : expr'exprexpr<=exprn"); }| expr GE expr { printf("rel-->expr>=exprn"); }| expr '>' expr { printf("rel-->expr>exprn"); }| expr { printf("rel-->exprn"); }

;

expr : expr'+' term { printf("expr-->expr+termn"); }| expr '-' term { printf("expr-->expr-termn"); }| term { printf("expr-->termn"); }

;

term : term'*' unary { printf("term-->term*unaryn"); }| term '/' unary { printf("term-->term/unaryn"); }| unary { printf("term-->unaryn"); }

;

unary :'!' unary { printf("unary-->!unaryn"); }| '-' unary %prec UMINUS{ printf("unary-->-unaryn"); }| factor { printf("unary-->factorn"); }

;

factor :'(' bool ')' { printf("factor-->(bool)n"); }| loc { printf("factor-->locn"); }| NUM { printf("factor-->numn"); }| REAL { printf("factor-->realn"); }| TRUE { printf("factor-->truen"); }| FALSE { printf("factor-->falsen"); }

Flex生成代码:

View Code

Test.l:[a-zA-Z_][a-zA-Z_0-9]* {returnID;}

[0-9]+.[0-9]+ {returnREAL;}

[0-9]+ {returnNUM;}"||" {returnOR;}"&&" {returnAND;}"|" {return '|';}"&" {return '&';}"<=" {returnLE;}"=" {returnGE;}">" {return '>';}"!=" {returnNE;}"=" { return '=';}"==" {returnEQ;}"+" {return '+';}"-" {return '-';}"*" {return '*';}"/" {return '/';}"(" {return '(';}")" {return ')';}";" {return ';';}"{" {return '{';}"}" {return '}';}"[" {return '['; }"]" {return ']';}

Test.y:rel : expr'exprexpr<=exprn"); }| expr GE expr { printf("rel-->expr>=exprn"); }| expr '>' expr { printf("rel-->expr>exprn"); }| expr { printf("rel-->exprn"); }

;

expr : expr'+' term { printf("expr-->expr+termn"); }| expr '-' term { printf("expr-->expr-termn"); }| term { printf("expr-->termn"); }

;

term : term'*' unary { printf("term-->term*unaryn"); }| term '/' unary { printf("term-->term/unaryn"); }| unary { printf("term-->unaryn"); }

;

unary :'!' unary { printf("unary-->!unaryn"); }| '-' unary %prec UMINUS{ printf("unary-->-unaryn"); }| factor { printf("unary-->factorn"); }

;

factor :'(' bool ')' { printf("factor-->(bool)n"); }| loc { printf("factor-->locn"); }| NUM { printf("factor-->numn"); }| REAL { printf("factor-->realn"); }| TRUE { printf("factor-->truen"); }| FALSE { printf("factor-->falsen"); }

Yacc生成部分代码：

View Code

#line 1334 "y.tab.c"yyvsp-=yylen;

yyssp-=yylen;

YY_STACK_PRINT (yyss, yyssp);*++yyvsp =yyval;/*Now `shift' the result of the reduction. Determine what state

that goes to, based on the state we popped back to and the rule

number reduced by.*/yyn=yyr1[yyn];

yystate= yypgoto[yyn - YYNTOKENS] + *yyssp;if (0 <= yystate && yystate <= YYLAST && yycheck[yystate] == *yyssp)

yystate=yytable[yystate];elseyystate= yydefgoto[yyn -YYNTOKENS];gotoyynewstate;/*------------------------------------.

| yyerrlab -- here on detecting error |

`------------------------------------*/yyerrlab:/*If not already recovering from an error, report this error.*/

if (!yyerrstatus)

{++yynerrs;#if YYERROR_VERBOSEyyn=yypact[yystate];if (YYPACT_NINF < yyn && yyn

{

YYSIZE_T yysize= 0;int yytype =YYTRANSLATE (yychar);const char*yyprefix;char *yymsg;intyyx;/*Start YYX at -YYN if negative to avoid negative indexes in

YYCHECK.*/

int yyxbegin = yyn < 0 ? -yyn : 0;/*Stay within bounds of both yycheck and yytname.*/

int yychecklim = YYLAST -yyn;int yyxend = yychecklim < YYNTOKENS ?yychecklim : YYNTOKENS;int yycount = 0;

yyprefix= ", expecting";for (yyx = yyxbegin; yyx < yyxend; ++yyx)if (yycheck[yyx + yyn] == yyx && yyx !=YYTERROR)

{

yysize+= yystrlen (yyprefix) +yystrlen (yytname [yyx]);

yycount+= 1;if (yycount == 5)

{

yysize= 0;break;

}

}

yysize+= (sizeof ("syntax error, unexpected")+yystrlen (yytname[yytype]));

yymsg= (char *) YYSTACK_ALLOC (yysize);if (yymsg != 0)

{char *yyp = yystpcpy (yymsg, "syntax error, unexpected");

yyp=yystpcpy (yyp, yytname[yytype]);if (yycount < 5)

{

yyprefix= ", expecting";for (yyx = yyxbegin; yyx < yyxend; ++yyx)if (yycheck[yyx + yyn] == yyx && yyx !=YYTERROR)

{

yyp=yystpcpy (yyp, yyprefix);

yyp=yystpcpy (yyp, yytname[yyx]);

yyprefix= "or";

}

}

yyerror (yymsg);

YYSTACK_FREE (yymsg);

}elseyyerror ("syntax error; also virtual memory exhausted");

}else

例如，程序片断

{

i = 2;

while (i <=100)

{

sum = sum + i;

i = i + 2;

}

}

(注：原本是在windwos环境下编程，最后到unix环境下，发现速度快了，灵活性高了，同时方便了很多。(flex，bison))

test.l

View Code

%option noyywrap%{

#include#include#include

%}%%

"if" {returnIF;}"while" {returnWHILE;}"do" {returnDO;}"break" {returnBREAK;}"int"|"float"|"bool"|"char" {returnBASIC;}"true" {returnTRUE;}"false" {returnFALSE;}"else" {returnELSE;}

[a-zA-Z_][a-zA-Z_0-9]* {returnID;}

[0-9]+.[0-9]+ {returnREAL;}

[0-9]+ {returnNUM;}"||" {returnOR;}"&&" {returnAND;}"|" {return '|';}"&" {return '&';}"<=" {returnLE;}"=" {returnGE;}">" {return '>';}"!=" {returnNE;}"=" { return '=';}"==" {returnEQ;}"+" {return '+';}"-" {return '-';}"*" {return '*';}"/" {return '/';}"(" {return '(';}")" {return ')';}";" {return ';';}"{" {return '{';}"}" {return '}';}"[" {return '['; }"]" {return ']';}"//".*{}

[ nt] {}%%

test.y

View Code

%{

#include#include

%}%left '+' '-'

%left '*' '/'

%nonassoc UMINUS%token NUM AND BASIC BREAK DO ELSE EQ FALSE GE%token ID IF INDEX LE MINUS NE OR REAL TRUE WHILE

KET%token RIGHT_BRA%%program : block { printf("program-->blockn"); }

;

block :'{' decls stmts '}' { printf("block-->{decls stmts}n"); }

;

decls : decls decl { printf("decls-->decls decln"); }| /*empty*/;

decl : type ID';' { printf("decl-->type id;n"); }

;

type : type'[' NUM ']' { printf("type-->type[num]n"); }| BASIC { printf("type-->basicn"); }

;

stmts : stmts stmt { printf("stmts-->stmts stmtn"); }| /*empty*/;

stmt : DO stmt WHILE'(' bool ')' ';' { printf("stmt-->do stmt while(bool);n"); }| IF '(' bool ')' stmt { printf("stmt--if(bool)stmtn"); }| IF '(' bool ')' stmt ELSE stmt { printf("stmt-->if(bool)stmt else stmtn"); }| WHILE '(' bool ')' stmt { printf("stmt-->while(bool)stmtn"); }| BREAK ';' { printf("stmt-->break;n"); }| block { printf("stmt-->blockn"); }| loc '=' bool ';' { printf("stmt-->loc=bool;n"); }

;

loc : loc'[' bool ']' { printf("loc-->loc[bool]n"); }| ID { printf("loc-->idn"); }

;bool : bool OR join { printf("bool-->bool||joinn"); }| join { printf("bool-->joinn"); }

;

join : join AND equality { printf("join-->join&&equalityn"); }| equality { printf("join-->equalityn"); }

;

equality : equality EQ rel { printf("equality-->equality==reln"); }| equality NE rel { printf("equality-->equality!=reln"); }| rel { printf("equality-->reln"); }

;

rel : expr'exprexpr<=exprn"); }| expr GE expr { printf("rel-->expr>=exprn"); }| expr '>' expr { printf("rel-->expr>exprn"); }| expr { printf("rel-->exprn"); }

;

expr : expr'+' term { printf("expr-->expr+termn"); }| expr '-' term { printf("expr-->expr-termn"); }| term { printf("expr-->termn"); }

;

term : term'*' unary { printf("term-->term*unaryn"); }| term '/' unary { printf("term-->term/unaryn"); }| unary { printf("term-->unaryn"); }

;

unary :'!' unary { printf("unary-->!unaryn"); }| '-' unary %prec UMINUS{ printf("unary-->-unaryn"); }| factor { printf("unary-->factorn"); }

;

factor :'(' bool ')' { printf("factor-->(bool)n"); }| loc { printf("factor-->locn"); }| NUM { printf("factor-->numn"); }| REAL { printf("factor-->realn"); }| TRUE { printf("factor-->truen"); }| FALSE { printf("factor-->falsen"); }

;%%#include"lex.yy.c"

intmain()

{extern FILE *yyin;

yyin=fopen("b.txt","r");

yyparse();return 0;

}

yyerror(char *s)

{

printf("%s error!n",s);

}

b.txt

View Code

{

i= 2;while (i <=100)

{

sum= sum +i;

i= i + 2;

}

}

在unix可以生成a.out就能直接用。