实验二语法分析器

1语法分析器《编译原理》上机实验作业（2）24.2语法分析器的构造语法分析器的任务：分析语言的结构1.为句子构造语法树；2.检查输入序列中的错误。主要工作：1.设计函数绘图语言的文法，使其适合递归下降分析；2.设计语法树的节点，用于存放表达式的语法树；3.设计递归下降子程序，分析句子并构造表达式的语法树；4.设计测试程序和测试用例，检验分析器是否正确。34.2.1函数绘图语言的文法1文法Program→ε|ProgramStatementSEMICOStatement→OriginStatment|ScaleStatment|RotStatment|ForStatmentOriginStatment→ORIGINISL_BRACKETExpressionCOMMAExpressionR_BRACKETScaleStatment→SCALEISL_BRACKETExpressionCOMMAExpressionR_BRACKETRotStatment→ROTISExpression-------函数f(t)=t的图形originis(200,300);--设置原点的偏移量rotispi/6;--设置旋转角度scaleis(2,1);--设置横、纵坐标比例forTfrom0to200step1draw(t,0);--横坐标forTfrom0to180step1draw(0,t);--纵坐标forTfrom0to150step1draw(t,t);--f(t)=t4Expression→ExpressionPLUSExpression|ExpressionMINUSExpression|ExpressionMULExpression|ExpressionDIVExpression|PLUSExpression|MINUSExpression|ExpressionPOWERExpression|CONST_ID|T|FUNCL_BRACKETExpressionR_BRACKET|L_BRACKETExpressionR_BRACKET1文法（续）ForStatment→FORTFROMExpressionTOExpressionSTEPExpressionDRAWL_BRACKETExpressionCOMMAExpressionR_BRACKET52改写文法为无二义文法表达式中的运算结合性非终结符PLUS、MINUS（二元）左结合ExpressionMUL、DIV左结合TermPLUS、MINUS（一元）右结合FactorPOWER右结合Component（原子表达式）无AtomExpression→ExpressionPLUSExpression|ExpressionMINUSExpression|ExpressionMULExpression|ExpressionDIVExpression|PLUSExpression|MINUSExpression|ExpressionPOWERExpression|CONST_ID|T|FUNCL_BRACKETExpressionR_BRACKET|L_BRACKETExpressionR_BRACKET6Expression的改写Expression→ExpressionPLUSExpression|ExpressionMINUSExpression引入Term提高算符的优先级，保留左递归使得算符左结合：Expression→ExpressionPLUSTerm|ExpressionMINUSTerm|TermTerm对应运算MUL和DIV，于是有：Term→TermMULTerm|TermDIVTerm|Factor反复改写，最终得到：Expression对应最低优先级的运算，PLUS和MINUS：7无二义的表达式文法ExpressionPLUS、MINUSTermMUL、DIVFactorPLUS、MINUSComponentPOWERAtom（原子表达式）Expression→ExpressionPLUSTerm|ExpressionMINUSTerm|TermTerm→TermMULFactor|TermDIVFactor|FactorFactor→PLUSFactor|MINUSFactor|ComponentComponent→AtomPOWERComponent|AtomAtom→CONST_ID|T|FUNCL_BRACKETExpressionR_BRACKET|L_BRACKETExpressionR_BRACKET83消除左递归和提取左因子消除program产生式的左递归Program→ProgramStatementSEMICO|εProgram→εProgram’Program’→StatementSEMICOProgram’|εProgram→StatementSEMICOProgram|ε93消除左递归和提取左因子（续）Term→FactorTerm'Term'→MULFactorTerm'|DIVFactorTerm'|ε（Factor和Componet对应的运算是右结合，故无左递归）消除Expression和Term的左递归Expression→TermExpression'Expression'→PLUSTermExpression'|MINUSTermExpression'|εExpression→ExpressionPLUSTerm|ExpressionMINUSTerm|Term104改写左结合的产生式为EBNF形式（避免子程序调用）voidProgram(){while(token!=NONTOKEN){Statement();MathchToken(SEMICO);}}改写为EBNF形式，以减少不必要的子程序调用。Program→{StatementSEMICO}的子程序：voidProgram(){if(token==NONTOKEN)return;Statement();MathchToken(SEMICO);Program();}递归子程序仅要求产生式没有左递归。Program→StatementSEMICOProgram|ε的子程序：11Expression→TermExpression'Expression'→PLUSTermExpression'|MINUSTermExpression'|εExpression'→(PLUS|MINUS)TermExpression'|εProgram→StatementSEMICOProgram|εExpression'→{(PLUS|MINUS)Term}Expression→Term{(PLUS|MINUS)Term}Expression的递归子程序:voidExpressin(){Term();while(token==PLUS||token==MINUS){MathchToken(token);Term();}}改写Expression产生式：12最终表达式的产生式Expression→Term{(PLUS|MINUS)Term}Term→Factor{(MUL|DIV)Factor}Factor→PLUSFactor|MINUSFactor|ComponentComponent→AtomPOWERComponent|AtomAtom→CONST_ID|T|FUNCL_BRACKETExpressionR_BRACKET|L_BRACKETExpressionR_BRACKET134.2.2表达式的语法树1.叶节点：常数、参数T等。2.两个孩子的内部节点：二元运算如Plus、Mul等。一元加：+5转化为5；一元减：-5转化为0-5。3.一个孩子的内部节点：函数调用，如sin(t)等。1语法树的节点表达式语法树的节点可以设计为以下三类：142节点的数据结构typedefdouble(*FuncPtr)(double);structExprNode{enumToken_TypeOpCode;//记号种类union{}Content;};struct{ExprNode*Left,*Right;}CaseOperator;//二元运算struct{ExprNode*Child;FuncPtrMathFuncPtr;}CaseFunc;//函数调用doubleCaseConst;//常数，绑定右值double*CaseParmPtr;//参数T，绑定左值15表达式-16+5**3/cos(T)的语法树+-/0.016**cos53TMINUSLeftRightPLUSLeftRightDIVLeftRightCONST_ID0.0CONST_ID16POWERLeftRightFUNCcoschildCONST_ID5CONST_ID3Tptrparameter163建立语法树的程序框架ExprNode*MakeExprNode(opcode,arg1,arg2,……){……switch(opcode){caseCONST_ID://常数节点ExprPtr-Content.CaseConst=arg1;break;caseT://参数节点ExprPtr-Content.CaseParmPtr=&Parameter;break;caseFUNC://函数调用节点ExprPtr-Content.CaseFunc.MathFuncPtr=arg1;ExprPtr-Content.CaseFunc.Child=(ExprNode*)arg2;break;default://二元运算节点ExprPtr-Content.CaseOperator.Left=(ExprNode*)arg1;ExprPtr-Content.CaseOperator.Right=(ExprNode*)arg2;break;}}174.2.3语法分析器的递归下降子程序1分析器所需的辅助子程序voidFetchToken();voidMatchToken(enumToken_TypeAToken);voidSyntaxError(intcase_of);FetchToken源程序：staticvoidFetchToken(){token=GetToken();if(token.type==ERRTOKEN)SyntaxErroe(1);}其中，token是存放记号的全程量；GetToken()是词法分析器接口；SyntaxErroe(case_of)是出错处理。184.2.3语法分析器的递归下降子程序（续）2主要产生式的递归子程序voidParser(char*SrcFilePtr);voidProgram();voidStatement();voidOriginStatement();voidRotStatement();voidScaleStatement();voidForStatement();structExprNode*Expression();structExprNode*Term();structExprNode*Factor();structExprNode*Component();structExprNode*Atom();19Parser的递归子程序voidParser(char*SrcFilePtr){}//endofParserFetchToken();//获取第一个记号Program();//进行递归下降分析CloseScanner();//关闭词法分析器if(!InitScanner(SrcFilePtr))//初始化词法分析器{printf(OpenSourceFileError!\n);return;}20ForStatement的递归子程序ForStatment→FORTFROMExpressionTOExpressionST