Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/src/ml-yacc/src/mkprstruct.sml
ViewVC logotype

Annotation of /sml/trunk/src/ml-yacc/src/mkprstruct.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 249 - (view) (download)
Original Path: sml/branches/SMLNJ/src/ml-yacc/src/mkprstruct.sml

1 : monnier 249 (* ML-Yacc Parser Generator (c) 1989 Andrew W. Appel, David R. Tarditi
2 :     *
3 :     * $Log$
4 :     * Revision 1.1.1.10 1999/04/17 18:56:12 monnier
5 :     * version 110.16
6 :     *
7 :     * Revision 1.1.1.1 1997/01/14 01:38:06 george
8 :     * Version 109.24
9 :     *
10 :     * Revision 1.2 1996/02/26 15:02:37 george
11 :     * print no longer overloaded.
12 :     * use of makestring has been removed and replaced with Int.toString ..
13 :     * use of IO replaced with TextIO
14 :     *
15 :     * Revision 1.1.1.1 1996/01/31 16:01:46 george
16 :     * Version 109
17 :     *
18 :     *)
19 :    
20 :     functor mkPrintStruct(structure LrTable : LR_TABLE
21 :     structure ShrinkLrTable : SHRINK_LR_TABLE
22 :     sharing LrTable = ShrinkLrTable.LrTable):PRINT_STRUCT =
23 :     struct
24 :     open Array List
25 :     infix 9 sub
26 :     structure LrTable = LrTable
27 :     open ShrinkLrTable LrTable
28 :    
29 :    
30 :     (* lineLength = approximately the largest number of characters to allow
31 :     on a line when printing out an encode string *)
32 :    
33 :     val lineLength = 72
34 :    
35 :     (* maxLength = length of a table entry. All table entries are encoded
36 :     using two 16-bit integers, one for the terminal number and the other
37 :     for the entry. Each integer is printed as two characters (low byte,
38 :     high byte), using the ML ascii escape sequence. We need 4
39 :     characters for each escape sequence and 16 characters for each entry
40 :     *)
41 :    
42 :     val maxLength = 16
43 :    
44 :     (* number of entries we can fit on a row *)
45 :    
46 :     val numEntries = lineLength div maxLength
47 :    
48 :     (* convert integer between 0 and 255 to the three character ascii
49 :     decimal escape sequence for it *)
50 :    
51 :     val chr =
52 :     let val lookup = Array.array(256,"\000")
53 :     val intToString = fn i =>
54 :     if i>=100 then "\\" ^ (Int.toString i)
55 :     else if i>=10 then "\\0" ^ (Int.toString i)
56 :     else "\\00" ^ (Int.toString i)
57 :     fun loop n = if n=256 then ()
58 :     else (Array.update(lookup,n,intToString n); loop (n+1))
59 :     in loop 0; fn i => lookup sub i
60 :     end
61 :    
62 :     val makeStruct = fn {table,name,print,verbose} =>
63 :     let
64 :     val states = numStates table
65 :     val rules = numRules table
66 :     fun printPairList (prEntry : 'a * 'b -> unit) l =
67 :     let fun f (EMPTY,_) = ()
68 :     | f (PAIR(a,b,r),count) =
69 :     if count >= numEntries then
70 :     (print "\\\n\\"; prEntry(a,b); f(r,1))
71 :     else (prEntry(a,b); f(r,(count+1)))
72 :     in f(l,0)
73 :     end
74 :     val printList : ('a -> unit) -> 'a list -> unit =
75 :     fn prEntry => fn l =>
76 :     let fun f (nil,_) = ()
77 :     | f (a :: r,count) =
78 :     if count >= numEntries then
79 :     (print "\\\n\\"; prEntry a; f(r,1))
80 :     else (prEntry a; f(r,count+1))
81 :     in f(l,0)
82 :     end
83 :     val prEnd = fn _ => print "\\000\\000\\\n\\"
84 :     fun printPairRow prEntry =
85 :     let val printEntries = printPairList prEntry
86 :     in fn l => (printEntries l; prEnd())
87 :     end
88 :     fun printPairRowWithDefault (prEntry,prDefault) =
89 :     let val f = printPairRow prEntry
90 :     in fn (l,default) => (prDefault default; f l)
91 :     end
92 :     fun printTable (printRow,count) =
93 :     (print "\"\\\n\\";
94 :     let fun f i = if i=count then ()
95 :     else (printRow i; f (i+1))
96 :     in f 0
97 :     end;
98 :     print"\"\n")
99 :     val printChar = print o chr
100 :    
101 :     (* print an integer between 0 and 2^16-1 as a 2-byte character,
102 :     with the low byte first *)
103 :    
104 :     val printInt = fn i => (printChar (i mod 256);
105 :     printChar (i div 256))
106 :    
107 :     (* encode actions as integers:
108 :    
109 :     ACCEPT => 0
110 :     ERROR => 1
111 :     SHIFT i => 2 + i
112 :     REDUCE rulenum => numstates+2+rulenum
113 :     *)
114 :    
115 :     val printAction =
116 :     fn (REDUCE rulenum) => printInt (rulenum+states+2)
117 :     | (SHIFT (STATE i)) => printInt (i+2)
118 :     | ACCEPT => printInt 0
119 :     | ERROR => printInt 1
120 :    
121 :     val printTermAction = fn (T t,action) =>
122 :     (printInt (t+1); printAction action)
123 :    
124 :     val printGoto = fn (NT n,STATE s) => (printInt (n+1); printInt s)
125 :    
126 :     val ((rowCount,rowNumbers,actionRows),entries)=
127 :     shrinkActionList(table,verbose)
128 :     val getActionRow = let val a = Array.fromList actionRows
129 :     in fn i => a sub i
130 :     end
131 :     val printGotoRow : int -> unit =
132 :     let val f = printPairRow printGoto
133 :     val g = describeGoto table
134 :     in fn i => f (g (STATE i))
135 :     end
136 :     val printActionRow =
137 :     let val f = printPairRowWithDefault(printTermAction,printAction)
138 :     in fn i => f (getActionRow i)
139 :     end
140 :     in print "val ";
141 :     print name;
142 :     print "=";
143 :     print "let val actionRows =\n";
144 :     printTable(printActionRow,rowCount);
145 :     print "val actionRowNumbers =\n\"";
146 :     printList (fn i => printInt i) rowNumbers;
147 :     print "\"\n";
148 :     print "val gotoT =\n";
149 :     printTable(printGotoRow,states);
150 :     print "val numstates = ";
151 :     print (Int.toString states);
152 :     print "\nval numrules = ";
153 :     print (Int.toString rules);
154 :     print "\n\
155 :     \val s = ref \"\" and index = ref 0\n\
156 :     \val string_to_int = fn () => \n\
157 :     \let val i = !index\n\
158 :     \in index := i+2; Char.ord(String.sub(!s,i)) + Char.ord(String.sub(!s,i+1)) * 256\n\
159 :     \end\n\
160 :     \val string_to_list = fn s' =>\n\
161 :     \ let val len = String.size s'\n\
162 :     \ fun f () =\n\
163 :     \ if !index < len then string_to_int() :: f()\n\
164 :     \ else nil\n\
165 :     \ in index := 0; s := s'; f ()\n\
166 :     \ end\n\
167 :     \val string_to_pairlist = fn (conv_key,conv_entry) =>\n\
168 :     \ let fun f () =\n\
169 :     \ case string_to_int()\n\
170 :     \ of 0 => EMPTY\n\
171 :     \ | n => PAIR(conv_key (n-1),conv_entry (string_to_int()),f())\n\
172 :     \ in f\n\
173 :     \ end\n\
174 :     \val string_to_pairlist_default = fn (conv_key,conv_entry) =>\n\
175 :     \ let val conv_row = string_to_pairlist(conv_key,conv_entry)\n\
176 :     \ in fn () =>\n\
177 :     \ let val default = conv_entry(string_to_int())\n\
178 :     \ val row = conv_row()\n\
179 :     \ in (row,default)\n\
180 :     \ end\n\
181 :     \ end\n\
182 :     \val string_to_table = fn (convert_row,s') =>\n\
183 :     \ let val len = String.size s'\n\
184 :     \ fun f ()=\n\
185 :     \ if !index < len then convert_row() :: f()\n\
186 :     \ else nil\n\
187 :     \ in (s := s'; index := 0; f ())\n\
188 :     \ end\n\
189 :     \local\n\
190 :     \ val memo = Array.array(numstates+numrules,ERROR)\n\
191 :     \ val _ =let fun g i=(Array.update(memo,i,REDUCE(i-numstates)); g(i+1))\n\
192 :     \ fun f i =\n\
193 :     \ if i=numstates then g i\n\
194 :     \ else (Array.update(memo,i,SHIFT (STATE i)); f (i+1))\n\
195 :     \ in f 0 handle Subscript => ()\n\
196 :     \ end\n\
197 :     \in\n\
198 :     \val entry_to_action = fn 0 => ACCEPT | 1 => ERROR | j => Array.sub(memo,(j-2))\n\
199 :     \end\n\
200 :     \val gotoT=Array.fromList(string_to_table(string_to_pairlist(NT,STATE),gotoT))\n\
201 :     \val actionRows=string_to_table(string_to_pairlist_default(T,entry_to_action),actionRows)\n\
202 :     \val actionRowNumbers = string_to_list actionRowNumbers\n\
203 :     \val actionT = let val actionRowLookUp=\n\
204 :     \let val a=Array.fromList(actionRows) in fn i=>Array.sub(a,i) end\n\
205 :     \in Array.fromList(map actionRowLookUp actionRowNumbers)\n\
206 :     \end\n\
207 :     \in LrTable.mkLrTable {actions=actionT,gotos=gotoT,numRules=numrules,\n\
208 :     \numStates=numstates,initialState=STATE ";
209 :     print (Int.toString ((fn (STATE i) => i) (initialState table)));
210 :     print "}\nend\n";
211 :     entries
212 :     end
213 :     end;

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0