Class: Rly::Grammar

Inherits:
Object
  • Object
show all
Defined in:
lib/rly/parse/grammar.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(terminals) ⇒ Grammar

Returns a new instance of Grammar.



8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
# File 'lib/rly/parse/grammar.rb', line 8

def initialize(terminals)
  @productions = [nil]
  @prodnames = {}
  @prodmap = {}

  @terminals = {}
  terminals.each do |t|
    raise ArgumentError unless t.upcase == t
    @terminals[t] = []
  end
  @terminals[:error] = []

  @nonterminals = {}
  @first = {}
  @follow = {}
  @precedence = {}
  @used_precedence = {}
  @start = nil
end

Instance Attribute Details

#nonterminals ⇒ Object (readonly)

Returns the value of attribute nonterminals.



6
7
8
 
# File 'lib/rly/parse/grammar.rb', line 6

def nonterminals
  @nonterminals
end

#precedence ⇒ Object (readonly)

Returns the value of attribute precedence.



6
7
8
 
# File 'lib/rly/parse/grammar.rb', line 6

def precedence
  @precedence
end

#prodnames ⇒ Object (readonly)

Returns the value of attribute prodnames.



6
7
8
 
# File 'lib/rly/parse/grammar.rb', line 6

def prodnames
  @prodnames
end

#productions ⇒ Object (readonly)

Returns the value of attribute productions.



6
7
8
 
# File 'lib/rly/parse/grammar.rb', line 6

def productions
  @productions
end

#start ⇒ Object (readonly)

Returns the value of attribute start.



6
7
8
 
# File 'lib/rly/parse/grammar.rb', line 6

def start
  @start
end

#terminals ⇒ Object (readonly)

Returns the value of attribute terminals.



6
7
8
 
# File 'lib/rly/parse/grammar.rb', line 6

def terminals
  @terminals
end

Instance Method Details

#add_production(name, symbols, enforced_prec = nil, &block) ⇒ Object

Raises:

  • (ArgumentError) 


28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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
 
# File 'lib/rly/parse/grammar.rb', line 28

def add_production(name, symbols, enforced_prec=nil, &block)
  raise ArgumentError unless name.downcase == name
  raise ArgumentError if name == :error

  symbols.each do |sym|
    if sym.is_a?(String)
      raise ArgumentError unless sym.length == 1
      @terminals[sym] = [] unless @terminals[sym]
    end
  end

  if enforced_prec
    precedence = @precedence[enforced_prec]
    raise RuntimeError.new("Nothing known about the precedence of '#{enforced_prec}'") unless precedence
    @used_precedence[precedence] = true
  else
    precedence = prec_for_rightmost_terminal(symbols)
  end

  mapname = "#{name.to_s} -> #{symbols.to_s}"
  raise ArgumentError.new("Production #{mapname} is already defined!") if @prodmap[mapname]

  index = @productions.count
  @nonterminals[name] = [] unless @nonterminals[name]

  symbols.each do |sym|
    if @terminals[sym]
      @terminals[sym] << index
    else
      @nonterminals[sym] = [] unless @nonterminals[sym]
      @nonterminals[sym] << index
    end
  end

  p = Production.new(index, name, symbols, precedence, block)

  @productions << p
  @prodmap[mapname] = p

  @prodnames[name] = [] unless @prodnames[name]
  @prodnames[name] << p

  p
end

#build_lritems ⇒ Object 



90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
# File 'lib/rly/parse/grammar.rb', line 90

def build_lritems
  @productions.each do |p|
    lastlri = p
    i = 0
    lr_items = []
    while true do
      if i > p.length
        lri = nil
      else
        lri = LRItem.new(p,i)
        lri.lr_after = @prodnames[lri.prod[i+1]] || []
        lri.lr_before = lri.prod[i-1] || nil
      end

      lastlri.lr_next = lri
      break unless lri
      lr_items << lri
      lastlri = lri
      i += 1
    end
    p.lr_items = lr_items
  end
end

#compute_first ⇒ Object 



114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
 
# File 'lib/rly/parse/grammar.rb', line 114

def compute_first
  return @first unless @first.empty?

  @terminals.keys.each { |t| @first[t] = [t] }
  @first[:'$end'] = [:'$end']
  @nonterminals.keys.each { |n| @first[n] = [] }
  while true
    any_changes = false
    nonterminals.keys.each do |n|
      raise RuntimeError.new("Unefined production '#{n}'") unless @prodnames[n]
      @prodnames[n].each do |p|
        _first(p.prod).each do |f|
          unless @first[n].include?(f)
            @first[n] << f
            any_changes = true
          end
        end
      end
    end
    break unless any_changes
  end

  @first
end

#compute_follow(start = nil) ⇒ Object 



139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
 
# File 'lib/rly/parse/grammar.rb', line 139

def compute_follow(start=nil)
  return @follow unless @follow.empty?

  compute_first if @first.empty?

  @nonterminals.keys.each { |n| @follow[n] = [] }

  start = @productions[1].name unless start

  @follow[start] = [:'$end']

  while true
    didadd = false
    @productions[1..-1].each do |p|
      p.prod.length.times do |i|
        b = p.prod[i]
        next unless @nonterminals.include?(b)

        fst = _first(p.prod[i+1..-1])
        hasempty = false
        fst.each do |f|
          if f != :'<empty>' && !@follow[b].include?(f)
            @follow[b] << f
            didadd = true
          end
          hasempty = true if f == :'<empty>'
        end
        if hasempty || i == p.prod.length - 1
          @follow[p.name].each do |f|
            unless @follow[b].include?(f)
              @follow[b] << f
              didadd = true
            end
          end
        end
      end
    end
    break unless didadd
  end

  @follow
end

#set_precedence(term, assoc, level) ⇒ Object

Raises:

  • (RuntimeError) 


73
74
75
76
77
78
79
 
# File 'lib/rly/parse/grammar.rb', line 73

def set_precedence(term, assoc, level)
  raise RuntimeError if @productions != [nil]
  raise ArgumentError if @precedence[term]
  raise ArgumentError unless [:left, :right, :noassoc].include?(assoc)

  @precedence[term] = [assoc, level]
end

#set_start(symbol = nil) ⇒ Object

Raises:

  • (RuntimeError) 


81
82
83
84
85
86
87
88
 
# File 'lib/rly/parse/grammar.rb', line 81

def set_start(symbol=nil)
  raise RuntimeError.new("No productions defined in #{self}") if @productions.empty?
  symbol = @productions[1].name unless symbol
  raise ArgumentError unless @nonterminals[symbol]
  @productions[0] = Production.new(0, :"S'", [symbol])
  @nonterminals[symbol] << 0
  @start = symbol
end