语法分析器的构造.ppt

《语法分析器的构造.ppt》由会员分享，可在线阅读，更多相关《语法分析器的构造.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、4.2 语法分析器的构造 主要工作：1设计函数绘图语言的文法，使适合递归下降分析；2设计语法树的节点，用于存放表达式的语法树；3设计递归下降子程序，分析句子并构造表达式的语法树；4设计测试程序和测试用例，检验分析器是否正确。语法分析器的任务：分析语言的结构，构造语法树14.2.1 函数绘图语言的文法 Program|Program Statement SEMICOStatement OriginStatment|ScaleStatment|RotStatment|ForStatmentOriginStatment ORIGIN IS L_BRACKET Expression COMMA Exp

2、ression R_BRACKETScaleStatment SCALE IS L_BRACKET Expression COMMA Expression R_BRACKETRotStatment ROT IS ExpressionForStatment FOR T FROM Expression TO Expression STEP Expression DRAW L_BRACKET Expression COMMA Expression R_BRACKET2Expression Expression PLUS Expression|Expression MINUS Expression|E

3、xpression 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_BRACKET3 改写文法为无二义文法 表达式中的运算结合性非终结符-PLUS、MINUS（二元）左结合Expression MUL、DIV左结合Term PLUS、MINUS（一元）右结合Factor POWER右结合Componen

4、t（原子表达式）无Atom4Expression 的改写Expression对应最低优先级的运算，PLUS和MINUS：Expression Expression PLUS Expression|Expression MINUS Expression引入Term提高算符的优先级，保留左递归使得算符左结合：Expression Expression PLUS Term|Expression MINUS Term|TermTerm对应运算MUL和DIV，于是有：Term Term MUL Term|Term DIV Term反复改写，最终得到：5无二义的表达式文法Expression Expres

5、sion PLUS Term|Expression MINUS Term|TermTerm Term MUL Factor|Term DIV Factor|FactorFactor PLUS Factor|MINUS Factor|ComponentComponent Atom POWER Component|AtomAtom CONST_ID|T|FUNC L_BRACKET Expression R_BRACKET|L_BRACKET Expression R_BRACKET PLUS、MINUS Expression MUL、DIV Term PLUS、MINUS Factor POWE

6、R Component（原子表达式）Atom6 消除无左递归和提取左因子（消除Program、Expression和Term 的左递归）Program Statement SEMICO Program|改写Expression Term ExpressionExpression PLUS Term Expression|MIMUS Term Expression|Term Factor TermTerm MUL Factor Term|DIV Factor Term|（Factor和Componet对应的运算是右结合，故无左递归）7 改写左结合的产生式为EBNF形式 （避免子程序调用）Prog

7、ram 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 ExpressionExpression PLUS Term Expression|MIMUS

8、 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

9、|DIV)Factor Factor PLUS Factor|MINUS Factor|ComponentComponent Atom POWER Component|AtomAtom CONST_ID|T|FUNC L_BRACKET Expression R_BRACKET|L_BRACKET Expression R_BRACKET 104.2.2 表达式的语法树 语法树的节点表达式语法树的节点可以设计为以下三类：1.叶节点：常数、参数T等。2.两个孩子的内部节点：二元运算如Plus、Mul等。一元加：+5转化为5；一元减：-5转化为0-5。3.一个孩子的内部节点：函数调用，如sin(t

10、)等。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页）#

11、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:/参数节点 ExprP

12、tr-Content.CaseParmPtr=&Parameter;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,

13、struct ExprNode*);ExprPtr-Content.CaseOperator.Right =(struct ExprNode*)va_arg(ArgPtr,struct ExprNode*);break;va_end(ArgPtr);return ExprPtr;154.2.3 语法分析器的递归下降子程序 分析器所需的辅助子程序 void FetchToken();void MatchToken(enum Token_Type AToken);void SyntaxError(int case_of);主要产生式的递归子程序 16void Parser(char*SrcFile

14、Ptr)if(!InitScanner(SrcFilePtr)/初始化词法分析器 printf(Open Source File Error!n);return;FetchToken();/获取第一个记号Program();/进行递归下降分析CloseScanner();/关闭词法分析器a)Parser的递归子程序17b)ForStatement的递归子程序static void ForStatement(void)struct ExprNode*start_ptr,*end_ptr,*step_ptr,*x_ptr,*y_ptr;MatchToken(FOR);MatchToken(T);M

15、atchToken(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 DRA

16、W L_BRACKET Expression COMMA Expression R_BRACKET18c)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);

17、return left;Expression Term (PLUS|MINUS)Term 194.2.4 语法分析器的测试 测试主程序与测试辅助子程序 a)测试主程序b)打印语法树的子程序#include extern void Parser(char*SrcFilePtr);void main(int argc,char*argv)if(argc2)printf(“Input Source!n);return;Parser(test.txt);void PrintSyntaxTree(struct ExprNode*root,int indent);从root开始，对语法树进行深度优先的先序

18、遍历，并且根据缩进值indent将当前被遍历的节点打印在适当的位置上。20例-16+5*3/cos(T)的语法树+-0.000000 16.000000 /*5.000000 3.000000 402da4 T21 测试语句的嵌入与测试结果 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/上届

19、同学的解答：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”被重复

20、0或若干次，于是有：Program Statement SEMICO 返回24FetchToken源程序：其中，token是存放记号的全程量；GetToken()是词法分析器接口；SyntaxErroe(case_of)是出错处理。static void FetchToken()token=GetToken();if(token.type=ERRTOKEN)SyntaxErroe(1);返回25void Parser(char*SrcFilePtr);void Program();void Statement();void OriginStatement();void RotStatement

21、();void ScaleStatement();void ForStatement();struct ExprNode*Expression();struct ExprNode*Term();struct ExprNode*Factor();struct ExprNode*Component();struct ExprNode*Atom();返回26Program Program Statement SEMICO|Program ProgramProgram 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