A table of LALR 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
DFA (Deterministic Finite Automaton) Generation
# 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
NFA (Non-deterministic Finite Automaton) Computation
# 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 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
for debug
# 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
for debug
# 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
for debug
# 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
resolve
# 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
complete
# 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
Disabled; run with --debug to generate this.
Generated with the Darkfish Rdoc Generator 1.1.6.