parse.c

tiny编译器++

/****************************************************/
/* File: parse.c                                    */
/* The parser implementation for the TINY compiler  */
/* Compiler Construction: Principles and Practice   */
/* Kenneth C. Louden                                */
/****************************************************/

#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 * program(void);
static TreeNode * decl_sequence(void);
static TreeNode * declaration(void);
static TreeNode * int_decl(void);
static TreeNode * bool_decl(void);
static TreeNode * string_decl(void);
static TreeNode * bool_exp(void);
static TreeNode * bool_term(void);
static TreeNode * bool_comp(void);
static TreeNode * bool_factor(void);
static TreeNode * stmt_sequence(void);
static TreeNode * statement(void);
static TreeNode * if_stmt(void);
static TreeNode * repeat_stmt(void);
static TreeNode * assign_stmt(void);
static TreeNode * read_stmt(void);
static TreeNode * write_stmt(void);
static TreeNode * while_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, "\n>>> ");
	fprintf(listing, "Syntax error at line %d: %s", lineno, message);
	Error = TRUE;
}

static void match(TokenType expected)
{
	if (token == expected)
		token = getToken();
	else
	{
		syntaxError("unexpected token -> ");
		printToken(token, tokenString);
		fprintf(listing, "");
	}
}

TreeNode * program(void)
{
	TreeNode * t = newProgNode();
	if ((t != NULL) && ((token == INT) ||
		(token == BOOL) || (token == STRING)))
	{
		t->child[0] = decl_sequence();
	}
	if (t != NULL)
	{
		t->child[1] = stmt_sequence();
	}

	return t;
}

TreeNode * decl_sequence(void)
{
	TreeNode * t = declaration();
	TreeNode * p = t;

	while (token != ENDFILE && ((token == INT)
		|| (token == BOOL) || (token == STRING) || (token == SEMI)))
	{
		TreeNode * q;
		match(SEMI);
		q = declaration();
		if (q != NULL)
		{
			if (t == NULL)
				t = p = q;
			else /* now p cannot be NULL either */
			{
				p->sibling = q;
				p = q;
			}
		}
	}

	return t;
}

TreeNode * declaration()
{
	TreeNode * t = NULL;
	switch (token)
	{
	case INT:
		int_decl();
		break;
	case BOOL:
		bool_decl();
		break;
	case STRING:
		string_decl();
		break;
	case ENDFILE:
		break;
	default:
		/*syntaxError("unexpected token -> ");
		printToken(token, tokenString);
		token = getToken();*/
		break;
	}
	return t;
}

TreeNode * int_decl(void)
{
	TreeNode * t = newDeclNode(IntK);
	match(INT);
	match(ID);

	return t;
}

TreeNode * bool_decl(void)
{
	TreeNode * t = newDeclNode(BoolK);
	match(BOOL);
	match(ID);

	return t;
}

TreeNode * string_decl(void)
{
	TreeNode * t = newDeclNode(StringK);
	match(STRING);
	match(ID);

	return t;
}

TreeNode * bool_exp(void)
{
	TreeNode * t = bool_term();
	while (token == OR)
	{
		TreeNode * p = newExpNode(OpK);
		if (p != NULL)
		{
			p->child[0] = t;
			p->attr.op = token;
			t = p;
			match(token);
			t->child[1] = bool_term();
		}
	}
	return t;
}

TreeNode * bool_term(void)
{
	TreeNode * t = bool_comp();
	while (token == AND)
	{
		TreeNode * p = newExpNode(OpK);
		if (p != NULL)
		{
			p->child[0] = t;
			p->attr.op = token;
			t = p;
			match(token);
			p->child[1] = bool_comp();
		}
	}
	return t;
}

TreeNode * bool_comp(void)
{
	TreeNode * t = bool_factor();
	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] = bool_factor();
	}

	return t;
}

TreeNode * bool_factor(void)
{
	TreeNode * t = NULL;
	switch (token)
	{
	case TINYTRUE:
		t = newExpNode(ConstK);
		if (t != NULL)
		{
			t->attr.val = 1;
		}
		match(TINYTRUE);
		break;
	case TINYFALSE:
		t = newExpNode(ConstK);
		if (t != NULL)
		{
			t->attr.val = 0;
		}
		match(TINYFALSE);
		break;
	case ID:
		t = newExpNode(IdK);
		if (t != NULL)
		{
			t->attr.name = copyString(tokenString);
		}
		match(ID);
		break;
	case NUM:
		t = newExpNode(ConstK);
		if (t != NULL)
		{
			t->attr.val = atoi(tokenString);
		}
		match(NUM);
		break;
	case LPAREN:
		match(LPAREN);
		t = bool_exp();
		match(RPAREN);
		break;
	case NOT:
		match(NOT);
		t = bool_exp();
		break;
	default:
		syntaxError("unexpected token -> ");
		printToken(token, tokenString);
		token = getToken();
		break;
	}
	return t;
}

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 */
			{
				p->sibling = q;
				p = q;
			}
		}
	}
	return t;
}

TreeNode * statement(void)
{
	TreeNode * t = NULL;
	switch (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;
	case WHILE:
		t = while_stmt();
		break;
	case ELSE:	/* handle error */
	case UNTIL:
	case END:
	case ENDFILE:
		break;
	default:
		syntaxError("unexpected token -> ");
		printToken(token, tokenString);
		token = getToken();
		break;
	} /* end case */
	return t;
}

TreeNode * if_stmt(void)
{
	TreeNode * t = newStmtNode(IfK);
	match(IF);
	if (t != NULL)
		t->child[0] = bool_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;
}

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] = bool_exp();
	return t;
}

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;
}

TreeNode * read_stmt(void)
{
	TreeNode * t = newStmtNode(ReadK);
	match(READ);
	if ((t != NULL) && (token == ID))
		t->attr.name = copyString(tokenString);
	match(ID);
	return t;
}

TreeNode * write_stmt(void)
{
	TreeNode * t = newStmtNode(WriteK);
	match(WRITE);
	if (t != NULL)
		t->child[0] = exp();
	return t;
}

TreeNode * while_stmt(void)
{
	TreeNode * t = newStmtNode(WhileK);
	match(WHILE);
	if (t != NULL)
	{
		t->child[0] = bool_exp();
	}
	match(DO);
	if (t != NULL)
	{
		t->child[1] = stmt_sequence();
	}
	match(END);

	return t;
}

TreeNode * exp(void)
{
	TreeNode * t = NULL;
	if (token == NOT)
	{
		t = bool_exp();
	}
	else if (token == STR)	/* handle string type */
	{
		t = newExpNode(ConstK);
		t->attr.name = copyString(tokenString);
		match(STR);
	}
	else
	{
		switch (getToken())
		{
		case PLUS:
		case MINUS:
		case TIMES:
		case OVER:
			ungetNextToken();
			t = simple_exp();
			break;
		case EQ:
		case LT:
		case OR:
		case AND:
		case NOT:
			ungetNextToken();
			t = bool_exp();
			break;
		case SEMI:
			ungetNextToken();
			if (token == ID)
			{
				match(ID);
			}
			else
			{
				match(NUM);
			}
			break;
		default:
			syntaxError("unexpected token -> ");
			printToken(token, tokenString);
			token = getToken();
			break;
		}
	}

	return t;
}

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;
}

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;
}

TreeNode * factor(void)
{
	TreeNode * t = NULL;
	switch (token)
	{
	case NUM:
		t = newExpNode(ConstK);
		if (t != NULL)
			t->attr.val = atoi(tokenString);
		match(NUM);
		break;
	case ID:
		t = newExpNode(IdK);
		if (t != NULL)
			t->attr.name = copyString(tokenString);
		match(ID);
		break;
	case LPAREN:
		match(LPAREN);
		t = exp();
		match(RPAREN);
		break;
	default:
		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 = program();
	if (token != ENDFILE)
		syntaxError("Code ends before file\n");
	return t;
}