# compilers_exp4

**Repository Path**: howarli/compilers_exp4

## Basic Information

- **Project Name**: compilers_exp4
- **Description**: 编译原理实验4，正则表达式转最小化DFA
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-11-29
- **Last Updated**: 2023-05-16

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Implementation of Regular expression


# Regular expression to NFA
使用了给出的示例代码，未作任何改变；

# convert NFA to DFA
基于给出的示例代码，完全重构了子集构造法的核心代码(`StateMinimization.java`)，并在DFA中新增自动NFA节点管理功能(`DFA.java`)
- 修复的示例代码BUG若干；
- 大幅提高代码效率，大幅减少DFA中的无用点；
- 使用了标准dfs代码结构，代码思路清晰易读；
- DFA对象自动管理NFA节点映射，使子集构造法代码简洁；
- DFA对象支持输出节点映射信息，转换结构更加清晰；

# DFA minimization
使用课本算法3.39最小化DFA状态数的算法，自主独立搭建代码结构(`StateMinimization.java`)
- 严格保证复杂度最坏不超过$O(n^2)$；
- 支持输出最小化后的DFA与原来DFA的映射关系；
- 保留DFA与NFA的映射信息；

# Example
## `c(a|b)*`
以正则表达式`c(a|b)*`为例，
程序构建出的NFA如下图所示：（红色为开始状态，蓝色为接受状态）

![NFA](NFA.png)

程序构建出的DFA如下图所示：（红色为开始状态，蓝色为接受状态）

![DFA](DFA.png)

最小化后的DFA只存在2个点，3条边，分别是：
```
(20:0->21:2 @ c)
(21:2->21:2 @ a)
(21:2->21:2 @ b)
```

程序原始输出为
```
1) Decompose the input regex into  subRegexes. 
2) Convert the regex into a regex tree;
        2.1) Convert the regex into a tree.
        2.2) Show the structure of the regex tree. 
regexID:pattern_c(a|b)* regex:c(a|b)*   RegexTree:
(-)->1
        firstChild:(c)->0
        (*)->3
(c)->0
(*)->3
        firstChild:(|)->2
(|)->2
        firstChild:(a)->0
        (b)->0
(a)->0
(b)->0
1) Convert the regex tree into a NFA.
3.1) build the NFA by Thompson construction. 
3.2) show the structure of the NFA. 
Start State:2
the transitTable is: 
(2:0->3:1 @ c)
(8:1->9:1 @ a)
(6:1->8:1 @ ε)
(9:1->7:1 @ ε)
(10:1->11:1 @ b)
(6:1->10:1 @ ε)
(11:1->7:1 @ ε)
(4:1->6:1 @ ε)
(7:1->5:2 @ ε)
(4:1->5:2 @ ε)
(7:1->6:1 @ ε)
(3:1->4:1 @ ε)
1) Now convert the regexes to a NFA by merging the start states into one start state and the accepting states into one accepting state!
Start State:12
the transitTable is: 
(2:1->3:1 @ c)
(8:1->9:1 @ a)
(6:1->8:1 @ ε)
(9:1->7:1 @ ε)
(10:1->11:1 @ b)
(6:1->10:1 @ ε)
(11:1->7:1 @ ε)
(4:1->6:1 @ ε)
(7:1->5:1 @ ε)
(4:1->5:1 @ ε)
(7:1->6:1 @ ε)
(3:1->4:1 @ ε)
(12:0->2:1 @ ε)
(5:1->13:2 @ ε)
1) Now convert the NFA to a DFA by Subset Construction!
original DFA:
======== show DFA ========
Start State:15
DFA to NFA state set mapping:
        15:0 = {12, 2}
        16:2 = {4, 13, 10, 5, 8, 3, 6}
        17:2 = {13, 10, 9, 5, 8, 6, 7}
        18:2 = {13, 10, 5, 8, 6, 7, 11}
the transitTable is: 
(15:0->16:2 @ c)
(16:2->17:2 @ a)
(16:2->18:2 @ b)
(17:2->17:2 @ a)
(17:2->18:2 @ b)
(18:2->17:2 @ a)
(18:2->18:2 @ b)
=========================
1) Minimize the DFA
Start DFN minimizing...
DFA minimize state set mapping: (new state = {old states})
        20:1 = {15}
        21:2 = {16,17,18}
DFA minimization done  (state count 4 -> 2 )
======== show DFA ========
Start State:20
DFA to NFA state set mapping:
        20:1 = {12, 2}
        21:2 = {4, 13, 10, 9, 5, 8, 3, 6, 7, 11}
the transitTable is: 
(20:0->21:2 @ c)
(21:2->21:2 @ a)
(21:2->21:2 @ b)
=========================
Bye, world!
```