class ABNF
Constants
- CoreRules
- EmptySequence
- EmptySet
- JustRecursion
- LeftRecursion
- NonRecursion
- OtherRecursion
- RightRecursion
- SelfRecursion
Public Class Methods
new()
click to toggle source
# File lib/abnf/abnf.rb, line 5 def initialize @names = [] @rules = {} @start = nil end
parse(desc, dont_merge_core_rules=false)
click to toggle source
# File lib/abnf/parser.rb, line 456 def ABNF.parse(desc, dont_merge_core_rules=false) grammar = ABNF.new Parser.new(grammar).parse(desc) grammar.merge(CoreRules) unless dont_merge_core_rules grammar end
regexp(desc, name=nil)
click to toggle source
# File lib/abnf/regexp.rb, line 8 def ABNF.regexp(desc, name=nil) ABNF.regexp_tree(desc, name).regexp end
regexp_tree(desc, name=nil)
click to toggle source
# File lib/abnf/regexp.rb, line 12 def ABNF.regexp_tree(desc, name=nil) ABNF.parse(desc).regexp_tree(name) end
Public Instance Methods
[](name)
click to toggle source
# File lib/abnf/abnf.rb, line 31 def [](name) @rules[name] end
[]=(name, rhs)
click to toggle source
# File lib/abnf/abnf.rb, line 35 def []=(name, rhs) @names << name unless @rules.include? name @rules[name] = rhs end
add(name, rhs)
click to toggle source
# File lib/abnf/abnf.rb, line 40 def add(name, rhs) if @rules.include? name @rules[name] |= rhs else @names << name @rules[name] = rhs end end
delete_unreachable!(starts)
click to toggle source
# File lib/abnf/abnf.rb, line 59 def delete_unreachable!(starts) rules = {} id_map = {} stack = [] starts.each {|name| next if id_map.include? name each_strongly_connected_component_from(name, id_map, stack) {|syms| syms.each {|sym| rules[sym] = @rules[sym] if @rules.include? sym } } } @rules = rules @names.reject! {|name| !@rules.include?(name)} self end
delete_useless!(starts=nil)
click to toggle source
# File lib/abnf/abnf.rb, line 76 def delete_useless!(starts=nil) if starts starts = [starts] if Symbol === starts delete_unreachable!(starts) end useful_names = {} using_names = {} @rules.each {|name, rhs| useful_names[name] = true if rhs.useful?(useful_names) rhs.each_var {|n| (using_names[n] ||= {})[name] = true } } queue = useful_names.keys until queue.empty? n = queue.pop next unless using_names[n] using_names[n].keys.each {|name| if useful_names[name] using_names[n].delete name elsif @rules[name].useful?(useful_names) using_names[n].delete name useful_names[name] = true queue << name end } end rules = {} @rules.each {|name, rhs| rhs = rhs.subst_var {|n| useful_names[n] ? nil : EmptySet} rules[name] = rhs unless rhs.empty_set? } #xxx: raise if some of start symbol becomes empty set? @rules = rules @names.reject! {|name| !@rules.include?(name)} self end
each() { |name, rules| ... }
click to toggle source
# File lib/abnf/abnf.rb, line 53 def each(&block) @names.each {|name| yield name, @rules[name] } end
include?(name)
click to toggle source
# File lib/abnf/abnf.rb, line 49 def include?(name) @rules.include? name end
merge(g)
click to toggle source
# File lib/abnf/abnf.rb, line 25 def merge(g) g.each {|name, rhs| self.add(name, rhs) } end
names()
click to toggle source
# File lib/abnf/abnf.rb, line 21 def names @names.dup end
regexp(name=start_symbol)
click to toggle source
# File lib/abnf/regexp.rb, line 16 def regexp(name=start_symbol) regexp_tree(name).regexp end
regexp_tree(name=nil)
click to toggle source
Convert a recursive rule to non-recursive rule if possible. This conversion is not perfect. It may fail even if possible. More work (survey) is needed.
# File lib/abnf/regexp.rb, line 24 def regexp_tree(name=nil) name ||= start_symbol env = {} each_strongly_connected_component_from(name) {|ns| rules = {} ns.each {|n| rules[n] = @rules[n] } resolved_rules = {} updated = true while updated updated = false ns.reject! {|n| !rules.include?(n)} rs = {} ns.reverse_each {|n| e = rules[n] if !e raise ABNFError.new("no rule defined: #{n}") end rs[n] = e.recursion(ns, n) if rs[n] & OtherRecursion != 0 raise TooComplex.new("too complex to convert to regexp: #{n} (#{ns.join(', ')})") end } ns.reverse_each {|n| e = rules[n] r = rs[n] if r & SelfRecursion == 0 resolved_rules[n] = e rules.delete n rules.each {|n2, e2| rules[n2] = e2.subst_var {|n3| n3 == n ? e : nil}} updated = true break end } next if updated # X = Y | a # Y = X | b # => # Y = Y | a | b ns.reverse_each {|n| e = rules[n] r = rs[n] if r & JustRecursion != 0 && r & ~(NonRecursion|JustRecursion) == 0 e = e.remove_just_recursion(n) resolved_rules[n] = e rules.delete n rules.each {|n2, e2| rules[n2] = e2.subst_var {|n3| n3 == n ? e : nil}} updated = true break end } next if updated # X = X a | b # => # X = b a* ns.reverse_each {|n| e = rules[n] r = rs[n] if r & LeftRecursion != 0 && r & ~(NonRecursion|JustRecursion|LeftRecursion|SelfRecursion) == 0 e = e.remove_left_recursion(n) resolved_rules[n] = e rules.delete n rules.each {|n2, e2| rules[n2] = e2.subst_var {|n3| n3 == n ? e : nil}} updated = true break end } next if updated # X = a X | b # => # X = a* b ns.reverse_each {|n| e = rules[n] r = rs[n] if r & RightRecursion != 0 && r & ~(NonRecursion|JustRecursion|RightRecursion|SelfRecursion) == 0 e = e.remove_right_recursion(n) resolved_rules[n] = e rules.delete n rules.each {|n2, e2| rules[n2] = e2.subst_var {|n3| n3 == n ? e : nil}} updated = true break end } next if updated end if 1 < rules.length raise TooComplex.new("too complex to convert to regexp: (#{ns.join(', ')})") end if rules.length == 1 n, e = rules.shift r = e.recursion(ns, n) if r & OtherRecursion != 0 raise TooComplex.new("too complex to convert to regexp: #{n} (#{ns.join(', ')})") end if r == NonRecursion resolved_rules[n] = e else # X = a X | b | X c # => # X = a* b c* left, middle, right = e.split_recursion(n) resolved_rules[n] = Seq.new(Alt.new(left).rep, Alt.new(middle), Alt.new(right).rep) end end class << resolved_rules include TSort alias tsort_each_node each_key def tsort_each_child(n, &block) self[n].each_var {|n2| yield n2 if self.include? n2 } end end resolved_rules.tsort_each {|n| env[n] = resolved_rules[n].subst_var {|n2| unless env[n2] raise Exception.new("unresolved nonterminal: #{n}") # bug end env[n2] } } } env[name].regexp_tree end
start_symbol()
click to toggle source
# File lib/abnf/abnf.rb, line 15 def start_symbol return @start if @start raise StandardError.new("no symbol defined") if @names.empty? @names.first end
start_symbol=(name)
click to toggle source
# File lib/abnf/abnf.rb, line 11 def start_symbol=(name) @start = name end
tsort_each_child(name) { |n| ... }
click to toggle source
# File lib/abnf/abnf.rb, line 130 def tsort_each_child(name) return unless @rules.include? name @rules.fetch(name).each_var {|n| yield n} end
tsort_each_node(&block)
click to toggle source
# File lib/abnf/abnf.rb, line 127 def tsort_each_node(&block) @names.each(&block) end