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