123456789_123456789_123456789_123456789_123456789_

Class: Racc::Grammar

Relationships & Source Files
Namespace Children
Classes:
Super Chains via Extension / Inclusion / Inheritance
Class Chain:
self, Forwardable
Inherits: Object
Defined in: lib/racc/grammar.rb

Class Method Summary

Instance Attribute Summary

Instance Method Summary

Constructor Details

.new(debug_flags = DebugFlags.new) ⇒ Grammar

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 24

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

Class Method Details

.define(&block)

Dynamic Generation Interface

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 201

def Grammar.define(&block)
  env = DefinitionEnv.new
  env.instance_eval(&block)
  env.grammar
end

Instance Attribute Details

#n_expected_srconflicts (rw)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 38

attr_accessor :n_expected_srconflicts

#start (readonly)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 36

attr_reader :start

#start_symbol=(s) (writeonly)

Raises:

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 175

def start_symbol=(s)
  raise CompileError, "start symbol set twice'" if @start
  @start = s
end

#symboltable (readonly)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 37

attr_reader :symboltable

#useless_nonterminal_exist?Boolean (readonly)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 84

def useless_nonterminal_exist?
  n_useless_nonterminals() != 0
end

#useless_rule_exist?Boolean (readonly)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 100

def useless_rule_exist?
  n_useless_rules() != 0
end

Instance Method Details

#[](x)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 40

def [](x)
  @rules[x]
end

#_compute_expand(t, set, lock) (private)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 504

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(rule)

Grammar Definition Interface

Raises:

  • (ArgumentError)
[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 166

def add(rule)
  raise ArgumentError, "rule added after the Grammar closed" if @closed
  @rules.push rule
end

#add_start_rule (private)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 430

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

#added?(sym) ⇒ Boolean

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 171

def added?(sym)
  @rules.detect {|r| r.target == sym }
end

#check_rules_nullable(rules) (private)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 537

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) (private)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 578

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) (private)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 550

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) (private)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 591

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) (private)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 498

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 (private)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 449

def compute_hash
  hash = 4   # size of dummy rule
  @rules.each do |rule|
    rule.hash = hash
    hash += (rule.size + 1)
  end
end

#compute_heads (private)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 458

def compute_heads
  @rules.each do |rule|
    rule.target.heads.push rule.ptrs[0]
  end
end

#compute_locate (private)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 483

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 (private)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 524

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 (private)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 472

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 (private)

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

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 564

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

#declare_precedence(assoc, syms)

Raises:

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 180

def declare_precedence(assoc, syms)
  raise CompileError, "precedence table defined twice" if @prec_table_closed
  @prec_table.push [assoc, syms]
end

#determine_terminals (private)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 465

def determine_terminals
  @symboltable.each do |s|
    s.term = s.heads.empty?
  end
end

#dfa Also known as: #states

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 120

def dfa
  (@states ||= States.new(self)).dfa
end

#each(&block)

Alias for #each_rule.

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 48

alias each each_rule

#each_index(&block)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 50

def each_index(&block)
  @rules.each_index(&block)
end

#each_rule(&block) Also known as: #each

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 44

def each_rule(&block)
  @rules.each(&block)
end

#each_useless_nonterminal

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 92

def each_useless_nonterminal
  return to_enum __method__ unless block_given?

  @symboltable.each_nonterminal do |sym|
    yield sym if sym.useless?
  end
end

#each_useless_rule

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 108

def each_useless_rule
  return to_enum __method__ unless block_given?

  each do |r|
    yield r if r.useless?
  end
end

#each_with_index(&block)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 54

def each_with_index(&block)
  @rules.each_with_index(&block)
end

#end_precedence_declaration(reverse)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 185

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

#fix_ident (private)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 442

def fix_ident
  @rules.each_with_index do |rule, idx|
    rule.ident = idx
  end
end

#init

Computation

Raises:

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 409

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)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 72

def intern(value, dummy = false)
  @symboltable.intern(value, dummy)
end

#n_useless_nonterminals

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 88

def n_useless_nonterminals
  @n_useless_nonterminals ||= each_useless_nonterminal.count
end

#n_useless_rules

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 104

def n_useless_rules
  @n_useless_rules ||= each_useless_rule.count
end

#nfa

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 116

def nfa
  (@states ||= States.new(self)).nfa
end

#nonterminal_base

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 80

def nonterminal_base
  @symboltable.nt_base
end

#parser_class

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 130

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

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 58

def size
  @rules.size
end

#state_transition_table

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 126

def state_transition_table
  states().state_transition_table
end

#states

Alias for #dfa.

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 124

alias states dfa

#symbols

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 76

def symbols
  @symboltable.symbols
end

#to_s

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 62

def to_s
  "<Racc::Grammar>"
end

#write_log(path)

[ GitHub ]

  
# File 'lib/racc/grammar.rb', line 156

def write_log(path)
  File.open(path, 'w') {|f|
    LogFileGenerator.new(states()).output f
  }
end