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.

[View source]

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

[View source]

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

[View source]

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

def followpos(node)
  followpos_table[node]
end

#lastpos(node) ⇒ Object

[View source]

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)
[View source]

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

[View source]

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