Racc::StateTransitionTableGenerator

    # File lib/racc/statetransitiontable.rb, line 70
70:     def initialize(states)
71:       @states = states
72:       @grammar = states.grammar
73:     end

     # File lib/racc/statetransitiontable.rb, line 252
252:     def act2actid(act)
253:       case act
254:       when Shift  then act.goto_id
255:       when Reduce then -act.ruleid
256:       when Accept then @states.shift_n
257:       when Error  then @states.reduce_n * 1
258:       else
259:         raise "racc: fatal: wrong act type #{act.class} in action table"
260:       end
261:     end

     # File lib/racc/statetransitiontable.rb, line 174
174:     def addent(all, arr, chkval, ptr)
175:       max = arr.size
176:       min = nil
177:       arr.each_with_index do |item, idx|
178:         if item
179:           min ||= idx
180:         end
181:       end
182:       ptr.push(7777)    # mark
183:       arr = arr[min...max]
184:       all.push [arr, chkval, mkmapexp(arr), min, ptr.size - 1]
185:     end

     # File lib/racc/statetransitiontable.rb, line 110
110:     def gen_action_tables(t, states)
111:       t.action_table = yytable  = []
112:       t.action_check = yycheck  = []
113:       t.action_default = yydefact = []
114:       t.action_pointer = yypact   = []
115:       e1 = []
116:       e2 = []
117:       states.each do |state|
118:         yydefact.push act2actid(state.defact)
119:         if state.action.empty?
120:           yypact.push nil
121:           next
122:         end
123:         vector = []
124:         state.action.each do |tok, act|
125:           vector[tok.ident] = act2actid(act)
126:         end
127:         addent e1, vector, state.ident, yypact
128:       end
129:       set_table e1, e2, yytable, yycheck, yypact
130:     end

     # File lib/racc/statetransitiontable.rb, line 132
132:     def gen_goto_tables(t, grammar)
133:       t.goto_table   = yytable2  = []
134:       t.goto_check   = yycheck2  = []
135:       t.goto_pointer = yypgoto   = []
136:       t.goto_default = yydefgoto = []
137:       e1 = []
138:       e2 = []
139:       grammar.each_nonterminal do |tok|
140:         tmp = []
141: 
142:         # decide default
143:         freq = Array.new(@states.size, 0)
144:         @states.each do |state|
145:           st = state.goto_table[tok]
146:           if st
147:             st = st.ident
148:             freq[st] += 1
149:           end
150:           tmp[state.ident] = st
151:         end
152:         max = freq.max
153:         if max > 1
154:           default = freq.index(max)
155:           tmp.map! {|i| default == i ? nil : i }
156:         else
157:           default = nil
158:         end
159:         yydefgoto.push default
160: 
161:         # delete default value
162:         tmp.pop until tmp.last or tmp.empty?
163:         if tmp.compact.empty?
164:           # only default
165:           yypgoto.push nil
166:           next
167:         end
168: 
169:         addent e1, tmp, (tok.ident - grammar.nonterminal_base), yypgoto
170:       end
171:       set_table e1, e2, yytable2, yycheck2, yypgoto
172:     end

    # File lib/racc/statetransitiontable.rb, line 75
75:     def generate
76:       t = StateTransitionTable.new(@states)
77:       gen_action_tables t, @states
78:       gen_goto_tables t, @grammar
79:       t.token_table = token_table(@grammar)
80:       t.reduce_table = reduce_table(@grammar)
81:       t.reduce_n = @states.reduce_n
82:       t.shift_n = @states.shift_n
83:       t.nt_base = @grammar.nonterminal_base
84:       t.token_to_s_table = @grammar.symbols.map {|sym| sym.to_s }
85:       t
86:     end

     # File lib/racc/statetransitiontable.rb, line 196
196:     def mkmapexp(arr)
197:       i = ii = 0
198:       as = arr.size
199:       map = ''
200:       maxdup = RE_DUP_MAX
201:       curr = nil
202:       while i < as
203:         ii = i + 1
204:         if arr[i]
205:           ii += 1 while ii < as and arr[ii]
206:           curr = '-'
207:         else
208:           ii += 1 while ii < as and not arr[ii]
209:           curr = '.'
210:         end
211: 
212:         offset = ii - i
213:         if offset == 1
214:           map << curr
215:         else
216:           while offset > maxdup
217:             map << "#{curr}{#{maxdup}}"
218:             offset -= maxdup
219:           end
220:           map << "#{curr}{#{offset}}" if offset > 1
221:         end
222:         i = ii
223:       end
224:       Regexp.compile(map, 'n')
225:     end

     # File lib/racc/statetransitiontable.rb, line 88
 88:     def reduce_table(grammar)
 89:       t = [0, 0, :racc_error]
 90:       grammar.each_with_index do |rule, idx|
 91:         next if idx == 0
 92:         t.push rule.size
 93:         t.push rule.target.ident
 94:         t.push(if rule.action.empty?   # and @params.omit_action_call?
 95:                then :_reduce_none
 96:                else "_reduce_#{idx}".intern
 97:                end)
 98:       end
 99:       t
100:     end

     # File lib/racc/statetransitiontable.rb, line 227
227:     def set_table(entries, dummy, tbl, chk, ptr)
228:       upper = 0
229:       map = '-' * 10240
230: 
231:       # sort long to short
232:       entries.sort! {|a,b| b[0].size <=> a[0].size }
233: 
234:       entries.each do |arr, chkval, expr, min, ptri|
235:         if upper + arr.size > map.size
236:           map << '-' * (arr.size + 1024)
237:         end
238:         idx = map.index(expr)
239:         ptr[ptri] = idx - min
240:         arr.each_with_index do |item, i|
241:           if item
242:             i += idx
243:             tbl[i] = item
244:             chk[i] = chkval
245:             map[i] = oo
246:           end
247:         end
248:         upper = idx + arr.size
249:       end
250:     end

     # File lib/racc/statetransitiontable.rb, line 102
102:     def token_table(grammar)
103:       h = {}
104:       grammar.symboltable.terminals.each do |t|
105:         h[t] = t.ident
106:       end
107:       h
108:     end