Tiny言語コンパイルプログラムの文法分析
13661 ワード
Tiny言語コンパイルプログラムの文法分析
約束:は、再帰的降下分析法を用いて、各構文記号のためのサブルーチンを作成する.各サブルーチンに入る前に新しいTokenを読み込みました. 文法構造の内部表現形式はシンタックスツリーであり、データ構造はglobals.hのtreeNodeである.文法分析をしながら文法構造の内部表現である文法ツリーを構築します. 構文解析器parse.c
約束:
/****************************************************/
/* File: parse.c */
/* The parser implementation for the TINY compiler */
/****************************************************/
#include "globals.h"
#include "util.h"
#include "scan.h"
#include "parse.h"
static TokenType token; /* holds current token */
/* function prototypes for recursive calls */
static TreeNode * stmt_sequence(void); /* */
static TreeNode * statement(void); /* */
static TreeNode * if_stmt(void); /* if */
static TreeNode * repeat_stmt(void); /* */
static TreeNode * assign_stmt(void); /* */
static TreeNode * read_stmt(void); /* */
static TreeNode * write_stmt(void); /* */
static TreeNode * exp(void); /* */
static TreeNode * simple_exp(void); /* */
static TreeNode * term(void); /* */
static TreeNode * factor(void); /* */
/* */
static void syntaxError(char * message)
{ fprintf(listing,"
>>> ");
fprintf(listing,"Syntax error at line %d: %s",lineno,message);
Error = TRUE;
}
/* token */
static void match(TokenType expected)
{ if (token == expected) token = getToken();/* getToken， */
else {
syntaxError("unexpected token -> ");
printToken(token,tokenString);
fprintf(listing," ");
}
}
/* stmt_sequence */
TreeNode * stmt_sequence(void)
{ TreeNode * t = statement();
TreeNode * p = t;
while ((token!=ENDFILE) && (token!=END) &&
(token!=ELSE) && (token!=UNTIL))/* */
{ TreeNode * q;
match(SEMI);/* */
q = statement();
if (q!=NULL) {
if (t==NULL) t = p = q;
else /* now p cannot be NULL either *//* t NULL， p NULL */
{ p->sibling = q;/* state */
p = q;
}
}
}
return t;
}
/* statement */
TreeNode * statement(void)
{ TreeNode * t = NULL;
switch (token) {/* token， */
case IF : t = if_stmt(); break;
case REPEAT : t = repeat_stmt(); break;
case ID : t = assign_stmt(); break;
case READ : t = read_stmt(); break;
case WRITE : t = write_stmt(); break;
default : syntaxError("unexpected token -> ");
printToken(token,tokenString);
token = getToken();
break;
} /* end case */
return t;
}
/* if_stmt */
TreeNode * if_stmt(void)
{
TreeNode * t = newStmtNode(IfK);
match(IF);
if (t!=NULL)
t->child[0] = exp();
match(THEN);
if (t!=NULL)
t->child[1] = stmt_sequence();
if (token==ELSE) {
match(ELSE);
if (t!=NULL)
t->child[2] = stmt_sequence();
}
match(END);
return t;
}
/* repeat_stmt */
TreeNode * repeat_stmt(void)
{
TreeNode * t = newStmtNode(RepeatK);
match(REPEAT);
if(t!=NULL){
t->child[0] = stmt_sequence();
}
match(UNTIL);
if(t!=NULL){
t->child[1] = exp();
}
return t;
}
/* assign_stmt */
TreeNode * assign_stmt(void)
{
TreeNode * t = newStmtNode(AssignK);
if((t!=NULL)&&(token==ID)){
t->attr.name = copyString(tokenString);
}
match(ID);
match(ASSIGN);
if(t!=NULL){
t->child[0] = exp();
}
return t;
}
/* read_stmt */
TreeNode * read_stmt(void)
{
TreeNode * t = newStmtNode(ReadK);
match(READ);
if((t!=NULL)&&(token==ID)){
t->attr.name = copyString(tokenString);
}
match(ID);
return t;
}
/* write_stmt */
TreeNode * write_stmt(void)
{
TreeNode * t = newStmtNode(WriteK);
match(WRITE);
if(t!=NULL){
t->child[0] = exp();
}
return t;
}
/* exp */
TreeNode * exp(void)
{ TreeNode * t = simple_exp();
if ((token==LT)||(token==EQ)) {
TreeNode * p = newExpNode(OpK);
if (p!=NULL) {
p->child[0] = t;
p->attr.op = token;
t = p;
}
match(token);
if (t!=NULL)
t->child[1] = simple_exp();
}
return t;
}
/* simple_stmt */
TreeNode * simple_exp(void)
{
TreeNode * t = term();
while ((token==PLUS)||(token==MINUS)){
TreeNode * p = newExpNode(OpK);
if (p!=NULL) {
p->child[0] = t;
p->attr.op = token;
t = p;
match(token);
t->child[1] = term();
}
}
return t;
}
/* term */
TreeNode * term(void)
{
TreeNode * t = factor();
while ((token==TIMES)||(token==OVER)){
TreeNode * p = newExpNode(OpK);
if (p!=NULL){
p->child[0] = t;
p->attr.op = token;
t = p;
match(token);
p->child[1] = factor();
}
}
return t;
}
/* factor */
TreeNode * factor(void)
{
char msgerror[100];
TreeNode * t = NULL;
switch (token) {
case NUM :
t = newExpNode(ConstK);
if ((t!=NULL) && (token==NUM)){
t->attr.val = atoi(tokenString);
}
match(NUM);
break;
case ID :
t = newExpNode(IdK);
if ((t!=NULL) && (token==ID)){
t->attr.name = copyString(tokenString);
}
match(ID);
break;
case LPAREN :
match(LPAREN);
t = exp();
match(RPAREN);
break;
default:
strcpy(msgerror,"unexpected token -> ");
strcat(msgerror,tokenString);
syntaxError(msgerror);
//syntaxError("unexpected token -> ");
//printToken(token,tokenString);
token = getToken();
break;
}
return t;
}
/****************************************/
/* the primary function of the parser */
/****************************************/
/* Function parse returns the newly
* constructed syntax tree
*/
TreeNode * parse(void)
{ TreeNode * t;
token = getToken();
t = stmt_sequence();
if (token!=ENDFILE)
syntaxError("Code ends before file
");
return t;
}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