class Journey::GTG::Builder
Attributes
ast[R]
endpoints[R]
root[R]
Public Class Methods
new(root)
click to toggle source
# File lib/journey/gtg/builder.rb, line 10 def initialize root @root = root @ast = Nodes::Cat.new root, DUMMY @followpos = nil end
Public Instance Methods
firstpos(node)
click to toggle source
# File lib/journey/gtg/builder.rb, line 81 def firstpos node case node when Nodes::Star firstpos(node.left) when Nodes::Cat if nullable? node.left firstpos(node.left) | firstpos(node.right) else firstpos(node.left) end when Nodes::Or node.children.map { |c| firstpos(c) }.flatten.uniq when Nodes::Unary firstpos(node.left) when Nodes::Terminal nullable?(node) ? [] : [node] else raise ArgumentError, 'unknown firstpos: %s' % node.class.name end end
followpos(node)
click to toggle source
# File lib/journey/gtg/builder.rb, line 123 def followpos node followpos_table[node] end
lastpos(node)
click to toggle source
# File lib/journey/gtg/builder.rb, line 102 def lastpos node case node when Nodes::Star firstpos(node.left) when Nodes::Or node.children.map { |c| lastpos(c) }.flatten.uniq when Nodes::Cat if nullable? node.right lastpos(node.left) | lastpos(node.right) else lastpos(node.right) end when Nodes::Terminal nullable?(node) ? [] : [node] when Nodes::Unary lastpos(node.left) else raise ArgumentError, 'unknown lastpos: %s' % node.class.name end end
nullable?(node)
click to toggle source
# File lib/journey/gtg/builder.rb, line 62 def nullable? node case node when Nodes::Group true when Nodes::Star true when Nodes::Or node.children.any? { |c| nullable?(c) } when Nodes::Cat nullable?(node.left) && nullable?(node.right) when Nodes::Terminal !node.left when Nodes::Unary nullable? node.left else raise ArgumentError, 'unknown nullable: %s' % node.class.name end end
transition_table()
click to toggle source
# File lib/journey/gtg/builder.rb, line 16 def transition_table dtrans = TransitionTable.new marked = {} state_id = Hash.new { |h,k| h[k] = h.length } start = firstpos(root) dstates = [start] until dstates.empty? s = dstates.shift next if marked[s] marked[s] = true # mark s s.group_by { |state| symbol(state) }.each do |sym, ps| u = ps.map { |l| followpos(l) }.flatten next if u.empty? if u.uniq == [DUMMY] from = state_id[s] to = state_id[Object.new] dtrans[from, to] = sym dtrans.add_accepting to ps.each { |state| dtrans.add_memo to, state.memo } else dtrans[state_id[s], state_id[u]] = sym if u.include? DUMMY to = state_id[u] accepting = ps.find_all { |l| followpos(l).include? DUMMY } accepting.each { |accepting_state| dtrans.add_memo to, accepting_state.memo } dtrans.add_accepting state_id[u] end end dstates << u end end dtrans end
Private Instance Methods
build_followpos()
click to toggle source
# File lib/journey/gtg/builder.rb, line 132 def build_followpos table = Hash.new { |h,k| h[k] = [] } @ast.each do |n| case n when Nodes::Cat lastpos(n.left).each do |i| table[i] += firstpos(n.right) end when Nodes::Star lastpos(n).each do |i| table[i] += firstpos(n) end end end table end
followpos_table()
click to toggle source
# File lib/journey/gtg/builder.rb, line 128 def followpos_table @followpos ||= build_followpos end
symbol(edge)
click to toggle source
# File lib/journey/gtg/builder.rb, line 149 def symbol edge case edge when Journey::Nodes::Symbol edge.regexp else edge.left end end