编译原理习题及答案1～3.ppt

第一章绪论第二章词法分析第三章语法分析 第一章绪论1 1完成下列选择题 1 下面叙述中正确的是 A 编译程序是将高级语言程序翻译成等价的机器语言程序的程序B 机器语言因其使用过于困难 所以现在计算机根本不使用机器语言C 汇编语言是计算机唯一能够直接识别并接受的语言D 高级语言接近人们的自然语言 但其依赖具体机器的特性是无法改变的 2 将编译过程分成若干 遍 是为了 A 提高程序的执行效率B 使程序的结构更加清晰C 利用有限的机器内存并提高机器的执行效率D 利用有限的机器内存但降低了机器的执行效率 3 构造编译程序应掌握 A 源程序B 目标语言C 编译方法D A C项 4 编译程序绝大多数时间花在上 A 出错处理B 词法分析B 目标代码生成D 表格管理 5 编译程序是对 A 汇编程序的翻译B 高级语言程序的解释执行C 机器语言的执行D 高级语言的翻译 解答 1 编译程序可以将用高级语言编写的源程序转换成与之在逻辑上等价的目标程序 而目标程序可以是汇编语言程序或机器语言程序 故选A 2 分多遍完成编译过程可使整个编译程序的逻辑结构更加清晰 故选B 3 构造编译程序应掌握源程序 目标语言和编译方法这三方面内容 故选D 4 编译各阶段的工作都涉及到构造 查找或更新有关表格 即编译过程的绝大部分时间都用在造表 查表和更新表格的事务上 故选D 5 由 1 可知 编译程序实际上实现了对高级语言程序的翻译 故选D 1 2计算机执行用高级语言编写的程序有哪些途径 它们之间的主要区别是什么 解答 计算机执行用高级语言编写的程序主要有两种途径 解释和编译 在解释方式下 翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序 然后执行这个机器代码程序的方法 而是每读入一条源程序的语句 就将其解释 翻译 成对应其功能的机器代码语句串并执行 然后再读入下一条源程序语句并解释执行 而所翻译的机器代码语句串在该语句执行后并不保留 这种方法是按源程序中语句的动态执行顺序逐句解释 翻译 执行的 如果一语句处于一循环体中 则每次循环执行到该语句时 都要将其翻译成机器代码后再执行 在编译方式下 高级语言程序的执行是分两步进行的 第一步首先将高级语言程序全部翻译成机器代码程序 第二步才是执行这个机器代码程序 因此 编译对源程序的处理是先翻译 后执行 从执行速度上看 编译型的高级语言比解释型的高级语言要快 但解释方式下的人机界面比编译型好 便于程序调试 这两种途径的主要区别在于 解释方式下不生成目标代码程序 而编译方式下生成目标代码程序 1 3请画出编译程序的总框图 如果你是一个编译程序的总设计师 设计编译程序时应当考虑哪些问题 解答 编译程序总框图如图1 1所示 作为一个编译程序的总设计师 首先要深刻理解被编译的源语言其语法及语义 其次 要充分掌握目标指令的功能及特点 如果目标语言是机器指令 还要搞清楚机器的硬件结构以及操作系统的功能 第三 对编译的方法及使用的软件工具也必须准确化 总之 总设计师在设计编译程序时必须估量系统功能要求 硬件设备及软件工具等诸因素对编译程序构造的影响 图1 1编译程序总框图 第二章词法分析2 1完成下列选择题 1 词法分析所依据的是 A 语义规则B 构词规则C 语法规则D 等价变换规则 2 词法分析器的输入是 A 单词符号串B 源程序C 语法单位D 目标程序 3 词法分析器的输出是 A 单词的种别编码B 单词的种别编码和自身的值C 单词在符号表中的位置D 单词自身值 4 状态转换图 见图2 1 接受的字集为 A 以0开头的二进制数组成的集合B 以0结尾的二进制数组成的集合C 含奇数个0的二进制数组成的集合D 含偶数个0的二进制数组成的集合 图2 1习题2 1的DFAM 5 对于任一给定的NFAM 一个DFAM 使L M L M A 一定不存在B 一定存在C 可能存在D 可能不存在 6 DFA适用于 A 定理证明B 语法分析C 词法分析D 语义加工 7 下面用正规表达式描述词法的论述中 不正确的是 A 词法规则简单 采用正规表达式已足以描述B 正规表达式的表示比上下文无关文法更加简洁 直观和易于理解C 正规表达式描述能力强于上下文无关文法D 有限自动机的构造比下推自动机简单且分析效率高 8 与 a b a b 等价的正规式是 A a b a b B a b C ab a b D a b 解答 1 由教材第一章1 3节中的词法分析 可知词法分析所遵循的是语言的构词规则 故选B 2 词法分析器的功能是输入源程序 输出单词符号 故选B 3 词法分析器输出的单词符号通常表示为二元式 单词种别 单词自身的值 故选B 4 虽然选项A B D都满足题意 但选项D更准确 故选D 5 NFA可以有DFA与之等价 即两者描述能力相同 也即 对于任一给定的NFAM 一定存在一个DFAM 使L M L M 故选B 6 DFA便于识别 易于计算机实现 而NFA便于定理的证明 故选C 7 本题虽然是第二章的题 但答案参见第三章3 1 3节 即选C 8 由于正则闭包R R R RR 故 a b a b a b a b 故选A 2 2什么是扫描器 扫描器的功能是什么 解答 扫描器就是词法分析器 它接受输入的源程序 对源程序进行词法分析并识别出一个个单词符号 其输出结果是单词符号 供语法分析器使用 通常把词法分析器作为一个子程序 每当语法分析器需要一个单词符号时就调用这个子程序 每次调用时 词法分析器就从输入串中识别出一个单词符号交给语法分析器 2 3设M x y a b f x y 为一非确定的有限自动机 其中f定义如下 f x a x y f x b y f y a f y b x y 试构造相应的确定有限自动机M 解答 对照自动机的定义M S f s0 Z 由f的定义可知f x a f y b 均为多值函数 因此M是一非确定有限自动机 先画出NFAM相应的状态图 如图2 2所示 图2 2习题2 3的NFAM 用子集法构造状态转换矩阵 如表2 1所示 表2 1状态转换矩阵将转换矩阵中的所有子集重新命名 形成表2 2所示的状态转换矩阵 即得到 将图2 3所示的DFAM 最小化 首先 将M 的状态分成终态组 1 2 与非终态组 0 其次 考察 1 2 由于 1 2 a 1 2 b 2 1 2 因此不再将其划分了 也即整个划分只有两组 0 和 1 2 令状态1代表 1 2 即把原来到达2的弧都导向1 并删除状态2 最后 得到如图2 4所示的化简了的DFAM 图2 3习题2 3的DFAM 其状态转换图如图2 3所示 图2 4图2 3化简后的DFAM 2 4正规式 ab a与正规式a ba 是否等价 请说明理由 解答 正规式 ab a对应的NFA如图2 5所示 正规式a ba 对应的NFA如图2 6所示 用子集法将图2 5和图2 6分别确定化为如图2 7 a 和 b 所示的状态转换矩阵 它们最终都可以得到最简DFA 如图2 8所示 因此 这两个正规式等价 图2 5正规式 ab a对应的NFA 图2 6正规式a ba 对应的NFA 图2 7图2 5和图2 6确定化后的状态转换矩阵 图2 8最简DFA 实际上 当闭包 取0时 正规式 ab a与正规式a ba 由初态X到终态Y之间仅存在一条a弧 由于 ab 在a之前 故描述 ab 的弧应在初态结点X上 而 ba 在a之后 故 ba 对应的弧应在终态结点Y上 因此 ab a和a ba 所对应的NFA也可分别描述为如图2 9 a 和 b 所示的形式 它们确定化并化简后仍可得到图2 8所示的最简DFA 图2 9 ab a和a ba 分别对应的NFA 2 5设有L G a2n 1b2ma2p 1 n 0 p 0 m 1 1 给出描述该语言的正规表达式 2 构造识别该语言的确定有限自动机 可直接用状态图形式给出 解答 该语言对应的正规表达式为a aa bb bb a aa 正规表达式对应的NFA如图2 10所示 图2 10习题2 5的NFA 用子集法将图2 10确定化 如图2 11所示 由图2 11重新命名后的状态转换矩阵可化简为 也可由最小化方法得到 0 2 1 3 5 4 6 7 图2 11习题2 5的状态转换矩阵 按顺序重新命名为0 1 2 3 4后得到最简的DFA 如图2 12所示 图2 12习题2 5的最简DFA 2 6有语言L w w 0 1 并且w中至少有两个1 又在任何两个1之间有偶数个0 试构造接受该语言的确定有限状态自动机 DFA 解答 对于语言L w中至少有两个1 且任意两个1之间必须有偶数个0 也即在第一个1之前和最后一个1之后 对0的个数没有要求 据此我们求出L的正规式为0 1 00 00 1 00 00 10 画出与正规式对应的NFA 如图2 13所示 图2 13习题2 6的NFA 用子集法将图2 13所示的NFA确定化 如图2 14所示由图2 14可看出非终态2和4的下一状态相同 终态6和8的下一状态相同 即得到最简状态为 0 1 2 4 3 5 6 8 7 按顺序重新命名为0 1 2 3 4 5 6 则得到最简DFA 如图2 15所示 图2 15习题2 6的最简DFA 2 7已知正规式 a b aa b和正规式 a b b 1 试用有限自动机的等价性证明这两个正规式是等价的 2 给出相应的正规文法 解答 1 正规式 a b aa b对应的NFA如图2 16所示 用子集法将图2 16所示的NFA确定化为DFA 如图2 17所示 图2 16正规式 a b aa b对应的NFA 图2 17图2 16确定化后的状态转换矩阵 由于对非终态的状态1 2来说 它们输入a b的下一状态是一样的 故状态1和状态2可以合并 将合并后的终态3命名为2 则得到表2 3 注意 终态和非终态即使输入a b的下一状态相同也不能合并 由此得到最简DFA 如图2 18所示 正规式 a b b对应的NFA如图2 19所示 用子集法将图2 19所示的NFA确定化为如图2 20所示的状态转换矩阵 表2 3合并后的状态转换矩阵 图2 18习题2 7的最简DFA 图2 19正规式 a b b对应的NFA 比较图2 20与图2 17 重新命名后的转换矩阵是完全一样的 也即正规式 a b b可以同样得到化简后的DFA如图2 18所示 因此 两个自动机完全一样 即两个正规文法等价 图2 20图2 19确定化后的状态转换矩阵 2 8构造一个DFA 它接收 a b 上所有不含abb的字符串 解 a b 上所有不含abb的字符串可表示为b a b a 2 9构造一个DFA 它接收 a b 上所有含偶数个a的字符串 解 a b 上所有含偶数个a的字符串可表示为 b ab a 2 10下列程序段以B表示循环体 A表示初始化 I表示增量 T表示测试 I 1 while I n sun sun a I I I 1 请用正规表达式表示这个程序段可能的执行序列 解答 用正规表达式表示程序段可能的执行序列为AT BIT 2 9将图2 21所示的非确定有限自动机 NFA 变换成等价的确定有限自动机 DFA 其中 X为初态 Y为终态 解答 用子集法将NFA确定化 如图2 22所示 图2 21习题2 9的NFA 图2 22习题2 9的状态转换矩阵 2 2 Y 2 4 2 2 Y 2 4 2 4 2 4 2 4 Y 2 4 Y 2 4 Y 图2 22所对应的DFA如图2 23所示 对图2 23所示的DFA进行最小化 首先将状态分为非终态集和终态集两部分 0 1 2 5 和 3 4 6 7 由终态集可知 对于状态3 6 7 无论输入字符是a还是b的下一状态均为终态集 而状态4在输入字符b的下一状态落入非终态集 故将其划分为 0 1 2 5 4 3 6 7 对于非终态集 在输入字符a b后按其下一状态落入的状态集不同而最终划分为 0 1 2 5 4 3 6 7 按顺序重新命名为0 1 2 3 4 5 得到最简DFA如图2 24所示 图2 23习题2 9的DFA 图2 24习题2 9的最简DFA 2 10有一台自动售货机 接收1分和2分硬币 出售3分钱一块的硬糖 顾客每次向机器中投放大于等于3分的硬币 便可得到一块糖 注意 只给一块并且不找钱 1 写出售货机售糖的正规表达式 2 构造识别上述正规式的最简DFA 解答 1 设a 1 b 2 则售货机售糖的正规表达式为a b a a b b a b 2 画出与正规表达式a b a a b b a b 对应的NFA 如图2 25所示 用子集法将图2 25所示的NFA确定化 如图2 26所示 图2 25习题2 10的NFA 由图2 26可看出 非终态2和非终态3面对输入符号a或b的下一状态相同 故合并为一个状态 即最简状态 0 1 2 3 4 图2 26习题2 10的状态转换矩阵 按顺序重新命名为0 1 2 3 则得到最简DFA 如图2 27所示 图2 27习题2 10的最简DFA 第三章语法分析3 1完成下列选择题 1 程序语言的语义需要用来描述 A 上下文无关文法B 上下文有关文法C 正规文法D 短语文法 2 2型文法对应 A 图灵机B 有限自动机C 下推自动机D 线性界限自动机 3 下述结论中 是正确的 A 1型语言 0型语言B 2型语言 1型语言C 3型语言 2型语言D A C均不成立 4 有限状态自动机能识别 A 上下文无关文法B 上下文有关文法C 正规文法D 短语文法 5 文法G S S xSx y所识别的语言是 A xyxB xyx C xnyxn n 0 D x yx 6 只含有单层分枝的子树称为 简单子树 则句柄的直观解释是 A 子树的末端结点 即树叶 组成的符号串B 简单子树的末端结点组成的符号串C 最左简单子树的末端结点组成的符号串D 最左简单子树的末端结点组成的符号串且该符号串必须含有终结符 7 下面对语法树错误的描述是 A 根结点用文法G S 的开始符S标记B 每个结点用G S 的一个终结符或非终结符标记C 如果某结点标记为 则它必为叶结点D 内部结点可以是非终结符 8 由文法开始符S经过零步或多步推导产生的符号序列是 A 短语B 句柄C 句型D 句子 9 设文法G S S SA AA a b则对句子aba的规范推导是 A S SA SAA AAA aAA abA abaB S SA SAA AAA AAa Aba abaC S SA SAA SAa Sba Aba abaD S SA Sa SAa Sba Aba aba 10 如果文法G S 是无二义的 则它的任何句子 其 A 最左推导和最右推导对应的语法树必定相同B 最左推导和最右推导对应的语法树可能不同C 最左推导和最右推导必定相同D 可能存在两个不同的最右推导 但它们对应的语法树相同 11 一个句型的分析树代表了该句型的 A 推导过程B 归约过程C 生成过程D 翻译过程 12 规范归约中的 可归约串 由定义 A 直接短语B 最右直接短语C 最左直接短语D 最左素短语 13 规范归约是指 A 最左推导的逆过程B 最右推导的逆过程C 规范推导D 最左归约的逆过程 14 文法G S S aAcB BdA AaB cB bScA b则句型aAcbBdcc的短语是 A BdB ccC aD b 15 文法G E E E T TT T P PP E i则句型P T i的句柄和最左素短语是 A P T和TB P和P TC i和P T iD P和P 16 采用自顶向下分析 必须 A 消除左递归B 消除右递归C 消除回朔D 提取公共左因子 17 对文法G E E E S SS S F FF E i则FIRST S A B i C i D 18 确定的自顶向下分析要求文法满足 A 不含左递归B 不含二义性C 无回溯D A C项 19 递归下降分析器由一组递归函数组成 且每一个函数对应文法的 A 一个终结符B 一个非终结符C 多个终结符D 多个非终结符 20 LL 1 分析表需要预先定义和构造两族与文法有关的集合 A FIRST和FOLLOWB FIRSTVT和FOLLOWC FIRST和LASTVTD FIRSTVT和LASTVT 21 设a b c是文法的终结符且满足优先关系ab和bc 则 A 必有acB 必有caC 必有baD A C都不一定成立 22 算符优先分析法要求 A 文法不存在 QR 的句型且任何终结符对 a b 满足ab a b和a b三种关系B 文法不存在 QR 的句型且任何终结符对 a b 至多满足ab a b和a b三种关系之一 C 文法可存在 QR 的句型且任何终结符对 a b 至多满足ab a b和a b三种关系之一D 文法可存在 QR 的句型且任何终结符对 a b 满足ab a b和a b三种关系 23 任何算符优先文法优先函数 A 有一个B 没有C 有若干个D 可能有若干个 24 在算符优先分析中 用来刻画可归约串 A 句柄B 直接短语C 素短语D 最左素短语 25 下面最左素短语必须具备的条件中有错误的是 A 至少包含一个终结符B 至少包含一个非终结符C 除自身外不再包含其他素短语D 在句型中具有最左性 26 对文法G S S b T T T S S其FIRSTVT T 为 A b B b C b D b 27 对文法G E E E T TT T i i句子1 2 8 6归约的值为 A 23B 42C 30D 17 28 下述FOLLOW集构造方法中错误的是 A 对文法开始符S有 FOLLOW S B 若有A B 则有FIRST FOLLOW B C 若有A B 则有FOLLOW B FOLLOW A D 若有A B 则有FOLLOW A FOLLOW B 29 若文法G S 的产生式有 AB 出现 则对A求FOLLOW集正确的是 A FOLLOW B FOLLOW A B FIRSTVT B FOLLOW A C FIRST B FOLLOW A D LASTVT B FOLLOW A 30 下面是自底向上分析方法 A 预测分析法B 递归下降分析法C LL 1 分析法D 算符优先分析法 31 下面是采用句柄进行归约的 A 算符优先分析法B 预测分析法C SLR 1 分析法D LL 1 分析法 32 一个指明了在分析过程中某时刻能看到产生式多大一部分 A 活前缀B 前缀C 项目D 项目集 33 若B为非终结符 则A B 为项目 A 接受B 归约C 移进D 待约 34 在LR 0 的ACTION子表中 如果某一行中存在标记为 rj 的栏 则 A 该行必定填满rjB 该行未填满rjC 其他行也有rjD GOTO子表中也有rj 35 LR分析法解决 移进 归约 冲突时 左结合意味着 A 打断联系实行移进B 打断联系实行归约C 建立联系实行移进D 建立联系实行归约 36 LR分析法解决 移进 归约 冲突时 右结合意味着 A 打断联系实行归约B 建立联系实行归约C 建立联系实行移进D 打断联系实行移进 解答 1 参见第四章4 1 1节 语义分析不像词法分析和语法分析那样可以分别用正规文法和上下文无关文法描述 由于语义是上下文有关的 因此语义分析须用上下文有关文法描述 即选B 2 2型文法对应下推自动机 故选C 3 由于不存在 3型语言 2型语言 1型语言 0型语言 故选D 4 3型文法即正规文法 它的识别系统是有限状态自动机 故选C 5 由S xSx y可知该文法所识别的语言一定是 y左边出现的x与y右边出现的x相等 故选C 6 最左简单子树的末端结点组成的符号串为句柄 故选C 7 内部结点 指非树叶结点 一定是非终结符 故选D 8 由文法开始符S经过零步或多步推导产生的符号序列一定是句型 仅当推导产生的符号序列全部由终结符组成时才是句子 即句子是句型的阵列 故选C 9 规范推导即最右推导 也即每一步推导都是对句型中的最右非终结符用相应产生式的右部进行替换 故选D 10 文法G S 的一个句子如果能找到两种不同的最左推导 或最右推导 或存在两棵不同的语法树 则它的任何句子 其最左推导和最右推导对应的语法树必定相同 故选A 11 一个句型的分析树代表了该句型的归约过程 故选B 12 规范归约中的 可归约串 即为句柄 也就是最左直接短语 故选C 13 规范归约的逆过程是规范推导 而规范推导即为最右推导 故选B 14 由图3 1可知应选A 图3 1句型aAcbBdcc对应的语法树 15 由图3 2可知 句柄 最左直接短语 为P 最左素短语为P T 故选B 16 回溯使自顶向下分析效率降低 左递归使得自顶向下的分析无法实现 二者相比消除左递归更为重要 故选A 17 FIRST F i 而由S F可知FIRST F FIRST S 即FIRST S i 故选B 18 左递归和二义性将无法实现自顶向下分析 回溯则使自顶向下分析效率下降 故选D 图3 2句型P T i对应的语法树及优先关系示意 19 递归下降分析器由一组递归函数组成 且每一个函数对应文法的一个非终结符 故选B 20 LL 1 分析表需要预先定义和构造两族与文法有关的集合FIRST和FOLLOW 故选A 21 由于ab和bc并不能使选项A B C成立 故选D 22 由算法优先文法可知应选B 23 有些算符优先文法不存在优先函数 有些算符优先文法存在优先函数 且只要存在一对优先函数 就存在无穷多对优先函数 故选D 24 在算符优先分析中是以 最左素短语 来刻画可归约串的 故选D 25 最左素短语必须具备的三个条件是 至少包含一个终结符 除自身外不得包含其他素短语 在句型中具有最左性 故选B 26 FIRSTVT T FIRSTVT S b 由T S可知FIRSTV S FIRSTVT T 即FIRSTVT T b 故选C 27 由图3 3可知应选B 28 若有A B则有FOLLOW A FOLLOW B 即选项C错 故选C 29 若文法G S 的产生式有 AB 出现 则有FIRST B FOLLOW A 故选C 图3 3句子1 2 8 6的语法树及值变化示意 30 自底向上的分析方法有算符优先分析法和LR分析法 故选D 31 自底向上分析采用归约方法 但算符优先分析用 最左素短语 归约 而LR分析用 句柄 归约 SLR 1 是LR分析法的一种 故选C 32 在LR分析中 一个项目指明了在分析过程的某个时刻所看到产生式的多大一部分 故选C 33 对文法G S S 称为 接受 项目 形如A a 的项目 其中a为终结符 称为 移进 项目 形如A B 的项目 其中B为非终结符 称为 待约 项目 故选D 34 在LR 0 的ACTION子表中 如果某一行存在标注为 rj 的栏 则该行必定填满rj 而在SLR 1 的ACTION子表中 如果某一行存在标注为 rj 的栏 则该行可能未填满rj 因此选A 35 LR分析法解决 移进 归约 冲突时 左结合意味着打断联系而实行归约 右结合意味着维持联系而实行移进 故选B 36 由 35 可知应选C 3 2令文法G N 为G N N D NDD 0 1 2 3 4 5 6 7 8 9 1 G N 的语言L G 是什么 2 给出句子0127 34和568的最左推导和最右推导 解答 1 G N 的语言L G N 是非负整数 2 最左推导 最右推导 3 3已知文法G S 为S aSb Sb b 试证明文法G S 为二义文法 解答 由文法G S S aSb Sb b 对句子aabbbb可对应如图3 4所示的两棵语法树 因此 文法G S 为二义文法 对句子abbb也可画出两棵不同的语法树 图3 4句子aabbbb对应的两棵不同语法树 3 4已知文法G S 为S SaS 试证明文法G S 为二义文法 解答 由文法G S S SaS 句子aa的语法树如图3 5所示 由图3 5可知 文法G S 为二义文法 图3 5句子aa对应的两棵不同的语法树 3 5按指定类型 给出语言的文法 1 L aibj j i 0 的上下文无关文法 2 字母表 a b 上的同时只有奇数个a和奇数个b的所有串的集合的正规文法 3 由相同个数a和b组成句子的无二义文法 解答 1 由L aibj j i 0 知 所求该语言对应的上下文无关文法首先应有S aSb型产生式 以保证b的个数不少于a的个数 其次 还需有S Sb或S b型的产生式 用以保证b的个数多于a的个数 因此 所求上下文无关文法G S 为G S S aSb Sb b 2 为了构造字母表 a b 上同时只有奇数个a和奇数个b的所有串集合的正规式 我们画出如图3 6所示的DFA 即由开始符S出发 经过奇数个a到达状态A 或经过奇数个b到达状态B 而由状态A出发 经过奇数个b到达状态C 终态 同样 由状态B出发经过奇数个a到达终态C 由图3 6可直接得到正规文法G S 如下 G S S aA bBA aS bC bB bS aC aC bA aB 图3 6 3 我们用一个非终结符A代表一个a 即有A a 用一个非终结符B代表一个b 即有B b 为了保证a和b的个数相同 则在出现一个a时应相应地出现一个B 出现一个b时则相应出现一个A 假定已推导出bA 如果下一步要推导出连续两个b 则应有bA bbAA 也即为了保证b和A的个数一致 应有A bAA 同理有B aBB 此外 为了保证递归地推出所要求的ab串 应有S aBS和S bAS 由此得到无二义文法G S 为G S S aBS bAS A bAA aB aBB b 3 6有文法G S S aAcB BdA AaB cB bScA b 1 试求句型aAaBcbbdcc和aAcbBdcc的句柄 2 写出句子acabcbbdcc的最左推导过程 解答 1 分别画出对应句型aAaBcbbdcc和aAcbBdcc的语法树如图3 7的 a b 所示 对树 a 直接短语有3个 AaB b和c 而AaB为最左直接短语 即为句柄 对树 b 直接短语有两个 Bd和c 而Bd为最左直接短语 能否不画出语法树 而直接由定义 即在句型中 寻找满足某个产生式的候选式这样一个最左子串 即句柄 呢 例如 对句型aAaBcbbdcc 我们可以由左至右扫描找到第一个子串AaB 它恰好是满足A AaB右部的子串 与树 a 对照 AaB的确是该句型的句柄 是否这一方法始终正确呢 我们继续检查句型aAcbBdcc 由左至右找到第一个子串c 这是满足A c右部的子串 但由树 b 可知 c不是该句型的句柄 由此可知 画出对应句型的语法树然后寻找最左直接短语是确定句柄的好方法 图3 7习题3 6的语法树 a aAaBcbbdcc b aAcbBdcc 2 句子acabcbbdcc的最左推导如下 3 7对于文法G S S L aS aL L S S 1 画出句型 S a 的语法树 2 写出上述句型的所有短语 直接短语 句柄 素短语和最左素短语 解答 1 句型 S a 的语法树如图3 8所示 2 由图3 8可知 短语 S a a S a S a 直接短语 a S 句柄 S 素短语 素短语可由图3 8中相邻终结符之间的优先关系求得 即 a 因此 素短语为a 图3 8句型 S a 的语法树 3 8下述文法描述了C语言整数变量的声明语句 G D D TLT int long shortL id L id 1 改造上述文法 使其接受相同的输入序列 但文法是右递归的 2 分别以上述文法G D 和改造后的文法G D 为输入序列inta b c构造分析树 解答 1 消除左递归后 文法G D 如下 D TLT int long shortL idL L idL 2 未消除左递归的文法G D 和消除左递归的文法G D 为输入序列inta b c构造的分析树分别如图3 9的 a b 所示 图3 9两种文法为inta b c构造的分析树 a 文法G D b 文法G D 3 9考虑文法G S S T a S aT T S S消除文法的左递归及提取公共左因子 然后对每个非终结符写出不带回溯的递归子程序 解答 消除文法G S 的左递归 S T a S aT ST T ST 提取公共左因子 S T aS S S T ST T ST 改造后的文法已经是LL 1 文法 不带回溯的递归子程序如下 voidmatch tokent if lookahead t lookahead nexttoken elseerror voidS if lookahead a match a S elseif lookahead match T if lookahead match elseerror voidS if lookahead match S voidT S T voidT if lookahead match S T 对于文法G S 中的产生式 T T S S 即将非终结符T由下面的正规表达式定义 T S S 然后将其用状态转换图表示为图3 10 这个状态转换图的作用就如同一个递归过程 函数 并借助于这种转换图来得到递归过程 函数 下降分析器 因此 前面的递归下降分析器程序可删除函数T 和T 而将T 和T 改为 图3 10非终结符T的状态转换图 voidT S while lookahead match S 3 10已知文法G A A aABl aB Bb d 1 试给出与G A 等价的LL 1 文法G A 2 构造G A 的LL 1 分析表 3 给出输入串aadl 的分析过程 解答 1 文法G A 存在左递归和回溯 故其不是LL 1 文法 要将G A 改造为LL 1 文法 首先要消除文法的左递归 即将形如P P 的产生式改造为P P P P 来消除左递归 由此 将产生式B Bb d改造为B dB B bB 其次 应通过提取公共左因子的方法来消除G A 中的回溯 即将产生式A aABl a改造为A aA A ABl 最后得到改造后的文法为G A A aA A ABl B dB B bB 求得 FIRST A a FIRST A a FIRST B d FIRST B b 对文法开始符号A 有FOLLOW A 由A ABl得FIRST B FOLLOW A 即FOLLOW A d 由A ABl得FIRST l FOLLOW B 即FOLLOW B l 由A aA 得FOLLOW A FOLLOW A 即FOLLOW A d 由B dB 得FOLLOW B FOLLOW B 即FOLLOW B l 对A ABl来说 FIRST A FOLLOW A a d 所以文法G A 为所求等价的LL 1 文法 2 构造预测分析表的方法如下 对文法G A 的每个产生式A 执行 步 对每个终结符a FIRST A 把A 加入到M A a 中 其中 为含有首字符a的候选式或为唯一的候选式 若 FIRST A 则对任何属于FOLLOW A 的终结符b 将A 加入到M A b 中 把所有无定义的M A a 标记上 出错 由此得到G A 的预测分析表 见表3 1 3 输入串aadl的分析过程见表3 2 表3 1预测分析表 表3 2输入串aadl的分析过程 3 11将下述文法改造为LL 1 文法 G V V N N E E V V EN i 解答 LL 1 文法的基本条件是不含左递归和回溯 公共左因子 而文法G V 中含有回溯 所以先消除回溯 得到文法G V G V V NV V E E VE E EN i 一个LL 1 文法的充要条件是 对每一个终结符A的任何两个不同产生式A 有下面的条件成立 1 FIRST FIRST 2 假若 则有FIRST FOLLOW A 即求出G V 的FIRST和FOLLOW集如下 FIRST N FIRST V FIRST E i FIRST V FIRST E FOLLOW V 由V E 得FIRST FOLLOW E 即FOLLOW E 由V NV 得FIRST V FOLLOW N 即FOLLOW N 由E VE 得FIRST E FOLLOW V 即FOLLOW V 由V NV 得FOLLOW V FOLLOW V 即FOLLOW V 由V NV 且V 得FOLLOW V FOLLOW N 即FOLLOW N 由E VE 得FOLLOW E FOLLOW E 即FOLLOW E 则 对V E 有 FIRST FIRST 对E E有 FIRST FIRST 对V E 有 FIRST FOLLOW V 对E E有 FIRST FOLLOW E 故文法G V 为LL 1 文法 3 12对文法G E E E T TT T P PP i 1 构造该文法的优先关系表 不考虑语句括号 并指出此文法是否为算符优先文法 2 构造文法G E 的优先函数 解答 1 FIRSTVT集构造方法 由P a 或P Qa 则a FIRSTVT P 若a FIRSTVT Q 且P Q 则a FIRSTVT P 也即FIRSTVT Q FIRSTVT P 由 得 由E E 得FIRSTVT E 由T T 得FIRSTVT T 由P i得FIRSTVT P i 由 得 由T P得FIRSTVT P FIRSTVT T 即FIRSTVT T i 由E T得FIRSTVT T FIRSTVT E 即FIRSTVT E i LASTVT集构造方法 由P a或P aQ 则a LASTVT P 若a LASTVT Q 且P Q 则a LASTVT P 也即LASTVT Q LASTVT P 由 得 E T 得LASTVT E T P 得LASTVT T P i 得LASTVT P i 由 得 由T P得LASTVT P LASTVT T 即LASTVT T i 由E T得LASTVT T LASTVT E 即LASTVT E i 优先关系表构造方法 对P ab 或P aQb 有ab 对P aR 而b FIRSTVT R 有a b 对P Rb 而a LASTVT R 有a b 解之无 由 得 E T 即 FIRSTVT T 有 i T P 即 FIRSTVT P 有 i 由 得 E E 即LASTVT E 有 i T T 即LASTVT T 有 i 得到优先关系表见表3 3 由于该文法的任何产生式的右部都不含两个相继并列的非终结符 故属算符文法 且该文法中的任何终结符对 见优先关系表 至多满足 和 三种关系之一 因而是算符优先文法 表3 3习题3 12的优先关系表 2 用关系图构造优先函数的方法是 对所有终结符a用有下脚标的fa ga为结点名画出全部终结符所对应的结点 若存在优先关系a b或ab 则画一条从fa到ga的有向弧 若a b或ab 则画一条从gb到fa的有向弧 最后 对每个结点都赋一个数 此数等于从该结点出发所能到达的结点 包括出发结点 的个数 赋给fa的数作为f a 赋给gb的数作为g b 用关系图法构造本题的优先函数 如图3 11所示 得到优先函数见表3 4 图3 11习题3 1 表3 4习题3 12的优先函数表 该优先函数表经检查与优先关系表没有矛盾 故为所求优先函数 也可由定义直接构造优先函数 其方法是 对每个终结符a 令f a g a 1 如果a b 而f a g b 则令f a g b 1 如果a b 而f a g b 则令g b f a 1 如果ab 而f a g b 则令min f a g b max f a g b 重复上述过程 直到每个终结符的函数值不再变化为止 如果有一个函数值大于2n n为终结符个数 则不存在优先函数 优先函数的计算过程如表3 5所示 表3 5优先函数的计算过程 3 13设有文法G S S a b A A SdA S 1 构造算符优先关系表 2 给出句型 SdSdS 的短语 简单短语 句柄 素短语和最左素短语 3 给出输入串 adb 的分析过程 解答 1 先求文法G S 的FIRSTVT集和LASTVT集 由S a b A 得FIRSTVT S a b 由A Sd 得FIRSTVT A d 又由A S 得FIRSTVT S FIRSTVT A 即FIRSTVT A d a b 由S a b A 得LASTVT S a b 由A dA得LASTVT A d 又由A S得LASTVT S LASTVT A 即LASTVT A d a b 构造优先关系表方法如下 对P ab 或P aQb 有ab 对P aR 而b FIRSTVT R 有a b 对P Rb 而a FIRSTVT R 有a b 由此得到 由S A 得 由S A 得 FIRSTVT A 即 d a b 由A dA得d FIRSTVT A 即d d d a d b d 由S A 得LASTVT A 即d a b 由A Sd 得LASTVT S d 即a d b d d 此外 由 S 得 由 FIRSTVT S 得 a b 由LASTVT S 得a b 最后得到算符优先关系表 见表3 6 由表3 6可以看出 任何两个终结符之间至多只满足 三种优先关系之一 故G S 为算符优先文法 表3 6习题3 13的算符优先关系表 2 为求出句型 SdSdS 的短语 简单短语 句柄 我们先画出该句型对应的语法树 如图3 12所示 由图3 12得到 短语 S SdS SdSdS SdSdS 简单短语 即直接短语 S句柄 即最左直接短语 S可以通过分析图3 12所示的语法树来求素短语和最左素短语 即找出语法树中的所有相邻终结符 中间可有一个非终结符 之间的优先关系 确定优先关系的原则是 图3 12句型 SdSdS 的语法树 同层的优先关系为 不同层时 层次离树根远者优先级高 层次离树根近者优先级低 恰好验证了优先关系表的构造算法 在句型 两侧加上语句括号 即 则有 和 由此我们得到句型 SdSdS 的优先关系如图3 13所示 注意 句型中的素短语具有如下形式 图3 13句型 SdSdS 的优先关系 而最左素短语就是该句型中所找到的最左边的那个素短语 即最左素短语必须具备三个条件 至少包含一个终结符 是否包含非终结符则按短语的要求确定 除自身外不得包含其他素短语 最小性 在句型中具有最左性 因此 由图3 13得到SdS为句型 SdSdS 的素短语 它同时也是该句型的最左素短语 3 输入串 adb 的分析过程见表3 7 为便于分析 同时给出了 adb 的语法树 如图3 14所示 表3 7输入串 adb 的分析过程 图3 14 adb 的语法树 3 14在算符优先分析法中 为什么要在找到最左素短语的尾时才返回来确定其对应的头 能否按扫描顺序先找到头后再找到对应的尾 为什么 解答 设句型的一般形式为N1a1N2a2 NnanNn 1 其中 每个ai都是终结符 而Ni则是可有可无的非终结符 对上述句型可以找出该句型中的所有素短语 每个素短语都具有如下形式 如果某句型得到的优先关系如下 则当从左至右扫描到第一个 时 再由此从右至左扫描到第一个 它们之间 当然不包含第一个 前的一个终结符和第一个 后的一个终结符 即为最左素短语 如果由左至右扫描到第一个 可以看出这并不一定是最左素短语的开头 因为由它开始并不一定是素短语 在其内部还可能包含其他更小的素短语 因此 在算符优先分析算法中 只有先找到最左素短语的尾 即 才返回来确定与其对应的头 即 而不能按扫描顺序先找到头然后再找到对应的尾 3 15试证明在算符文法中 任何句型都不包含两个相邻的非终结符 解答 设文法G S VT VN S 其中VT是终结符集 VN是非终结符集 为产生式集合 S是开始符号 对句型的推导长度n作如下归纳 1 当n 1时 S 则存在一条产生式S 属于 其中a VT VN 由于文法是算符文法 所以 中没有两个相邻非终结符 故归纳初始成立 2 设n k时结论成立 则对任何k 1步推导所产生的句型必为其中 VT VN U VN 而U V是一条产生式 由归纳假设 U是非终结符 设 1 2 n 1 2 m 其中 i j VT VN 1 i n 1 2 j m 但 n和 m必为位于U两侧的终结符 设V V1V2 Vr 由于它是算符文法的一个产生式右部候选式 因此V1V2 Vr中不会有相邻的非终结符出现 又因为 nV1和Vr 1中的 n 1为终结符 也即在推导长度为k 1时所产生的句型 1 2 nV1V2 Vr 1 2 m不会出现相邻的非终结符 故n k 1时结论成立 显然 在 或 为空时结论也成立 3 16给出文法G S S aSb PP bPc bQcQ Qa a 1 它是Chomsky哪一型文法 2 它生成的语言是什么 3 它是不是算符优先文法 请构造算符优先关系表并证实之 4 文法G S 消除左递归 提取公共左因子后是不是LL 1 文法 请证实 解答 1 根据Chomsky的定义 对任何形如A 的产生式 有A VN VT VN 时为2型文法 而文法G S 恰好满足这一要求 故为Chomsky2型文法 2 由文法G S 可以看出 S推出串的形式是aiPbi i 0 P推出串的形式是bjQcj j 1 Q推出串的形式是ak k 1 因此 文法G S 生成的语言是L aibjakcjbi i 0 j 1 k 1 3 求出文法G S 的FIRSTVT集和LASTVT集 FIRSTVT S a b FIRSTVT P b FIRSTVT Q a LASTVT S b c LASTVT P c LASTVT Q a 构造优先关系表如表3 8所示 由于在优先关系中同时出现了a a和a a以及b b和b b 故文法G S 不是算符优先文法 表3 8习题3 16的优先关系表 4 消除文法G S 的左递归 S aSb PP bPc bQcQ aQ Q aQ 提取公共左因子后得到文法G S S aSb PP bP P Pc QcQ aQ Q aQ 求每个非终结符的FIRST集和FOLLOW集如下 FIRST S a b FIRST P b FIRST P a b FIRST Q a FIRST Q a FOLLOW S b FOLLOW P b c FOLLOW P b c FOLLOW Q c FOLLOW Q c 通过检查G S 可以得到 每一个非终结符的所有候选式首符集两两不相交 存在形如A 的产生式Q aQ 但有FIRST aQ FOLLOW Q a c 所以文法G S 是LL 1 文法 3 17LR分析器与优先关系分析器在识别句柄时的主要异同是什么 解答 如果S aA 且有A 则称 是句型 相对于非终结符A的短语 特别的 如果有A 则称 是句型 相对于规则A 的直接短语 一个句型的最左直接短语称为该句型的句柄 规范归约是关于 的一个最右推导的逆过程 因此 规范归约也称最左归约 请注意句柄的 最左 特征 LR分析器用规范归约的方法寻找句柄 其基本思想是 在规范归约的过程中 一方面记住已经归约的字符串 即记住 历史 另一方面根据所用的产生式推测未来可能碰到的输入字符串 即对未来进行 展望 当一串貌似句柄的符号串呈现于栈顶时 则可根据历史 展望以及现实的输入符号等三方面的材料 来确定栈顶的符号串是否构成相对某一产生式的句柄 事实上 规范归约的中心问题恰恰是如何寻找或确定一个句型的句柄 给出了寻找句柄的不同算法也就给出了不同的规范归约方法 如LR 0 SLR 1 LR 1 以及LALR就是在归约方法上进行区别的