编译原理 5章.pptVIP

第5章 自上而下语法分析 编译原理 陈炬桦 isscjh@mail.sysu.edu.cn 5．2 消除左递归方法 为了避免无限循环，自上而下分析法的文法不应含有左递归。有则消除。 文法的左递归性 直接左递归：U→Ux | y 间接左递归：U Ux 例：G22[A]： A →[B B →X] | BA X →Xa | Xb | a | b 用扩展的BNF表示法消除左递归 ① { } 零次或多次， m~n次 ② [ ] 零次或一次，可选项。 ③ ( ) 描述提取公因子。 例：G[标识符]： 标识符 →字母 | 标识符 字母 | 标识符 数字 数字 →0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 字母 →a|b|c|e|f|g|h|i|j|k|m|n|o|p|q|r|s|t|u|v|w|x|y|z 显然标识符产生式有左递归，可改写为 标识符 →字母 { 字母 | 数字} 直接改写法 U→Ux | y = U→yU’, U’→ xU’ | ε U→Ux1 | Ux2… | Uxm | y1 | y2 … yn = U→U(x1 | x2… | xm) | (y1 | y2 … yn) = U→ (y1 | y2 … yn)U’ U’→ (x1 | x2… | xm)U’ | ε 直接改写法举例 例：G22[A]： A →[B B →X] | BA X →Xa | Xb | a | b 改写为： G22[A]： A →[B B →X]B’ B’ → AB’|ε X → aX’ | bX’ X’ → aX’ | bX’ | ε 消除左递归算法 ① 将VN符号整理成序 Uk，k=1,…,n ② for i:=1 to n do begin j:=i+1 to n do 替换 Ui→Ujα中的Uj 消除Ui产生式中的直接左递归 end ③ 化简，删除多余产生式 消除左递归算法举例 例5.4 设文法 A→Bcd B →Ce | f C →Ab | c 变换： B →Ce | f = B →Abe | ce | f A→Bcd = A→ Abecd | cecd | fcd 消除左递归 A→ cecdA’ | fcdA’ A’→becd A’|ε B →Abe | ce | f C →Ab | c 删除多余产生式 5.3 LL(k)文法 最左推导 从左到右扫描输入串 向前查看K（≥1）个符号，选择产生式 本课程只讨论LL(1) LL(1)文法的判断条件 α∈(VN∪VT)* FIRST(α)={a | α aβ，a∈VT，β∈(VN∪VT)*} U∈VN FOLLOW(U)= {b | S xUby,b∈VT,x,y∈ (VN∪VT)*} 定义5.1 文法G是LL(1)： U→ x1 | x2… | xn 如果 FIRST(xi)∩FIRST(xj)=Φ 当ε∈FIRST(xi)时，FIRST(xi)∩FOLLOW(U)=Φ 集合FIRST、FOLLOW的构造 FIRST(α)的构造 ①　α∈VT，FIRST(α)= {α} ②　α∈VN，α→a…，a ∈FIRST(α)； α→ε，ε∈FIRST(α) ③　α∈VN，α→XY…， FIRST(X)-{ε} FIRST(α)， 若X ε，则FIRST(Y)-{ε} FIRST(α) 集合FIRST、FOLLOW的构造 FOLLOW（U）的构造 ① U是开始符号，则#∈ FOLLOW(U) ② A→xUy， 则FIRST(y)-{ε} FOLLOW（U） ③ A→xUy，y ε, (包括A→xU) 则FOLLOW(A) FOLLOW(U) 构造FIRST、FOLLOW举例 例G27[S] S→A A→BA’ A’→iBA’|ε B→CB’ B’→+CB’| ε C→)A*|( FIRST FOL