Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | (* ML-Yacc Parser Generator (c) 1989 Andrew W. Appel, David R. Tarditi *) |
2 | structure LrTable : LR_TABLE = | |
3 | struct | |
4 | val sub = Array.sub | |
5 | infix 9 sub | |
6 | datatype ('a,'b) pairlist = EMPTY | |
7 | | PAIR of 'a * 'b * ('a,'b) pairlist | |
8 | datatype term = T of int | |
9 | datatype nonterm = NT of int | |
10 | datatype state = STATE of int | |
11 | datatype action = SHIFT of state | |
12 | | REDUCE of int (* rulenum from grammar *) | |
13 | | ACCEPT | |
14 | | ERROR | |
15 | exception Goto of state * nonterm | |
16 | type table = {states: int, rules : int,initialState: state, | |
17 | action: ((term,action) pairlist * action) array, | |
18 | goto : (nonterm,state) pairlist array} | |
19 | val numStates = fn ({states,...} : table) => states | |
20 | val numRules = fn ({rules,...} : table) => rules | |
21 | val describeActions = | |
22 | fn ({action,...} : table) => | |
23 | fn (STATE s) => action sub s | |
24 | val describeGoto = | |
25 | fn ({goto,...} : table) => | |
26 | fn (STATE s) => goto sub s | |
27 | fun findTerm (T term,row,default) = | |
28 | let fun find (PAIR (T key,data,r)) = | |
29 | if key < term then find r | |
30 | else if key=term then data | |
31 | else default | |
32 | | find EMPTY = default | |
33 | in find row | |
34 | end | |
35 | fun findNonterm (NT nt,row) = | |
36 | let fun find (PAIR (NT key,data,r)) = | |
37 | if key < nt then find r | |
38 | else if key=nt then SOME data | |
39 | else NONE | |
40 | | find EMPTY = NONE | |
41 | in find row | |
42 | end | |
43 | val action = fn ({action,...} : table) => | |
44 | fn (STATE state,term) => | |
45 | let val (row,default) = action sub state | |
46 | in findTerm(term,row,default) | |
47 | end | |
48 | val goto = fn ({goto,...} : table) => | |
49 | fn (a as (STATE state,nonterm)) => | |
50 | case findNonterm(nonterm,goto sub state) | |
51 | of SOME state => state | |
52 | | NONE => raise (Goto a) | |
53 | val initialState = fn ({initialState,...} : table) => initialState | |
54 | val mkLrTable = fn {actions,gotos,initialState,numStates,numRules} => | |
55 | ({action=actions,goto=gotos, | |
56 | states=numStates, | |
57 | rules=numRules, | |
58 | initialState=initialState} : table) | |
59 | end; |