《编译原理》期末复习资料（完整版）

n n m m

1. 给出语言{abab| n,m≥0}的一个上下文无关文法。(6分)

解：G[S]：S—>AB

A—>aAb |ε B—>aBb |ε n m m n

2. 给出语言{1010| n,m≥0}的一个上下文无关文法。

解： G[S]：S—>1S0 | A

A—>0A1 |ε

3. P48 第6题（5）、（6）.画语法树

6、已知文法G：

<表达式>::=<项>｜<表达式>＋<项> <项>::=<因子>｜<项>*<因子> <因子>::=（<表达式>）｜i （５）i+(i+i) （６）i+i*i

解：(5)语法树： （6）语法树：

4. P48第13题 直接短语等

13、 一个上下文无关文法生成句子abbaa的推导树如下：

(3)求直接短语

解：直接短语有：a ε b

P102例题6.1及其分析.( 后加画语法树) 例6.1 设文法G[S]为： (1)S—>aAcBe (2)A—>b (3)A—>Ab (4)B—>d

对输入串abbcde#进行分析，检查该符号串是否是G[S]的句子。

解：设一个先进后出的符号符，并把句子左括号“#”号放入栈底，其分析过程如下： 步骤 （1） （2） （3） （4） （5） （6） （7） （8） （9） （10） （11） 符号栈 # #a #ab #aA #aAb #aA #aAc #aAcd #aAcB #aAcBe #S 输入符号串 abbcde# 移进 bbcde# 移进 bcde# 归约（A—>b） bcde# 移进 cde# 归约（A—>Ab） cde# 移进 de# 移进 e# 归约（B—>d） e# 移进 # 归约（S—>aAcBe） # 接受 动作 语法树如下：

一、 计算分析题（60%）

1、正规式→ NFA→ DFA→ 最简DFA P72第1题（1）、（4）；

第一题1、构造下列正规式相应的DFA.

（1）1(0|1)*101 解：先构造NFA

用子集法将NFA确定化 S A AB AC ABZ 0 A AC A AC 1 A AB AB ABZ AB 除S，A外，重新命名其他状态，令AB为B、AC为C、ABZ为D，因为D含有Z（NFA的终态），所以D为终态,因此有： S A B C D 得到DFA如下所示： 0 A C A C 1 A B B D B

(4) b((ab)*|bb)*ab 解：先构造NFA

得到DFA如下所示：

P72第4题（a）

4、把下图确定化和最小化

解：确定化：

用子集法将NFA确定化 0 01 1 a 01 01 0 b 1 1 重新命名，以Ａ、Ｂ、Ｃ代替{0}、{01}、{1}，其中A为初态，A，B为终态，因此有：

A B C a B B A b C C 最小化：：

初始分划得终态组{A,B}，非终态组{C}

Π0：{A,B}，{C}，对终态组进行审查，判断A和B是等价的，故这是最后的划分。重新命名，以A、C代替{A,B}、{C}，因此有： A C a A A b C 即DFA最小化如下：

第7题

7、给文法G[S]： S→aA|bQ A→aA|bB|b B→bD|aQ Q→aQ|bD|b D→bB|aA E→aB|bF F→bD|aE|b

构造相应的最小的DFA。 解：先构造NFA：

用子集法将NFA确定化： S A BZ B Q DZ D a A A Q Q Q A A b Q BZ D D DZ B B 将S、A、BZ、B、Q、DZ、D重新命名，分别用0、1、2、3、4、5、6表示。因为2、5中含有Z，所以它们为终态。因此有： 0 1 2 3 4 5 a 1 1 4 4 4 1 b 4 2 6 6 5 3

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《编译原理》期末复习资料（完整版）在线全文阅读。