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

Instance Method Summary collapse

Constructor Details

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

Returns a new instance of Rule.

Parameters:

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

Options Hash (options):

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


56
57
58
59
60
61
62
63
64
65
66
67
 
# File 'lib/ebnf/rule.rb', line 56

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)
  @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:



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

def comp
  @comp
end

#comprehension of this rule(ofthisrule) ⇒ Rule

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

Returns:



24
 
# File 'lib/ebnf/rule.rb', line 24

attr_accessor :comp

#expr ⇒ Array

Returns:

  • (Array) 


32
33
34
 
# File 'lib/ebnf/rule.rb', line 32

def expr
  @expr
end

#expr rule expression(ruleexpression) ⇒ Array

Returns:

  • (Array) 


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

attr_accessor :expr

#first ⇒ Array<Rule> (readonly)

Returns:



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

def first
  @first
end

#first terminals that immediately procede this rule(terminalsthatimmediatelyprocedethisrule) ⇒ Array<Rule> (readonly)

Returns:



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

attr_reader :first

#follow ⇒ Array<Rule> (readonly)

Returns:



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

def follow
  @follow
end

#follow terminals that immediately follow this rule(terminalsthatimmediatelyfollowthisrule) ⇒ Array<Rule> (readonly)

Returns:



44
 
# File 'lib/ebnf/rule.rb', line 44

attr_reader :follow

#id ⇒ String

Returns:

  • (String) 


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

def id
  @id
end

#id of rule(ofrule) ⇒ String

Returns:

  • (String) 


19
 
# File 'lib/ebnf/rule.rb', line 19

attr_accessor :id

#kind ⇒ :rule, ...

Returns:

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


28
29
30
 
# File 'lib/ebnf/rule.rb', line 28

def kind
  @kind
end

#kind of rule(ofrule) ⇒ :rule, ...

Returns:

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


28
 
# File 'lib/ebnf/rule.rb', line 28

attr_accessor :kind

#orig ⇒ String

Returns:

  • (String) 


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

def orig
  @orig
end

#orig original rule(originalrule) ⇒ String

Returns:

  • (String) 


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

attr_accessor :orig

#start ⇒ Boolean

Returns:

  • (Boolean) 


48
49
50
 
# File 'lib/ebnf/rule.rb', line 48

def start
  @start
end

#start indicates that this is a starting rule(indicatesthatthisisastartingrule) ⇒ Boolean

Returns:

  • (Boolean) 


48
 
# File 'lib/ebnf/rule.rb', line 48

attr_accessor :start

#sym ⇒ Symbol

Returns:

  • (Symbol) 


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

def sym
  @sym
end

#sym for rule ⇒ Symbol

Returns:

  • (Symbol) 


15
 
# File 'lib/ebnf/rule.rb', line 15

attr_accessor :sym

Instance Method Details

#<=>(other) ⇒ Object

Rules compare using their ids



277
278
279
280
281
282
283
 
# File 'lib/ebnf/rule.rb', line 277

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) 


248
249
250
251
252
 
# File 'lib/ebnf/rule.rb', line 248

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

Returns:

  • (Integer) —

    if number of terminals added



208
209
210
211
212
213
 
# File 'lib/ebnf/rule.rb', line 208

def add_first(terminals)
  @first ||= []
  terminals -= @first  # Remove those already in 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>)

Returns:

  • (Integer) —

    if number of terminals added



219
220
221
222
223
224
225
226
227
 
# File 'lib/ebnf/rule.rb', line 219

def add_follow(terminals)
  terminals -= @follow || []  # Remove those already in first
  terminals -= [:_eps]  # Special case, don't add empty string as a follow terminal
  unless terminals.empty?
    @follow ||= []
    @follow += terminals
  end
  terminals.length
end

#alt? ⇒ Boolean

Is this rule of the form (alt …)?

Returns:

  • (Boolean) 


235
236
237
 
# File 'lib/ebnf/rule.rb', line 235

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)



76
77
78
79
80
81
82
83
 
# File 'lib/ebnf/rule.rb', line 76

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) 


257
258
259
 
# File 'lib/ebnf/rule.rb', line 257

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

#first_includes_eps? ⇒ Boolean

Do the firsts of this rule include the empty string?

Returns:

  • (Boolean) 


201
202
203
 
# File 'lib/ebnf/rule.rb', line 201

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

#inspect ⇒ Object 



239
240
241
242
243
 
# File 'lib/ebnf/rule.rb', line 239

def inspect
  "#<EBNF::Rule:#{object_id} " +
  {:sym => sym, :id => id, :kind => kind, :expr => expr}.inspect +
  ">"
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:



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

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

#seq? ⇒ Boolean

Is this rule of the form (seq …)?

Returns:

  • (Boolean) 


230
231
232
 
# File 'lib/ebnf/rule.rb', line 230

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



189
190
191
192
193
194
195
196
197
 
# File 'lib/ebnf/rule.rb', line 189

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

#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:



130
131
132
133
134
135
136
137
138
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
181
 
# File 'lib/ebnf/rule.rb', line 130

def to_bnf
  return [self] unless kind == :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.kind == :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_s ⇒ Object 



100
 
# File 'lib/ebnf/rule.rb', line 100

def to_s; to_sxp; end

#to_sxp ⇒ String

Serializes this rule to an S-Expression

Returns:

  • (String) 


87
88
89
90
91
92
93
94
95
96
97
98
99
 
# File 'lib/ebnf/rule.rb', line 87

def to_sxp
  elements = [kind, sym, 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
  begin
    require 'sxp'
    SXP::Generator.string(elements)
  rescue LoadError
    elements.to_sxp
  end
end

#to_ttl ⇒ String

Serializes this rule to an Turtle

Returns:

  • (String) 


104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
 
# File 'lib/ebnf/rule.rb', line 104

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, kind == :terminal ? "re" : "g", 1, false)
  "\n" + statements.join("\n")
end