Class: Lrama::Grammar

Inherits:
Object
  • Object
show all
Defined in:
lib/lrama/grammar.rb,
lib/lrama/grammar/code.rb,
lib/lrama/grammar/rule.rb,
lib/lrama/grammar/union.rb,
lib/lrama/grammar/symbol.rb,
lib/lrama/grammar/printer.rb,
lib/lrama/grammar/auxiliary.rb,
lib/lrama/grammar/reference.rb,
lib/lrama/grammar/precedence.rb,
lib/lrama/grammar/error_token.rb

Overview

Grammar is the result of parsing an input grammar file

Defined Under Namespace

Classes: Auxiliary, Code, ErrorToken, Precedence, Printer, Reference, Rule, Symbol, Union

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Grammar

Returns a new instance of Grammar.



26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
# File 'lib/lrama/grammar.rb', line 26

def initialize
  @printers = []
  @error_tokens = []
  @symbols = []
  @types = []
  @_rules = []
  @rules = []
  @sym_to_rules = {}
  @empty_symbol = nil
  @eof_symbol = nil
  @error_symbol = nil
  @undef_symbol = nil
  @accept_symbol = nil
  @aux = Auxiliary.new

  append_special_symbols
end

Instance Attribute Details

#_rules ⇒ Object

Returns the value of attribute _rules.



19
20
21
 
# File 'lib/lrama/grammar.rb', line 19

def _rules
  @_rules
end

#accept_symbol ⇒ Object (readonly)

Returns the value of attribute accept_symbol.



18
19
20
 
# File 'lib/lrama/grammar.rb', line 18

def accept_symbol
  @accept_symbol
end

#aux ⇒ Object (readonly)

Returns the value of attribute aux.



18
19
20
 
# File 'lib/lrama/grammar.rb', line 18

def aux
  @aux
end

#eof_symbol ⇒ Object (readonly)

Returns the value of attribute eof_symbol.



18
19
20
 
# File 'lib/lrama/grammar.rb', line 18

def eof_symbol
  @eof_symbol
end

#error_symbol ⇒ Object (readonly)

Returns the value of attribute error_symbol.



18
19
20
 
# File 'lib/lrama/grammar.rb', line 18

def error_symbol
  @error_symbol
end

#error_tokens ⇒ Object

Returns the value of attribute error_tokens.



19
20
21
 
# File 'lib/lrama/grammar.rb', line 19

def error_tokens
  @error_tokens
end

#expect ⇒ Object

Returns the value of attribute expect.



19
20
21
 
# File 'lib/lrama/grammar.rb', line 19

def expect
  @expect
end

#initial_action ⇒ Object

Returns the value of attribute initial_action.



19
20
21
 
# File 'lib/lrama/grammar.rb', line 19

def initial_action
  @initial_action
end

#lex_param ⇒ Object

Returns the value of attribute lex_param.



19
20
21
 
# File 'lib/lrama/grammar.rb', line 19

def lex_param
  @lex_param
end

#parse_param ⇒ Object

Returns the value of attribute parse_param.



19
20
21
 
# File 'lib/lrama/grammar.rb', line 19

def parse_param
  @parse_param
end

#printers ⇒ Object

Returns the value of attribute printers.



19
20
21
 
# File 'lib/lrama/grammar.rb', line 19

def printers
  @printers
end

#rules ⇒ Object

Returns the value of attribute rules.



19
20
21
 
# File 'lib/lrama/grammar.rb', line 19

def rules
  @rules
end

#sym_to_rules ⇒ Object

Returns the value of attribute sym_to_rules.



19
20
21
 
# File 'lib/lrama/grammar.rb', line 19

def sym_to_rules
  @sym_to_rules
end

#symbols ⇒ Object

Returns the value of attribute symbols.



19
20
21
 
# File 'lib/lrama/grammar.rb', line 19

def symbols
  @symbols
end

#types ⇒ Object

Returns the value of attribute types.



19
20
21
 
# File 'lib/lrama/grammar.rb', line 19

def types
  @types
end

#undef_symbol ⇒ Object (readonly)

Returns the value of attribute undef_symbol.



18
19
20
 
# File 'lib/lrama/grammar.rb', line 18

def undef_symbol
  @undef_symbol
end

#union ⇒ Object

Returns the value of attribute union.



19
20
21
 
# File 'lib/lrama/grammar.rb', line 19

def union
  @union
end

Instance Method Details

#add_error_token(ident_or_tags:, code:, lineno:) ⇒ Object 



48
49
50
 
# File 'lib/lrama/grammar.rb', line 48

def add_error_token(ident_or_tags:, code:, lineno:)
  @error_tokens << ErrorToken.new(ident_or_tags: ident_or_tags, code: code, lineno: lineno)
end

#add_left(sym, precedence) ⇒ Object 



98
99
100
 
# File 'lib/lrama/grammar.rb', line 98

def add_left(sym, precedence)
  set_precedence(sym, Precedence.new(type: :left, precedence: precedence))
end

#add_nonassoc(sym, precedence) ⇒ Object 



94
95
96
 
# File 'lib/lrama/grammar.rb', line 94

def add_nonassoc(sym, precedence)
  set_precedence(sym, Precedence.new(type: :nonassoc, precedence: precedence))
end

#add_nterm(id:, alias_name: nil, tag: nil) ⇒ Object 



77
78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/lrama/grammar.rb', line 77

def add_nterm(id:, alias_name: nil, tag: nil)
  return if @symbols.find {|s| s.id == id }

  sym = Symbol.new(
    id: id, alias_name: alias_name, number: nil, tag: tag,
    term: false, token_id: nil, nullable: nil,
  )
  @symbols << sym
  @nterms = nil

  return sym
end

#add_precedence(sym, precedence) ⇒ Object 



106
107
108
 
# File 'lib/lrama/grammar.rb', line 106

def add_precedence(sym, precedence)
  set_precedence(sym, Precedence.new(type: :precedence, precedence: precedence))
end

#add_printer(ident_or_tags:, code:, lineno:) ⇒ Object 



44
45
46
 
# File 'lib/lrama/grammar.rb', line 44

def add_printer(ident_or_tags:, code:, lineno:)
  @printers << Printer.new(ident_or_tags: ident_or_tags, code: code, lineno: lineno)
end

#add_right(sym, precedence) ⇒ Object 



102
103
104
 
# File 'lib/lrama/grammar.rb', line 102

def add_right(sym, precedence)
  set_precedence(sym, Precedence.new(type: :right, precedence: precedence))
end

#add_rule(lhs:, rhs:, lineno:) ⇒ Object 



119
120
121
 
# File 'lib/lrama/grammar.rb', line 119

def add_rule(lhs:, rhs:, lineno:)
  @_rules << [lhs, rhs, lineno]
end

#add_term(id:, alias_name: nil, tag: nil, token_id: nil, replace: false) ⇒ Object 



52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
# File 'lib/lrama/grammar.rb', line 52

def add_term(id:, alias_name: nil, tag: nil, token_id: nil, replace: false)
  if token_id && (sym = @symbols.find {|s| s.token_id == token_id })
    if replace
      sym.id = id
      sym.alias_name = alias_name
      sym.tag = tag
    end

    return sym
  end

  if sym = @symbols.find {|s| s.id == id }
    return sym
  end

  sym = Symbol.new(
    id: id, alias_name: alias_name, number: nil, tag: tag,
    term: true, token_id: token_id, nullable: false
  )
  @symbols << sym
  @terms = nil

  return sym
end

#add_type(id:, tag:) ⇒ Object 



90
91
92
 
# File 'lib/lrama/grammar.rb', line 90

def add_type(id:, tag:)
  @types << Type.new(id: id, tag: tag)
end

#build_code(type, token_code) ⇒ Object 



131
132
133
134
 
# File 'lib/lrama/grammar.rb', line 131

def build_code(type, token_code)
  build_references(token_code)
  Code.new(type: type, token_code: token_code)
end

#build_references(token_code) ⇒ Object 



123
124
125
126
127
128
129
 
# File 'lib/lrama/grammar.rb', line 123

def build_references(token_code)
  token_code.references.map! do |type, value, tag, first_column, last_column|
    Reference.new(type: type, value: value, ex_tag: tag, first_column: first_column, last_column: last_column)
  end

  token_code
end

#compute_first_set ⇒ Object 



220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
 
# File 'lib/lrama/grammar.rb', line 220

def compute_first_set
  terms.each do |term|
    term.first_set = Set.new([term]).freeze
    term.first_set_bitmap = Lrama::Bitmap.from_array([term.number])
  end

  nterms.each do |nterm|
    nterm.first_set = Set.new([]).freeze
    nterm.first_set_bitmap = Lrama::Bitmap.from_array([])
  end

  while true do
    changed = false

    @rules.each do |rule|
      rule.rhs.each do |r|
        if rule.lhs.first_set_bitmap | r.first_set_bitmap != rule.lhs.first_set_bitmap
          changed = true
          rule.lhs.first_set_bitmap = rule.lhs.first_set_bitmap | r.first_set_bitmap
        end

        break unless r.nullable
      end
    end

    break unless changed
  end

  nterms.each do |nterm|
    nterm.first_set = Lrama::Bitmap.to_array(nterm.first_set_bitmap).map do |number|
      find_symbol_by_number!(number)
    end.to_set
  end
end

#compute_nullable ⇒ Object 



171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
 
# File 'lib/lrama/grammar.rb', line 171

def compute_nullable
  @rules.each do |rule|
    case
    when rule.rhs.empty?
      rule.nullable = true
    when rule.rhs.any?(&:term)
      rule.nullable = false
    else
      # noop
    end
  end

  while true do
    rs  = @rules.select {|e| e.nullable.nil? }
    nts = nterms.select {|e| e.nullable.nil? }
    rule_count_1  = rs.count
    nterm_count_1 = nts.count

    rs.each do |rule|
      if rule.rhs.all?(&:nullable)
        rule.nullable = true
      end
    end

    nts.each do |nterm|
      find_rules_by_symbol!(nterm).each do |rule|
        if rule.nullable
          nterm.nullable = true
        end
      end
    end

    rule_count_2  = @rules.count {|e| e.nullable.nil? }
    nterm_count_2 = nterms.count {|e| e.nullable.nil? }

    if (rule_count_1 == rule_count_2) && (nterm_count_1 == nterm_count_2)
      break
    end
  end

  rules.select {|r| r.nullable.nil? }.each do |rule|
    rule.nullable = false
  end

  nterms.select {|r| r.nullable.nil? }.each do |nterm|
    nterm.nullable = false
  end
end

#epilogue=(epilogue) ⇒ Object 



148
149
150
 
# File 'lib/lrama/grammar.rb', line 148

def epilogue=(epilogue)
  @aux.epilogue = epilogue
end

#epilogue_first_lineno=(epilogue_first_lineno) ⇒ Object 



144
145
146
 
# File 'lib/lrama/grammar.rb', line 144

def epilogue_first_lineno=(epilogue_first_lineno)
  @aux.epilogue_first_lineno = epilogue_first_lineno
end

#find_rules_by_symbol(sym) ⇒ Object 



289
290
291
 
# File 'lib/lrama/grammar.rb', line 289

def find_rules_by_symbol(sym)
  @sym_to_rules[sym.number]
end

#find_rules_by_symbol!(sym) ⇒ Object 



285
286
287
 
# File 'lib/lrama/grammar.rb', line 285

def find_rules_by_symbol!(sym)
  find_rules_by_symbol(sym) || (raise "Rules for #{sym} not found")
end

#find_symbol_by_id(id) ⇒ Object 



265
266
267
268
269
270
 
# File 'lib/lrama/grammar.rb', line 265

def find_symbol_by_id(id)
  @symbols.find do |sym|
    # TODO: validate uniqueness of Token#s_value and Symbol#alias_name
    sym.id == id || sym.alias_name == id.s_value
  end
end

#find_symbol_by_id!(id) ⇒ Object 



272
273
274
 
# File 'lib/lrama/grammar.rb', line 272

def find_symbol_by_id!(id)
  find_symbol_by_id(id) || (raise "Symbol not found: #{id}")
end

#find_symbol_by_number!(number) ⇒ Object 



276
277
278
279
280
281
282
283
 
# File 'lib/lrama/grammar.rb', line 276

def find_symbol_by_number!(number)
  sym = @symbols[number]

  raise "Symbol not found: #{number}" unless sym
  raise "[BUG] Symbol number mismatch. #{number}, #{sym}" if sym.number != number

  sym
end

#find_symbol_by_s_value(s_value) ⇒ Object 



255
256
257
258
259
 
# File 'lib/lrama/grammar.rb', line 255

def find_symbol_by_s_value(s_value)
  @symbols.find do |sym|
    sym.id.s_value == s_value
  end
end

#find_symbol_by_s_value!(s_value) ⇒ Object 



261
262
263
 
# File 'lib/lrama/grammar.rb', line 261

def find_symbol_by_s_value!(s_value)
  find_symbol_by_s_value(s_value) || (raise "Symbol not found: #{s_value}")
end

#nterms ⇒ Object 



305
306
307
 
# File 'lib/lrama/grammar.rb', line 305

def nterms
  @nterms ||= @symbols.select(&:nterm?)
end

#nterms_count ⇒ Object 



301
302
303
 
# File 'lib/lrama/grammar.rb', line 301

def nterms_count
  nterms.count
end

#prepare ⇒ Object 



152
153
154
155
156
157
158
159
160
161
162
163
 
# File 'lib/lrama/grammar.rb', line 152

def prepare
  normalize_rules
  collect_symbols
  replace_token_with_symbol
  fill_symbol_number
  fill_default_precedence
  fill_sym_to_rules
  fill_nterm_type
  fill_symbol_printer
  fill_symbol_error_token
  @symbols.sort_by!(&:number)
end

#prologue=(prologue) ⇒ Object 



140
141
142
 
# File 'lib/lrama/grammar.rb', line 140

def prologue=(prologue)
  @aux.prologue = prologue
end

#prologue_first_lineno=(prologue_first_lineno) ⇒ Object 



136
137
138
 
# File 'lib/lrama/grammar.rb', line 136

def prologue_first_lineno=(prologue_first_lineno)
  @aux.prologue_first_lineno = prologue_first_lineno
end

#set_precedence(sym, precedence) ⇒ Object 



110
111
112
113
 
# File 'lib/lrama/grammar.rb', line 110

def set_precedence(sym, precedence)
  raise "" if sym.nterm?
  sym.precedence = precedence
end

#set_union(code, lineno) ⇒ Object 



115
116
117
 
# File 'lib/lrama/grammar.rb', line 115

def set_union(code, lineno)
  @union = Union.new(code: code, lineno: lineno)
end

#terms ⇒ Object 



297
298
299
 
# File 'lib/lrama/grammar.rb', line 297

def terms
  @terms ||= @symbols.select(&:term?)
end

#terms_count ⇒ Object 



293
294
295
 
# File 'lib/lrama/grammar.rb', line 293

def terms_count
  terms.count
end

#validate! ⇒ Object

TODO: More validation methods



166
167
168
169
 
# File 'lib/lrama/grammar.rb', line 166

def validate!
  validate_symbol_number_uniqueness!
  validate_no_declared_type_reference!
end