Racc::States

    # File lib/racc/state.rb, line 24
24:     def initialize(grammar, debug_flags = DebugFlags.new)
25:       @grammar = grammar
26:       @symboltable = grammar.symboltable
27:       @d_state = debug_flags.state
28:       @d_la    = debug_flags.la
29:       @d_prec  = debug_flags.prec
30:       @states = []
31:       @statecache = {}
32:       @actions = ActionTable.new(@grammar, self)
33:       @nfa_computed = false
34:       @dfa_computed = false
35:     end

    # File lib/racc/state.rb, line 50
50:     def [](i)
51:       @states[i]
52:     end

     # File lib/racc/state.rb, line 195
195:     def dfa
196:       return self if @dfa_computed
197:       nfa
198:       compute_dfa
199:       @dfa_computed = true
200:       self
201:     end

    # File lib/racc/state.rb, line 60
60:     def each_index(&block)
61:       @states.each_index(&block)
62:     end

    # File lib/racc/state.rb, line 54
54:     def each_state(&block)
55:       @states.each(&block)
56:     end

    # File lib/racc/state.rb, line 44
44:     def inspect
45:       '#<state table>'
46:     end

    # File lib/racc/state.rb, line 87
87:     def n_rrconflicts
88:       @n_rrconflicts ||= inject(0) {|sum, st| sum + st.n_rrconflicts }
89:     end

    # File lib/racc/state.rb, line 79
79:     def n_srconflicts
80:       @n_srconflicts ||= inject(0) {|sum, st| sum + st.n_srconflicts }
81:     end

     # File lib/racc/state.rb, line 101
101:     def nfa
102:       return self if @nfa_computed
103:       compute_nfa
104:       @nfa_computed = true
105:       self
106:     end

    # File lib/racc/state.rb, line 83
83:     def rrconflict_exist?
84:       n_rrconflicts() != 0
85:     end

    # File lib/racc/state.rb, line 70
70:     def should_report_srconflict?
71:       srconflict_exist? and
72:           (n_srconflicts() != @grammar.n_expected_srconflicts)
73:     end

    # File lib/racc/state.rb, line 40
40:     def size
41:       @states.size
42:     end

    # File lib/racc/state.rb, line 75
75:     def srconflict_exist?
76:       n_srconflicts() != 0
77:     end

    # File lib/racc/state.rb, line 91
91:     def state_transition_table
92:       @state_transition_table ||= StateTransitionTable.generate(self.dfa)
93:     end

     # File lib/racc/state.rb, line 316
316:     def addrel(tbl, i, item)
317:       if a = tbl[i]
318:         a.push item
319:       else
320:         tbl[i] = [item]
321:       end
322:     end

     # File lib/racc/state.rb, line 153
153:     def addsym(table, sym, ptr)
154:       unless s = table[sym]
155:         table[sym] = s = ISet.new
156:       end
157:       s.add ptr
158:     end

     # File lib/racc/state.rb, line 585
585:     def check_useless
586:       used = []
587:       @actions.each_reduce do |act|
588:         if not act or act.refn == 0
589:           act.rule.useless = true
590:         else
591:           t = act.rule.target
592:           used[t.ident] = t
593:         end
594:       end
595:       @symboltable.nt_base.upto(@symboltable.nt_max - 1) do |n|
596:         unless used[n]
597:           @symboltable[n].useless = true
598:         end
599:       end
600:     end

     # File lib/racc/state.rb, line 205
205:     def compute_dfa
206:       la = lookahead()
207:       @states.each do |state|
208:         state.la = la
209:         resolve state
210:       end
211:       set_accept
212:       @states.each do |state|
213:         pack state
214:       end
215:       check_useless
216:     end

     # File lib/racc/state.rb, line 110
110:     def compute_nfa
111:       @grammar.init
112:       # add state 0
113:       core_to_state  [ @grammar[0].ptrs[0] ]
114:       # generate LALR states
115:       cur = 0
116:       @gotos = []
117:       while cur < @states.size
118:         generate_states @states[cur]   # state is added here
119:         cur += 1
120:       end
121:       @actions.init
122:     end

     # File lib/racc/state.rb, line 160
160:     def core_to_state(core)
161:       #
162:       # convert CORE to a State object.
163:       # If matching state does not exist, create it and add to the table.
164:       #
165: 
166:       k = fingerprint(core)
167:       unless dest = @statecache[k]
168:         # not registered yet
169:         dest = State.new(@states.size, core)
170:         @states.push dest
171: 
172:         @statecache[k] = dest
173:         
174:         puts "core_to_state: create state   ID #{dest.ident}" if @d_state
175:       else
176:         if @d_state
177:           puts "core_to_state: dest is cached ID #{dest.ident}"
178:           puts "core_to_state: dest core #{dest.core.join(' ')}"
179:         end
180:       end
181: 
182:       dest
183:     end

     # File lib/racc/state.rb, line 312
312:     def create_tmap(size)
313:       Array.new(size, 0)   # use Integer as bitmap
314:     end

     # File lib/racc/state.rb, line 347
347:     def digraph(map, relation)
348:       n = relation.size
349:       index    = Array.new(n, nil)
350:       vertices = []
351:       @infinity = n + 2
352: 
353:       index.each_index do |i|
354:         if not index[i] and relation[i]
355:           traverse i, index, vertices, map, relation
356:         end
357:       end
358:     end

     # File lib/racc/state.rb, line 522
522:     def do_resolve_sr(stok, rtok)
523:       puts "resolve_sr: s/r conflict: rtok=#{rtok}, stok=#{stok}" if @d_prec
524: 
525:       unless rtok and rtok.precedence
526:         puts "resolve_sr: no prec for #{rtok}(R)" if @d_prec
527:         return :CantResolve
528:       end
529:       rprec = rtok.precedence
530: 
531:       unless stok and stok.precedence
532:         puts "resolve_sr: no prec for #{stok}(S)" if @d_prec
533:         return :CantResolve
534:       end
535:       sprec = stok.precedence
536: 
537:       ret = if rprec == sprec
538:               ASSOC[rtok.assoc] or
539:                   raise "racc: fatal: #{rtok}.assoc is not Left/Right/Nonassoc"
540:             else
541:               (rprec > sprec) ? (:Reduce) : (:Shift)
542:             end
543: 
544:       puts "resolve_sr: resolved as #{ret.id2name}" if @d_prec
545:       ret
546:     end

     # File lib/racc/state.rb, line 421
421:     def each_t(tbl, set)
422:       0.upto( set.size ) do |i|
423:         (0..7).each do |ii|
424:           if set[idx = i * 8 + ii] == 1
425:             yield tbl[idx]
426:           end
427:         end
428:       end
429:     end

     # File lib/racc/state.rb, line 185
185:     def fingerprint(arr)
186:       arr.map {|i| i.ident }.pack('L*')
187:     end

     # File lib/racc/state.rb, line 124
124:     def generate_states(state)
125:       puts "dstate: #{state}" if @d_state
126: 
127:       table = {}
128:       state.closure.each do |ptr|
129:         if sym = ptr.dereference
130:           addsym table, sym, ptr.next
131:         end
132:       end
133:       table.each do |sym, core|
134:         puts "dstate: sym=#{sym} ncore=#{core}" if @d_state
135: 
136:         dest = core_to_state(core.to_a)
137:         state.goto_table[sym] = dest
138:         id = sym.nonterminal?() ? @gotos.size : nil
139:         g = Goto.new(id, sym, state, dest)
140:         @gotos.push g if sym.nonterminal?
141:         state.gotos[sym] = g
142:         puts "dstate: #{state.ident} --#{sym}--> #{dest.ident}" if @d_state
143: 
144:         # check infinite recursion
145:         if state.ident == dest.ident and state.closure.size == 1
146:           raise CompileError,
147:               sprintf("Infinite recursion: state %d, with rule %d",
148:                       state.ident, state.ptrs[0].rule.ident)
149:         end
150:       end
151:     end

     # File lib/racc/state.rb, line 218
218:     def lookahead
219:       #
220:       # lookahead algorithm ver.3 -- from bison 1.26
221:       #
222: 
223:       gotos = @gotos
224:       if @d_la
225:         puts "\n--- goto ---"
226:         gotos.each_with_index {|g, i| print i, ' '; p g }
227:       end
228: 
229:       ### initialize_LA()
230:       ### set_goto_map()
231:       la_rules = []
232:       @states.each do |state|
233:         state.check_la la_rules
234:       end
235: 
236:       ### initialize_F()
237:       f     = create_tmap(gotos.size)
238:       reads = []
239:       edge  = []
240:       gotos.each do |goto|
241:         goto.to_state.goto_table.each do |t, st|
242:           if t.terminal?
243:             f[goto.ident] |= (1 << t.ident)
244:           elsif t.nullable?
245:             edge.push goto.to_state.gotos[t].ident
246:           end
247:         end
248:         if edge.empty?
249:           reads.push nil
250:         else
251:           reads.push edge
252:           edge = []
253:         end
254:       end
255:       digraph f, reads
256:       if @d_la
257:         puts "\n--- F1 (reads) ---"
258:         print_tab gotos, reads, f
259:       end
260: 
261:       ### build_relations()
262:       ### compute_FOLLOWS
263:       path = nil
264:       edge = []
265:       lookback = Array.new(la_rules.size, nil)
266:       includes = []
267:       gotos.each do |goto|
268:         goto.symbol.heads.each do |ptr|
269:           path = record_path(goto.from_state, ptr.rule)
270:           lastgoto = path.last
271:           st = lastgoto ? lastgoto.to_state : goto.from_state
272:           if st.conflict?
273:             addrel lookback, st.rruleid(ptr.rule), goto
274:           end
275:           path.reverse_each do |g|
276:             break if     g.symbol.terminal?
277:             edge.push    g.ident
278:             break unless g.symbol.nullable?
279:           end
280:         end
281:         if edge.empty?
282:           includes.push nil
283:         else
284:           includes.push edge
285:           edge = []
286:         end
287:       end
288:       includes = transpose(includes)
289:       digraph f, includes
290:       if @d_la
291:         puts "\n--- F2 (includes) ---"
292:         print_tab gotos, includes, f
293:       end
294: 
295:       ### compute_lookaheads
296:       la = create_tmap(la_rules.size)
297:       lookback.each_with_index do |arr, i|
298:         if arr
299:           arr.each do |g|
300:             la[i] |= f[g.ident]
301:           end
302:         end
303:       end
304:       if @d_la
305:         puts "\n--- LA (lookback) ---"
306:         print_tab la_rules, lookback, la
307:       end
308: 
309:       la
310:     end

     # File lib/racc/state.rb, line 563
563:     def pack(state)
564:       ### find most frequently used reduce rule
565:       act = state.action
566:       arr = Array.new(@grammar.size, 0)
567:       act.each do |t, a|
568:         arr[a.ruleid] += 1  if a.kind_of?(Reduce)
569:       end
570:       i = arr.max
571:       s = (i > 0) ? arr.index(i) : nil
572: 
573:       ### set & delete default action
574:       if s
575:         r = @actions.reduce(s)
576:         if not state.defact or state.defact == r
577:           act.delete_if {|t, a| a == r }
578:           state.defact = r
579:         end
580:       else
581:         state.defact ||= @actions.error
582:       end
583:     end

     # File lib/racc/state.rb, line 389
389:     def print_atab(idx, tab)
390:       tab.each_with_index do |i,ii|
391:         printf '%-20s', idx[ii].inspect
392:         p i
393:       end
394:     end

     # File lib/racc/state.rb, line 396
396:     def print_tab(idx, rel, tab)
397:       tab.each_with_index do |bin,i|
398:         print i, ' ', idx[i].inspect, ' << '; p rel[i]
399:         print '  '
400:         each_t(@symboltable, bin) {|t| print ' ', t }
401:         puts
402:       end
403:     end

     # File lib/racc/state.rb, line 406
406:     def print_tab_i(idx, rel, tab, i)
407:       bin = tab[i]
408:       print i, ' ', idx[i].inspect, ' << '; p rel[i]
409:       print '  '
410:       each_t(@symboltable, bin) {|t| print ' ', t }
411:     end

     # File lib/racc/state.rb, line 414
414:     def printb(i)
415:       each_t(@symboltable, i) do |t|
416:         print t, ' '
417:       end
418:       puts
419:     end

     # File lib/racc/state.rb, line 324
324:     def record_path(begst, rule)
325:       st = begst
326:       path = []
327:       rule.symbols.each do |t|
328:         goto = st.gotos[t]
329:         path.push goto
330:         st = goto.to_state
331:       end
332:       path
333:     end

     # File lib/racc/state.rb, line 435
435:     def resolve(state)
436:       if state.conflict?
437:         resolve_rr state, state.ritems
438:         resolve_sr state, state.stokens
439:       else
440:         if state.rrules.empty?
441:           # shift
442:           state.stokens.each do |t|
443:             state.action[t] = @actions.shift(state.goto_table[t])
444:           end
445:         else
446:           # reduce
447:           state.defact = @actions.reduce(state.rrules[0])
448:         end
449:       end
450:     end

     # File lib/racc/state.rb, line 452
452:     def resolve_rr(state, r)
453:       r.each do |item|
454:         item.each_la(@symboltable) do |t|
455:           act = state.action[t]
456:           if act
457:             unless act.kind_of?(Reduce)
458:               raise "racc: fatal: #{act.class} in action table"
459:             end
460:             # Cannot resolve R/R conflict (on t).
461:             # Reduce with upper rule as default.
462:             state.rr_conflict act.rule, item.rule, t
463:           else
464:             # No conflict.
465:             state.action[t] = @actions.reduce(item.rule)
466:           end
467:         end
468:       end
469:     end

     # File lib/racc/state.rb, line 471
471:     def resolve_sr(state, s)
472:       s.each do |stok|
473:         goto = state.goto_table[stok]
474:         act = state.action[stok]
475: 
476:         unless act
477:           # no conflict
478:           state.action[stok] = @actions.shift(goto)
479:         else
480:           unless act.kind_of?(Reduce)
481:             puts 'DEBUG -------------------------------'
482:             p stok
483:             p act
484:             state.action.each do |k,v|
485:               print k.inspect, ' ', v.inspect, "\n"
486:             end
487:             raise "racc: fatal: #{act.class} in action table"
488:           end
489: 
490:           # conflict on stok
491: 
492:           rtok = act.rule.precedence
493:           case do_resolve_sr(stok, rtok)
494:           when :Reduce
495:             # action is already set
496: 
497:           when :Shift
498:             # overwrite
499:             act.decref
500:             state.action[stok] = @actions.shift(goto)
501: 
502:           when :Error
503:             act.decref
504:             state.action[stok] = @actions.error
505: 
506:           when :CantResolve
507:             # shift as default
508:             act.decref
509:             state.action[stok] = @actions.shift(goto)
510:             state.sr_conflict stok, act.rule
511:           end
512:         end
513:       end
514:     end

     # File lib/racc/state.rb, line 552
552:     def set_accept
553:       anch = @symboltable.anchor
554:       init_state = @states[0].goto_table[@grammar.start]
555:       targ_state = init_state.action[anch].goto_state
556:       acc_state  = targ_state.action[anch].goto_state
557: 
558:       acc_state.action.clear
559:       acc_state.goto_table.clear
560:       acc_state.defact = @actions.accept
561:     end

     # File lib/racc/state.rb, line 335
335:     def transpose(rel)
336:       new = Array.new(rel.size, nil)
337:       rel.each_with_index do |arr, idx|
338:         if arr
339:           arr.each do |i|
340:             addrel new, i, idx
341:           end
342:         end
343:       end
344:       new
345:     end

     # File lib/racc/state.rb, line 360
360:     def traverse(i, index, vertices, map, relation)
361:       vertices.push i
362:       index[i] = height = vertices.size
363: 
364:       if rp = relation[i]
365:         rp.each do |proci|
366:           unless index[proci]
367:             traverse proci, index, vertices, map, relation
368:           end
369:           if index[i] > index[proci]
370:             # circulative recursion !!!
371:             index[i] = index[proci]
372:           end
373:           map[i] |= map[proci]
374:         end
375:       end
376: 
377:       if index[i] == height
378:         while true
379:           proci = vertices.pop
380:           index[proci] = @infinity
381:           break if i == proci
382: 
383:           map[proci] |= map[i]
384:         end
385:       end
386:     end