在词法分析器scanner.h和scanner.c都正确且存在的情况下，加入parser.h和parser.c就可以完成语法分析器！
“parser”是语法分析器。输入流是“字典”，输出流是语法树。
step2
编写parser.h 代码如下：
#ifndef PARSER_H #define PARSER_H #include"scanner.h" typedef double (*FuncPtr)(double); struct ExprNode //语法树节点类型 { enum Token_Type OpCode;//PLUS,MINUS,MUL,DIV,POWER,FUNC,CONST_ID，T union { struct{ExprNode *Left,*Right;}CaseOperater;//二元运算：只有左右孩子的内部节点 struct{ExprNode *Child;FuncPtr MathFuncPtr;}CaseFunc;//函数调用：只有一个孩子的内部节点，还有一个指向对应函数名的指针 MathFuncPtr double CaseConst;//常数：叶子节点 右值 double *CaseParmPtr;//参数T 左值：存放T的值得地址 }Content; }; extern void Parser(char *SrcFilePtr); //语法分析器对外接口 #endif // PARSER_H
step1
插入parser.c
#include"parser.h" #ifndef PARSER_DEBUG #include"semantic.h" #endif // PARSER_DEBUG double Parameter = 0, Origin_x = 0, Origin_y = 0, Scale_x = 1, Scale_y = 1, Rot_angle = 0; static Token token;//记号 static void FetchToken();//调用词法分析器的GetToken，把得到的当前记录保存起来。如果得到的记号是非法输入errtoken，则指出一个语法错误 static void MatchToken(enum Token_Type AToken);//匹配当前记号 static void SyntaxError(int case_of);//处理语法错误的子程序。根据错误的性质打印相关信息并且终止程序运行。错误性质可以根据传参不同来区分：SyntaxError（1）词法错 SyntaxError（2）语法错 static void ErrMsg(unsigned LineNo, char *descrip, char *string);//打印错误信息 static void PrintSyntaxTree(struct ExprNode * root, int indent);//前序遍历打印树 //非终结符递归子程序声明 有2类 //第1类 //语法分析，不构造语法树，因此语句的子程序均设计为过程->void类型的函数 static void Program();//递归下降分析 static void Statement(); static void OriginStatement(); static void RotStatement(); static void ScaleStatement(); static void ForStatement(); //第2类 //语法分析+构造语法树，因此表达式均设计为返回值为指向语法树节点的指针的函数。 static struct ExprNode *Expression();//二元加减 static struct ExprNode *Term();//乘除 static struct ExprNode *Factor();//一元正负 //把项和因子独立开处理解决了加减号与乘除号的优先级问题。在这几个过程的反复调用中，始终传递fsys变量的值，保证可以在出错的情况下跳过出错的符号，使分析过程得以进行下去。 static struct ExprNode *Component();//幂 static struct ExprNode *Atom();//参数T，函数，括号->一个整体的 void enter(char *x) { printf("enter in "); printf(x); printf(" "); } void back(char *x) { printf("exit from "); printf(x); printf(" "); } void call_match(char *x) { printf("matchtoken "); printf(x); printf(" "); } void Tree_trace(ExprNode *x) { PrintSyntaxTree(x, 1); } //外部接口与语法树构造函数声明 extern void Parser(char* SrcFilePtr); static struct ExprNode * MakeExprNode(enum Token_Type opcode, ...);//生成语法树的一个节点 static void FetchToken()//调用词法分析器的GetToken，把得到的当前记录保存起来。 { token = GetToken(); if (token.type == ERRTOKEN) SyntaxError(1); //如果得到的记号是非法输入errtoken，则指出一个语法错误 } //匹配当前的记号， static void MatchToken(enum Token_Type The_Token) { if (token.type != The_Token) SyntaxError(2);//若失败，则指出语法错误 FetchToken();//若成功，则获取下一个 } //语法错误处理 static void SyntaxError(int case_of) { switch (case_of) { case 1: ErrMsg(LineNo, " 错误记号 ", token.lexeme); break; case 2: ErrMsg(LineNo, " 不是预期记号 ", token.lexeme); break; } } //打印错误信息 void ErrMsg(unsigned LineNo, char *descrip, char *string) { printf("Line No %5d:%s %s ! ", LineNo, descrip, string); CloseScanner(); exit(1); } //先序遍历并打印表达式的语法树 根！左！右！ void PrintSyntaxTree(struct ExprNode *root, int indent) { int temp; for (temp = 1; temp <= indent; temp++) printf(" ");//缩进 switch (root->OpCode)//打印根节点 { case PLUS: printf("%s ", "+"); break; case MINUS: printf("%s ", "-"); break; case MUL: printf("%s ", "*"); break; case DIV: printf("%s ", "/"); break; case POWER: printf("%s ", "**"); break; case FUNC: printf("%x ", root->Content.CaseFunc.MathFuncPtr); break; case CONST_ID: printf("%f ", root->Content.CaseConst); break; case T: printf("%s ", "T"); break; default: printf("Error Tree Node ! "); exit(0); } if (root->OpCode == CONST_ID || root->OpCode == T)//叶子节点返回 return;//常数和参数只有叶子节点 常数：右值；参数：左值地址 if (root->OpCode == FUNC)//递归打印一个孩子节点 PrintSyntaxTree(root->Content.CaseFunc.Child, indent + 1);//函数有孩子节点和指向函数名的指针 else//递归打印两个孩子节点 {//二元运算：左右孩子的内部节点 PrintSyntaxTree(root->Content.CaseOperater.Left, indent + 1); PrintSyntaxTree(root->Content.CaseOperater.Right, indent + 1); } } //绘图语言解释器入口（与主程序的外部接口） void Parser(char *SrcFilePtr)//语法分析器的入口 { enter("Parser"); if (!InitScanner(SrcFilePtr))//初始化词法分析器 { printf("Open Source File Error ! "); return; } FetchToken();//获取第一个记号 Program();//递归下降分析 CloseScanner();//关闭词法分析器 back("Parser"); return; } //Program的递归子程序 static void Program() { enter("Program"); while (token.type != NONTOKEN)//记号类型不是空 { Statement();//转到每一种文法 MatchToken(SEMICO);//匹配到分隔符 } back("Program"); } //----------Statement的递归子程序 static void Statement()//转到每一种文法 { enter("Statement"); switch (token.type) { case ORIGIN: OriginStatement(); break; case SCALE: ScaleStatement(); break; case ROT: RotStatement(); break; case FOR: ForStatement(); break; default: SyntaxError(2); } back("Statement"); } //----------OriginStatement的递归子程序 //eg:origin is (20, 200); static void OriginStatement(void) { struct ExprNode *tmp;//语法树节点的类型 enter("OriginStatement"); MatchToken(ORIGIN); MatchToken(IS); MatchToken(L_BRACKET);//eg:origin is ( tmp = Expression(); Origin_x = GetExprValue(tmp);//获取横坐标点平移距离 DelExprTree(tmp);//删除一棵树 MatchToken(COMMA);//eg:, tmp = Expression(); Origin_y = GetExprValue(tmp); //获取纵坐标的平移距离 DelExprTree(tmp); MatchToken(R_BRACKET);//eg:) back("OriginStatement"); } //----------ScaleStatement的递归子程序 //eg:scale is (40, 40); static void ScaleStatement(void) { struct ExprNode *tmp; enter("ScaleStatement"); MatchToken(SCALE); MatchToken(IS); MatchToken(L_BRACKET);//eg:scale is ( tmp = Expression(); Scale_x = GetExprValue(tmp);//获取横坐标的比例因子 DelExprTree(tmp); MatchToken(COMMA);//eg:, tmp = Expression(); Scale_y = GetExprValue(tmp);//获取纵坐标的比例因子 DelExprTree(tmp); MatchToken(R_BRACKET);//eg:) back("ScaleStatement"); } //----------RotStatement的递归子程序 //eg:rot is 0; static void RotStatement(void) { struct ExprNode *tmp; enter("RotStatement"); MatchToken(ROT); MatchToken(IS);//eg:rot is tmp = Expression(); Rot_angle = GetExprValue(tmp);//获取旋转角度 DelExprTree(tmp); back("RotStatement"); } //----------ForStatement的递归子程序 //对右部文法符号的展开->遇到终结符号直接匹配，遇到非终结符就调用相应子程序 //ForStatement中唯一的非终结符是Expression，他出现在5个不同位置，分别代表循环的起始、终止、步长、横坐标、纵坐标，需要5个树节点指针保存这5棵语法树 static void ForStatement() { //eg:for T from 0 to 2*pi step pi/50 draw (t, -sin(t)); double Start, End, Step;//绘图起点、终点、步长 struct ExprNode *start_ptr, *end_ptr, *step_ptr, *x_ptr, *y_ptr;//指向各表达式语法树根节点 enter("ForStatement"); //遇到非终结符就调用相应子程序 MatchToken(FOR); call_match("FOR"); MatchToken(T); call_match("T"); MatchToken(FROM); call_match("FROM");// eg:for T from start_ptr = Expression();//获得参数起点表达式的语法树 Start = GetExprValue(start_ptr);//计算参数起点表达式的值 DelExprTree(start_ptr);//释放参数起点语法树所占空间 eg:0 MatchToken(TO); call_match("TO");// eg:to end_ptr = Expression();//构造参数终点表达式语法树 End = GetExprValue(end_ptr);//计算参数终点表达式的值 eg:2*pi DelExprTree(end_ptr);//释放参数终点语法树所占空间 MatchToken(STEP); call_match("STEP");// eg:step step_ptr = Expression();//构造参数步长表达式语法树 Step = GetExprValue(step_ptr);//计算参数步长表达式的值 eg:pi/50 DelExprTree(step_ptr);//释放参数步长语法树所占空间 MatchToken(DRAW); call_match("DRAW"); MatchToken(L_BRACKET); call_match("(");// eg:draw（ x_ptr = Expression();//跟节点 eg:t MatchToken(COMMA); call_match(",");// eg:, y_ptr = Expression();//根节点 MatchToken(R_BRACKET); call_match(")"); DrawLoop(Start, End, Step, x_ptr, y_ptr); //绘制图形 DelExprTree(x_ptr); //释放横坐标语法树所占空间 DelExprTree(y_ptr); //释放纵坐标语法树所占空间 back("ForStatement"); } //----------Expression的递归子程序 //把函数设计为语法树节点的指针，在函数内引进2个语法树节点的指针变量，分别作为Expression左右操作数（Term）的语法树节点指针 //表达式应该是由正负号或无符号开头、由若干个项以加减号连接而成。 static struct ExprNode* Expression()//展开右部，并且构造语法树 { struct ExprNode *left, *right;//左右子树节点的指针 Token_Type token_tmp;//当前记号 enter("Expression"); left = Term();//分析左操作数且得到其语法树 while (token.type == PLUS || token.type == MINUS) { token_tmp = token.type; MatchToken(token_tmp); right = Term();//分析右操作数且得到其语法树 left = MakeExprNode(token_tmp, left, right);//构造运算的语法树，结果为左子树 } Tree_trace(left);//打印表达式的语法树 back("Expression"); return left;//返回最终表达式的语法树 } //----------Term的递归子程序 //项是由若干个因子以乘除号连接而成 static struct ExprNode* Term() { struct ExprNode *left, *right; Token_Type token_tmp; left = Factor(); while (token.type == MUL || token.type == DIV) { token_tmp = token.type; MatchToken(token_tmp); right = Factor(); left = MakeExprNode(token_tmp, left, right); } return left; } //----------Factor的递归子程序 //因子则可能是一个标识符或一个数字，或是一个以括号括起来的子表达式 static struct ExprNode *Factor() { struct ExprNode *left, *right; if (token.type == PLUS) //匹配一元加运算 { MatchToken(PLUS); right = Factor(); //表达式退化为仅有右操作数的表达式 } else if (token.type == MINUS) { MatchToken(MINUS); right = Factor(); left = new ExprNode; left->OpCode = CONST_ID; left->Content.CaseConst = 0.0; right = MakeExprNode(MINUS, left, right); } else right = Component(); //匹配非终结符Component return right; } //----------Component的递归子程序 //幂 static struct ExprNode* Component()//右结合 { struct ExprNode *left, *right; left = Atom(); if (token.type == POWER) { MatchToken(POWER); right = Component(); //递归调用Component以实现POWER的右结合 left = MakeExprNode(POWER, left, right); } return left; } //----------Atom的递归子程序 //包括分隔符 函数 常数 参数 static struct ExprNode* Atom() { struct Token t = token; struct ExprNode *address = nullptr, *tmp; switch (token.type) { case CONST_ID: MatchToken(CONST_ID); address = MakeExprNode(CONST_ID, t.value); break; case T: MatchToken(T); address = MakeExprNode(T); break; case FUNC: MatchToken(FUNC); MatchToken(L_BRACKET); tmp = Expression(); address = MakeExprNode(FUNC, t.FuncPtr, tmp); MatchToken(R_BRACKET); break; case L_BRACKET: MatchToken(L_BRACKET); address = Expression(); MatchToken(R_BRACKET); break; default: SyntaxError(2); } return address; } //----------生成语法树的一个节点 static struct ExprNode *MakeExprNode(enum Token_Type opcode, ...) { struct ExprNode *ExprPtr = new(struct ExprNode); ExprPtr->OpCode = opcode;//接收记号的类别 va_list ArgPtr;//声明一个转换参数的变量 va_start(ArgPtr, opcode); //初始化变量 switch (opcode)//根据记号的类别构造不同的节点 { case CONST_ID://常数 ExprPtr->Content.CaseConst = (double)va_arg(ArgPtr, double);//右值 break; case T://参数 ExprPtr->Content.CaseParmPtr = &Parameter;//左值：地址 break; case FUNC://函数调用 ExprPtr->Content.CaseFunc.MathFuncPtr = (FuncPtr)va_arg(ArgPtr, FuncPtr);//指向对应函数名的指针 MathFuncPtr ExprPtr->Content.CaseFunc.Child = (struct ExprNode*)va_arg(ArgPtr, struct ExprNode *);//孩子的内部节点 break; default://二元运算节点 ExprPtr->Content.CaseOperater.Left = (struct ExprNode *)va_arg(ArgPtr, struct ExprNode *); ExprPtr->Content.CaseOperater.Right = (struct ExprNode *)va_arg(ArgPtr, struct ExprNode *); break; } va_end(ArgPtr);//结束变量列表,和va_start成对使用 return ExprPtr; }
step3
插入parsermain代码
#include<stdio.h> #include<stdlib.h> extern void Parser(char *SrcFilePtr);//测试主程序 void main() { Parser("test0.txt");//调用parser进行语法分析，其中被测试的语句在test.txt中 system("pause"); } //通过更改的Parser()函数参数来改变要读取的文件（在yufa>parsertest目录下可看到0-5 6个txt文件）