1 (* ML
-Yacc Parser
Generator (c
) 1989 Andrew W
. Appel
, David R
. Tarditi
*)
2 structure LrTable
: LR_TABLE
=
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
*)
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
22 fn ({action
,...} : table
) =>
23 fn (STATE s
) => action sub s
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
32 | find EMPTY
= default
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
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
)
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
,
58 initialState
=initialState
} : table
)