lex+yacc 构造语法树（一）

68 阅读 0 评论 45 点赞

我是靠谱客的博主鲤鱼奇异果，最近开发中收集的这篇文章主要介绍lex+yacc 构造语法树（一），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

本文章是基于一种为 small C语言的语法规则，通过lex和yacc编写归约规则，使得当输入一个合法程序的时候，输出基于归约规则和语法规则的语法树，该语法树的表现形式为缩进，同列的元素为兄弟节点，往右推进一列的元素为儿子节点。

假定small C的语法规则如下：

INT =>
/* integer 1*/
ID => /* identier2*/
SEMI => ;
COMMA => ,
DOT => .
BINARYOP => /* binary operators3 */
UNARYOP => /* unary operators4 */
ASSIGNOP => =
TYPE => int
LP => (
RP => )
LB => [
RB => ]
LC => {
RC => }
STRUCT => struct
RETURN ) return
IF => if
ELSE => else
BREAK => break
CONT => continue
FOR => for

1 A sequence of digits or digits followed by x(0X)" or " without spaces.
2 A character string consisting of alphabetic characters, digits and the underscore. In addition, digits can't be the rst character.

符号的优先级如下：

确定好这些规则后，我们便可以写出lex.l文件如下：

%{
#include <stdlib.h>
#include <string.h>
#include "y.tab.h"
void
yyerror(char *s);
int No_Line=1;
struct Node* newNode(char* nameIn,int line);
%}
%%
n
{No_Line++;}
int
{ yylval.token_p= newNode(yytext,No_Line);
return TYPE;}
struct
{ yylval.token_p= newNode(yytext,No_Line);
return STRUCT; }
return
{ yylval.token_p= newNode(yytext,No_Line);
return RETURN; }
if
{ yylval.token_p= newNode(yytext,No_Line);
return IF ; }
else
{ yylval.token_p= newNode(yytext,No_Line);
return ELSE ;}
break
{ yylval.token_p= newNode(yytext,No_Line);
return BREAK;}
cont
{ yylval.token_p= newNode(yytext,No_Line);
return CONT; }
for
{ yylval.token_p= newNode(yytext,No_Line);
return FOR;
}
read
{ yylval.token_p= newNode(yytext,No_Line);
return READ;
}
write
{ yylval.token_p= newNode(yytext,No_Line);
return WRITE;
}
0(x|X)([0-9A-F]{1,8})
{
yylval.token_p= newNode(yytext,No_Line);
return INT;
}
[0-9]{1,10}
{
yylval.token_p= newNode(yytext,No_Line);
return INT;
}
[a-zA-Z_]([a-zA-Z_0-9]*)
{
yylval.token_p= newNode(yytext,No_Line);
return ID;
}
[;]
{
yylval.token_p= newNode(yytext,No_Line);
return SEMI;
}
[,]
{
yylval.token_p= newNode(yytext,No_Line);
return COMMA;
}
[.]
{
yylval.token_p= newNode(yytext,No_Line);
return DOT;
}
(!)|(++)|(--)|(~)
{
yylval.token_p= newNode(yytext,No_Line);
return UNARYOP;
}
[-]
{yylval.token_p = newNode(yytext, No_Line);
return (SUB);}
(*)|(/)|(%)
{
yylval.token_p= newNode(yytext,No_Line);
return BINARYOP1;
}
(+)
{
yylval.token_p= newNode(yytext,No_Line);
return BINARYOP2;
}
(<<)|(>>)
{
yylval.token_p= newNode(yytext,No_Line);
return BINARYOP3;
}
(>)|(>=)|(<)|(<=)
{
yylval.token_p= newNode(yytext,No_Line);
return BINARYOP4;
}
(==)|(!=)
{
yylval.token_p= newNode(yytext,No_Line);
return BINARYOP5;
}
[&]
{
yylval.token_p= newNode(yytext,No_Line);
return BINARYOP6;
}
"^"
{
yylval.token_p= newNode(yytext,No_Line);
return BINARYOP7;
}
(|)
{
yylval.token_p= newNode(yytext,No_Line);
return BINARYOP8;
}
(&&)
{
yylval.token_p= newNode(yytext,No_Line);
return BINARYOP9;
}
(||)
{
yylval.token_p= newNode(yytext,No_Line);
return BINARYOP10;
}
(+=)|(-=)|(*=)|(/=)|(&=)|(^=)|(|=)|(<<=)|(>>=)
{
yylval.token_p= newNode(yytext,No_Line);
return BINARYOP11;
}
[=]
{ yylval.token_p= newNode(yytext,No_Line);
return ASSIGNOP;}
[(]
{ yylval.token_p= newNode(yytext,No_Line);
return LP;
}
[)]
{ yylval.token_p= newNode(yytext,No_Line);
return RP;
}
[[]
{ yylval.token_p= newNode(yytext,No_Line);
return LB;
}
[]]
{ yylval.token_p= newNode(yytext,No_Line);
return RB;
}
[{]
{ yylval.token_p= newNode(yytext,No_Line);
return LC;
}
[}]
{ yylval.token_p= newNode(yytext,No_Line);
return RC;
}
[ t]+
;
.
yyerror("Error:invalid input.n");
%%
int yywrap() {
return 1;
}

由以上的程序可以看出，我们根据语法规则给每个元素判定它所属的token，并新建一个记录了元素内容和它所属行数的node。node的新建代码如下：

struct Node* newNode (char* node_name,int line)
{
struct Node *p=(struct Node*)malloc(sizeof(struct Node));
if (p==NULL)
{
printf("Error:out of memory.n");
exit(1);
}
strncpy(p->name,node_name,20);
p->brother=NULL;
p->child=NULL;
p->No_Line=line;
p->No_Child=0;
p->col=0;
p->IsBegin=0;
return p;
}

通过编译lex.l文件可以得到lex.yy.c，为下一步yacc文件的编写打下基础。这部分将在下一章详细介绍。