• / 28
  • 下载费用:16 金币  

语法分析器构造

关 键 词:
语法分析器构造 构造语法分析器
资源描述:
4.2 语法分析器的构造 主要工作 : 1.设计函数绘图语言的文法,使适合递归下降分析 ; 2.设计语法树的节点,用于存放表达式的语法树; 3.设计递归下降子程序, 分析句子并构造表达式的语法树; 4.设计测试程序和测试用例,检验分析器是否正确 。 语法分析器的任务: 分析语言的结构,构造语法树 1 4.2.1 函数绘图语言的文法 Program → ε| Program Statement SEMICO Statement → OriginStatment | ScaleStatment | RotStatment | ForStatment OriginStatment → ORIGIN IS L_BRACKET Expression COMMA Expression R_BRACKET ScaleStatment → SCALE IS L_BRACKET Expression COMMA Expression R_BRACKET RotStatment → ROT IS Expression ForStatment → FOR T FROM Expression TO Expression STEP Expression DRAW L_BRACKET Expression COMMA Expression R_BRACKET 2 Expression → Expression PLUS Expression | Expression MINUS Expression | Expression MUL Expression | Expression DIV Expression | PLUS Expression | MINUS Expression | Expression POWER Expression | CONST_ID | T | FUNC L_BRACKET Expression R_BRACKET | L_BRACKET Expression R_BRACKET 3 改写文法为无二义文法 表达式中的运算结合性非终结符 --------------------------------------------- -- PLUS、MINUS(二元) 左结合Expression MUL、DIV左结合Term PLUS、MINUS(一元)右结合Factor POWER右结合Component (原子表达式)无Atom 4 Expression 的改写 Expression对应最低优先级的运算,PLUS和MINUS: Expression → Expression PLUS Expression | Expression MINUS Expression 引入Term提高算符的优先级, 保留左递归使得算符左结合: Expression → Expression PLUS Term | Expression MINUS Term | Term Term对应运算MUL和DIV,于是有: Term → Term MUL Term | Term DIV Term 反复改写,最终得到: 5 无二义的表达式文法 Expression → Expression PLUS Term | Expression MINUS Term | Term Term → Term MUL Factor | Term DIV Factor | Factor Factor → PLUS Factor | MINUS Factor | Component Component → Atom POWER Component | Atom Atom → CONST_ID | T | FUNC L_BRACKET Expression R_BRACKET | L_BRACKET Expression R_BRACKET PLUS、MINUS Expression MUL、DIV Term PLUS、MINUS Factor POWER Component (原子表达式)Atom 6 消除无左递归和提取左因子 (消除Program、Expression和Term 的左递归) Program → Statement SEMICO Program |ε 改写 Expression → Term Expression' Expression'→ PLUS Term Expression' | MIMUS Term Expression' |ε Term → Factor Term' Term' → MUL Factor Term' | DIV Factor Term' |ε (Factor和Componet对应的运算是右结合,故无左递归) 7 改写左结合的产生式为EBNF形式 (避免子程序调用) Program → Statement SEMICO Program |ε的子程序 : void Program() { if (token == NONTOKEN) return; Statement(); MathchToken(SEMICO); Program(); } Program → { Statement SEMICO }的子程序: void Program() { while (token != NONTOKEN) { Statement(); MathchToken(SEMICO); } } 文法的改写: 8 改写Expression产生式 : Expression →Term Expression' Expression' → PLUS Term Expression' | MIMUS Term Expression' |ε Expression'→(PLUS|MIMUS)Term Expression'|ε Program → Statement SEMICO Program |ε Expression' → {(PLUS|MIMUS)Term } Expression → Term {(PLUS|MINUS)Term } void Expressin() {Term(); while (token==PLUS || token==MINUS) { MathchToken(token); Term();} } Expression的递归子程序: 9 表达式的产生式 Expression → Term { ( PLUS | MINUS) Term } Term → Factor { ( MUL | DIV ) Factor } Factor → PLUS Factor | MINUS Factor | Component Component → Atom POWER Component | Atom Atom → CONST_ID | T | FUNC L_BRACKET Expression R_BRACKET | L_BRACKET Expression R_BRACKET 10 4.2.2 表达式的语法树 语法树的节点 表达式语法树的节点可以设计为以下三类: 1. 叶节点:常数、参数T等。 2. 两个孩子的内部节点:二元运算如Plus、Mul等。 一元加:+5转化为5; 一元减:-5转化为0-5。 3. 一个孩子的内部节点:函数调用,如sin(t)等 。 11 节点的数据结构: typedef double (* FuncPtr)(double); struct ExprNode { enum Token_Type OpCode;// 记号种类 union { struct { ExprNode *Left, *Right; } CaseOperator;// 二元运算 struct { ExprNode * Child; FuncPtr MathFuncPtr; } CaseFunc;// 函数调用 double CaseConst; // 常数,绑定右值 double * CaseParmPtr; // 参数T,绑定左值 } Content; }; 12 表达式:-16+5**3/cos(T) 13 语法树的建立(78页 ) #include double Parameter; 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= break; 14 case FUNC:// 函数调用节点 ExprPtr-Content.CaseFunc.MathFuncPtr = (FuncPtr)va_arg(ArgPtr, FuncPtr); ExprPtr-Content.CaseFunc.Child =(struct ExprNode *)va_arg(ArgPtr,struct ExprNode *); break; default:// 二元运算节点 ExprPtr-Content.CaseOperator.Left =(struct ExprNode *)va_arg(ArgPtr,struct ExprNode *); ExprPtr-Content.CaseOperator.Right =(struct ExprNode *)va_arg(ArgPtr,struct ExprNode *); break; } va_end(ArgPtr); return ExprPtr; } 15 4.2.3 语法分析器的递归下降子程序 分析器所需的辅助子程序 void FetchToken (); void MatchToken (enum Token_Type AToken); void SyntaxError (int case_of); 主要产生式的递归子程序 16 void Parser(char * SrcFilePtr) { if(!InitScanner(SrcFilePtr))// 初始化词法分析 器 { printf(“Open Source File Error ! \n“); return; } FetchToken();// 获取第一个记号 Program();// 进行递归下降分析 CloseScanner();// 关闭词法分析器 } a) Parser的递归子程序 17 b) ForStatement的递归子程序 static void ForStatement (void) { struct ExprNode *start_ptr, *end_ptr, *step_ptr, *x_ptr, *y_ptr; MatchToken (FOR); MatchToken(T); MatchToken (FROM); start_ptr = Expression(); MatchToken (TO); end_ptr = Expression(); MatchToken (STEP); step_ptr = Expression(); MatchToken (DRAW); MatchToken (L_BRACKET); x_ptr = Expression(); MatchToken (COMMA); y_ptr = Expression(); MatchToken (R_BRACKET); } ForStatment → FOR T FROM Expression TO Expression STEP Expression DRAW L_BRACKET Expression COMMA Expression R_BRACKET 18 c) Expression的递归子程序 static struct ExprNode * Expression() { struct ExprNode *left, *right; Token_Type token_tmp; left = Term(); while (token.type==PLUS || token.type==MINUS) { token_tmp = token.type; MatchToken(token_tmp); right = Term(); left = MakeExprNode(token_tmp,left,right); } return left; } Expression → Term { ( PLUS | MINUS) Term } 19 4.2.4 语法分析器的测试 测试主程序与测试辅助子程序 a) 测试主程序 b) 打印语法树的子程序 #include extern void Parser(char * SrcFilePtr); void main(int argc, char *argv[]) { if(argc 测试语句的嵌入与测试结果 a) 测试语句的加入: 1. 上层子程序入口与出口加入“enter”和 “exit” 2. 终结符匹配后加入“mathctoken ***” 3. 表达式(Expression)构造后,打印语法树 b) 被测试源程序: FOR T FROM 0 TO 2*PI STEP PI/50 DRAW (cos(T),sin(T)); -16+5**3/cos(T) c) 测试结果(看程序运行) 22 // 上届同学的解答: c_comments /* ([^*]|**[^*/])*** */ // 习题解答: c_comments /* ([^*]|*[^/])* */ // 多重入口: c_comments /* // (YACC)多重入口: {c_comments} BEGIN c_comment_entry ;// 注释开始 “*/“BEGIN 0; // 注释结束 .; \nLineNo ++; 结 束 23 改写Program产生式: 对于产生式: Program → Statement SEMICO Program |ε 按其不同的右部候选项展开,会得到下述序列: ε, Statement SEMICO, Statement SEMICO Statement SEMICO,. 即“Statement SEMICO”被重复0或若干次,于是有: Program → { Statement SEMICO } 返回 24 FetchToken源程序: 其中,token是存放记号的全程量; GetToken()是词法分析器接口; SyntaxErroe(case_of)是出错处理。 static void FetchToken() { token = GetToken(); if (token.type == ERRTOKEN) SyntaxErroe(1); } 返回 25 void Parser(char * SrcFilePtr); void Program(); void Statement(); void OriginStatement(); void RotStatement(); void ScaleStatement(); void ForStatement(); struct ExprNode * Expression(); struct ExprNode * Term(); struct ExprNode * Factor(); struct ExprNode * Component(); struct ExprNode * Atom(); 返回 26 Program → Program Statement SEMICO |ε Program → ε Program’ Program’ → Statement SEMICO Program’|ε Program → Statement SEMICO Program |ε 返回 27 --------------- 函数f(t)=t的图形 origin is (200, 300);-- 设置原点的偏移量 rot is pi/6;-- 设置旋转角度 scale is (2, 1);-- 设置横、纵坐标比例 for T from 0 to 200 step 1 draw (t, 0); -- 横坐标 for T from 0 to 180 step 1 draw (0, t); -- 纵坐标 for T from 0 to 150 step 1 draw (t, t); -- f(t)=t 返回 28
展开阅读全文
  麦档网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:语法分析器构造
链接地址:https://www.maidoc.com/p-15679443.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2018-2020 maidoc.com版权所有  文库上传用户QQ群:3303921 

麦档网为“文档C2C模式”,即用户上传的文档所得金币直接给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的金币归上传人(含作者)所有。
备案号:蜀ICP备17040478号-3  
川公网安备:51019002001290号 


收起
展开