利用CLOSURE与GO构造识别该文法规范句型活前缀的DFA

首先，我们需要定义该文法的规则，假设该文法为 $G=(\Sigma, N, P, S)$，其中：

- $\Sigma$ 为终结符集合，包含所有的终结符号；
- $N$ 为非终结符集合，包含所有的非终结符号；
- $P$ 为产生式集合；
- $S$ 为开始符号。

然后，我们需要根据该文法构造出一个DFA，用于识别该文法规范句型的活前缀。

构造DFA的过程如下：

1. 定义状态集合 $Q$，其中每个状态代表一个文法符号的集合，即 $Q=\{V|V\subseteq\Sigma\cup N\}$。

2. 定义转移函数 $f$，其中 $f:Q\times(\Sigma\cup N)\rightarrow Q$，表示从当前状态经过一个符号转移到下一个状态。

对于每个状态 $V\in Q$ 和每个文法符号 $X\in\Sigma\cup N$，我们可以根据产生式集合 $P$，构建出从状态 $V$ 经过符号 $X$ 转移的下一个状态，具体方法如下：

- 如果 $X$ 是终结符号，则 $f(V,X)=\{X\}$；
- 如果 $X$ 是非终结符号，则 $f(V,X)$ 包含所有可以由 $V$ 推导出 $X$ 的符号串的集合，即 $f(V,X)=\{wX|V\Rightarrow wX\}$。

3. 定义起始状态 $q_0$，即 $q_0=\{S\}$。

4. 定义接受状态集合 $F$，即 $F=\{V|V\subseteq\Sigma\cup N\text{ 且 }V\text{ 中包含某个非终结符号 }A\text{ 的所有前缀}\}$。

最后，我们可以用 GO 语言来实现该 DFA，代码如下：

type state map[string]struct{}

type dfa struct {
    states     map[state]int
    transitions map[int]map[string]int
    start      int
    accepts    map[int]state
}

func buildDFA(rules []string, start string) *dfa {
    // 构造文法符号集合，包括终结符号和非终结符号
    symbols := make(map[string]bool)
    for _, rule := range rules {
        for _, sym := range strings.Split(rule, " ")[1:] {
            symbols[sym] = true
        }
    }
    // 构造状态集合
    states := make(map[state]int)
    queue := []state{{start}}
    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]
        if _, ok := states[curr]; ok {
            continue
        }
        states[curr] = len(states)
        for sym := range symbols {
            next := make(state)
            for _, rule := range rules {
                if strings.HasPrefix(strings.Join(curr, " "), rule) {
                    rhs := strings.Split(rule, " ")[1:]
                    if len(rhs) > 0 && rhs[0] == sym {
                        next.Add(rhs...)
                    }
                }
            }
            if len(next) > 0 {
                queue = append(queue, next)
            }
        }
    }
    // 构造转移函数和接受状态集合
    transitions := make(map[int]map[string]int)
    accepts := make(map[int]state)
    for s, si := range states {
        transitions[si] = make(map[string]int)
        for sym := range symbols {
            next := make(state)
            for _, rule := range rules {
                if strings.HasPrefix(strings.Join(s, " "), rule) {
                    rhs := strings.Split(rule, " ")[1:]
                    if len(rhs) > 0 && rhs[0] == sym {
                        next.Add(rhs...)
                    }
                }
            }
            if len(next) > 0 {
                if _, ok := states[next]; !ok {
                    panic("unexpected state")
                }
                transitions[si][sym] = states[next]
                if _, ok := next[endSymbol]; ok {
                    if _, ok := accepts[si]; !ok {
                        accepts[si] = make(state)
                    }
                    accepts[si].Add(next.Prefix(endSymbol)...)
                }
            }
        }
    }
    // 返回 DFA
    return &dfa{
        states:     states,
        transitions: transitions,
        start:      states[state{start}],
        accepts:    accepts,
    }
}

func (d *dfa) accepts(input string) bool {
    curr := d.start
    for _, sym := range strings.Split(input, " ") {
        if next, ok := d.transitions[curr][sym]; ok {
            curr = next
        } else {
            return false
        }
    }
    _, ok := d.accepts[curr]
    return ok
}

func (s state) Add(elems ...string) {
    for _, elem := range elems {
        s[elem] = struct{}{}
    }
}

func (s state) Prefix(prefix string) []string {
    res := []string{}
    for elem := range s {
        if strings.HasPrefix(elem, prefix) {
            res = append(res, elem)
        }
    }
    return res
}

const endSymbol = "$"

func main() {
    rules := []string{
        "S -> E",
        "E -> T | E + T | E - T",
        "T -> F | T * F | T / F",
        "F -> ( E ) | ID",
    }
    d := buildDFA(rules, "S")
    fmt.Println(d.accepts("E + T * F $")) // true
    fmt.Println(d.accepts("E + $")) // false
}

在上述代码中，我们使用 `state` 类型来表示文法符号的集合，使用 `dfa` 类型来表示 DFA。在 `buildDFA` 函数中，我们按照上述方法构造 DFA，并在构造过程中判断每个状态是否为接受状态。在 `accepts` 函数中，我们按照 DFA 的转移函数从起始状态开始，遍历输入字符串中的每个符号，并根据转移函数进行状态转移，最后判断当前状态是否为接受状态。