-
Notifications
You must be signed in to change notification settings - Fork 9
/
CompileFSM.n
82 lines (79 loc) · 3.17 KB
/
CompileFSM.n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
using Nemerle.Collections;
using Nemerle.Text;
using Nemerle.Utility;
using Nemerle.Compiler;
using Nemerle.Compiler.Parsetree;
using Nemerle.Compiler.Typedtree;
using System;
using System.Linq;
using SCG = System.Collections.Generic;
namespace Nemerle.Parser
{
partial internal class RuleCompiler
{
public CompileFsm(fsm : FSM) : PExpr
{
def manager = _grammarCompiller.Typer.Manager;
def fsm = FSMTransform.MakeDeterministic(fsm);
def okState = fsm.StateCount;
def endState = fsm.StateCount + 1;
def labelIds = array(fsm.StateCount + 2);
for(mutable i = 0; i < labelIds.Length; ++i)
labelIds[i] = Util.next_id(manager);
def goto(n) { PExpr.Typed(Location.Default, TExpr.Goto(manager.InternalType.Void, labelIds[n], 1)) }
def label(n) { PExpr.Typed(Location.Default, TExpr.Label(manager.InternalType.Void, labelIds[n], TExpr.DefaultValue(manager.InternalType.Void))) }
def states = $[0..fsm.StateCount - 1].Fold(SCG.Dictionary(), (state, states) =>
{
def transitions = fsm.Transitions.Filter(t => t.From == state);
def symbolTransitions = transitions.MapFiltered(_ is Transition.Symbol, _ :> Transition.Symbol);
def isOkState = fsm.OkStates.Contains(state);
states.Add(state, (isOkState, symbolTransitions));
states;
});
def statements = SCG.List();
statements.Add(<[ mutable okPos = -1 ]>);
statements.Add(<[ mutable curPos = pos ]>);
when (fsm.StartState != 0)
statements.Add(goto(fsm.StartState));
for (mutable state = 0; state < fsm.StateCount; ++state)
{
def (isOkState, symbolTransitions) = states[state];
when (!symbolTransitions.IsEmpty())
{
statements.Add(label(state));
when (isOkState)
statements.Add(<[ okPos = curPos ]>);
statements.Add(<[ when (curPos >= text.Length) $(goto(endState)) ]>);
def getDestination(transition)
{
def (isOkState, symbolTransitions) = states[transition.To];
if (symbolTransitions.IsEmpty())
if (isOkState)
okState;
else
endState;
else
transition.To;
}
match (symbolTransitions)
{
| [Symbol(RangeSet(Ranges = [range])) as transition] when range.from == char.MinValue && range.to == char.MaxValue =>
statements.Add(<[ ++curPos ]>);
statements.Add(goto(getDestination(transition)));
| _ =>
statements.Add(<[ c = text[curPos] ]>);
statements.Add(<[ ++curPos ]>);
foreach (transition in symbolTransitions)
statements.Add(<[ when ($(TestCharConditionCode(transition.Chars))) $(goto(getDestination(transition))) ]>);
statements.Add(goto(endState));
}
}
}
statements.Add(label(okState));
statements.Add(<[ okPos = curPos ]>);
statements.Add(label(endState));
statements.Add(<[ okPos ]>);
PExpr.Sequence(statements.NToList());
}
}
}