编译原理复习一：正则表达式-NFA NFA-DFA DFA最小化（附题目与答案超详细）

梦里梦外; 2023-09-30 19:46 8阅读 0赞

> **需要原卷和答案可以点赞关注收藏评论区留言私信**
> 
> **对题目解法有疑问也可留言**

下面以具体考试题目来讲解编译原理考试中的重点题目，大致可以分为以下几道大题

1：正则表达式转换为NFA，NFA转换为DFA，DFA最小化

2：LR(0)分析，构造LR(0)自动机，进一步对SLR(1)进行分析，由于LR(1)状态数太多过于复杂，考试中一般不会手动构造

3：语义分析中注释语法树的构造与对节点求值

4：中间代码生成中的生成三地址码等等

下面着重讲解正则表达式转换为NFA，NFA转换为DFA，DFA最小化这三个过程，考试中通常作为一道大题的三个小问呈现，必须掌握

下面是一些基本概念的编译器结构的填空题

1.  Fill in the blanks

a. Normally, A complier consists of a number of phases. They are Scanner, \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_, \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_, \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_, Code Generator, and \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_.

b. The logical units the scanner generates are called Tokens. For a modern programming language, there are five types of token. They are \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_, \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_, \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_, \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_, \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_.

## 答案 ##

a. \_\_Grammar\_Parser\_, \_\_\_\_Sematic Analyzer\_\_\_, \_\_Source Code Optimizer\_, \_Target Code Optimizer \_.

b.\_\_Reserved Words\_\_\_\_, \_\_\_Identifier\_\_\_\_\_\_, \_\_\_Number\_\_\_\_, \_\_\_\_Operator\_\_\_, \_\_Special Symbol\_\_

a) “int” is a \_\_\_ Reserved Word b) “printf” is a \_\_\_Reserved Word  c) “s” is a (an) \_ Identifier \_\_

d) “= =” is a \_\_\_\_\_ Operator\_\_\_\_\_ e) “0” is a\_\_\_\_\_\_ Number\_ \_\_\_\_

d. Terminal symbol Non-Terminal symbol, start symbol ,and \_\_\_Product Rules

1.  1.  Compiler —— 一种应用程序，将源代码转换为指定的目标代码。
    2.  Source code —— 文本文件，其中内容是按照指定的文法规则描述特定的算法，
    3.  Scanner —— 将文本字符串按照词法规则，转换为特定的内部标识，供编译器后续分析。
    4.  Tokens ——源文件中最基本的信息单元
    5.  Terminal symbol ——文法规则中不需要产生式定义的符号

Ambiguous Grammar —使用不同推导方法，推导出不同语法树，就称该文法为二义文法

## 一、正则表达式转换为NFA ##

**Construct minimum-state DFA for the following regular expression: a(b|ab)\*, which includes：**

Convert the regular express into NFA first

Convert the NFA into DFA

Minimize the state of DFA

让我们看看正则表达式是如何转换为NFA的，主要是对三个规则的应用，对正则表达式中连接，并，闭包三个运算的具体展开

答案如下

![19966b7ba7224e73b89aac895c491c66.png][]

## 二、NFA转换为DFA ##

接下来把NFA转换为DFA，一般用到的是子集构造法，这里博主用自己的话通俗易懂的描述以下

> 有一个表 表的列为输入符号和I
> 
> 第一列第一行I填入从开始状态出发经过任意个空集能到达的状态 Ia Ib填从I中状态出发经过一个a或者一个b所能到达的状态，经过一个a或者一个b后后面可以跟任意个空集（注意空集必须出现在a或b的后面）
> 
> 然后把第一行的Ia Ib填入第二行的I中，重复上面的规则，直至没有新状态加入I中，然后给I中状态重新编号即可

![19d46594cd4348a09585f9f3afe6f628.png][]

新状态构造后的DFA如下

![e9d90e93eeb8444d8d83c9a7a3bfbe95.png][]

## 三、DFA最小化 ##

DFA最小化一般就是进行状态的划分，把不可区分的状态分为一类

> 状态间可区分定义：两个状态输入同一个输入符号时，一个进入非接受状态，另一个进入接受状态则说这个输入符号区分这两个状态
> 
> 一开始将状态划分为接受状态和非接受状态两类，然后反复运用上面规则直至不能划分即可

上述DFA最小化如下

![838812ac0cf1428e837ff1fbd7302873.png][]

**创作不易 觉得有帮助请点赞关注收藏~~~**

[19966b7ba7224e73b89aac895c491c66.png]: https://img-blog.csdnimg.cn/19966b7ba7224e73b89aac895c491c66.png
[19d46594cd4348a09585f9f3afe6f628.png]: https://img-blog.csdnimg.cn/19d46594cd4348a09585f9f3afe6f628.png
[e9d90e93eeb8444d8d83c9a7a3bfbe95.png]: https://img-blog.csdnimg.cn/e9d90e93eeb8444d8d83c9a7a3bfbe95.png
[838812ac0cf1428e837ff1fbd7302873.png]: https://img-blog.csdnimg.cn/838812ac0cf1428e837ff1fbd7302873.png