北方工业大学编译原理第4章习题

第四章第四章 语法分析语法分析 自上而下分析自上而下分析 4 1 语法分析器的功能语法分析器的功能 4 2 自上而下分析面临的问题自上而下分析面临的问题 4 3 LL 1 分析法分析法 4 4 递归下降分析程序构造递归下降分析程序构造 4 5 预测分析程序预测分析程序 4 1 考虑下面文法考虑下面文法G S S Aa A BB B Sb c 请消除该文法的左递归 请消除该文法的左递归 解 解 非终结符排序为非终结符排序为S A B S和和A的产生式都不含直接左递归 的产生式都不含直接左递归 将将S代入到代入到B的候选后 的候选后 B的产生式为 的产生式为 B Aab c 把把A代入到代入到B的候选后 的候选后 B的产生式为 的产生式为 B BBab c 消除消除B的直接左递归 的直接左递归 B的产生式为 的产生式为 B cB B BabB 消除左递归后的文法为 消除左递归后的文法为 S Aa S Aa A BB 或者或者A BB B cB B cB B BabB B cB abB 4 2 试消除下面文法试消除下面文法G A 中的左递归 并提取公共左因子 中的左递归 并提取公共左因子 判断改写后的文法是否为判断改写后的文法是否为LL 1 文法文法 A aABe a B Bb d 解解 1 首先消除左递归 首先消除左递归 A aABe a B dB B bB 2 提取公共左因子 提取公共左因子 A aA A ABe B dB B bB 3 该文法不含左递归 而且每一个 该文法不含左递归 而且每一个 非终结符的各个产生式的候选首符集两非终结符的各个产生式的候选首符集两 两不相交 两不相交 FIRST A a FOLLOW A d FIRST A a FOLLOW A d FIRST B d FOLLOW B e FIRST B b FOLLOW B e 证明 证明 对于具有形如对于具有形如A 的产生式有 的产生式有 A ABe B bB FIRST Abe FOLLOW A a d FIRST bB FOLLOW B b e 满足满足LL 1 文法的条件 文法的条件 这个文法是这个文法是LL 1 的的 4 3 考虑下面文法考虑下面文法G1 1 消去 消去G1的左递归 然后对每个非终结符 写出不的左递归 然后对每个非终结符 写出不 带回溯的递归子程序 带回溯的递归子程序 S a T T T S S 解 解 消除消除文法的直接文法的直接左递归左递归 得到文法 得到文法G S S a T T ST T ST S T T 的递归子程序分别为 的递归子程序分别为 procedure S begin if sym a or sym then advance else if sym then begin advance T if sym then advance else error end else error end procedure T begin S T end procedure T begin if sym then begin advance S T end end 其中 过程其中 过程advance把输入串指示器把输入串指示器IP调至指向下一个输入调至指向下一个输入 符号 符号 sym是指是指IP当前所指的那个输入符号 当前所指的那个输入符号 error为出错诊为出错诊 断处理程序 断处理程序 解 解 消除消除文法的直接文法的直接左递归左递归 得到文法 得到文法G S S a T T ST T ST 2 经改写后的文法是否是 经改写后的文法是否是LL 1 的 给出它的预测分析表 的 给出它的预测分析表 G S S a T T ST T ST 解 求每个非终结符号解 求每个非终结符号的的FIRST和和FPLLOW集合 集合 FIRST S a FIRST T a FIRST T FOLLOW S FOLLOW T FOLLOW T 该文法的预测分析表为 该文法的预测分析表为 a SS aS S T TT S T T S T T S T T T T S T 这个分析表不含有多重定义入口 故改写后的文法是这个分析表不含有多重定义入口 故改写后的文法是LL 1 的 的 4 4 对下面的文法对下面的文法G E TE E E T FT T T F PF F F P E a b 1 计算这个文法的每个非终结符的计算这个文法的每个非终结符的FIRST和和FOLLOW 解 解 FIRST E a b FIRST E FIRST T a b FIRST T a b FIRST F a b FIRST F FIRST P a b FOLLOW E FOLLOW E FOLLOW T FOLLOW T FOLLOW F a b FOLLOW F a b FOLLOW P a b 2 证明这个文法是证明这个文法是LL 1 的 的 证明 对于具有形如证明 对于具有形如A 的产生式有 的产生式有 E E T T F F P E a b FIRST E FOLLOW E FIRST T FOLLOW T a b FIRST F FOLLOW F a b FIRST E FIRST a FIRST b FIRST 满足满足LL 1 文法的条件 文法的条件 这个文法是这个文法是LL 1 的的 3 构造它的预测分析表 构造它的预测分析表 ab EE T E E T E E T E E T E E E EE E TT FT T FT T FT T FT T T T TT T TT TT TT FF PF F PF P PF F PF F F F F F F F F F F PP E P aP bP 预测分析表预测分析表 4 构造它的递归下降分析程序 构造它的递归下降分析程序 利用预测分析表构造该文法的递归下降分析程序 可使我们尽利用预测分析表构造该文法的递归下降分析程序 可使我们尽 早的发现分析中出现的错误 分析程序构造如下 早的发现分析中出现的错误 分析程序构造如下 procedure E begin if sym or sym a or sym b or sym then begin T E end else error end procedure E begin if sym then begin advance E end else if sym and sym then error end procedure T begin if sym or sym a or sym b or sym then begin F T end else error end 4 构造它的递归下降分析程序 构造它的递归下降分析程序 procedure T begin if sym or sym a or sym b or sym then T else if sym then error end procedure F begin if sym or sym a or sym b or sym then begin P F end else error end procedure F begin if sym then begin advance F end end 4 构造它的递