Class: EBNF::Rule

Inherits:
Object
  • Object
show all
Defined in:
lib/ebnf/rule.rb

Overview

Represent individual parsed rules

Constant Summary collapse

BNF_OPS =

Operations which are flattened to seprate rules in to_bnf

%w{
  alt opt plus seq star
}.map(&:to_sym).freeze
TERM_OPS = 
%w{
  diff hex range
}.map(&:to_sym).freeze

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(sym, id, expr, options = {}) ⇒ Rule

option options [Boolean] :start

Parameters:

  • id (Integer)
  • sym (Symbol)
  • expr (Array)
  • options (Hash{Symbol => Object}) (defaults to: {})

Options Hash (options):

  • :kind (Symbol)
  • :ebnf (String)
  • :first (Array)
  • :follow (Array) 


66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
 
# File 'lib/ebnf/rule.rb', line 66

def initialize(sym, id, expr, options = {})
  @sym, @id = sym, id
  @expr = expr.is_a?(Array) ? expr : [:seq, expr]
  @ebnf = options[:ebnf]
  @top_rule = options.fetch(:top_rule, self)
  @first = options[:first]
  @follow = options[:follow]
  @start = options[:start]
  @kind = case
  when options[:kind] then options[:kind]
  when sym.to_s == sym.to_s.upcase then :terminal
  when !BNF_OPS.include?(@expr.first) then :terminal
  else :rule
  end
end

Instance Attribute Details

#comp ⇒ Rule

A comprehension is a sequence which contains all elements but the first of the original rule.

Returns:



25
26
27
 
# File 'lib/ebnf/rule.rb', line 25

def comp
  @comp
end

#expr ⇒ Array

Rule expression

Returns:

  • (Array) 


35
36
37
 
# File 'lib/ebnf/rule.rb', line 35

def expr
  @expr
end

#first ⇒ Array<Rule> (readonly)

Terminals that immediately procede this rule

Returns:



45
46
47
 
# File 'lib/ebnf/rule.rb', line 45

def first
  @first
end

#follow ⇒ Array<Rule> (readonly)

Terminals that immediately follow this rule

Returns:



50
51
52
 
# File 'lib/ebnf/rule.rb', line 50

def follow
  @follow
end

#id ⇒ String

ID of rule

Returns:

  • (String) 


20
21
22
 
# File 'lib/ebnf/rule.rb', line 20

def id
  @id
end

#kind ⇒ :rule, ...

Kind of rule

Returns:

  • (:rule, :terminal, or :pass) 


30
31
32
 
# File 'lib/ebnf/rule.rb', line 30

def kind
  @kind
end

#orig ⇒ String

Original EBNF

Returns:

  • (String) 


40
41
42
 
# File 'lib/ebnf/rule.rb', line 40

def orig
  @orig
end

#start ⇒ Boolean

Indicates that this is a starting rule

Returns:

  • (Boolean) 


55
56
57
 
# File 'lib/ebnf/rule.rb', line 55

def start
  @start
end

#sym ⇒ Symbol

Symbol of rule

Returns:

  • (Symbol) 


16
17
18
 
# File 'lib/ebnf/rule.rb', line 16

def sym
  @sym
end

Class Method Details

.from_sxp(sxp) ⇒ Rule

Return a rule from its SXP representation:

Also may have (first …), (follow …), or (start #t)

Examples:

inputs

(pass (plus (range "#x20\\t\\r\\n")))
(rule ebnf "1" (star (alt declaration rule)))
(terminal O_ENUM "17" (seq "[^" (plus CHAR) "]"))

Parameters:

  • sxp (Array)

Returns:



94
95
96
97
98
99
100
101
102
103
104
 
# File 'lib/ebnf/rule.rb', line 94

def self.from_sxp(sxp)
  expr = sxp.detect {|e| e.is_a?(Array) && ![:first, :follow, :start].include?(e.first.to_sym)}
  first = sxp.detect {|e| e.is_a?(Array) && e.first.to_sym == :first}
  first = first[1..-1] if first
  follow = sxp.detect {|e| e.is_a?(Array) && e.first.to_sym == :follow}
  follow = follow[1..-1] if follow
  start = sxp.any? {|e| e.is_a?(Array) && e.first.to_sym == :start}
  sym = sxp[1] if sxp[1].is_a?(Symbol)
  id = sxp[2] if sxp[2].is_a?(String)
  Rule.new(sym, id, expr, :kind => sxp.first, :first => first, :follow => follow, :start => start)
end

Instance Method Details

#<=>(other) ⇒ Object

Rules compare using their ids



376
377
378
379
380
381
382
 
# File 'lib/ebnf/rule.rb', line 376

def <=>(other)
  if id.to_i == other.id.to_i
    id <=> other.id
  else
    id.to_i <=> other.id.to_i
  end
end

#==(other) ⇒ Boolean

Two rules are equal if they have the same #sym, #kind and #expr

Parameters:

Returns:

  • (Boolean) 


347
348
349
350
351
 
# File 'lib/ebnf/rule.rb', line 347

def ==(other)
  sym   == other.sym &&
  kind  == other.kind &&
  expr  == other.expr
end

#add_first(terminals) ⇒ Integer

Add terminal as proceding this rule

Parameters:

  • terminals (Array<Rule, Symbol, String>)

Returns:

  • (Integer) —

    if number of terminals added



284
285
286
287
288
289
 
# File 'lib/ebnf/rule.rb', line 284

def add_first(terminals)
  @first ||= []
  terminals = terminals.map {|t| t.is_a?(Rule) ? t.sym : t} - @first
  @first += terminals
  terminals.length
end

#add_follow(terminals) ⇒ Integer

Add terminal as following this rule. Don’t add _eps as a follow

Parameters:

  • terminals (Array<Rule, Symbol, String>)

Returns:

  • (Integer) —

    if number of terminals added



295
296
297
298
299
300
301
302
303
 
# File 'lib/ebnf/rule.rb', line 295

def add_follow(terminals)
  # Remove terminals already in follows, and empty string
  terminals = terminals.map {|t| t.is_a?(Rule) ? t.sym : t} - (@follow || []) - [:_eps]
  unless terminals.empty?
    @follow ||= []
    @follow += terminals
  end
  terminals.length
end

#alt? ⇒ Boolean

Is this rule of the form (alt …)?

Returns:

  • (Boolean) 


324
325
326
 
# File 'lib/ebnf/rule.rb', line 324

def alt?
  expr.is_a?(Array) && expr.first == :alt
end

#build(expr, options = {}) ⇒ Object

Build a new rule creating a symbol and numbering from the current rule Symbol and number creation is handled by the top-most rule in such a chain

Parameters:

  • expr (Array)
  • options (Hash{Symbol => Object}) (defaults to: {})

Options Hash (options):

  • :kind (Symbol)
  • :ebnf (String) —

    EBNF instance (used for messages)



113
114
115
116
117
118
119
120
 
# File 'lib/ebnf/rule.rb', line 113

def build(expr, options = {})
  new_sym, new_id = (@top_rule ||self).send(:make_sym_id)
  Rule.new(new_sym, new_id, expr, {
    :kind => options[:kind],
    :ebnf => @ebnf,
    :top_rule => @top_rule || self,
  }.merge(options))
end

#equivalent?(other) ⇒ Boolean

Two rules are equivalent if they have the same #expr

Parameters:

Returns:

  • (Boolean) 


356
357
358
 
# File 'lib/ebnf/rule.rb', line 356

def equivalent?(other)
  expr  == other.expr
end

#first_includes_eps? ⇒ Boolean

Do the firsts of this rule include the empty string?

Returns:

  • (Boolean) 


277
278
279
 
# File 'lib/ebnf/rule.rb', line 277

def first_includes_eps?
  @first && @first.include?(:_eps)
end

#for_sxp ⇒ Array

Return representation for building S-Expressions

Returns:

  • (Array) 


124
125
126
127
128
129
130
131
132
 
# File 'lib/ebnf/rule.rb', line 124

def for_sxp
  elements = [kind, sym]
  elements << id if id
  elements << [:start, true] if start
  elements << first.sort_by(&:to_s).unshift(:first) if first
  elements << follow.sort_by(&:to_s).unshift(:follow) if follow
  elements << expr
  elements
end

#inspect ⇒ Object 



338
339
340
341
342
 
# File 'lib/ebnf/rule.rb', line 338

def inspect
  "#<EBNF::Rule:#{object_id} " +
  {:sym => sym, :id => id, :kind => kind, :expr => expr}.inspect +
  ">"
end

#non_terminals(ast) ⇒ Array<Rule>

Return the non-terminals for this rule. For seq, this is the first non-terminals in the seq. For alt, this is every non-terminal ni the alt

Parameters:

  • ast (Array<Rule>) —

    The set of rules, used to turn symbols into rules

Returns:



228
229
230
231
232
233
234
235
236
237
238
 
# File 'lib/ebnf/rule.rb', line 228

def non_terminals(ast)
  @non_terms ||= (alt? ? expr[1..-1] : expr[1,1]).map do |sym|
    case sym
    when Symbol
      r = ast.detect {|r| r.sym == sym}
      r if r && r.rule?
    else
      nil
    end
  end.compact
end

#pass? ⇒ Boolean

Is this a pass?

Returns:

  • (Boolean) 


313
314
315
 
# File 'lib/ebnf/rule.rb', line 313

def pass?
  kind == :pass
end

#rewrite(src_rule, dst_rule) ⇒ Rule

Rewrite the rule substituting src_rule for dst_rule wherever it is used in the production (first level only).

Parameters:

Returns:



365
366
367
368
369
370
371
372
373
 
# File 'lib/ebnf/rule.rb', line 365

def rewrite(src_rule, dst_rule)
  case @expr
  when Array
    @expr = @expr.map {|e| e == src_rule.sym ? dst_rule.sym : e}
  else
    @expr = dst_rule.sym if @expr == src_rule.sym
  end
  self
end

#rule? ⇒ Boolean

Is this a rule?

Returns:

  • (Boolean) 


319
320
321
 
# File 'lib/ebnf/rule.rb', line 319

def rule?
  kind == :rule
end

#seq? ⇒ Boolean

Is this rule of the form (seq …)?

Returns:

  • (Boolean) 


329
330
331
 
# File 'lib/ebnf/rule.rb', line 329

def seq?
  expr.is_a?(Array) && expr.first == :seq
end

#starts_with?(sym) ⇒ Array<Symbol, String>

Does this rule start with a sym? It does if expr is that sym, expr starts with alt and contains that sym, or expr starts with seq and the next element is that sym

Parameters:

  • sym (Symbol, class) —

    Symbol matching any start element, or if it is String, any start element which is a String

Returns:

  • (Array<Symbol, String>) —

    list of symbol (singular), or strings which are start symbol, or nil if there are none



265
266
267
268
269
270
271
272
273
 
# File 'lib/ebnf/rule.rb', line 265

def starts_with?(sym)
  if seq? && sym === (v = expr.fetch(1, nil))
    [v]
  elsif alt? && expr.any? {|e| sym === e}
    expr.select {|e| sym === e}
  else
    nil
  end
end

#terminal? ⇒ Boolean

Is this a terminal?

Returns:

  • (Boolean) 


307
308
309
 
# File 'lib/ebnf/rule.rb', line 307

def terminal?
  kind == :terminal
end

#terminals(ast) ⇒ Array<Rule>

Return the terminals for this rule. For seq, this is the first terminals or strings in the seq. For alt, this is every non-terminal ni the alt

Parameters:

  • ast (Array<Rule>) —

    The set of rules, used to turn symbols into rules

Returns:



245
246
247
248
249
250
251
252
253
254
255
256
257
 
# File 'lib/ebnf/rule.rb', line 245

def terminals(ast)
  @terms ||= (alt? ? expr[1..-1] : expr[1,1]).map do |sym|
    case sym
    when Symbol
      r = ast.detect {|r| r.sym == sym}
      r if r && r.terminal?
    when String
      sym
    else
      nil
    end
  end.compact
end

#to_bnf ⇒ Array<Rule>

Transform EBNF rule to BNF rules:

* Transform (a [n] rule (op1 (op2))) into two rules:
  (a [n] rule (op1 a.2))
  (_a_1 [n.1] rule (op2))
* Transform (a rule (opt b)) into (a rule (alt _empty "foo"))
* Transform (a rule (star b)) into (a rule (alt _empty (seq b a)))
* Transform (a rule (plus b)) into (a rule (seq b (star b)

Returns:



170
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
219
220
221
 
# File 'lib/ebnf/rule.rb', line 170

def to_bnf
  return [self] unless rule?
  new_rules = []

  # Look for rules containing recursive definition and rewrite to multiple rules. If `expr` contains elements which are in array form, where the first element of that array is a symbol, create a new rule for it.
  if expr.any? {|e| e.is_a?(Array) && (BNF_OPS + TERM_OPS).include?(e.first)}
    #   * Transform (a [n] rule (op1 (op2))) into two rules:
    #     (a.1 [n.1] rule (op1 a.2))
    #     (a.2 [n.2] rule (op2))
    # duplicate ourselves for rewriting
    this = dup
    new_rules << this

    expr.each_with_index do |e, index|
      next unless e.is_a?(Array) && e.first.is_a?(Symbol)
      new_rule = build(e)
      this.expr[index] = new_rule.sym
      new_rules << new_rule
    end

    # Return new rules after recursively applying #to_bnf
    new_rules = new_rules.map {|r| r.to_bnf}.flatten
  elsif expr.first == :opt
    this = dup
    #   * Transform (a rule (opt b)) into (a rule (alt _empty b))
    this.expr = [:alt, :_empty, expr.last]
    new_rules = this.to_bnf
  elsif expr.first == :star
    #   * Transform (a rule (star b)) into (a rule (alt _empty (seq b a)))
    this = dup
    new_rule = this.build([:seq, expr.last, this.sym])
    this.expr = [:alt, :_empty, new_rule.sym]
    new_rules = [this] + new_rule.to_bnf
  elsif expr.first == :plus
    #   * Transform (a rule (plus b)) into (a rule (seq b (star b)
    this = dup
    this.expr = [:seq, expr.last, [:star, expr.last]]
    new_rules = this.to_bnf
  elsif [:alt, :seq].include?(expr.first)
    # Otherwise, no further transformation necessary
    new_rules << self
  elsif [:diff, :hex, :range].include?(expr.first)
    # This rules are fine, the just need to be terminals
    raise "Encountered #{expr.first.inspect}, which is a #{self.kind}, not :terminal" unless self.terminal?
    new_rules << self
  else
    # Some case we didn't think of
    raise "Error trying to transform #{expr.inspect} to BNF"
  end
  
  return new_rules
end

#to_sxp ⇒ String Also known as: to_s

Return SXP representation of this rule

Returns:

  • (String) 


136
137
138
 
# File 'lib/ebnf/rule.rb', line 136

def to_sxp
  for_sxp.to_sxp
end

#to_ttl ⇒ String

Serializes this rule to an Turtle

Returns:

  • (String) 


144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
 
# File 'lib/ebnf/rule.rb', line 144

def to_ttl
  @ebnf.debug("to_ttl") {inspect}
  comment = orig.strip.
    gsub(/"""/, '\"\"\"').
    gsub("\\", "\\\\").
    sub(/^\"/, '\"').
    sub(/\"$/m, '\"')
  statements = [
    %{:#{id} rdfs:label "#{id}"; rdf:value "#{sym}";},
    %{  rdfs:comment #{comment.inspect};},
  ]
  
  statements += ttl_expr(expr, terminal? ? "re" : "g", 1, false)
  "\n" + statements.join("\n")
end