Class: EBNF::Rule
- Inherits:
-
Object
- Object
- EBNF::Rule
- 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
-
#cleanup ⇒ Object
Determines preparation and cleanup rules for reconstituting EBNF ? * + from BNF.
-
#comp ⇒ Rule
A comprehension is a sequence which contains all elements but the first of the original rule.
-
#expr ⇒ Array
Rule expression.
-
#first ⇒ Array<Rule>
readonly
Terminals that immediately procede this rule.
-
#follow ⇒ Array<Rule>
readonly
Terminals that immediately follow this rule.
-
#id ⇒ String
ID of rule.
-
#kind ⇒ :rule, ...
Kind of rule.
-
#orig ⇒ String
Original EBNF.
-
#start ⇒ Boolean
Indicates that this is a starting rule.
-
#sym ⇒ Symbol
Symbol of rule.
Class Method Summary collapse
-
.from_sxp(sxp) ⇒ Rule
Return a rule from its SXP representation:.
Instance Method Summary collapse
-
#<=>(other) ⇒ Object
Rules compare using their ids.
- #==(other) ⇒ Boolean
-
#add_first(terminals) ⇒ Integer
Add terminal as proceding this rule.
-
#add_follow(terminals) ⇒ Integer
Add terminal as following this rule.
-
#alt? ⇒ Boolean
Is this rule of the form (alt …)?.
-
#build(expr, kind: nil, cleanup: nil, **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.
-
#equivalent?(other) ⇒ Boolean
Two rules are equivalent if they have the same #expr.
-
#first_includes_eps? ⇒ Boolean
Do the firsts of this rule include the empty string?.
-
#for_sxp ⇒ Array
Return representation for building S-Expressions.
-
#initialize(sym, id, expr, kind: nil, ebnf: nil, first: nil, follow: nil, start: nil, top_rule: nil, cleanup: nil) ⇒ Rule
constructor
A new instance of Rule.
- #inspect ⇒ Object
-
#non_terminals(ast) ⇒ Array<Rule>
Return the non-terminals for this rule.
-
#pass? ⇒ Boolean
Is this a pass?.
-
#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).
-
#rule? ⇒ Boolean
Is this a rule?.
-
#seq? ⇒ Boolean
Is this rule of the form (seq …)?.
-
#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.
-
#terminal? ⇒ Boolean
Is this a terminal?.
-
#terminals(ast) ⇒ Array<Rule>
Return the terminals for this rule.
-
#to_bnf ⇒ Array<Rule>
Transform EBNF rule to BNF rules:.
-
#to_sxp ⇒ String
(also: #to_s)
Return SXP representation of this rule.
-
#to_ttl ⇒ String
Serializes this rule to an Turtle.
Constructor Details
#initialize(sym, id, expr, kind: nil, ebnf: nil, first: nil, follow: nil, start: nil, top_rule: nil, cleanup: nil) ⇒ Rule
Returns a new instance of Rule.
70 71 72 73 74 75 76 77 78 79 80 |
# File 'lib/ebnf/rule.rb', line 70 def initialize(sym, id, expr, kind: nil, ebnf: nil, first: nil, follow: nil, start: nil, top_rule: nil, cleanup: nil) @sym, @id = sym, id @expr = expr.is_a?(Array) ? expr : [:seq, expr] @ebnf, @kind, @first, @follow, @start, @cleanup, @top_rule = ebnf, kind, first, follow, start, cleanup, top_rule @top_rule ||= self @kind ||= case 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
#cleanup ⇒ Object
Determines preparation and cleanup rules for reconstituting EBNF ? * + from BNF
58 59 60 |
# File 'lib/ebnf/rule.rb', line 58 def cleanup @cleanup end |
#comp ⇒ Rule
A comprehension is a sequence which contains all elements but the first of the original rule.
25 26 27 |
# File 'lib/ebnf/rule.rb', line 25 def comp @comp end |
#expr ⇒ Array
Rule expression
35 36 37 |
# File 'lib/ebnf/rule.rb', line 35 def expr @expr end |
#first ⇒ Array<Rule> (readonly)
Terminals that immediately procede this rule
45 46 47 |
# File 'lib/ebnf/rule.rb', line 45 def first @first end |
#follow ⇒ Array<Rule> (readonly)
Terminals that immediately follow this rule
50 51 52 |
# File 'lib/ebnf/rule.rb', line 50 def follow @follow end |
#id ⇒ String
ID of rule
20 21 22 |
# File 'lib/ebnf/rule.rb', line 20 def id @id end |
#kind ⇒ :rule, ...
Kind of rule
30 31 32 |
# File 'lib/ebnf/rule.rb', line 30 def kind @kind end |
#orig ⇒ String
Original EBNF
40 41 42 |
# File 'lib/ebnf/rule.rb', line 40 def orig @orig end |
#start ⇒ Boolean
Indicates that this is a starting rule
55 56 57 |
# File 'lib/ebnf/rule.rb', line 55 def start @start end |
#sym ⇒ Symbol
Symbol of rule
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)
94 95 96 97 98 99 100 101 102 103 104 105 106 |
# 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 cleanup = sxp.detect {|e| e.is_a?(Array) && e.first.to_sym == :cleanup} cleanup = cleanup[1..-1] if cleanup 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, cleanup: cleanup, start: start) end |
Instance Method Details
#<=>(other) ⇒ Object
Rules compare using their ids
385 386 387 388 389 390 391 |
# File 'lib/ebnf/rule.rb', line 385 def <=>(other) if id.to_i == other.id.to_i id.to_s <=> other.id.to_s else id.to_i <=> other.id.to_i end end |
#==(other) ⇒ Boolean
356 357 358 359 360 |
# File 'lib/ebnf/rule.rb', line 356 def ==(other) sym == other.sym && kind == other.kind && expr == other.expr end |
#add_first(terminals) ⇒ Integer
Add terminal as proceding this rule
293 294 295 296 297 298 |
# File 'lib/ebnf/rule.rb', line 293 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
304 305 306 307 308 309 310 311 312 |
# File 'lib/ebnf/rule.rb', line 304 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 …)?
333 334 335 |
# File 'lib/ebnf/rule.rb', line 333 def alt? expr.is_a?(Array) && expr.first == :alt end |
#build(expr, kind: nil, cleanup: nil, **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
114 115 116 117 118 119 120 121 122 |
# File 'lib/ebnf/rule.rb', line 114 def build(expr, kind: nil, cleanup: nil, **) new_sym, new_id = (@top_rule ||self).send(:make_sym_id) Rule.new(new_sym, new_id, expr, kind: kind, ebnf: @ebnf, top_rule: (@top_rule || self), cleanup: cleanup, **) end |
#equivalent?(other) ⇒ Boolean
Two rules are equivalent if they have the same #expr
365 366 367 |
# File 'lib/ebnf/rule.rb', line 365 def equivalent?(other) expr == other.expr end |
#first_includes_eps? ⇒ Boolean
Do the firsts of this rule include the empty string?
286 287 288 |
# File 'lib/ebnf/rule.rb', line 286 def first_includes_eps? @first && @first.include?(:_eps) end |
#for_sxp ⇒ Array
Return representation for building S-Expressions
126 127 128 129 130 131 132 133 134 135 |
# File 'lib/ebnf/rule.rb', line 126 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 << [:cleanup, cleanup] if cleanup elements << expr elements end |
#inspect ⇒ Object
347 348 349 350 351 |
# File 'lib/ebnf/rule.rb', line 347 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
237 238 239 240 241 242 243 244 245 246 247 |
# File 'lib/ebnf/rule.rb', line 237 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?
322 323 324 |
# File 'lib/ebnf/rule.rb', line 322 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).
374 375 376 377 378 379 380 381 382 |
# File 'lib/ebnf/rule.rb', line 374 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?
328 329 330 |
# File 'lib/ebnf/rule.rb', line 328 def rule? kind == :rule end |
#seq? ⇒ Boolean
Is this rule of the form (seq …)?
338 339 340 |
# File 'lib/ebnf/rule.rb', line 338 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
274 275 276 277 278 279 280 281 282 |
# File 'lib/ebnf/rule.rb', line 274 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?
316 317 318 |
# File 'lib/ebnf/rule.rb', line 316 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
254 255 256 257 258 259 260 261 262 263 264 265 266 |
# File 'lib/ebnf/rule.rb', line 254 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_1))
(_a_1 [n.1] rule (op2))
* Transform (a rule (opt b)) into (a rule (alt _empty b))
* 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)
Transformation includes information used to re-construct non-transformed AST representation
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 222 223 224 225 226 227 228 229 230 |
# File 'lib/ebnf/rule.rb', line 176 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] this.cleanup = :opt new_rules = this.to_bnf elsif expr.first == :star # * Transform (a rule (star b)) into (a rule (alt _empty (seq b a))) this = dup this.cleanup = :star new_rule = this.build([:seq, expr.last, this.sym], cleanup: :merge) 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.cleanup = :plus 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
139 140 141 |
# File 'lib/ebnf/rule.rb', line 139 def to_sxp for_sxp.to_sxp end |
#to_ttl ⇒ String
Serializes this rule to an Turtle
147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 |
# File 'lib/ebnf/rule.rb', line 147 def to_ttl @ebnf.debug("to_ttl") {inspect} if @ebnf comment = orig.to_s.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 |