# compiler-coursework

**Repository Path**: polarlush/compiler-coursework

## Basic Information

- **Project Name**: compiler-coursework
- **Description**: 1. Python程序实现自动机最小化并生成求解过程pdf文件
2. 使用 O(n) 算法求解FIRST，FOLLOW，SELECT 集
- **Primary Language**: Python
- **License**: GPL-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-06-10
- **Last Updated**: 2022-11-03

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 项目简介

## 目录结构

* LL_1 - LL(1)文法求解FIRST(), FOLLOW(), SELECT()的Python程序目录
* NFA - NFA转为DFA，并将DFA最小化并输出

## NFA convert

### quintuple of NFA

以下给出NFA的正规定义：

<Q, Σ, q0, F, δ>:

A finite set of States (Q)
A finite set of Input Alphabets (Σ)
Start State (q0)
A finite set of Final States (F)
Transition Function (δ)

### Steps to transfer NFA

给出NFA到DFA转换过程如下：

#### Epsilon Closure

首先需要实现计算epsilon闭包的算法，
其基本思路仿照是一个树形图**遍历搜索算法**。
所以我们的算法总体上使用BFA以及一个栈模拟递归。
epsilon算法在图中搜索一个给定root结点的所有子结点，查看边上的转移条件。
当这个条件是epsilon时把这个子结点保留在搜索路径，否则把这个子结点为根的树剪去。

#### NFA to DFA

一个NFA的等价DFA具有和NFA一样的字符集Σ，但其余的所有元素都不一样。

构建等价DFA的状态结点的方式是将所有当前可能**状态的集合**作为一个DFA的**状态结点**。
首先需要构造新的初始状态**q0**，这个状态的epsilon-closure构成等价DFA的q0
我们根据可能接受的字符**依次**从旧状态构造新的结点和新的**状态转换函数**。

#### Minimize

最小化的算法是构造等价的集合分划。
首先给出原始分划：终态集和非终态集。

对于一个给定的分划，对其执行**等价验证算法**。
该算法的思想是对于一个状态集合S，取该集合第一个元素。将集合剩余的元素依次与第一个元素比较，如果全都与第一个元素相等，那么它们都等价。与第一个元素不相等的元素则存入暂时未求解的元素集合unresolved，留到之后求解。