《编译原理》子集构造算法

subset_construct.js

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))
}

test.js

let subset_construct = require('./subset_construct')
require('mocha')
require('should')

/**
 * 模拟《编译原理》P98
 */
describe('============Subset Construction Test============', function () {

    //字符集
    let charset = ['a', 'b'];
    //NFA转换表 
    /*
    NFA
        a             b
    0   {3,8}       {5}
    1   {3}         {5}
    2   {3}         \
    3   {3,8}       {5}
    4   \           {5}
    5   {3,8}       {5}
    6   {3,8}         {5}
    7   {8}         \
    8   \           {9}
    9   \           {10}
    */
    let Ntran = {
        0: { '': [1, 2, 4, 7], a: [3, 8], b: [5] },
        1: { '': [2, 4], a: [3], b: [5] },
        2: { '': [], a: [3], b: [] },
        3: { '': [1, 2, 4, 6, 7], 'a': [3, 8], 'b': [5] },
        4: { '': [], 'a': [], 'b': [5] },
        5: { '': [1, 2, 4, 6, 7], 'a': [3, 8], 'b': [5] },
        6: { '': [1, 2, 4, 7], 'a': [3, 8], 'b': [5] },
        7: { '': [], 'a': [8], 'b': [] },
        8: { '': [], 'a': [], 'b': [9] },
        9: { '': [], 'a': [], 'b': [10] },
        10: { '': [], 'a': [], 'b': [] },
    }

    //预期的的DFA转换表
    let expected = require('./expected_dfa.json')

    describe(`
    charset: ${JSON.stringify(charset)}
    NFA: ${JSON.stringify(Ntran)}
    `, function () {
        it(`expected ${JSON.stringify(expected)}`, function () {
            let actual = subset_construct(charset, Ntran)
            should.deepEqual(actual.Dtran, expected.Dtran)
            should.deepEqual(actual.Dstates, expected.Dstates)

        })
    })
})