编译原理习题与解析（第2版）·二区了 B-BAIB010 B→BAlBOJE A→123…9 A→123…9 答案：d 分析： a不能惟导出一位偶数 b.不能推导出所有满足条件 一位 二位偶数，如12 c.不能推导出满足条件的二位偶数，如12。 d.从Z正好推导出语言：{xx是非0开头的正偶数} 所以选d。 8.(湖北省高等教育白学考试)设有文法 G[四：I→I1 IOIaIcla[blc 下列符号申中是该文法的句子的有 ①ab0②a0c0l③aaa④bcl0 可选项有： a.①b.②③④c.③④d.①2③④ 答案：b 分析： 句子的定义为：由文法开始符号推导出的符号串为句型，全部由终结符号组成的句型 为句子。 这个定义不仅说明了什么样的符号串是句子，同时也给出了问题的求解方法：判断 个符号串是否为文法描述语言的句子，那就从文法的开始符号出发进行推导，看是否能推 导出一个与该符号串相同的终结符号串。 因为存在推导： I→I1→101→1c01→I0c01→a0c01 Iaaaaaa II0=l10-lc10-bc10 其他符号串不能由开始符号推导出， 所以选b 9.在下述描述程序设计语言语法的BNF表示中，“→”表示(1)_，“1”表示(2) [W表示w可出现(3)_次，{W表示W可出现(4)_次。 设某程序设计语言的ON语句的语法规则为： <ON语句>一ON<变量>G0TO水标号>{，<标号>} <变量>一ABZ <标号>→LL2…L 在下述给定的语句中，不符合语法的语句是(5)一 可选项有 （1)a.恒等于b.不等于 c.取决于d.定义为 24Page
◆第3章文法和语言的形式定义·.■ (2)a.与 b.或 c.非 d.引导开关参数 (3)、(4)a.1b.n(n21)c.n(n22)d.0或1e.n(n20) (5)a.ON A GOTO LI b.ON B LI,LI,L2 c.ON Z GOTO LI L2 d.ON C La,Ly 答案：(1)d(2)b(3)d(4)e(5)c 分析 (5)因为从开始符号<ON语句>出发，存在以下推导： <ON语句>一ON<变量>[GOTO]<标号> {}中内容出现0次 马ON<变量2G0TO<标号> ,0中内容出现1次 →ONAG0T0<标号 ON A GOTO LI <ON语句>→ON<变量>[GOTO小水标号>，标号>，标号>0中内容出现2次 →ON<变量>G0T0<标号>，<标号>，<标号>0中内容出现1次 ONAG0TL1,L1,L2 <ON语句>→ON<变量>GOIO<标号>，<标号>{}中内容出现1次 →ON<变量><标号>，<标号>[中内容出现0次 ONC L2.L3 而符号串“ON Z GOTO L,L2”不能由开始符号<ON语句>推导出。 所以选c。 10.（长沙铁道学院1984)给定文法 G[A]: 下面的符号串中，为该文法句子的是 ①cc②bcbc ③bcbcc④becbec⑤bbbc 可选项有： a.①⑤ b.①③④c.①④ d.①④⑤e.①②③④⑤ 答案：a 分析： 因为从文法开始符号A出发，存在以下推导： A→cc A=bA→bbA=bbbA→bbbcc 其他符号串不能由开始符号A推导出 所以选a。 11,(华中科技大学1993)某程序设计语言的表达式由运算符1、2、、标识符、（和 组成。0、2的优先级相同，的优先级低于0、2，优先级相同的运算符从右向左计算， 可以用括号改变运算顺序，则这种表达式的文法可描述为」 (设E为识别符号 文法字汇表V={E,T,F,(,),01,0,0,i) 洗项有：
编译原理习题与解析（第2版）一二 a.E-T|E0 T E02T b.E-T|TO E TO2E T→FI10 T→FIF0T F-(E)i F-(E)i c.E→TIE0T d.E→TIT0E T→FIT8F|T82F T→FIF0TIFB2T F→(E)i F→(E)i 答案：d 分析： 对于个包含运算符的语言，运算符的结合顺序、运算符的优先级在文法中反映为递 归的方向和推导（或归约）的先后 运算符左递归表明左边的运算先处理，对应运算符左结合；运算符右递归表明右边的 运算先处理，对应运算符右结合。 两个运算符连续出现，后推导出（或先被归约）的，表明其运算先被处理（如优先生 成指令)，因而优先级高：反之，先推导出（或后被归约）的，表明其运算后被处理（如 后生成指令)，因而优先级低。 明白了这一点，该题就好判断了。 对丁题中的要求：日1、02的优先级相同，03的优先级低于01、02，则表明0比01、02先推 导出来，即应该为图3.1所示4种情形。因此题中所给选项a和不成立 U 0 (1) (2) (3) (4) 图3.】可能的文法推导顺序 又因为优先级相同的运算符从右向左计算，这表明应采用右递归。如图3.2所示。故题 中选项c不成立。 1 (2) 图3.2可能的文法递归结构 26 Pag明
、第3章文法和语言的形式定义·” 而选项d满足所有条件，故选d。 12.(湖北省高等教育自学考试)一个句型中的最左 称为该句型的句柄 可选项有： a.短语b.直接短语或简单短语c.素短语d.终结符号 答案：b 13.(湖北省高等教有自学考试)设有文法GT T→T*FF F+F↑PP P→(Ta 该文法句型T*PT(T*F)的直接短语是下列符号串 ①(T*F) ②T*F ③P ④Pt(T*F) 可选项有： a.①和③ b.②和③ c.③ d.①和③ 答案：b 分析： 与句型T*P↑(T*F)相应的语法树如图3.3所示。 图3.3句型TpTF)相应的语法树 直接短语就是简单子树的末端结点符号串，所以，该句型的直接短语为相对于F的P和 相对于T的TF. 14.一个上下文无关文法G包括4个组成部分，它们是：一组(1)，一组(2)， -个(3)，以及一组(4)一· 可选项有： a.字符串 b.字母数字串 c.产生式 d.结束符号 c.开始符号f.文法 g非终结符号h.终结符号 答案：(1)h(2)g(3)e (4)c 15.(大连理工大学1985)如果一个文法的产生式形式是A一Ba或是A一a,其中A
编译原理习题与解析（第2版）二一一 BeVN,a∈VT,则称此文法是左线性的。对每一个左线性文法G1, 一个右线性文 法G2,使得L(G尸L(G2)。 可选项有： a.都存在 b.不存在 c.不一定存在d.无法判定 答案：a 16.(华北计算技术研究所1984) 正规文法能产生下面的语言 L={ab"n21} 可选项有： 且，存在一个 b.不存在任何 c.无法判断 答案：b 分析： 产生该语言的文法是2型文法，如下述文法GS]: GIS]:S-aAblab 17.(华北计算技术研究所1984)上下文无关文法 产生下述语言 L={a%"ce1,n心1} 可选项有： a.可以b.不可以 答案：a 分析： 下述文法G可产生该语言： G[S]:S→AB A-aAblab B-Bclc 18.如果一个文法满足 ,则称该文法是二义文法。 ①文法中存在某个句子，它有两棵（包括两棵）以上不同的语法树 ②文法中存在某个句子，它有两个（包括两个）以上不同的最右（最左）推导 ③文法中存在某个句子，它有两个（包括两个）以上不同的最右（最左）归约 ④在进行归约时，文法的某些规范句型的句柄不惟一 可选项有： a.① b.② c.(3)d.4 e.②③ E①2③ g.①②③④ 答案：g 分析： 推导和归约是互逆的。一个没有二义性的文法的句型的最左、最右推导/归约是惟一的， 且一定对应着惟一的一棵语法树。 19.(武汉大学1988)正规文法 二义性的。 可选项有： a可以是 b.一定不是 c.一定是 28 Page