SNL语言吉大计算机编译原理课程设计.doc

/* analyze.h */
#ifndef _ANALYZE_H_
#define _ANALYZE_H_

#define ScopeMaxLevel 20

#include "TreeNode.h"

enum IdKind { typeKind , varKind , procKind };
enum TypeKind { intType , charType , arrayType , recordType , boolType};
enum AccessKind { dir , indir };

struct TypeIR;
struct SymbolChain;

struct ParamChain
{
SymbolChain * entry;
ParamChain * next;
};
struct FieldChain
{
char idName[10];
TypeIR * unitType;
int offset;
FieldChain * next;
};
struct TypeIR
{
int size;
TypeKind kind;
union
{
struct
{
TypeIR * indexType;
TypeIR * elementType;
}ArrayAttr;
FieldChain * body;
}More;
};

struct AttributeIR
{
TypeIR * idType;
IdKind kind;
union More
{
struct
{
AccessKind access;
int level;
int offset;
}VarAttr;
struct
{
int level;
ParamChain * param;
int code;
int size;
}ProcKind;
};
};
struct SymbolChain
{
int line;
char idName[10];
AttributeIR attrIR;
SymbolChain * next;
};

class analyze
{
private:
TreeNode * root;
int level;
SymbolChain * Scope[ScopeMaxLevel];
SymbolChain * Backup[ScopeMaxLevel];
private:
ofstream output;
analyze(ofstream o, TreeNode * r);
~analyze();

void PrintSymbolChain();
bool FindField();
bool SearchChain(char *,int,SymbolChain * &);
bool FindEntry(char *,bool,SymbolChain * &);
bool FindEntry2(char *,SymbolChain * &,IdKind);
bool Enter(char *,SymbolChain * &);
void DestroyChain();
void CreateChain();
void analysis(TreeNode *);
public:
void RecordType(TreeNode * t,SymbolChain * entry);
void ArrayType(TreeNode * t , SymbolChain * entry);
void nameType(TreeNode * t , SymbolChain * entry);
SymbolChain * NewTy();
void TypeProcess(TreeNode * t , SymbolChain *);
void Body(TreeNode * t);
void ProcDecPart(TreeNode * t);
void VarDecPart(TreeNode * t);
void TypeDecPart(TreeNode * t);
static void doAnalyze(TreeNode * , ofstream );
};
#endif

/* parse.h */

#ifndef _PARSE_H_
#define _PARSE_H_

#include"TokenList.h"
#include"TreeNode.h"

class parse{
private:
ofstream * output;
TokenList * head;
TokenList * cur;
TreeNode * root;

void fieldvarMore(TreeNode * t);
TreeNode * fieldvar();
void variMore(TreeNode * t);
TreeNode * variable();
TreeNode * factor();
TreeNode * term();
TreeNode * Simple_exp();
TreeNode * Exp();
TreeNode * ActParamMore();
TreeNode * ActParamList();
TreeNode * CallStmRest();
TreeNode * ReturnStm();
TreeNode * OutputStm();
TreeNode * InputStm();
TreeNode * LoopStm();
TreeNode * ConditionalStm();
TreeNode * ArrayRest();
TreeNode * FieldRest();
TreeNode * AssignmentRest();
TreeNode * AllCall();
TreeNode * Stm();
TreeNode * StmMore();
TreeNode * StmList();
TreeNode * ProgramBody();
TreeNode * procBody();
TreeNode * ProcDecPart();
void FidMore(TreeNode * t);
void FormList(TreeNode * t);
TreeNode * Param();
TreeNode * ParamMore();
TreeNode * ParamDecList();
void ParamList(TreeNode * t);
TreeNode * ProcDeclaration();
TreeNode * ProcDec();
void varIdMore(TreeNode * t);
void VarIdList(TreeNode * t);
TreeNode * VarDecMore();
TreeNode * VarDecList();
TreeNode * VarDeclaration();
TreeNode * VarDec();
void IdMore(TreeNode * t);
void IdList(TreeNode * t);
TreeNode * FieldDecMore();
TreeNode * FieldDecList();
void RecType(TreeNode * t);
void ArrayType(TreeNode * t);
void StructureType(TreeNode * t);
void BaseType(TreeNode * t);
void TypeDef(TreeNode * t);
void TypeId(TreeNode * t);
TreeNode * TypeDecMore();
TreeNode * TypeDecList();
TreeNode * TypeDeclaration();
TreeNode * TypeDec();
TreeNode * DeclarePart();
TreeNode * DeclarePart2();
TreeNode * ProgramHead();
TreeNode * Program();

ofstream * getOutputStream();
TokenList * getCur();
TokenList * getHead();

char * getNextTokenSem();
char * getCurrentTokenSem();

void setCur(TokenList * t);
void setOutputStream(ofstream * o);
void setHead(TokenList * t);

bool read();
bool matchSem(const char[]);
bool matchLex(LexType l);

bool matchNextLex(LexType l);
bool matchNextSem(const char s[]);
LexType getNextTokenLex();
LexType getCurTokenLex();

parse(TokenList * ,ofstream *);
~parse();

void printTree(TreeNode * root);

int getCurrentTokenLineNO();
public:
static TreeNode * doParse(TokenList * , ofstream *);
};

#endif

/* scan.h */
#ifndef _SCAN_H_
#define _SCAN_H_

#include "TokenList.h"

class scan
{
public:
static TokenList * doScan(ifstream * ,ofstream *);

private:
ifstream * inputFile;
ofstream * outputFile;
scan();
scan(ifstream * , ofstream *);
~scan();
ifstream * getInputFile();
ofstream * getOutputFile();
void setInputFile(ifstream *);
void setOutputFile(ofstream *);
void clearArray();
char getNextChar();
LexType lookup(char *);
TokenList * getTokenList();
void printTokenList(TokenList *);

};
#endif

/* Token.h */
#ifndef _TOKEN_H_
#define _TOKEN_H_
#include<iostream>
#include<fstream>
using namespace std;
enum LexType {
ID, //标识符
CHARC, //字符串
RESERVEDWORD, //保留字
INST, //整型常量符
OP, //运算符
ASSIGN, //赋值运算符
DELIMITER, //分界符
RANGE, //数组下标
POINTER, //结构类型成员运算符
DOT, //程序结束标志
ENDFILE, //文件结束标志
ERROR, //错误符号
};

class Token
{
public:
Token();
Token(int, char*,LexType);
~Token();
void printToken(ofstream *);
void printToken1();
void setLex(LexType);
void setSem(char *);
void setLine(int);
int getLine();
LexType getLex();
char * getSem();

private:
int line;
char * sem;
LexType lex;
};
#endif

/*TokenList.h*/
#ifndef _TOKENLIST_H_
#define _TOKENLIST_H_

#include "Token.h"

class TokenList{

public:
TokenList();
~TokenList();
void setToken(Token *);
void setNext(TokenList *);
void setNumber(int);
int getNumber();
Token * getToken();
TokenList * getNext();
void append();

private:
int number;
Token * token;
TokenList * next;
};

#endif
/* Treenode.h */
#ifndef _TREENODE_H_
#define _TREENODE_H_
#include <string>
#include <iostream>
#include <fstream>
using namespace std;
enum NODE_KIND //语法树节点
{
ProK, //根标志
PheadK, //程序头

TypeK, //类型声明
VarK, //变量声明
ProcDecK, //单个过程声明
StmLK, //语句序列

DecK, //声明节点
StmtK, //语句节点
ExpK //表达式节点
};
//********************************************************
enum DEC_KIND //具体声明
{
ArrayK, //数组
CharK, //字符
IntegerK, //整型
RecordK, //记录
IdK //Type定义的类型
};
enum STMT_KIND //具体语句
{
IfK, //if语句
WhileK, //while语句
AssignK, //赋值语句
ReadK, //read语句
WriteK, //write语句
CallK, //过程调用语句
ReturnK //返回语句
};
enum EXP_KIND //具体表达式
{
OpK, //操作符
ConstK, //常整型
IdEK, //标识符
ArrayEK, //数组
FieldEK, //域
CHAREK //单字符
};
union KIND//记录语法树节点具体类型
{
DEC_KIND dec;//声明
STMT_KIND stmt;//语句
EXP_KIND exp;//表达式
};
//*****************************************************************
enum PARAM_TYPE//过程参数属性
{
valparamtype,//值参
varparamtype//变参
};
enum EXP_OP_TYPE//表达式运算符类型
{
LT,
EQ,
PLUS,
MINUS,
TIMES,
OVER
};
struct ArrayAttr//数组属性
{
int low;//上界
int up;//下届
DEC_KIND childType;//类型
};
struct ProcAttr //过程属性
{
PARAM_TYPE paramtype;
};
struct ExpAttr //表达式属性
{
EXP_OP_TYPE op;
int val;
};
struct Attr //属性
{
ArrayAttr arrayattr;
ProcAttr procattr;
ExpAttr expattr;
};
class TreeNode
{
public:
NODE_KIND nodekind;

TreeNode * child[3];
TreeNode * sibling;
char * idname[3];
int lineno;
KIND kind;
char * type_name;
Attr attr;
int idnum;
int childnum;
public:

//设置表达式属性*****************************************************
void setAttrExpVal(int i);
void setAttrExpOpType(char * s);
EXP_OP_TYPE getAttrExpOpType();
//设置过程属性*******************************************************
void setProcAttrParamType(PARAM_TYPE d);
//设置数组属性*******************************************************
void setArrayAttrType(DEC_KIND d);
void setArrayAttrUp(int u);
void setArrayAttrLow(int l);

void setLineNo(int l);
void setNodeKind(NODE_KIND n);
void setTypeName(char * s);
void setIdName(char *s);

void setChild (int i , TreeNode * c);
void setChild(TreeNode *);
void setSibling(TreeNode * t);

void setKindOfDec(DEC_KIND);
DEC_KIND getKindOfDec();
void setKindOfStmt(STMT_KIND);
void setKindOfExp(EXP_KIND);

TreeNode * getSibling();
TreeNode * getChild(int i);
int getIdNum();
char * getIdName(int i);

~TreeNode();
TreeNode();
TreeNode(NODE_KIND n);

void printTreeNode();
void printTreeNode(ofstream * out);

};
#endif
/* zparse.h */
#ifndef _ZPARSE_H_
#define _ZPARSE_H_
#include "TreeNode.h"
#include "TokenList.h"

#define Sy_Stack_Max 20 //符号栈大小
#define OpS_Stack_Max 20 //操作符栈大小
#define OpN_Stack_Max 20 //操作数栈大小
//******************************************************
//********************非终极符集************************
//******************************************************
enum VN_VT{
VN_Program,//开始符
VN_ProgramHead,
VN_ProgramName,
VN_DeclarePart,
VN_TypeDec,
VN_TypeDeclaration,
VN_TypeDecList,
VN_TypeDecMore,
VN_TypeId,
VN_TypeDef,
VN_BaseType,
VN_Structuretype,
VN_ArrayType,
VN_Low,
VN_Top,
VN_RecType,
VN_FieldDecList,
VN_FieldDecMore,
VN_IdList,
VN_IdMore,
VN_VarDec,
VN_VarDeclaration,
VN_VarDecList,
VN_VarDecMore,
VN_VarIdList,
VN_VarIdMore,
VN_ProcDec,
VN_ProcDeclaration,
VN_ProcDecMore,
VN_ProcName,
VN_ParamList,
VN_ParamDecList,
VN_ParamMore,
VN_Param,
VN_FormList,
VN_FidMore,
VN_ProcDecPart,
VN_ProcBody,
VN_ProgramBody,
VN_StmList,
VN_StmMore,
VN_Stm,
VN_AssCall,
VN_AssignmentRest,
VN_ConditionalStm,
VN_LoopStm,
VN_InputStm,
VN_InVar,
VN_OutputStm,
VN_ReturnStm,
VN_CallStmRest,
VN_ActParamList,
VN_ActParamMore,
VN_RelExp,
VN_OtherRelExp,
VN_Exp,
VN_OtherTerm,
VN_Term,
VN_OtherFactor,
VN_Factor,
VN_Variable,
VN_VariMore,
VN_FieldVar,
VN_FieldVarMore,
VN_CmpOp,
VN_AddOp,
VN_MultOp,
VN_BaseTypeOfArray,

vt_program = 70,//为了与VN区分
vt_id,
vt_type,
vt_var,
vt_procedure,
vt_begin,
vt_integer,
vt_char,
vt_array,
vt_arraydot,
vt_of,
vt_record,
vt_intc,
vt_end,
vt_semicolon,
vt_comma,
vt_rparen,
vt_lparen,
vt_if,
vt_while,
vt_return,
vt_read,
vt_write,
vt_else,
vt_fi,
vt_endwh,
vt_assign,
vt_lmidparen,
vt_pointer,
vt_dot,
vt_lt,
vt_eq,
vt_rmidparen,
vt_then,
vt_do,
vt_plus,
vt_minus,
vt_mul,
vt_div,
vt_charc,
vt_error
};

class treestack{
public:
TreeNode * & tree;
treestack * next;
treestack * pre;
treestack(TreeNode * & t):tree(t),next(NULL),pre(NULL){}
};
//****************************************************
//******************zparse类**************************
//****************************************************
class zparse{
public:
treestack * currentTree;
treestack * headTree;
int treeNum;
void tree_push(TreeNode * &);
void tree_pop();

TreeNode * Optr[OpS_Stack_Max];
int optrtop;
void optr_push(TreeNode * );
TreeNode * optr_pop();

TreeNode * Opnd[OpN_Stack_Max];
int opndtop;
void opnd_push(TreeNode * );
TreeNode * opnd_pop();

private:
TokenList * head; //TokenList头节点
TokenList * cur; //TokenList当前节点
TreeNode * root; //语法树根节点
ofstream * output; //输出语法树
int LL1Table[70][41]; //语法分析表

VN_VT Sy_Stack[Sy_Stack_Max];
int sy_top;
void sy_push(VN_VT);
VN_VT sy_pop();

zparse(TokenList * , ofstream *);
~zparse();

bool read();
TokenList * getCur();
int getCurrentTokenLineNO();
char * getCurrentTokenSem();
LexType getCurrentTokenLex();
bool matchSem(const char[]);
bool matchLex(LexType l);

int convertTokenToVT();
bool matchVT();

void ExceptionThrow();

TreeNode * parseLL();
void CreateTable();
void predict(int num);
int Priosity(TreeNode *);

void process1();
void process2();
void process3();
void process4();
void process5();
void process6();
void process7();
void process8();
void process9();
void process10();
void process11();
void process12();
void process13();
void process14();
void process15();
void process16();
void process17();
void process18();
void process19();
void process20();
void process21();
void process22();
void process23();
void process24();
void process25();
void process26();
void process27();
void process28();
void process29();
void process30();
void process31();
void process32();
void process33();
void process34();
void process35();
void process36();
void process37();
void process38();
void process39();
void process40();
void process41();
void process42();
void process43();
void process44();
void process45();
void process46();
void process47();
void process48();
void process49();
void process50();
void process51();
void process52();
void process53();
void process54();
void process55();
void process56();
void process57();
void process58();
void process59();
void process60();
void process61();
void process62();
void process63();
void process64();
void process65();
void process66();
void process67();
void process68();
void process69();
void process70();
void process71();
void process72();
void process73();
void process74();
void process75();
void process76();
void process77();
void process78();
void process79();
void process80();
void process81();
void process82();
void process83();
void process84();
void process85();
void process86();
void process87();
void process88();
void process89();
void process90();
void process91();
void process92();
void process93();
void process94();
void process95();
void process96();
void process97();
void process98();
void process99();
void process100();
void process101();
void process102();
void process103();
void process104();

void process105();
void process106();

void printTree(TreeNode * root);
public:
static TreeNode * doZParse(TokenList * ,ofstream *);
};
#endif
/* analyze.cpp */
#include "analyze.h"

int aexception;
char * exceName;
void ExceptionThrow(TreeNode * t)
{
aexception = t->lineno;
if (t->getIdName(0) != NULL)
{
strcpy(exceName , t->getIdName(0));
throw(exceName);
}
throw(aexception);
}
void analyze::doAnalyze(TreeNode * t, ofstream o){
try
{
analyze analyzer(o , t);
analyzer.analysis(analyzer.root);
}
catch(int exception)
{
cout<<"error in line "<<exception<<endl;

}
catch(char * exceName)
{
cout<<"