class Racc::Grammar

Attributes

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

Public Class Methods

define(&block) click to toggle source

Dynamic Generation Interface

# File lib/racc/grammar.rb, line 196
def Grammar.define(&block)
  env = DefinitionEnv.new
  env.instance_eval(&block)
  env.grammar
end
new(debug_flags = DebugFlags.new) click to toggle source
# File lib/racc/grammar.rb, line 21
def initialize(debug_flags = DebugFlags.new)
  @symboltable = SymbolTable.new
  @debug_symbol = debug_flags.token
  @rules   = []  # :: [Rule]
  @start   = nil
  @n_expected_srconflicts = nil
  @prec_table = []
  @prec_table_closed = false
  @closed = false
  @states = nil
end

Public Instance Methods

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

Grammar Definition Interface

# File lib/racc/grammar.rb, line 161
def add(rule)
  raise ArgumentError, "rule added after the Grammar closed" if @closed
  @rules.push rule
end
added?(sym) click to toggle source
# File lib/racc/grammar.rb, line 166
def added?(sym)
  @rules.detect {|r| r.target == sym }
end
declare_precedence(assoc, syms) click to toggle source
# File lib/racc/grammar.rb, line 175
def declare_precedence(assoc, syms)
  raise CompileError, "precedence table defined twice" if @prec_table_closed
  @prec_table.push [assoc, syms]
end
dfa() click to toggle source
# File lib/racc/grammar.rb, line 115
def dfa
  (@states ||= States.new(self)).dfa
end
Also aliased as: states
each(&block)
Alias for: each_rule
each_index(&block) click to toggle source
# File lib/racc/grammar.rb, line 47
def each_index(&block)
  @rules.each_index(&block)
end
each_rule(&block) click to toggle source
# File lib/racc/grammar.rb, line 41
def each_rule(&block)
  @rules.each(&block)
end
Also aliased as: each
each_with_index(&block) click to toggle source
# File lib/racc/grammar.rb, line 51
def each_with_index(&block)
  @rules.each_with_index(&block)
end
end_precedence_declaration(reverse) click to toggle source
# File lib/racc/grammar.rb, line 180
def end_precedence_declaration(reverse)
  @prec_table_closed = true
  return if @prec_table.empty?
  table = reverse ? @prec_table.reverse : @prec_table
  table.each_with_index do |(assoc, syms), idx|
    syms.each do |sym|
      sym.assoc = assoc
      sym.precedence = idx
    end
  end
end
init() click to toggle source

Computation

# File lib/racc/grammar.rb, line 404
def init
  return if @closed
  @closed = true
  @start ||= @rules.map {|r| r.target }.detect {|sym| not sym.dummy? }
  raise CompileError, 'no rule in input' if @rules.empty?
  add_start_rule
  @rules.freeze
  fix_ident
  compute_hash
  compute_heads
  determine_terminals
  compute_nullable_0
  @symboltable.fix
  compute_locate
  @symboltable.each_nonterminal {|t| compute_expand t }
  compute_nullable
  compute_useless
end
intern(value, dummy = false) click to toggle source
# File lib/racc/grammar.rb, line 69
def intern(value, dummy = false)
  @symboltable.intern(value, dummy)
end
n_useless_nonterminals() click to toggle source
# File lib/racc/grammar.rb, line 85
def n_useless_nonterminals
  @n_useless_nonterminals ||=
      begin
        n = 0
        @symboltable.each_nonterminal do |sym|
          n += 1 if sym.useless?
        end
        n
      end
end
n_useless_rules() click to toggle source
# File lib/racc/grammar.rb, line 100
def n_useless_rules
  @n_useless_rules ||=
      begin
        n = 0
        each do |r|
          n += 1 if r.useless?
        end
        n
      end
end
nfa() click to toggle source
# File lib/racc/grammar.rb, line 111
def nfa
  (@states ||= States.new(self)).nfa
end
nonterminal_base() click to toggle source
# File lib/racc/grammar.rb, line 77
def nonterminal_base
  @symboltable.nt_base
end
parser_class() click to toggle source
# File lib/racc/grammar.rb, line 125
def parser_class
  states = states()   # cache
  if $DEBUG
    srcfilename = caller(1).first.slice(/\A(.*?):/, 1)
    begin
      write_log srcfilename + ".output"
    rescue SystemCallError
    end
    report = lambda {|s| $stderr.puts "racc: #{srcfilename}: #{s}" }
    if states.should_report_srconflict?
      report["#{states.n_srconflicts} shift/reduce conflicts"]
    end
    if states.rrconflict_exist?
      report["#{states.n_rrconflicts} reduce/reduce conflicts"]
    end
    g = states.grammar
    if g.useless_nonterminal_exist?
      report["#{g.n_useless_nonterminals} useless nonterminals"]
    end
    if g.useless_rule_exist?
      report["#{g.n_useless_rules} useless rules"]
    end
  end
  states.state_transition_table.parser_class
end
size() click to toggle source
# File lib/racc/grammar.rb, line 55
def size
  @rules.size
end
start_symbol=(s) click to toggle source
# File lib/racc/grammar.rb, line 170
def start_symbol=(s)
  raise CompileError, "start symbol set twice'" if @start
  @start = s
end
state_transition_table() click to toggle source
# File lib/racc/grammar.rb, line 121
def state_transition_table
  states().state_transition_table
end
states()
Alias for: dfa
symbols() click to toggle source
# File lib/racc/grammar.rb, line 73
def symbols
  @symboltable.symbols
end
to_s() click to toggle source
# File lib/racc/grammar.rb, line 59
def to_s
  "<Racc::Grammar>"
end
useless_nonterminal_exist?() click to toggle source
# File lib/racc/grammar.rb, line 81
def useless_nonterminal_exist?
  n_useless_nonterminals() != 0
end
useless_rule_exist?() click to toggle source
# File lib/racc/grammar.rb, line 96
def useless_rule_exist?
  n_useless_rules() != 0
end
write_log(path) click to toggle source
# File lib/racc/grammar.rb, line 151
def write_log(path)
  File.open(path, 'w') {|f|
    LogFileGenerator.new(states()).output f
  }
end

Private Instance Methods

_compute_expand(t, set, lock) click to toggle source
# File lib/racc/grammar.rb, line 499
def _compute_expand(t, set, lock)
  if tmp = t.expand
    set.update tmp
    return set
  end
  tok = nil
  set.update_a t.heads
  t.heads.each do |ptr|
    tok = ptr.dereference
    if tok and tok.nonterminal?
      unless lock[tok.ident]
        lock[tok.ident] = true
        _compute_expand tok, set, lock
      end
    end
  end
  set
end
add_start_rule() click to toggle source
# File lib/racc/grammar.rb, line 425
def add_start_rule
  r = Rule.new(@symboltable.dummy,
               [@start, @symboltable.anchor, @symboltable.anchor],
               UserAction.empty)
  r.ident = 0
  r.hash = 0
  r.precedence = nil
  @rules.unshift r
end
check_rules_nullable(rules) click to toggle source
# File lib/racc/grammar.rb, line 532
def check_rules_nullable(rules)
  rules.delete_if do |rule|
    rule.null = true
    rule.symbols.each do |t|
      unless t.nullable?
        rule.null = false
        break
      end
    end
    rule.nullable?
  end
end
check_rules_useless(rules) click to toggle source
# File lib/racc/grammar.rb, line 573
def check_rules_useless(rules)
  rules.delete_if do |rule|
    rule.useless = false
    rule.symbols.each do |sym|
      if sym.useless?
        rule.useless = true
        break
      end
    end
    not rule.useless?
  end
end
check_symbols_nullable(symbols) click to toggle source
# File lib/racc/grammar.rb, line 545
def check_symbols_nullable(symbols)
  symbols.delete_if do |sym|
    sym.heads.each do |ptr|
      if ptr.rule.nullable?
        sym.null = true
        break
      end
    end
    sym.nullable?
  end
end
check_symbols_useless(s) click to toggle source
# File lib/racc/grammar.rb, line 586
def check_symbols_useless(s)
  s.delete_if do |t|
    t.heads.each do |ptr|
      unless ptr.rule.useless?
        t.useless = false
        break
      end
    end
    not t.useless?
  end
end
compute_expand(t) click to toggle source

Sym#expand

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

Rule#hash

# File lib/racc/grammar.rb, line 444
def compute_hash
  hash = 4   # size of dummy rule
  @rules.each do |rule|
    rule.hash = hash
    hash += (rule.size + 1)
  end
end
compute_heads() click to toggle source

Sym#heads

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

Sym#locate

# File lib/racc/grammar.rb, line 478
def compute_locate
  @rules.each do |rule|
    t = nil
    rule.ptrs.each do |ptr|
      unless ptr.reduce?
        tok = ptr.dereference
        tok.locate.push ptr
        t = tok if tok.terminal?
      end
    end
    rule.precedence = t
  end
end
compute_nullable() click to toggle source

Sym#nullable?, Rule#nullable?

# File lib/racc/grammar.rb, line 519
def compute_nullable
  @rules.each       {|r| r.null = false }
  @symboltable.each {|t| t.null = false }
  r = @rules.dup
  s = @symboltable.nonterminals
  begin
    rs = r.size
    ss = s.size
    check_rules_nullable r
    check_symbols_nullable s
  end until rs == r.size and ss == s.size
end
compute_nullable_0() click to toggle source

Sym#self_null?

# File lib/racc/grammar.rb, line 467
def compute_nullable_0
  @symboltable.each do |s|
    if s.terminal?
      s.snull = false
    else
      s.snull = s.heads.any? {|loc| loc.reduce? }
    end
  end
end
compute_useless() click to toggle source

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

# File lib/racc/grammar.rb, line 559
def compute_useless
  @symboltable.each_terminal {|sym| sym.useless = false }
  @symboltable.each_nonterminal {|sym| sym.useless = true }
  @rules.each {|rule| rule.useless = true }
  r = @rules.dup
  s = @symboltable.nonterminals
  begin
    rs = r.size
    ss = s.size
    check_rules_useless r
    check_symbols_useless s
  end until r.size == rs and s.size == ss
end
determine_terminals() click to toggle source

Sym#terminal?

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

Rule#ident LocationPointer#ident

# File lib/racc/grammar.rb, line 437
def fix_ident
  @rules.each_with_index do |rule, idx|
    rule.ident = idx
  end
end