自己动手写一个编译器Tiny语言解析器实现

然后,上一篇文章简介Tiny词法分析,实现语言。本文将介绍Tiny的语法分析器的实现。

1 Tiny语言的语法

下图是Tiny在BNF中的文法。

自己动手写一个编译器Tiny语言解析器实现

文法的定义能够看出。INNY语言有以下特点:

1 程序共同拥有5中语句:if语句,repea语句,read语句,write语法和assign语句。

2 if语句以end作为结束符号,if语句和repeat语句同意语句序列作为主体。

3 输入/输出由保留字read和write開始。read语句一次仅仅读出一个变量,而write语句一次仅仅写出一个表达式。

2 Tiny编译器的语法树结构

TINY有两种主要的结构类型:语句和表达式。语句共同拥有5类:(if语句、repeat语句、assign语句、read语句和read语句)。表达式共同拥有3类(算符标的是、常量表达式和标识符表达式)。因此,语法树节点首先安装它是语句还是表达式来进行分类,接着依据语句或表达式的种类进行再次分类。

树节点最大可有3个孩子的结构(仅在带有else部分的if

语句才用到)。

语句通过同属域而不是子域来排序,即由父亲到他的孩子的唯一物理连接是到最左孩子的。孩子则在一个标准连接表中自左向右连接到一起,这样的连接称作同属连接,用于差别父子连接。

自己动手写一个编译器Tiny语言解析器实现自己动手写一个编译器Tiny语言解析器实现

左边的图片是同属连接,右边的图片表示父子连接。

一个Tiny语法树节点的C声明例如以下:

/***********   Syntax tree for parsing ************/
/**************************************************/ typedef enum {StmtK,ExpK} NodeKind;
typedef enum {IfK,RepeatK,AssignK,ReadK,WriteK} StmtKind;
typedef enum {OpK,ConstK,IdK} ExpKind; /* ExpType is used for type checking */
typedef enum {Void,Integer,Boolean} ExpType; #define MAXCHILDREN 3 typedef struct treeNode
{ struct treeNode * child[MAXCHILDREN];
struct treeNode * sibling;
int lineno;
NodeKind nodekind;
union { StmtKind stmt; ExpKind exp;} kind;
union { TokenType op;
int val;
char * name; } attr;
ExpType type; /* for type checking of exps */
} TreeNode; /**************************************************/

以下画出语法树的结构。用矩形框表示语句节点。用圆形框或椭圆形框表示表达式节点。

仍然以Tiny语言的阶乘为例,给出Tiny程序的语法树。

{ Sample program
in TINY language -
computes factorial
}
read x; { input an integer }
if 0 < x then { don't compute if x <= 0 }
fact := 1;
repeat
fact := fact * x;
x := x - 1
until x = 0;
write fact { output factorial of x }
end

自己动手写一个编译器Tiny语言解析器实现

3 使用Yacc生成Tiny分析程序

源代码例如以下。相应这第一节给出的Tiny的BNF文法。

%{
#define YYPARSER /* distinguishes Yacc output from other code files */ #include "globals.h"
#include "util.h"
#include "scan.h"
#include "parse.h" #define YYSTYPE TreeNode *
static char * savedName; /* for use in assignments */
static int savedLineNo; /* ditto */
static TreeNode * savedTree; /* stores syntax tree for later return */ %} %token IF THEN ELSE END REPEAT UNTIL READ WRITE
%token ID NUM
%token ASSIGN EQ LT PLUS MINUS TIMES OVER LPAREN RPAREN SEMI
%token ERROR %% /* Grammar for TINY */ program : stmt_seq
{ savedTree = $1;}
;
stmt_seq : stmt_seq SEMI stmt
{ YYSTYPE t = $1;
if (t != NULL)
{ while (t->sibling != NULL)
t = t->sibling;
t->sibling = $3;
$$ = $1; }
else $$ = $3;
}
| stmt { $$ = $1; }
;
stmt : if_stmt { $$ = $1; }
| repeat_stmt { $$ = $1; }
| assign_stmt { $$ = $1; }
| read_stmt { $$ = $1; }
| write_stmt { $$ = $1; }
| error { $$ = NULL; }
;
if_stmt : IF exp THEN stmt_seq END
{ $$ = newStmtNode(IfK);
$$->child[0] = $2;
$$->child[1] = $4;
}
| IF exp THEN stmt_seq ELSE stmt_seq END
{ $$ = newStmtNode(IfK);
$$->child[0] = $2;
$$->child[1] = $4;
$$->child[2] = $6;
}
;
repeat_stmt : REPEAT stmt_seq UNTIL exp
{ $$ = newStmtNode(RepeatK);
$$->child[0] = $2;
$$->child[1] = $4;
}
;
assign_stmt : ID { savedName = copyString(tokenString);
savedLineNo = lineno; }
ASSIGN exp
{ $$ = newStmtNode(AssignK);
$$->child[0] = $4;
$$->attr.name = savedName;
$$->lineno = savedLineNo;
}
;
read_stmt : READ ID
{ $$ = newStmtNode(ReadK);
$$->attr.name =
copyString(tokenString);
}
;
write_stmt : WRITE exp
{ $$ = newStmtNode(WriteK);
$$->child[0] = $2;
}
;
exp : simple_exp LT simple_exp
{ $$ = newExpNode(OpK);
$$->child[0] = $1;
$$->child[1] = $3;
$$->attr.op = LT;
}
| simple_exp EQ simple_exp
{ $$ = newExpNode(OpK);
$$->child[0] = $1;
$$->child[1] = $3;
$$->attr.op = EQ;
}
| simple_exp { $$ = $1; }
;
simple_exp : simple_exp PLUS term
{ $$ = newExpNode(OpK);
$$->child[0] = $1;
$$->child[1] = $3;
$$->attr.op = PLUS;
}
| simple_exp MINUS term
{ $$ = newExpNode(OpK);
$$->child[0] = $1;
$$->child[1] = $3;
$$->attr.op = MINUS;
}
| term { $$ = $1; }
;
term : term TIMES factor
{ $$ = newExpNode(OpK);
$$->child[0] = $1;
$$->child[1] = $3;
$$->attr.op = TIMES;
}
| term OVER factor
{ $$ = newExpNode(OpK);
$$->child[0] = $1;
$$->child[1] = $3;
$$->attr.op = OVER;
}
| factor { $$ = $1; }
;
factor : LPAREN exp RPAREN
{ $$ = $2; }
| NUM
{ $$ = newExpNode(ConstK);
$$->attr.val = atoi(tokenString);
}
| ID { $$ = newExpNode(IdK);
$$->attr.name =
copyString(tokenString);
}
| error { $$ = NULL; }
; %% int yyerror(char * message)
{ fprintf(listing,"Syntax error at line %d: %s\n",lineno,message);
fprintf(listing,"Current token: ");
printToken(yychar,tokenString);
Error = TRUE;
return 0;
} TreeNode * parse(void)
{ yyparse();
return savedTree;
}

4 执行程序

点击下载完整可执行代码,按以下的步骤便可执行。

Step 1 在命令行输入

$ ./build.sh

Step 2 改动生成的y.tab.c代码。

yacc生成的y.tab.c中使用yylex()函数来获取字符,须要替换成我们在上一篇文章中提供的由lex生成的getToken()函数。

在y.tab.c中找到

yychar = yylex ();

替换成

yychar = getToken ();

Step 3 make && run

在命令行中输入例如以下命令便可执行程序

$ make
$ ./tiny.out sample.tny

程序执行后会打印出语法树。节点间关系以空格标识。

TINY COMPILATION: sample.tny

Syntax tree:
Read: x
If
Op: <
Const: 0
Id: x
Assign to: fact
Const: 1
Repeat
Assign to: fact
Op: *
Id: fact
Id: x
Assign to: x
Op: -
Id: x
Const: 1
Op: =
Id: x
Const: 0
Write
Id: fact

大家能够对比着第二节给出的图片,查看输出的语法树结构,体会一下Tiny语法树中相应的数据结构的设计。

5 小结

本文主要介绍了Tiny语言的语法分析器的实现过程。下一篇文章将介绍Tiny语言的语义分析,主要包含符号表的生成和类型检查的算法。

版权声明:本文博主原创文章,博客,未经同意不得转载。

上一篇:一个简单的json解析器


下一篇:高手教您编写简单的JSON解析器