Class: Journey::GTG::Builder

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

Constant Summary collapse

DUMMY =

:nodoc:

Nodes::Literal.new Object.new

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(root) ⇒ Builder

Returns a new instance of Builder.



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

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.



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

def ast
  @ast
end

#endpoints ⇒ Object (readonly)

Returns the value of attribute endpoints.



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

def endpoints
  @endpoints
end

#root ⇒ Object (readonly)

Returns the value of attribute root.



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

def root
  @root
end

Instance Method Details

#firstpos(node) ⇒ Object 



81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
# 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) ⇒ Object 



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

def followpos node
  followpos_table[node]
end

#lastpos(node) ⇒ Object 



102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
 
# 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) ⇒ Boolean

Returns:

  • (Boolean) 


62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
# 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 ⇒ Object 



16
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
 
# 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