《实验二语法分析器》由会员分享，可在线阅读，更多相关《实验二语法分析器（29页珍藏版）》请在金锄头文库上搜索。
1、1,语法分析器,编译原理上机实验作业（2）,2,4.2 语法分析器的构造,语法分析器的任务：分析语言的结构为句子构造语法树；检查输入序列中的错误。,主要工作：设计函数绘图语言的文法，使其适合递归下降分析；设计语法树的节点，用于存放表达式的语法树；设计递归下降子程序，分析句子并构造表达式的语法树；设计测试程序和测试用例，检验分析器是否正确。,3,4.2.1 函数绘图语言的文法 文法,Program | Program Statement SEMICOStatement OriginStatment | ScaleStatment | RotStatment | ForStatmentOrigin
2、Statment ORIGIN IS L_BRACKET Expression COMMA Expression R_BRACKETScaleStatment SCALE IS L_BRACKET Expression COMMA Expression R_BRACKETRotStatment ROT IS Expression,- 函数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);- 横坐
3、标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,4,Expression Expression PLUS Expression | Expression MINUS Expression | Expression MUL Expression | Expression DIV Expression | PLUS Expression | MINUS Expression | Expression POWER Expression | CONST_ID | T
4、 | FUNC L_BRACKET Expression R_BRACKET | L_BRACKET Expression R_BRACKET, 文法（续）,ForStatment FOR T FROM Expression TO Expression STEP Expression DRAW L_BRACKET Expression COMMA Expression R_BRACKET,5, 改写文法为无二义文法,表达式中的运算结合性 非终结符 PLUS、MINUS（二元） 左结合Expression MUL、DIV左结合Term PLUS、MINUS（一元）右结合Factor POWER右
5、结合Component（原子表达式）无Atom,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
6、,6,Expression 的改写,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 | Factor,反复改写，最终得到：,Expression对应最低优先级的运算，PLUS和MINUS：,7,无二义的表达式文法,E
7、xpressionPLUS、MINUSTermMUL、DIV FactorPLUS、MINUSComponentPOWERAtom （原子表达式）,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 Expr
8、ession R_BRACKET| L_BRACKET Expression R_BRACKET,8, 消除左递归和提取左因子,消除program产生式的左递归,Program Program Statement SEMICO |,Program ProgramProgram Statement SEMICO Program|,Program Statement SEMICO Program |,9, 消除左递归和提取左因子（续）,Term Factor TermTerm MUL Factor Term | DIV Factor Term |,（Factor和Componet对应的运算是右结合
9、，故无左递归）,消除Expression和Term 的左递归,Expression Term ExpressionExpression PLUS Term Expression | MINUS Term Expression |,Expression Expression PLUS Term |Expression MINUS Term |Term,10, 改写左结合的产生式为EBNF形式（避免子程序调用）,void Program() while (token != NONTOKEN) Statement(); MathchToken(SEMICO); ,改写为EBNF形式，以减少不必要的子
10、程序调用。Program Statement SEMICO 的子程序：,void Program() if (token = NONTOKEN) return; Statement(); MathchToken(SEMICO); Program();,递归子程序仅要求产生式没有左递归。Program Statement SEMICO Program |的子程序：,11,Expression Term ExpressionExpression PLUS Term Expression | MINUS Term Expression |,Expression(PLUS|MINUS)Term Exp
11、ression|Program Statement SEMICO Program |,Expression (PLUS|MINUS)Term Expression Term (PLUS|MINUS)Term Expression的递归子程序:,void Expressin()Term(); while (token=PLUS | token=MINUS) MathchToken(token); Term(); ,改写Expression产生式：,12,最终表达式的产生式,Expression Term ( PLUS | MINUS) Term Term Factor ( MUL | DIV )
12、 Factor Factor PLUS Factor | MINUS Factor | ComponentComponent Atom POWER Component | Atom,Atom CONST_ID | T| FUNC L_BRACKET Expression R_BRACKET | L_BRACKET Expression R_BRACKET,13,4.2.2 表达式的语法树,叶节点：常数、参数T等。两个孩子的内部节点：二元运算如Plus、Mul等。一元加：+5转化为5；一元减：-5转化为0-5。一个孩子的内部节点：函数调用，如sin(t)等。, 语法树的节点 表达式语法树的节点可
13、以设计为以下三类：,14, 节点的数据结构,typedef double (* FuncPtr)(double);struct ExprNode enum Token_Type OpCode;/ 记号种类 union Content;,struct ExprNode *Left, *Right; CaseOperator;/ 二元运算,struct ExprNode * Child; FuncPtr MathFuncPtr; CaseFunc;/ 函数调用,double CaseConst; / 常数，绑定右值,double * CaseParmPtr; / 参数T，绑定左值,15,表达式-1
14、6+5*3/cos(T)的语法树,16, 建立语法树的程序框架,ExprNode * MakeExprNode( opcode, arg1, arg2,) switch(opcode) case CONST_ID:/ 常数节点ExprPtr-Content.CaseConst = arg1;break; case T:/ 参数节点ExprPtr-Content.CaseParmPtr = ,17,4.2.3 语法分析器的递归下降子程序, 分析器所需的辅助子程序 void FetchToken (); void MatchToken (enum Token_Type AToken); void SyntaxError (int case_of);,FetchToken源程序：static void FetchToken()token = GetToken(); if (token.type = ERRTOKEN) SyntaxErroe(1);,
