Parent

Racc::Grammar

Attributes

start[R]
symboltable[R]
n_expected_srconflicts[RW]

Public Class Methods

define(&block) click to toggle source

Dynamic Generation Interface

     # File lib/racc/grammar.rb, line 198
198:     def Grammar.define(&block)
199:       env = DefinitionEnv.new
200:       env.instance_eval(&block)
201:       env.grammar
202:     end
new(debug_flags = DebugFlags.new) click to toggle source
    # File lib/racc/grammar.rb, line 23
23:     def initialize(debug_flags = DebugFlags.new)
24:       @symboltable = SymbolTable.new
25:       @debug_symbol = debug_flags.token
26:       @rules   = []  # :: [Rule]
27:       @start   = nil
28:       @n_expected_srconflicts = nil
29:       @prec_table = []
30:       @prec_table_closed = false
31:       @closed = false
32:       @states = nil
33:     end

Public Instance Methods

[](x) click to toggle source
    # File lib/racc/grammar.rb, line 39
39:     def [](x)
40:       @rules[x]
41:     end
add(rule) click to toggle source

Grammar Definition Interface

     # File lib/racc/grammar.rb, line 163
163:     def add(rule)
164:       raise ArgumentError, "rule added after the Grammar closed" if @closed
165:       @rules.push rule
166:     end
added?(sym) click to toggle source
     # File lib/racc/grammar.rb, line 168
168:     def added?(sym)
169:       @rules.detect {|r| r.target == sym }
170:     end
declare_precedence(assoc, syms) click to toggle source
     # File lib/racc/grammar.rb, line 177
177:     def declare_precedence(assoc, syms)
178:       raise CompileError, "precedence table defined twice" if @prec_table_closed
179:       @prec_table.push [assoc, syms]
180:     end
dfa() click to toggle source
     # File lib/racc/grammar.rb, line 117
117:     def dfa
118:       (@states ||= States.new(self)).dfa
119:     end
Also aliased as: states
each(&block) click to toggle source
Alias for: each_rule
each_index(&block) click to toggle source
    # File lib/racc/grammar.rb, line 49
49:     def each_index(&block)
50:       @rules.each_index(&block)
51:     end
each_rule(&block) click to toggle source
    # File lib/racc/grammar.rb, line 43
43:     def each_rule(&block)
44:       @rules.each(&block)
45:     end
Also aliased as: each
each_with_index(&block) click to toggle source
    # File lib/racc/grammar.rb, line 53
53:     def each_with_index(&block)
54:       @rules.each_with_index(&block)
55:     end
end_precedence_declaration(reverse) click to toggle source
     # File lib/racc/grammar.rb, line 182
182:     def end_precedence_declaration(reverse)
183:       @prec_table_closed = true
184:       return if @prec_table.empty?
185:       table = reverse ? @prec_table.reverse : @prec_table
186:       table.each_with_index do |(assoc, syms), idx|
187:         syms.each do |sym|
188:           sym.assoc = assoc
189:           sym.precedence = idx
190:         end
191:       end
192:     end
init() click to toggle source

Computation

     # File lib/racc/grammar.rb, line 406
406:     def init
407:       return if @closed
408:       @closed = true
409:       @start ||= @rules.map {|r| r.target }.detect {|sym| not sym.dummy? }
410:       raise CompileError, 'no rule in input' if @rules.empty?
411:       add_start_rule
412:       @rules.freeze
413:       fix_ident
414:       compute_hash
415:       compute_heads
416:       determine_terminals
417:       compute_nullable_0
418:       @symboltable.fix
419:       compute_locate
420:       @symboltable.each_nonterminal {|t| compute_expand t }
421:       compute_nullable
422:       compute_useless
423:     end
intern(value, dummy = false) click to toggle source
    # File lib/racc/grammar.rb, line 71
71:     def intern(value, dummy = false)
72:       @symboltable.intern(value, dummy)
73:     end
n_useless_nonterminals() click to toggle source
    # File lib/racc/grammar.rb, line 87
87:     def n_useless_nonterminals
88:       @n_useless_nonterminals ||=
89:           begin
90:             n = 0
91:             @symboltable.each_nonterminal do |sym|
92:               n += 1 if sym.useless?
93:             end
94:             n
95:           end
96:     end
n_useless_rules() click to toggle source
     # File lib/racc/grammar.rb, line 102
102:     def n_useless_rules
103:       @n_useless_rules ||=
104:           begin
105:             n = 0
106:             each do |r|
107:               n += 1 if r.useless?
108:             end
109:             n
110:           end
111:     end
nfa() click to toggle source
     # File lib/racc/grammar.rb, line 113
113:     def nfa
114:       (@states ||= States.new(self)).nfa
115:     end
nonterminal_base() click to toggle source
    # File lib/racc/grammar.rb, line 79
79:     def nonterminal_base
80:       @symboltable.nt_base
81:     end
parser_class() click to toggle source
     # File lib/racc/grammar.rb, line 127
127:     def parser_class
128:       states = states()   # cache
129:       if $DEBUG
130:         srcfilename = caller(1).first.slice(/\A(.*?):/, 1)
131:         begin
132:           write_log srcfilename + ".output"
133:         rescue SystemCallError
134:         end
135:         report = lambda {|s| $stderr.puts "racc: #{srcfilename}: #{s}" }
136:         if states.should_report_srconflict?
137:           report["#{states.n_srconflicts} shift/reduce conflicts"]
138:         end
139:         if states.rrconflict_exist?
140:           report["#{states.n_rrconflicts} reduce/reduce conflicts"]
141:         end
142:         g = states.grammar
143:         if g.useless_nonterminal_exist?
144:           report["#{g.n_useless_nonterminals} useless nonterminals"]
145:         end
146:         if g.useless_rule_exist?
147:           report["#{g.n_useless_rules} useless rules"]
148:         end
149:       end
150:       states.state_transition_table.parser_class
151:     end
size() click to toggle source
    # File lib/racc/grammar.rb, line 57
57:     def size
58:       @rules.size
59:     end
start_symbol=(s) click to toggle source
     # File lib/racc/grammar.rb, line 172
172:     def start_symbol=(s)
173:       raise CompileError, "start symbol set twice'" if @start
174:       @start = s
175:     end
state_transition_table() click to toggle source
     # File lib/racc/grammar.rb, line 123
123:     def state_transition_table
124:       states().state_transition_table
125:     end
states() click to toggle source
Alias for: dfa
symbols() click to toggle source
    # File lib/racc/grammar.rb, line 75
75:     def symbols
76:       @symboltable.symbols
77:     end
to_s() click to toggle source
    # File lib/racc/grammar.rb, line 61
61:     def to_s
62:       "<Racc::Grammar>"
63:     end
useless_nonterminal_exist?() click to toggle source
    # File lib/racc/grammar.rb, line 83
83:     def useless_nonterminal_exist?
84:       n_useless_nonterminals() != 0
85:     end
useless_rule_exist?() click to toggle source
     # File lib/racc/grammar.rb, line 98
 98:     def useless_rule_exist?
 99:       n_useless_rules() != 0
100:     end
write_log(path) click to toggle source
     # File lib/racc/grammar.rb, line 153
153:     def write_log(path)
154:       File.open(path, 'w') {|f|
155:         LogFileGenerator.new(states()).output f
156:       }
157:     end

Private Instance Methods

_compute_expand(t, set, lock) click to toggle source
     # File lib/racc/grammar.rb, line 501
501:     def _compute_expand(t, set, lock)
502:       if tmp = t.expand
503:         set.update tmp
504:         return set
505:       end
506:       tok = h = nil
507:       set.update_a t.heads
508:       t.heads.each do |ptr|
509:         tok = ptr.dereference
510:         if tok and tok.nonterminal?
511:           unless lock[tok.ident]
512:             lock[tok.ident] = true
513:             _compute_expand tok, set, lock
514:           end
515:         end
516:       end
517:       set
518:     end
add_start_rule() click to toggle source
     # File lib/racc/grammar.rb, line 427
427:     def add_start_rule
428:       r = Rule.new(@symboltable.dummy,
429:                    [@start, @symboltable.anchor, @symboltable.anchor],
430:                    UserAction.empty)
431:       r.ident = 0
432:       r.hash = 0
433:       r.precedence = nil
434:       @rules.unshift r
435:     end
check_rules_nullable(rules) click to toggle source
     # File lib/racc/grammar.rb, line 534
534:     def check_rules_nullable(rules)
535:       rules.delete_if do |rule|
536:         rule.null = true
537:         rule.symbols.each do |t|
538:           unless t.nullable?
539:             rule.null = false
540:             break
541:           end
542:         end
543:         rule.nullable?
544:       end
545:     end
check_rules_useless(rules) click to toggle source
     # File lib/racc/grammar.rb, line 575
575:     def check_rules_useless(rules)
576:       rules.delete_if do |rule|
577:         rule.useless = false
578:         rule.symbols.each do |sym|
579:           if sym.useless?
580:             rule.useless = true
581:             break
582:           end
583:         end
584:         not rule.useless?
585:       end
586:     end
check_symbols_nullable(symbols) click to toggle source
     # File lib/racc/grammar.rb, line 547
547:     def check_symbols_nullable(symbols)
548:       symbols.delete_if do |sym|
549:         sym.heads.each do |ptr|
550:           if ptr.rule.nullable?
551:             sym.null = true
552:             break
553:           end
554:         end
555:         sym.nullable?
556:       end
557:     end
check_symbols_useless(s) click to toggle source
     # File lib/racc/grammar.rb, line 588
588:     def check_symbols_useless(s)
589:       s.delete_if do |t|
590:         t.heads.each do |ptr|
591:           unless ptr.rule.useless?
592:             t.useless = false
593:             break
594:           end
595:         end
596:         not t.useless?
597:       end
598:     end
compute_expand(t) click to toggle source

Sym#expand

     # File lib/racc/grammar.rb, line 495
495:     def compute_expand(t)
496:       puts "expand> #{t.to_s}" if @debug_symbol
497:       t.expand = _compute_expand(t, ISet.new, [])
498:       puts "expand< #{t.to_s}: #{t.expand.to_s}" if @debug_symbol
499:     end
compute_hash() click to toggle source

Rule#hash

     # File lib/racc/grammar.rb, line 446
446:     def compute_hash
447:       hash = 4   # size of dummy rule
448:       @rules.each do |rule|
449:         rule.hash = hash
450:         hash += (rule.size + 1)
451:       end
452:     end
compute_heads() click to toggle source

Sym#heads

     # File lib/racc/grammar.rb, line 455
455:     def compute_heads
456:       @rules.each do |rule|
457:         rule.target.heads.push rule.ptrs[0]
458:       end
459:     end
compute_locate() click to toggle source

Sym#locate

     # File lib/racc/grammar.rb, line 480
480:     def compute_locate
481:       @rules.each do |rule|
482:         t = nil
483:         rule.ptrs.each do |ptr|
484:           unless ptr.reduce?
485:             tok = ptr.dereference
486:             tok.locate.push ptr
487:             t = tok if tok.terminal?
488:           end
489:         end
490:         rule.precedence = t
491:       end
492:     end
compute_nullable() click to toggle source

Sym#nullable?, Rule#nullable?

     # File lib/racc/grammar.rb, line 521
521:     def compute_nullable
522:       @rules.each       {|r| r.null = false }
523:       @symboltable.each {|t| t.null = false }
524:       r = @rules.dup
525:       s = @symboltable.nonterminals
526:       begin
527:         rs = r.size
528:         ss = s.size
529:         check_rules_nullable r
530:         check_symbols_nullable s
531:       end until rs == r.size and ss == s.size
532:     end
compute_nullable_0() click to toggle source

Sym#self_null?

     # File lib/racc/grammar.rb, line 469
469:     def compute_nullable_0
470:       @symboltable.each do |s|
471:         if s.terminal?
472:           s.snull = false
473:         else
474:           s.snull = s.heads.any? {|loc| loc.reduce? }
475:         end
476:       end
477:     end
compute_useless() click to toggle source

Sym#useless?, Rule#useless? FIXME: what means “useless”?

     # File lib/racc/grammar.rb, line 561
561:     def compute_useless
562:       @symboltable.each_terminal {|sym| sym.useless = false }
563:       @symboltable.each_nonterminal {|sym| sym.useless = true }
564:       @rules.each {|rule| rule.useless = true }
565:       r = @rules.dup
566:       s = @symboltable.nonterminals
567:       begin
568:         rs = r.size
569:         ss = s.size
570:         check_rules_useless r
571:         check_symbols_useless s
572:       end until r.size == rs and s.size == ss
573:     end
determine_terminals() click to toggle source

Sym#terminal?

     # File lib/racc/grammar.rb, line 462
462:     def determine_terminals
463:       @symboltable.each do |s|
464:         s.term = s.heads.empty?
465:       end
466:     end
fix_ident() click to toggle source

Rule#ident LocationPointer#ident

     # File lib/racc/grammar.rb, line 439
439:     def fix_ident
440:       @rules.each_with_index do |rule, idx|
441:         rule.ident = idx
442:       end
443:     end

Disabled; run with --debug to generate this.

[Validate]

Generated with the Darkfish Rdoc Generator 1.1.6.