编译原理 自上而下分析题型

常见题型1：消除左递归、提公因子

• 消除左递归：
  P→Pα|β (β不以P开头)
  则可改写规则为:
  P→βP’
  P’→αP’|ε
  例：S→Sa|b
  消除左递归：
  S→bS’
  S’→aS’|ε

• 提公因子
  S→aS|aa|ab
  提公因子：
  S→aA;
  A→S|a|b;

• 消除文法中的一切左递归
  ①将文法中所有非终结符按某一顺序排列A1、A2……
  ②从A1开始消除A1的直接左递归（如果存在的话），A1右部替换A2右部中的A1，若存在直接左递归则消除之。
  ③消除无用产生式，即从开始符号出发永远无法到达的非终结符的产生规则。
  简单来说就是将产生式代入其他产生式，消除直接左递归
  例G：S→Qc | c
  Q→Rb | b
  R→Sa | a
  先将S代入R:R→Qca | ca| a(无左递归，继续）
  将Q代入R:R→Rbca | bca| ca| a (存在直接左递归，消除)
  最终得：
  S→Qc | c
  Q→Rb | b
  R→bcaR’ | caR’| aR’
  R’→bcaR’ | ε

常见题型2 构造预测分析表、判断LL(1)文法

思路：首先要求文法first集、follow集
再根据first集、follow集构造预测分析表
最后根据LL(1)文法的3条规则判断是否为LL（1）文法

对于一个产生式:
S→ABCc | c | BA
A→a | ε
B→b
C→c

• FIRST集
  (1) 对于S→…的这个产生式，如果右边的候选式第一个为终结符，该终结符直接加入first(S)，例中{c}属于first（S）
  (2)对于S→…的这个产生式，如果右边的候选式第一个为非终结符，该非终结符的first集的非ε元素加入first（S），例中A的first集{a}加入first(S)
  (3)对于S→…的这个产生式，若右边第一个符号是非终结符而且紧随其后的是很多个非终结符，要注意第一个非终结符是否可能为ε。
  如果第一个非终结符存在候选式为ε，则后一个非终结符的first集也加入first（S），以此类推。
  如果所有的非终结符都能够推导出 ε ，{ε} 加入first(S)
  例中{first(A)- ε}+{first(B)- ε}要加入first(S)

• FOLLOW集
  (1)对于开始符S，将#加入follow(S)
  (2)查找文法所有产生式的候选式非终结符，找到需要的非终结符
  (2.1)如果非终结符后为终结符，该终结符加入follow集
  例中{c}加入follow（C）
  (2.2)如果非终结符后为非终结符，该非终结符的first集加入follow集
  例中first（C）加入follow（B）
  (2.3)如果非终结符为候选式尾，该产生式的follow集加入非终结符的follow集
  例中follow（S）加入follow（A）
  注意：follow(B)也包括follow（S），A可能为ε，B也有可能在候选式尾

• 构造预测分析表（可以求select集，也可以直接判断）
  例：
  文法G: E →TE’
  E’ →+TE’ |ε
  T →FT’
  T’ →*FT’ |ε
  F →(E) | i
  FIRST集
  FIRST(E)={ ( , I }
  FIRST(E’)={ + , ε }
  FIRST(T)={ ( , I }
  FIRST(T’)={ * , ε }
  FIRST(F)={ ( , I }
  FOLLOW集
  FOLLOW(E)={ )，# }
  FOLLOW(E’)={ )，# }
  FOLLOW(T)={ +，)，#}
  FOLLOW(T’)={ +，)，#}
  FOLLOW(F)={ *，+，)，#}
  构造预测分析表
  （1）对于产生式 F →(E) | i，候选式第一个字符为终结符，select（ F →(E)）={ （ }，select（F →i）={ i }
  在预测分析表内直接记录，如图
  （2）对于产生式 E →TE’，候选式第一个字符为非终结符，select（ E →TE’）=first（T）={ i , ( }
  （3）对于产生式E’ →+TE’ |ε，存在候选式E’ →ε，select（E’ →ε）=follow（E’）={ ），#}
  

• 判断LL(1)文法
  （1）文法不含左递归
  （2）文法的每一个非终结符A的各产生式的候选式首符集两两不相交
  例： F →(E) | i
  first((E))∩first(i)为 空
  （3）文法中的每个非终结符A，若存在候选首符集包含ε，则FIRST(A)∩FOLLOW(A)为空
  例：E’ →+TE’ |ε
  FIRST(E’)∩FOLLOW(E’)为空
  如果文法都符合3条规则，则为LL(1)文法
  上面这个文法就都符合3条规则，是LL（1）文法