语法分析器的构造.ppt

《语法分析器的构造.ppt》由会员分享，可在线阅读，更多相关《语法分析器的构造.ppt（28页珍藏版）》请在三一办公上搜索。

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

2、MMA Expression 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_BRACKET,3,Expression Expression PLUS Expression|Expression MINUS Exp

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

4、右结合Component（原子表达式）无Atom,5,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,反复改写，最终得到：,6,无二义的

5、表达式文法,Expression Expression 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

6、 PLUS、MINUS Factor POWER Component（原子表达式）Atom,7,消除无左递归和提取左因子（消除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对应的运算是右结合，故无左递归）,8,改写左

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);,文法的改写：,9,改写Expression产生式：,Expression Term ExpressionExpres

8、sion 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的递归子程序:,10,表达式的产生式,Expression T

9、erm(PLUS|MINUS)Term Term Factor(MUL|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,11,4.2.2 表达式的语法树,语法树的节点表达式语法树的节点可以设计为以下三类：1.叶节点：常数、参数T等。,2.两个孩子的内部节点：二元运算如Plus、Mul等。,一元加：+5转化为

10、5；一元减：-5转化为0-5。,3.一个孩子的内部节点：函数调用，如sin(t)等。,12,节点的数据结构：,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，绑定左值 Co

11、ntent;,13,表达式：-16+5*3/cos(T),14,语法树的建立（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

12、_arg(ArgPtr,double);break;case T:/参数节点 ExprPtr-Content.CaseParmPtr=,15,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

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

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

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

16、xpression STEP Expression DRAW L_BRACKET Expression COMMA Expression R_BRACKET,19,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=Make

17、ExprNode(token_tmp,left,right);return left;,Expression Term(PLUS|MINUS)Term,20,4.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*roo

18、t,int indent);从root开始，对语法树进行深度优先的先序遍历，并且根据缩进值indent将当前被遍历的节点打印在适当的位置上。,21,例-16+5*3/cos(T)的语法树,+-0.000000 16.000000/*5.000000 3.000000 402da4 T,22,测试语句的嵌入与测试结果,a)测试语句的加入：1.上层子程序入口与出口加入“enter”和“exit”2.终结符匹配后加入“mathctoken*”3.表达式（Expression）构造后，打印语法树,b)被测试源程序：FOR T FROM 0 TO 2*PI STEP PI/50 DRAW(cos(T),

19、sin(T);-16+5*3/cos(T)c)测试结果（看程序运行）,23,/上届同学的解答：c_comments/*(*|*/)*/习题解答：c_comments/*(*|*/)*/多重入口：c_comments/*,/（YACC）多重入口：c_comments BEGIN c_comment_entry;/注释开始*/BEGIN 0;/注释结束.;nLineNo+;,结 束,24,改写Program产生式：,对于产生式：Program Statement SEMICO Program|按其不同的右部候选项展开，会得到下述序列：,，Statement SEMICO，Statement SEM

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

21、tatement();void OriginStatement();void RotStatement();void ScaleStatement();void ForStatement();struct ExprNode*Expression();struct ExprNode*Term();struct ExprNode*Factor();struct ExprNode*Component();struct ExprNode*Atom();,返回,27,Program Program Statement SEMICO|,Program ProgramProgram Statement SEMICO Program|,Program Statement SEMICO Program|,返回,28,-函数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,返回,