编译原理习题解答.ppt

本演示文稿可能包含观众讨论和即席反应 使用PowerPoint可以跟踪演示时的即席反应 在幻灯片放映中 右键单击鼠标请选择 会议记录 选择 即席反应 选项卡必要时输入即席反应单击 确定 撤消此框此动作将自动在演示文稿末尾创建一张即席反应幻灯片 包括您的观点 编译程序的设计原理与实现 如何让计算机认识 理解和执行高级程序设计语言 龚俊2004年1月 第5章习题解答1 习题4 2 构造下述文法的递归子程序 G S S aASb Bd A cS B bB d 解 err2 NEXT w err1 NEXT w NEXT w S子程序 n n n y y NEXT w 遇 时 n y b d NEXT w y NEXT w n y NEXT w err3 y n B子程序 A子程序 是LL 1 文法 第5章习题解答2 习题5 2 已知文法 1 求选择集合 证明是LL 1 文法 2 构造LL 1 分析表 G S 解 1 求选择集合 2 LL 1 分析表 三对选择集合两两不相交 G S 是LL 1 文法 第5章习题解答3 习题5 3 P92 4 1 设有文法G A 判断LL 1 A BCc gDB B bCDE C DaB ca D dD E gAf c 解 select first B first C b d a c select first D a d a select follow B a c d f g follow B first C follow A follow C a c d f g follow C c first D first E c d g follow D b follow A first E a a b c f g follow A f select g select b select c select d select follow D a b c f g select d select c 是LL 1 文法 第5章习题解答5 习题5 4 P92 4 3设有文法G S 化为LL 1 文法 S A A B AiB B C B C C A 解 文法变换 消除左递归 A B AiB A B iB 或A BA A iBA B C B C B C C 或B CB B CB 整理后得 G S S A A BA A iBA B CB B CB C A select i select select select i select select 第5章习题解答6 习题5 10 P94 4 10考虑文法 G S S aA bB A 0A 1 B 0B 1 构造活前缀的DFA 即句柄识别器 解 扩展文法 编码 活前缀的DFA 即句柄识别器 句柄识别器 DFA 中无冲突状态 G S 是LR 0 文法 是LR 0 文法吗 第5章习题解答7 G S 的LR 0 分析表 第5章习题解答8 习题5 12 P94 4 9设有文法G S S rD D D i i 解 构造活前缀的DFA 即句柄识别器 扩展文法 编码 S r D OK r 1 r 2 r 3 i i 在状态 处出现 移进 归约 冲突 G S 不是LR 0 文法 follow S 可以解决冲突 即若当前单词为 则移进 4 当前单词为 则归约r 1 G S 是SLR 1 文法 第5章习题解答9 文法G S 的SLR 1 分析表 第7章习题解答1 习题7 3 P121 5 1 1 5 写出逆波兰式 a b c abc 或a0b c a b c d e abcde A C D A CD A B C D AB C D 快速写出要点 变元顺序不变 算符先算在前 验证 pos A B C D pos A B pos C D pos A B pos C D AB pos C pos D AB C D 第6章习题解答1 习题6 2 设有程序片断如下 试填写符号表 floatexe x y intx y 5 10 floata intb 5 10 b 2 5 15 如何确定下标变量b 2 5 的地址 解 第6章习题解答2 ENT 2 v3 v5 vn atp y v4 vf itp x 临时变量值区 b值区 y值 a值 管理区 exe值 x值 链接表 1 itp 9 0 10 4 0 a a c i r b v3 v4 v5 v6 v7 v7 v b v6 v rtp a v5 vn v4 vf itp x rtp exe SYNBL FINFL ACTL AINFL TYPEL floatexe x y intx y 5 10 floata intb 5 10 b 2 5 15 f y Addr b 2 5 v32 第7章习题解答2 习题7 4 写出下述语句的四元式序列 1 if x 0 x a b 2 c 2 while a b b 2 a 5 wh abt1 dot1 2at3 t35t4 t4 b we 解 第7章习题解答3 试用分别用最左推导法和最左归约法分析 翻译 符号串a b c d 的逆波兰式生成过程 习题7 6 已知算术表达式的逆波兰翻译文法 解 最左推导 Z T T F F F a a F a a E a a E T a a E T T 导出序列 分离导出序列 删除动作符号 a b c d 源表达式 删除文法符号 abc d 逆波兰式 第7章习题解答5 习题7 9 根据 例7 13 表达式的四元式属性翻译文法 写出a b d 的LL 1 法翻译过程 解 属性翻译文法 LL 1 分析表 F i PUSH i E 第7章习题解答6 a b d 的LL 1 法翻译过程 a F E T F a a E T P a a a a E T P a a T E T a E E a E G T a b T E G T a b F E G T F a b b E G T P b b ab E G T P b ab SEM M T E G T a T E T a E E QT q 分析表 w x SYN n E G ab abt1 S while WH R DO do S WE we 第7章习题解答7 习题7 10 试对下述四元式属性翻译文法进行文法变换 以便适应自底向上翻译的要求 S v PUSH v E ASSI S if R IF if S else EL el S IE ie S while WH R DO do S WE we 解 S while WH R DO do S WE we 如 令 为Sw 为Sd 则 Sw while WH Sd Sw R DO do S SdS WE we 第8章习题解答1 习题8 3 P151 7 5划分基本块 作程序流图 intC A 0 B 1 L1 A A B ifB CgotoL2 B B 1 gotoL1 L2 printA halt 0 A 1 B lb L1 ABt1 t1 A BCt2 ift2 B1t3 t3 B gt L1 lb L2 pr A pr A B1 B2 B3 B4 B1 B2 B3 B4 L1 L2 程序流图 基本块划分 第8章习题解答2 习题8 4 设有基本块上的语句序列 A 2 3 B C B 2 3 B C C 2 3 B C 写出四元式序列 构造优化的DAG表示 根据优化的DAG 重组四元式 t7t8t9 BCt2 6t2A A B ACt8 6t8C 第9章习题解答1 习题9 6 已知下列语句 if a b c x a b c d a b while A 0 A 2 B C B 2 B C 试分别解答 写出优化的四元式序列 标记变量的活跃信息 描述单寄存器R下的目标代码生成过程 解 if a b c x a b c d a b a y b y t1 y 四元式序列 t1 n c y t2 y ift2 n a y b y t3 y c y d y t4 y t5 n t3 n t6 y t6 n x y ie t3 y t4 n t5 y 第9章习题解答2 OBJ p QUAT q B SEM RDV LTR c t1 y LDR a ADDR b t2 y FJR LDR a ADDR b t3 y LDR c STR t4LDR t3 t4 y ADDR t3 STR x a y b y t1 y t1 n c y t2 y ift2 n a y b y t3 y c y d y t4 y t3 y t4 n t5 y t5 n t3 n t6 y ie STR t3 t6 n x y SUBR d DIVR t4 t5 y t6 y 单寄存器R下的目标代码生成过程 第9章习题解答3 while A 0 A 2 B C B 2 B C OBJ p QUAT q B SEM RDV FJR t1 y LDR A NER 0 t2 y LDR B DIVR C ADDR 2 t3 y A y wh A y 0t1 y dot1 n B y C y t2 y 2t2 y t3 y A y B y STR A STR B 单寄存器R下的目标代码生成过程 t3 n A y B y we JMP 第9章习题解答4 习题9 2 P167 9 4 已知四元式序列 T1 B C T2 A T1 T3 D 1 T4 E F T5 T3 T4 W T2 T5 求两个寄存器下目标代码生成过程 T1 y B y C y T2 y A y T1 n T3 y D y 1 T4 y E y F y T5 y T3 n T4 n W y T2 n T5 n T1 LDR0 B SUBR0 C B C A D E F MULR0 A T2 T3 LDR1 D ADDR1 1 T4 STR0 T2 LDR0 F T2 MULR0 F T5 MULR1 R0 W LDR0 T2 DIVR0 R1 第5章习题解答4 习题5 3 P92 4 2 设有文法G E 解 求选择集合 E TE E E T FT T T F PF F F P E a b select a b select select select a b select a b select follow T follow T select a b select select follow F follow F first T fillow T a b a b select select a select b 是LL 1 文法 第5章习题解答10 习题5 9 P94 4 8文法G S S AS b A SA a G S 是LR 0 或SLR 1 文法吗 扩展文法 编码以及活前缀DFA 如右图 abab有两棵不同的语法树 下图 是二义性文法 二义性文法一定不是LR 0 或SLR 1 文法 解 AS SAb 第7章习题解答4 习题7 7 写出下述表达式的四元式属性翻译文法 G E 解 四元式属性翻译文法 F i PUSH i E 语义栈 第5章习题1 习题5 3 构造下述文法的递归子程序 产生式S Bd的首符号为b d 产生式A 的首符号 后继符 a b d 提示 G E E T T T T F F F F i E 习题5 1 解释下述词语 语法分析 语法分析的分类 习题5 2 构造下述文法的递归子程序 G S S aASb BdA cS B bB d 第5章习题2 习题5 4 解释词语 LL 1 文法 LL 1 分析法 习题5 5 已知文法 G S S aASb Bd A cS B bB d 1 求选择集合 证明是LL 1 文法 2 构造LL 1 分析表 习题5 6 P92 4 1 P92 4 2 习题5 7 P92 4 3 P92 4 4 第5章习题3 习题5 8 解释下列词语 文法出现 LR 0 文法 LR 0 分析器组成 习题5 9 P94 4 8 1 2 习题5 10 P94 4 10 1 2 第5章习题4 习题5 11 解释下列词语 移进 归约冲突 LR 0 句柄识别器 SLR 1 句柄识别器 LR 0 文法 SLR 1 文法 LR 0 与SLR 1 分析器的组成 习题5 12 P94 4 9 习题5 13 P94 4 11 第6章习题1 习题6 1 解释下述词语 符号表 标识符的语义信息 符号表的功能 4 c语言符号表的管理方式 习题6 2 设有程序片断如下 试填写符号表 floatexe x y intx y 5 10 floata intb 5 10 b 2 5 15 如何确定下标变量b 2 5 的地址 第7章习题1 习题7 1 解释下列词语 中间代码 常见的几种中间代码形式 习题7 2 指出下述语法成分的四元式结构设计 条件语句 while循环语句 习题7 3 P121 5 1 1 5 习题7 4 写出的四元式序列 1 if x 0 x a b 2 c 2 while a b b 2 a 5 3 a1 y 2 x 6 gotoa1 第7章习题2 习题7 5 解释下列词语 属性文法 语法制导翻译技术 试用分别用最左推导法和最左归约法分析 翻译 符号串a b c d 的逆波兰式生成过程 习题7 7 写出下述表达式的四元式属性翻译文法 G E 习题7 6 已知算术表达式的逆波兰翻译文法 第7章习题3 习题7 8 根据语法制导翻译器的实现结构 习题7 9 根据 例7 13 表达式的四元式属性翻译文法 写出a b c d 的LL 1 法翻译过程 分别指出下述语法分析器式怎样扩展的 递归子程序 LL 1 LR 习题7 10 试对下述四元式属性翻译文法进行文法变换 以便适应自底向上翻译的要求 S v PUSH v E ASSI S if R IF if S else EL el S IE ie S while WH R DO do S WE