西理工编译原理试题集1-7(4)

令S表示不以0开始的奇数集合。

S → 〈奇数头〉〈整数〉〈奇数尾〉|〈奇数头〉〈奇数尾〉|〈奇数尾〉 〈奇数尾〉→ 1|3|5|7|9

〈奇数头〉→ 2|4|6|8|〈奇数尾〉 〈整数〉→ 〈整数〉〈数字〉|〈数字〉 〈数字〉→ 0|〈奇数头〉

9写一个上下文无关文法CFG，使其语言是能被5整除且不以0开头的无符号整数的集合。（如｛5,10,15，?.｝） 答：

能被5整除的数从形式上看，是以0和5结尾的数字串。题目要求的不以0开头，并要注意0不是该语言的句子。所求文法为： G(S)：S→MF｜5

F→5｜0

M→MD｜N D→N｜0

N→1｜2｜3｜4｜5｜6｜7｜8｜9 10证明下面的文法是二义的：

S→iSeS｜iS｜i

答：（根据文法的二义性的定义，如果要证明该文法是二义的，必须找到一个句子，使得该句子具有两个不同的最右推导或两个不同的语法树。我们首先分析这个文法，根据我们对程序语言的了解，不难发现，这个文法应该是用来表示if?.else?.结构的（用“i”代表“if”或语句集，“e”代表“else”）。因此我们就要到if?.else?结构中去找二义性。我们知道，程序语言一般都规定else部分是和它前面离它最近的没有被匹配的的if语句进行匹配。而上面的这个文法体现不出这种限制，因此我们可以找这样一个句子，在else前面有两个if（如句子iiiei），else和不同的if进行匹配时就会产生不同的语义。） 解答：

考虑句子iiiei，存在如下两个最右推导： S => iSeS => iSei => iiSei => iiiei S => iS => iiSeS => iiSei => iiiei

11 某程序设计语言的表达式由运算符θ1、θ2、θ3、标识符、（、）组成，其中θ1和θ2的优先级相同，θ3的优先级低于θ1、θ2的优先级，优先级相同的运算符从右往左计算，可以用括号改变运算的顺序，则下述四种文法中哪一个可以描述上述的表达式文法？

设E为识别符号，终结符号集=,θ1、θ2、θ3、（、）、I}，非终结符号集={E、T、F}。

a.

E→T|Eθ1T|Eθ2T T→F|Tθ3F F→(E)|I

b. E→T|Tθ1E|Tθ2E

T→F|Fθ3T F→(E)|I

c. E→T|Eθ3T

T→F|Tθ1F|Tθ2F F→(E)|I

d. E→T|Tθ3 E 答：

（对于一个包含运算符的语言，运算符的结合顺序、运算符的优先级在文法中反映为递归的方向和推导（或规约）的先后，左递归表明左边的运算先处理，对应的运算符左结合；右递归表明右边的运算先处理，对应的运算符右结合。两个运算符连续出现，后推导出（或先被规约）的，表明其运算先被处理，因此优先级高；反之，先推导出（或后被规约）的，表明其运算后被处理，因此优先级低。） 题意要求：θ1和θ2的优先级相同，θ3的优先级低于θ1、θ2的优先级，因此θ3比θ1、θ2先推导出来，即应为图3所示的四种情形。

T→F|Fθ1T|Fθ2T F→(E)|I

U U V θ 1θ 3V (1) U U U θ 3V (2) U U θ 1V V U θ 2θ 3V (3) U U U θ 3V (4) U θ 2V 图3可能的文法推导顺序 因此a和b不成立。

又因为优先级相同的运算符从右往左计算，应采用右递归，即应为图4所示的情形。

U U θ 1W (1) U V θ 1V U θ 2W (2 U V θ 2V U θ 3W (3) V θ 3V

图4可能的文法递归结构 故c不成立,应为d。

第三章 词法分析

本章要点

１．词法分析器设计， ２．正规表达式与有限自动机， ３．词法分析器自动生成。

本章目标：

１．理解对词法分析器的任务，掌握词法分析器的设计； ２．掌握正规表达式与有限自动机； ３．掌握词法分析器的自动产生。

本章重点：

1．词法分析器的作用和接口，用高级语言编写词法分析器等内容，它们与词法分析器的实现有关。应重点掌握词法分析器的任务与设计，状态转换图等内容。 2．掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法。 （1）非形式描述的语言 ? 正规式

（2）正规式 ? NFA（非确定的有限自动机） （3）NFA ? DFA（确定的有限自动机） （4）DFA ? 最简DFA 本章难点

（1） 非形式描述的语言 ? 正规式

（2） 正规式 ? NFA（非确定的有限自动机） （3） NFA ? DFA（确定的有限自动机） （4） DFA ? 最简DFA

作业题 一、单项选择题

（按照组卷方案，至少15道）

1. 程序语言下面的单词符号中， 一般不需要超前搜索

a. 关键字 b. 标识符 c. 常数 d. 算符和界符 2. 在状态转换图的实现中， 一般对应一个循环语句

a. 不含回路的分叉结点 b. 含回路的状态结点 c. 终态结点 d. 都不是 3. 用了表示字母，d表示数字，?={l，d}，则定义标识符的正则表达式可以是： 。

(a)ld* (b)ll* (c)l(l | d)* (d)ll* | d* 4. 正规表达式(ε|a|b)2表示的集合是

(a),ε，ab，ba，aa，bb} (b){ab，ba，aa，bb}

(c){a，b，ab，aa，ba，bb- (d),ε，a，b，aa，bb，ab，ba}

5. 有限状态自动机可用五元组（VT，Q，δ，q0，Qf）来描述，设有一有限状态自动机M的定义如下：

VT={0， 1}，Q={q0， q1， q2}，Qf={q2}，δ的定义为： δ（q0，0）=q1 δ（q1，0）=q2 δ（q2，1）=q2 δ（q2，0）=q2 M所对应的状态转换图为 。

6. 有限状态自动机可用五元组（VT，Q，δ，q0，Qf）来描述，设有一有限状态自动机M的定义如下：

VT={0， 1}，Q={q0， q1， q2}，Qf={q2}，δ的定义为： δ（q0，0）=q1 δ（q1，0）=q2 δ（q2，1）=q2 δ（q2，0）=q2

M所能接受的语言可以用正则表达式表示为 。

①(0|1)* ②00(0|1)* ③(0|1)*00 ④0(0|1)*0

7 . 有限状态自动机可用五元组（VT，Q，δ，q0，Qf）来描述，设有一有限状态自动机M的定义如下：

VT={0， 1}，Q={q0， q1， q2}，Qf={q2}，δ的定义为： δ（q0，0）=q1 δ（q1，0）=q2 δ（q2，1）=q2 δ（q2，0）=q2 M所能接受的语言为 。

①由0和1所组成的符号串的集合

②以0为头符号和尾符号、由0和1所组成的符号串的集合 ③以两个0结束的，由0和1所组成的符号串的集合 ④以两个0开始的，由0和1所组成的符号串的集合

8. 从接受语言的能力上来说，非确定型有穷自动机和________是等价的。

a. ⅰ.正规式；ⅱ.上下文无关文法；ⅲ.确定性有穷自动机；

b. ⅰ.左线性正规文法；ⅱ.右线性正规文法；ⅲ.确定性有穷自动机； c. ⅰ.正规式；ⅱ.上下文无关文法；ⅲ.正规文法； d. ⅰ.正规式；ⅱ.确定性有穷自动机；ⅲ.下推自动机；

9. 下面四个选项中，关于编译过程中扫描器的任务的叙述，________是较为完整且正确的。 ①组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输出；删除注释；删除空格和无用字符；行计数、列计数；发现并定位词法错误；建立符号表。 ②按词法规则分割出单词，识别其属性，并转换成属性字的形式输出；发现并定位词法错误；建立符号表；输出状态转换图；把状态转换图自动转换成词法扫描程序。

③组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输出。

④组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字 …… 此处隐藏：1705字，全部文档内容请下载后查看。喜欢就下载吧 ……