Class: ActionDispatch::Journey::GTG::Builder

Inherits:
Object
  • Object
show all
Defined in:
lib/action_dispatch/journey/gtg/builder.rb

Overview

:nodoc:

Constant Summary collapse

DUMMY = 
Nodes::Dummy.new

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(root) ⇒ Builder

Returns a new instance of Builder.



13
14
15
16
17
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 13

def initialize(root)
  @root      = root
  @ast       = Nodes::Cat.new root, DUMMY
  @followpos = nil
end

Instance Attribute Details

#ast ⇒ Object (readonly)

Returns the value of attribute ast.



11
12
13
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 11

def ast
  @ast
end

#endpoints ⇒ Object (readonly)

Returns the value of attribute endpoints.



11
12
13
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 11

def endpoints
  @endpoints
end

#root ⇒ Object (readonly)

Returns the value of attribute root.



11
12
13
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 11

def root
  @root
end

Instance Method Details

#firstpos(node) ⇒ Object 



84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 84

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.flat_map { |c| firstpos(c) }.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) ⇒ Object 



126
127
128
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 126

def followpos(node)
  followpos_table[node]
end

#lastpos(node) ⇒ Object 



105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 105

def lastpos(node)
  case node
  when Nodes::Star
    firstpos(node.left)
  when Nodes::Or
    node.children.flat_map { |c| lastpos(c) }.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) ⇒ Boolean

Returns:

  • (Boolean) 


65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 65

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 ⇒ Object 



19
20
21
22
23
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
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 19

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.flat_map { |l| followpos(l) }
      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