Class: ParseTable

Inherits:
Object show all
Includes:
SourceCodeDumpable
Defined in:
lib/rpdf2txt-rockit/parse_table.rb

Constant Summary collapse

@@default_action_map =

We save the actions in a compact numerical way to save space and time:

The action table is an array of arrays. Each state number is an index
into the array and its array contains an even number of integers.
Each pair of integers represent one unique action. The first of the 
integers is the action and the second is the number representing the
terminals for which it apply. The least significant 'action_bits' bits
of the action number determines the type of action by giving an index
into the 'action_map'. Its default value is:
  [:REDUCE, :SHIFT, :ACCEPT]
so that

[:REDUCE, :SHIFT, :ACCEPT]

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods included from SourceCodeDumpable

as_code, as_method_named, as_module_method_named, #create_new, indent_lines, name_hash, #new_of_my_type, #parameter_named, #to_compact_src, #to_src_in_module, #type_to_src

Constructor Details

#initialize(productions, tokens, priorities = nil, actionTable = ArrayOfArrays.new, gotoHash = Hash.new, actionBits = 2, actionMap = @@default_action_map) ⇒ ParseTable

Returns a new instance of ParseTable.



30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 30

def initialize(productions, tokens, priorities = nil,
 actionTable = ArrayOfArrays.new, gotoHash = Hash.new,
 actionBits = 2, actionMap = @@default_action_map)
  @productions, @start_state, @language = productions, 0, "UNNAMED_LANGUAGE"
  @priorities = priorities
  @tokens, @nonterminals = tokens, nonterminals(productions)
  @action_table, @goto_hash = actionTable, gotoHash
  @action_cache = ArrayOfHashes.new
  @mask = Array.new
  @action_map, @action_bits, @action_mask = actionMap, actionBits, 0
  while actionBits > 0
    @action_mask = (@action_mask << 1) | 1
    actionBits -= 1
  end
  init_productionnum_to_nonterminal_number_hash
  init_tokentype_to_token_number_hash
end

Instance Attribute Details

#language ⇒ Object

Returns the value of attribute language.



10
11
12
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 10

def language
  @language
end

#priorities ⇒ Object (readonly)

Returns the value of attribute priorities.



9
10
11
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 9

def priorities
  @priorities
end

#start_state ⇒ Object (readonly)

Returns the value of attribute start_state.



9
10
11
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 9

def start_state
  @start_state
end

#tokens ⇒ Object (readonly)

Returns the value of attribute tokens.



9
10
11
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 9

def tokens
  @tokens
end

Class Method Details

.new_from_grammar(aGrammar) ⇒ Object 



12
13
14
15
16
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 12

def ParseTable.new_from_grammar(aGrammar)
  pt = self.new(aGrammar.productions, aGrammar.tokens, aGrammar.priorities)
  pt.language = aGrammar.name || "UNNAMED_LANGUAGE"
  pt
end

Instance Method Details

#==(other) ⇒ Object 



52
53
54
55
56
57
58
59
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 52

def ==(other)
  other.class == self.class and
    other.productions == @productions and
    other.tokens == @tokens and
    other.action_table == @action_table and
    other.goto_hash == @goto_hash and
    other.start_state == @start_state
end

#action_to_actionnum(action) ⇒ Object 



150
151
152
153
154
155
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 150

def action_to_actionnum(action)
  Profiler.__enter__(:ParseTable_action_to_actionnum, action) if $PROFILE
  res = @action_map.index(action[0]) + (action[1] << @action_bits)
  Profiler.__leave__(:ParseTable_action_to_actionnum) if $PROFILE
  res
end

#actionnum_to_action(actionNumber) ⇒ Object 



146
147
148
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 146

def actionnum_to_action(actionNumber)
  [@action_map[actionNumber & @action_mask], actionNumber >> @action_bits]
end

#actions(state, tokenType) ⇒ Object 



114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 114

def actions(state, tokenType)
  actions = @action_cache[state][tokenType]
  unless actions
    actions = Array.new
    actionnums = @action_table[state]
    token_mask = mask(@token_to_number[tokenType])
    i = 0
    while i < actionnums.length
	if(actionnums[i+1] & token_mask > 0)
 actions.push actionnum_to_action(actionnums[i])
	end
	i += 2
    end
    @action_cache[state][tokenType] = actions
  end
  actions
end

#add_action(state, aTokenType, action) ⇒ Object 



61
62
63
64
65
66
67
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 61

def add_action(state, aTokenType, action)
  Profiler.__enter__(:ParseTable_add_action, state, aTokenType, action) if $PROFILE
  @action_cache[state].clear
  actionnum = action_to_actionnum(action)
  @action_table[state] << actionnum << token_to_terminalset(aTokenType)
  Profiler.__leave__(:ParseTable_add_action) if $PROFILE
end

#add_action_for_terminalset(state, action, terminalSet) ⇒ Object 



69
70
71
72
73
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 69

def add_action_for_terminalset(state, action, terminalSet)
  Profiler.__enter__(:ParseTable_add_action_for_terminalset, state, action, terminalSet) if $PROFILE
  @action_table[state] << action_to_actionnum(action) << terminalSet.to_i
  Profiler.__leave__(:ParseTable_add_action_for_terminalset) if $PROFILE
end

#add_goto(state, aNonTerminal, newState) ⇒ Object 



105
106
107
108
109
110
111
112
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 105

def add_goto(state, aNonTerminal, newState)
  begin
    @goto_hash[state][@nonterminals.index(aNonTerminal)] = newState
  rescue NameError
    @goto_hash[state] = Hash.new
    retry
  end
end

#compact! ⇒ Object

Unify terminal sets for identical actions



76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 76

def compact!
  Profiler.__enter__(:ParseTable_compact!) if $PROFILE
  actions, i, new_index = Hash.new, 0, 0
  @action_table.map! do |actionnums|
    actions.clear; 
    i, new_actionnums, new_index = 0, Array.new, 0
    while i < actionnums.length
	if (index = actions[actionnums[i]])
 new_actionnums[index+1] |= actionnums[i+1]
	else
 actions[actionnums[i]] = new_index
 new_index += 2
 new_actionnums << actionnums[i] << actionnums[i+1]
	end
	i += 2
    end
    new_actionnums
  end
  Profiler.__leave__(:ParseTable_compact!) if $PROFILE
end

#each_terminalset(state) ⇒ Object 



138
139
140
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 138

def each_terminalset(state)
  @action_table[state].each_with_index {|e,i| yield(e) if i % 2 == 1}
end

#goto(state, productionNumber) ⇒ Object 



157
158
159
160
161
162
163
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 157

def goto(state, productionNumber)
  begin
    @goto_hash[state][@productionnum_to_nonterminal_num[productionNumber]]
  rescue Exception
    nil
  end
end

#inspect ⇒ Object 



190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 190

def inspect
  str = "ParseTable\n"
  str += "Tokens: #{@tokens.inspect}\n"
  str += "NonTerminals: #{@nonterminals.inspect}\n"
  str += "Productions:\n#{productions_inspect}\n"
  str += "Actions: \n"
  max_state = @action_table.length-1
  (max_state+1).times do |state|
    str += "#{state}:\t"
    @tokens.each do |t|
	str += inspect_actions(actions(state, t)) + ","
    end
    str += "| "
    @nonterminals.each do |nt|
	i = @productions.index(@productions.detect {|p| p.nonterminal == nt})
	str += ((ns=goto(state, i)) ? "#{ns}" : " ") + ","
    end
    str += "\n"
  end
  str
end

#mask(index) ⇒ Object 



101
102
103
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 101

def mask(index)
  @mask[index] || (@mask[index] = (1 << index))
end

#num_states ⇒ Object 



48
49
50
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 48

def num_states
  @action_table.length
end

#production(number) ⇒ Object 



165
166
167
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 165

def production(number)
  @productions[number]
end

#terminalset_to_terminals(terminalSet) ⇒ Object 



142
143
144
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 142

def terminalset_to_terminals(terminalSet)
  @tokens.select {|t| terminalSet & mask(@token_to_number[t]) > 0}
end

#to_src(name = "parse_table", nameHash = {}) ⇒ Object 



169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 169

def to_src(name = "parse_table", nameHash = {})
  names = name_hash(@tokens) {|t| "t"}
  str = @tokens.to_src("tokens", names) + "\n"
  names.update(name_hash(@productions) {|p| "p"})
  str << @productions.to_src("productions", names) + "\n"
  str << @priorities.to_src("priorities", names) + "\n"
  #str << "r = :REDUCE\n"
  #str << "s = :SHIFT\n"
  str << @action_table.to_compact_src("action_table") + "\n"
  str << @goto_hash.to_compact_src("goto_hash") + "\n"
  str << assign_to(name, 
     new_of_my_type(as_code("productions"), 
		    as_code("tokens"),
		    as_code("priorities"),
		    as_code("action_table"), 
		    as_code("goto_hash"),
		    @action_bits,
		    @action_map))
  str
end

#token_to_terminalset(aTokenType) ⇒ Object 



97
98
99
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 97

def token_to_terminalset(aTokenType)
  mask(@token_to_number[aTokenType])
end

#valid_tokens(state) ⇒ Object 



132
133
134
135
136
 
# File 'lib/rpdf2txt-rockit/parse_table.rb', line 132

def valid_tokens(state)
  terminal_set = 0
  each_terminalset(state) {|ts| terminal_set |= ts}
  terminalset_to_terminals(terminal_set)
end