if not goods.has(s) then bads.add(s)
end
- # Remove their transitions
+ # Remove their transitions and tags
for s in bads do
for t in s.ins.to_a do t.delete
for t in s.outs.to_a do t.delete
+ if tags.has_key(s) then
+ for t in tags[s] do retrotags[t].remove(s)
+ tags.keys.remove(s)
+ end
end
# Keep only the good stuff
states.clear
states.add_all(goods)
+ states.add(start)
end
# Generate a minimal DFA
# split accept states.
# An accept state is distinct with a non accept state.
- for s1 in states do
+ for s1 in accept do
for s2 in states do
if distincts[s1].has(s2) then continue
- if not accept.has(s1) then continue
if not accept.has(s2) then
distincts[s1].add(s2)
distincts[s2].add(s1)
end
end
- # Produce a graphvis file for the automaton
- fun to_dot(filepath: String)
+ # Produce a graphviz string from the automatom
+ #
+ # Set `merge_transitions = false` to generate one edge by transition (default true).
+ fun to_dot(merge_transitions: nullable Bool): Writable
do
var names = new HashMap[State, String]
var ni = 0
ni += 1
end
- var f = new FileWriter.open(filepath)
- f.write("digraph g \{\n")
+ var f = new Buffer
+ f.append("digraph g \{\n")
+ f.append("rankdir=LR;")
+ var state_nb = 0
for s in states do
- f.write("s{names[s]}[shape=oval")
+ f.append("s{names[s]}[shape=circle")
#f.write("label=\"\",")
if accept.has(s) then
- f.write(",color=blue")
+ f.append(",shape=doublecircle")
end
if tags.has_key(s) then
- f.write(",label=\"")
+ f.append(",label=\"")
for token in tags[s] do
- f.write("{token.name.escape_to_c}\\n")
+ f.append("{token.name.escape_to_dot}\\n")
end
- f.write("\"")
+ f.append("\"")
else
- f.write(",label=\"\"")
+ f.append(",label=\"{state_nb}\"")
end
- f.write("];\n")
+ f.append("];\n")
var outs = new HashMap[State, Array[nullable TSymbol]]
for t in s.outs do
var a
for s2, a in outs do
var labe = ""
for c in a do
+ if merge_transitions == false then labe = ""
if not labe.is_empty then labe += "\n"
if c == null then
- labe += "''"
+ labe += "ε"
else
labe += c.to_s
end
+ if merge_transitions == false then
+ f.append("s{names[s]}->s{names[s2]} [label=\"{labe.escape_to_dot}\"];\n")
+ end
+ end
+ if merge_transitions or else true then
+ f.append("s{names[s]}->s{names[s2]} [label=\"{labe.escape_to_c}\"];\n")
end
- f.write("s{names[s]}->s{names[s2]} [label=\"{labe.escape_to_c}\"];\n")
end
+ state_nb += 1
end
- f.write("empty->s{names[start]}; empty[label=\"\",shape=none];\n")
-
- f.write("\}\n")
- f.close
+ f.append("empty->s{names[start]}; empty[label=\"\",shape=none];\n")
+ f.append("\}\n")
+ return f
end
# Transform a NFA to a DFA.
return dfa
end
+ # Transform a NFA to a epsilonless NFA.
+ fun to_nfa_noe: Automaton
+ do
+ assert_valid
+
+ trim
+
+ var dfa = new Automaton.empty
+ var n2d = new ArrayMap[Set[State], State]
+ var seen = new ArraySet[Set[State]]
+ var st = eclosure([start])
+ var todo = [st]
+ n2d[st] = dfa.start
+ seen.add(st)
+ while not todo.is_empty do
+ var nfa_states = todo.pop
+ #print "* work on {nfa_states.inspect}={nfa_states} (remains {todo.length}/{seen.length})"
+ var dfa_state = n2d[nfa_states]
+ for s in nfa_states do
+ for t in s.outs do
+ if t.symbol == null then continue
+ var nfa_dest = eclosure([t.to])
+ #print "{nfa_states} -> {sym} -> {nfa_dest}"
+ var dfa_dest
+ if seen.has(nfa_dest) then
+ #print "* reuse {nfa_dest.inspect}={nfa_dest}"
+ dfa_dest = n2d[nfa_dest]
+ else
+ #print "* new {nfa_dest.inspect}={nfa_dest}"
+ dfa_dest = new State
+ dfa.states.add(dfa_dest)
+ n2d[nfa_dest] = dfa_dest
+ todo.add(nfa_dest)
+ seen.add(nfa_dest)
+ end
+ dfa_state.add_trans(dfa_dest, t.symbol)
+ end
+
+ # Mark accept and tags
+ if accept.has(s) then
+ if tags.has_key(s) then
+ for t in tags[s] do
+ dfa.add_tag(dfa_state, t)
+ end
+ end
+ dfa.accept.add(dfa_state)
+ end
+ end
+ end
+ return dfa
+ end
+
# Epsilon-closure on a state of states.
# Used by `to_dfa`.
private fun eclosure(states: Collection[State]): Set[State]
end
add "# Lexer generated by nitcc for the grammar {name}\n"
- add "module {name}_lexer is no_warning \"missing-doc\"\n"
+ add "module {name}_lexer is generated, no_warning \"missing-doc\"\n"
add("import nitcc_runtime\n")
var p = parser
nitlanguage / nit.git / blobdiff