接着上一篇文章介绍的Tiny语言的词法分析的实现，本文将介绍Tiny语言的语法分析器的实现。
1 Tiny语言的语法
下图是Tiny在BNF中的文法，
文法的定义可以看出，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语法树节点的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 3typedef 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; repeatfact := fact * x;x := x – 1 until x = 0; write fact { output factorial of x }end
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; 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收敛自己的脾气，偶尔要刻意沉默，
