/
parse_stack.cr
177 lines (143 loc) · 5.08 KB
/
parse_stack.cr
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
module CLTK
def self.is_terminal?(sym)
sym && (s = sym.to_s) == s.upcase
end
def self.is_nonterminal?(sym)
sym && sym.to_s == sym.to_s.downcase
end
class Parser
# The ParseStack class is used by a Parser to keep track of state
# during parsing.
class ParseStack
# Resolve the Productions Callbacks into
# the AST Tree
class OutputStackVisitor
alias ProcsType = Hash(Int32, Tuple(CLTK::Parser::ProdProc, Int32)) |
Array(Tuple(CLTK::Parser::ProdProc, Int32))
def initialize(@env : Environment, @procs : ProcsType) ; end
def resolve(tree : Tuple(Int32, Array(CLTK::Parser::StackType), Array(CLTK::StreamPosition)))
cb, args, positions = tree
resolved_args = args.map { |arg| resolve(arg).as(CLTK::Type) }
@env.set_positions positions
@procs[cb].first.call(
resolved_args, @env
)
end
def resolve(value : Array)
value.map { |v|
resolve(v).as(CLTK::Type)
}
end
def resolve(value : CLTK::Type)
value.as(CLTK::Type)
end
end
# @return [Integer] ID of this parse stack.
getter :id
# @return [Array<Object>] Array of objects produced by {Reduce} actions.
getter :output_stack
# @return [Array<Integer>] Array of states used when performing {Reduce} actions.
getter :state_stack
@cbuffer = [] of Int32
@output_stack = [] of CLTK::Parser::StackType
# Instantiate a new ParserStack object.
def initialize(@id : Int32, @output_stack = [] of CLTK::Parser::StackType, @state_stack = [0] of Int32, @node_stack = [] of Int32, @connections = [] of {Int32, Int32}, @labels = [] of String, @positions = [] of StreamPosition)
end
def resolve(env, procs)
OutputStackVisitor.new(env, procs).resolve(@output_stack.last)
end
# Branch this stack, effectively creating a new copy of its
# internal state.
#
# @param [Integer] new_id ID for the new ParseStack.
#
# @return [ParseStack]
def branch(new_id)
ParseStack.new(new_id, @output_stack.dup, @state_stack.dup,
@node_stack.dup, @connections.dup, @labels.dup, @positions.dup)
end
# @return [StreamPosition] Position data for the last symbol on the stack.
def position
if @positions.empty?
StreamPosition.new
else
@positions.last.dup
end
end
# Push new state and other information onto the stack.
#
# @param [Integer] state ID of the shifted state.
# @param [Object] o Value of Token that caused the shift.
# @param [Symbol] node0 Label for node in parse tree.
# @param [StreamPosition] position Position token that got shifted.
#
# @return [void]
def push(state, o, node0, position)
@state_stack << state
if o.is_a? Array
@output_stack = @output_stack + [o.map{ |e| e.as(CLTK::Parser::StackType) }.as(CLTK::Parser::StackType)]
elsif o.is_a? CLTK::Parser::StackType
@output_stack << o
else
@output_stack << o#.as(CLTK::Parser::StackType)
end
@node_stack << @labels.size
@labels << if CLTK.is_terminal?(node0) && o
node0.to_s + "(#{o})"
else
node0.to_s
end.as(String)
@positions << position.not_nil!
if CLTK.is_nonterminal?(node0)
@cbuffer.each do |node1|
@connections << {@labels.size - 1, node1}
end
end
end
# Pop some number of objects off of the inside stacks.
#
# @param [Integer] n Number of object to pop off the stack.
#
# @return [Array(Object, StreamPosition)] Values popped from the output and positions stacks.
def pop(n = 1)
@state_stack.pop(n)
# Pop the node stack so that the proper edges can be added
# when the production's left-hand side non-terminal is
# pushed onto the stack.
@cbuffer = @node_stack.pop(n)
{@output_stack.pop(n), @positions.pop(n)}
end
# Fetch the result stored in this ParseStack. If there is more
# than one object left on the output stack there is an error.
#
# @return [Object] The end result of this parse stack.
def result
if @output_stack.size == 1
return @output_stack.last
else
raise Parser::Exceptions::InternalParserException.new "The parsing stack should have 1 element on the output stack, not #{@output_stack.size}."
end
end
# @return [Integer] Current state of this ParseStack.
def state
@state_stack.last
end
# @return [String] Representation of the parse tree in the DOT langauge.
def tree
tree = "digraph tree#{@id} {\n"
@labels.each_with_index do |label, i|
tree += "\tnode#{i} [label=\"#{label}\""
if CLTK.is_terminal?(label)
tree += " shape=box"
end
tree += "];\n"
end
tree += "\n"
@connections.each do |from, to|
tree += "\tnode#{from} -> node#{to};\n"
end
tree += "}"
end
end
end
end