Class: ABNF

Inherits:
Object
  • Object
show all
Includes:
TSort
Defined in:
lib/abnf/abnf.rb,
lib/abnf/parser.rb,
lib/abnf/regexp.rb,
lib/abnf/grammar.rb,
lib/abnf/corerules.rb

Defined Under Namespace

Classes: ABNFError, Alt, Elt, Parser, Rep, Seq, Term, TooComplex, Var

Constant Summary collapse

NonRecursion =

X = a

1
JustRecursion =

X = Y

2
LeftRecursion =

X = Y a

4
RightRecursion =

X = a Y

8
SelfRecursion =

Y is X in JustRecursion, LeftRecursion and RightRecursion

16
OtherRecursion =

otherwise

32
EmptySet = 
Alt._new
EmptySequence = 
Seq._new
CoreRules =

taken from RFC 2234

ABNF.parse(<<'End', true) # taken from RFC 2234
ALPHA          =  %x41-5A / %x61-7A   ; A-Z / a-z
BIT            =  "0" / "1"
CHAR           =  %x01-7F ; any 7-bit US-ASCII character, excluding NUL
CR             =  %x0D ; carriage return
CRLF           =  CR LF ; Internet standard newline
CTL            =  %x00-1F / %x7F ; controls
DIGIT          =  %x30-39 ; 0-9
DQUOTE         =  %x22 ; " (Double Quote)
HEXDIG         =  DIGIT / "A" / "B" / "C" / "D" / "E" / "F"
HTAB           =  %x09 ; horizontal tab
LF             =  %x0A ; linefeed
LWSP           =  *(WSP / CRLF WSP) ; linear white space (past newline)
OCTET          =  %x00-FF ; 8 bits of data
SP             =  %x20
VCHAR          =  %x21-7E ; visible (printing) characters
WSP            =  SP /

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ ABNF

Returns a new instance of ABNF.



5
6
7
8
9
 
# File 'lib/abnf/abnf.rb', line 5

def initialize
  @names = []
  @rules = {}
  @start = nil
end

Class Method Details

.parse(desc, dont_merge_core_rules = false) ⇒ Object 



456
457
458
459
460
461
 
# 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) ⇒ Object 



8
9
10
 
# 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) ⇒ Object 



12
13
14
 
# File 'lib/abnf/regexp.rb', line 12

def ABNF.regexp_tree(desc, name=nil)
  ABNF.parse(desc).regexp_tree(name)
end

Instance Method Details

#[](name) ⇒ Object 



31
32
33
 
# File 'lib/abnf/abnf.rb', line 31

def [](name)
  @rules[name]
end

#[]=(name, rhs) ⇒ Object 



35
36
37
38
 
# File 'lib/abnf/abnf.rb', line 35

def []=(name, rhs)
  @names << name unless @rules.include? name
  @rules[name] = rhs
end

#add(name, rhs) ⇒ Object 



40
41
42
43
44
45
46
47
 
# 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) ⇒ Object 



59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
# 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) ⇒ Object 



76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
 
# 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(&block) ⇒ Object 



53
54
55
56
57
 
# File 'lib/abnf/abnf.rb', line 53

def each(&block)
  @names.each {|name|
    yield name, @rules[name]
  }
end

#include?(name) ⇒ Boolean

Returns:

  • (Boolean) 


49
50
51
 
# File 'lib/abnf/abnf.rb', line 49

def include?(name)
  @rules.include? name
end

#merge(g) ⇒ Object 



25
26
27
28
29
 
# File 'lib/abnf/abnf.rb', line 25

def merge(g)
  g.each {|name, rhs|
    self.add(name, rhs)
  }
end

#names ⇒ Object 



21
22
23
 
# File 'lib/abnf/abnf.rb', line 21

def names
  @names.dup
end

#regexp(name = start_symbol) ⇒ Object 



16
17
18
 
# File 'lib/abnf/regexp.rb', line 16

def regexp(name=start_symbol)
  regexp_tree(name).regexp
end

#regexp_tree(name = nil) ⇒ Object

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.



24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
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
 
# 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 ⇒ Object

Raises:

  • (StandardError) 


15
16
17
18
19
 
# 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) ⇒ Object 



11
12
13
 
# File 'lib/abnf/abnf.rb', line 11

def start_symbol=(name)
  @start = name
end

#tsort_each_child(name) ⇒ Object 



130
131
132
133
 
# 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) ⇒ Object 



127
128
129
 
# File 'lib/abnf/abnf.rb', line 127

def tsort_each_node(&block)
  @names.each(&block)
end