Class: Depager::LALR::Grammar

Inherits:
Grammar
  • Object
show all
Defined in:
lib/depager/lr.rb

Instance Attribute Summary collapse

Attributes inherited from Grammar

#f0e, #first1, #lhs_to_rule, #mask_sym, #nonterms, #precs, #rulelist, #syms, #terms

Instance Method Summary collapse

Methods inherited from Grammar

#[], #first, #initialize, #make_sym_first, #make_sym_mask, #mask_size, #nonterm?, #sym_mask, #symname, #symset, #term?

Constructor Details

This class inherits a constructor from Depager::Grammar

Instance Attribute Details

#memo_closure ⇒ Object

Returns the value of attribute memo_closure.



34
35
36
 
# File 'lib/depager/lr.rb', line 34

def memo_closure
  @memo_closure
end

Instance Method Details

#closure(rule, n, base = nil) ⇒ Object 



111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
 
# File 'lib/depager/lr.rb', line 111

def closure(rule, n, base = nil)
  i = 0
  appended = {}
  result = [base || LRItem[rule, n]]
  memo = memo_closure

  while i < result.size
    ds = result[i].dotsym
    if nonterm?(ds) && !appended[ds]
      unless memo[ds]
        memo[ds] = []
        lhs_to_rule[ds].each do |rule|
          memo[ds] << LRItem[rule, 0]
        end
      end
      result.concat memo[ds]
      appended[ds] = true
    end
    i += 1
  end
  result
end

#closure1(rule, n, la) ⇒ Object 



74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
# File 'lib/depager/lr.rb', line 74

def closure1(rule, n, la)
  key = [rule.n, n, la]
  return @memo_closure1[key] if @memo_closure1[key]

  result = [LRItem[rule, n, symset(la)]]
  memo   = n == 0 ? { result[0].rule.n => result[0] } : {}
  memo2  = {}
  i = 0
  while i < result.size
    ri = result[i]
    i += 1
    dotsym = ri.dotsym
    next unless nonterm? dotsym

    b = first(ri.dotrest)
    if    b.delete(EPS) then b.merge! ri.la
    elsif memo2[ri] then next
    end
    memo2[ri] = true

    lhs_to_rule[dotsym].each do |rule|
      if (li = memo[rule.n])
        unless b.subset_of? li.la
          li.la.merge! b
          result << li
        end
      else
        li = memo[rule.n] = LRItem[rule, 0, b]
        result << li
      end
    end
  end

  result.uniq!
  @memo_closure1[key] = result
end

#initialize_depend ⇒ Object 



36
37
38
39
40
41
42
43
 
# File 'lib/depager/lr.rb', line 36

def initialize_depend
  @first1[TLA] = [TLA]
  @sym_mask[TLA] = (1 << @sym_mask.size)
  @mask_sym << TLA
  make_sym_f0e
  @memo_closure  = {}
  @memo_closure1 = {}
end

#make_sym_f0e ⇒ Object 



45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
# File 'lib/depager/lr.rb', line 45

def make_sym_f0e
  @f0e = {}
  @empty_rules.each do |lhs, rule_no|
    @f0e[lhs] = { rule_no => symset([EPS]) }
  end
  begin
    changed = false
    @rulelist.each do |rule|
      next unless @f0e[rule.rhs[0]]

      lhs = rule.lhs
      rhs = rule.rhs
      @f0e[lhs] ||= {}
      @f0e[rhs[0]].each do |n, fst|
        @f0e[lhs][n] ||= symset
        if fst.include? EPS
          fst = fst.dup
          fst.delete(EPS)
          fst.merge!(first(rhs[1..]))
        end
        unless fst.subset_of? @f0e[lhs][n]
          @f0e[lhs][n].merge! fst
          changed = true
        end
      end
    end
  end while changed
end