Last active
February 28, 2020 07:43
-
-
Save light0x00/6f4f64b62d3a53e112ff8371a11e795c to your computer and use it in GitHub Desktop.
《编译原理》子集构造算法
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| const _ = require("lodash"); | |
| /** | |
| * 使用子集构造法,将NFA转为DFA. 基于《编译原理》P97的伪代码的实现. | |
| * @param charset NFA所接受的字符集 | |
| * @param Ntran NFA转换表 | |
| */ | |
| module.exports = function subset_construct(charset, Ntran) { | |
| let cursor = 0; //区分Dstates中的状态集是否访问过. cursor之前的为已访问, cursor之后为未访问. | |
| let Dstates = [] //DFA的状态集 | |
| let Dtran = {} //DFA的转换表 | |
| Dstates.push(e_closure([0])) //起始状态0输入e可到达的状态集 | |
| //遍历尚未标记的DFA状态 T | |
| while (cursor < Dstates.length) { | |
| let T = Dstates[cursor]; | |
| cursor++; | |
| Dtran[T] = {} | |
| for (let c of charset) { | |
| let T_c = move(T, c) //状态T 在输入c时可达的非空状态集 T_c | |
| let T_e = e_closure(T_c) //状态集 T_c 可达的 | |
| let U = combine(T_c, T_e) | |
| //判断状态集U 是否已经存在于Dstates 不存在则放入 | |
| let exists = Dstates.find(states => states.length == U.length && _.difference(states, T).length == 0 | |
| ) != null | |
| if (!exists) { | |
| Dstates.push(U) | |
| } | |
| /* | |
| 放入DFA转换表,这表示T在分别输入(charset U ε)中的每一个字符时,可达的状态集, | |
| */ | |
| Dtran[T][c] = U | |
| } | |
| } | |
| /** | |
| * 返回给定状态集T输入ε可达的状态集 | |
| * @param {*} T 状态集T | |
| */ | |
| function e_closure(T) { | |
| let result = [] | |
| for (let s of T) { | |
| result = combine(result, Ntran[s]['']) | |
| result = combine(result, e_closure(Ntran[s][''])) //递归寻找ε | |
| } | |
| return result | |
| } | |
| /** | |
| * 返回给定状态集T输入c可达的状态集 | |
| * @param {*} T 状态集T | |
| */ | |
| function move(T, input) { | |
| let result = [] | |
| for (let s of T) { | |
| result = combine(result, Ntran[s][input]) | |
| } | |
| return result | |
| } | |
| return { Dstates, Dtran } | |
| } | |
| /* 工具性方法 */ | |
| function combine(arr1, arr2) { | |
| return _.sortBy(_.union(arr1, arr2)) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment