《西安电子科技大学编译原理03-6》由会员分享，可在线阅读，更多相关《西安电子科技大学编译原理03-6（32页珍藏版）》请在金锄头文库上搜索。
1、语法分析器编译原理上机作业（2 ）1词法分析器语法分析器的构造 语法分析器的任务：分析语言的结构 1. 为结构正确的输入构造语法树/分析树 ； 2. 检查输入序列中的错误。主要工作： 1. 设计函数绘图语言的文法，使其适合递归下降分析； 2. 设计语法树的结点，用于存放表达式的语法树； 3. 设计递归下降子程序，分析句子并构造表达式的语法树； 4. 设计测试程序和测试用例，检验分析器是否正确。记号句子结构21 函数绘图语言的文法文法 Program | Program Statement SEMICO Statement OriginStatment | ScaleStatment| RotS
2、tatment | 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- 函数f(t)=t的图形 origin is (200, 300); - 设置原点的偏移量 scale is (2, 1);- 设置横、纵坐标缩放比例 rot is pi/6;- 设置旋转角度 for T f
3、rom 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)=t3- 函数f(t)=t的图形 origin is (200, 300); - 设置原点的偏移量 scale is (2, 1);- 设置横、纵坐标缩放比例 rot is pi/6;- 设置旋转角度 for T from 0 to 200 step 1 draw (t, 0);- 横坐标 for T from 0 to 180 step 1
4、 draw (0, t);- 纵坐标 for T from 0 to 150 step 1 draw (t, t);- f(t)=tExpression 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
5、| L_BRACKET Expression R_BRACKET文法（续）ForStatment FOR TFROM Expression TO Expression STEP Expression DRAW L_BRACKET Expression COMMA Expression R_BRACKET文法特点： 二义、左递归左因子4改写文法为无二义文法 表达式中的运算结合性 非终结符PLUS、MINUS（二元） 左结合MUL、DIV左结合PLUS、MINUS（一元）右结合POWER右结合原子表达式 无 Expression Expression PLUS Expression| Expres
6、sion 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_BRACKETExpression Term Factor Component Atom低高5Expression 的改写Expression Expression PLU
7、S Expression| Expression MINUS Expression引入Term提高算符的优先级，保留左递归使得算符左结合：Expression Expression PLUS Term| Expression MINUS Term| TermTerm对应运算MUL和DIV，于是有： Expression Expression MUL Expression| Expression DIV Expression反复改写，最终得到：Expression对应最低优先级的运算，PLUS和MINUS：Term Term MUL Term| Term DIV TermTerm Term MU
8、L Factor| Term DIV Factor | Factor6无二义的表达式文法ExpressionPLUS、MINUS TermMUL、DIV FactorPLUS、MINUS ComponentPOWER Atom （原子表达式）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 C
9、omponent | Atom Atom CONST_ID | T | FUNC L_BRACKET Expression R_BRACKET | L_BRACKET Expression R_BRACKET7无二义的完整文法Program | Program Statement SEMICO Statement OriginStatment | ScaleStatment| RotStatment | ForStatment OriginStatment ORIGIN IS L_BRACKET Expression COMMA Expression R_BRACKET ScaleStatme
10、nt SCALE IS L_BRACKET Expression COMMA Expression R_BRACKET RotStatment ROT IS ExpressionExpression 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
11、 | FUNC L_BRACKET Expression R_BRACKET | L_BRACKET Expression R_BRACKET8消除左递归和提取左因子消除program产生式的左递归Program Program Statement SEMICO |改写为： Program Program Program Statement SEMICO Program|它等价于： Program Statement SEMICO Program |9消除左递归和提取左因子（续）Term Factor Term Term MUL Factor Term| DIV Factor Term|消除E
12、xpression和Term 的左递归 Expression Term Expression Expression PLUS Term Expression| MINUS Term Expression|Expression Expression PLUS Term |Expression MINUS Term|Term Term Term MUL Factor | Term DIV Factor | Factor10无二义/无左递归的完整文法Program Statement SEMICO Program | Statement OriginStatment | ScaleStatment|
13、 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 ExpressionExpression Term Expression Expression PLUS Term Expression | MINUS Term Expression | Term Factor Ter
14、m Term MUL Factor Term | DIV Factor Term | 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左因子11改写产生式为EBNF形式，Statement SEMICO，Statement SEMICO Statement SEMICO .即“Statement SEMI
15、CO”被重复0或若干次，于是有：构造文法的状态转换图 化简 写出EBNF形式的产生式 简便方法：考察产生式是否具有EBNF对应的结构。若有则转 换为相应的EBNF形式。 如：对于产生式：Program Statement SEMICO Program | 按其不同的右部候选项展开，会得到下述序列：Program Statement SEMICO void Program() while ( ) Statement(); MathchToken(SEMICO); token != NONTOKEN12Expression Term Expression Expression PLUS Term Expression | MINUS Term Expression | Expression(PLUS|MINUS) Term Expression| Program Statement SEMICO Program | （对比二
