[理学]第3章 语法分析1.ppt

* if x3 then if x0 then x:=5 else x:=-5 例3.8 条件语句 if x3 then if x0 then x:=5 else x:=-5 else 与离它 近 的 if then 匹配 S → if C then S (1) | if C then S else S (2) | id := E (3) (G3.3) C → E = E | E E | E E (4)...(6) E → E + E | - E | id | n (7)...(10) * 3.2.4.2 二义性的消除 文法二义性不能说明程序设计语言是二义的。程序设计语言不能二义。 消除语言二义的两种方法： ①将二义文法改写为非二义文法； ②规定二义文法中符号的优先级和结合性，使仅产生一棵分析树。 1 将二义文法改写为非二义文法 再分析id+id*id和id+id+id： 例3.9 与G3.2等价的非二义文法: E → E + T | T T → T * F | F (G3.4) F →（E） | -F | id 问题：如何将二义文法改写为非二义文法？ E→E+E | E*E |（E） (G3.2) | -E | id * 新引入的非终结符T限制了每一步直接推导均有唯一选择； 最终分析树的形状，仅与文法有关，与推导方法无关； 非终结符的引入，增加了推导步骤（分析树增高）； 越接近 S 的文法符号的优先级越低。（如E→E+T），+的优先级最低。 对于A→αAβ，若A在终结符左边出现（即终结符在β中），则A产生式具有左结合性质。 例如: E→E+T中E在+的左边，则+具有左结合性质. 若产生式形如E→T+E，则+具有右结合性质。 通过例 3.9可以看出： E → E + T | T T → T * F | F (G3.4) F →（E） | -F | id * 1 改写二义文法为非二义文法（续1） 改写二义文法的关键步骤： 引入一个新的非终结符，增加一个子结构并提高一级优先级； 递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性。 例3.10 改写二义文法G3.2为G3.4 ： E→E+E | E*E |（E） (G3.2) | -E | id E → E + T | T T → T * F | F (G3.4) F →（E） | -F | id * 1 改写二义文法为非二义文法（续2） if-then-else和if-then：在一个复合if语句中，可能then多于else，使得else不知与哪个then结合。 一般原则是右结合，即else与其左边最近的then结合。 改写文法的根据是将S分为完全匹配（MS）和不完全匹配（UMS）两类，并且在UMS中规定else右结合。 S → if C then S | if C then S else S | id := E (G3.3) C → E=E | EE | EE E → E+E | -E | id | n S → MS (1) | UMS (2) MS → if C then MS else MS (3) | id := E (4) UMS→ if C then S (5) | if C then MS else UMS (6) (G3.5) 再讨论“悬空else”问题 E → E + T | T (10)...(11) T → (E) | -T | id | n (12)...(15) 消除二义性的产生式的集合（G3.5） C → E = E | E E | E E (7)...(9) * 1 改写二义文法为非二义文法（续3） if x3 then if x0 then x:=5 else x:=-5 S → MS (1) | UMS (2) MS → if