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.



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

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.



9
10
11
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 9

def ast
  @ast
end

#endpoints ⇒ Object (readonly)

Returns the value of attribute endpoints.



9
10
11
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 9

def endpoints
  @endpoints
end

#root ⇒ Object (readonly)

Returns the value of attribute root.



9
10
11
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 9

def root
  @root
end

Instance Method Details

#firstpos(node) ⇒ Object 



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

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 



124
125
126
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 124

def followpos(node)
  followpos_table[node]
end

#lastpos(node) ⇒ Object 



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

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) 


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

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 



17
18
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
 
# File 'lib/action_dispatch/journey/gtg/builder.rb', line 17

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