Class: Dendroid::Parsing::ChartWalker

Inherits:
Object
  • Object
show all
Defined in:
lib/dendroid/parsing/chart_walker.rb

Overview

A chart walker visits a chart produced by the Earley recognizer. It visits the chart backwards: it begins with the chart entries representing a successful recognition then walks to the predecessor entries and so on.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(theChart) ⇒ ChartWalker

Returns a new instance of ChartWalker.

Parameters:



145
146
147
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 145

def initialize(theChart)
  @chart = theChart
end

Instance Attribute Details

#chart ⇒ Dendroid::Recognizer::Chart (readonly)

Returns The chart to visit.

Returns:



142
143
144
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 142

def chart
  @chart
end

Instance Method Details

#all_paths_advance(ctx, paths, pass) ⇒ Object

Iterate over each path, if allowed perform a step back

Parameters:



200
201
202
203
204
205
206
207
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 200

def all_paths_advance(ctx, paths, pass)
  paths.each do |prg|
    next if prg.state == :Complete || prg.state == :Delegating
    next if pass == :secondary && prg.state == :Waiting

    step_back(prg, ctx, paths)
  end
end

#completer_backwards(walk_progress, context, paths, predecessors) ⇒ Object 



318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 318

def completer_backwards(walk_progress, context, paths, predecessors)
  # Trying to remove some predecessors with some disambiguation technique
  forerunners = disambiguate_predecessors(walk_progress, predecessors)

  if forerunners.size == 1
    pred = forerunners[0]
    if context.known_entry? pred
      context.start_delegation(pred, walk_progress)
    elsif pred.predecessors.size == 1
      context.add_and_node(walk_progress, pred)
    else
      pre_forerunners = disambiguate_predecessors(walk_progress, pred.predecessors)
      index_empty = pre_forerunners.find_index { |entry| entry.dotted_item.empty? }
      if index_empty
        entry_empty = pre_forerunners.delete_at(index_empty)
        walk_progress.add_node_empty(entry_empty)
        walk_progress.curr_item = entry_empty.predecessors[0] # Assuming only one predecessor
      end
      if pre_forerunners.size == 1
        new_node = walk_progress.push_and_node(pre_forerunners[0])
        context.advance(walk_progress, pred, new_node)
      else
        new_node = walk_progress.push_or_node(pred.origin, pre_forerunners.size)
        context.advance(walk_progress, pred, new_node)
        fork(walk_progress, paths, pre_forerunners)
      end
    end
  else
    # AMBIGUITY: multiple valid predecessors
    walk_progress.push_or_node(forerunners)
    fork(walk_progress, paths, forerunners)
  end
end

#disambiguate_predecessors(_progress, predecessors) ⇒ Array<Dendroid::Recognizer::EItem>

Check whether given chart entry has multiple predecessorss. If yes, then apply disambiguation to reduce the number of valid predecessors If there are still multiple predecessors, then sort them.

Parameters:

Returns:



277
278
279
280
281
282
283
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 277

def disambiguate_predecessors(_progress, predecessors)
  if predecessors.size > 1
    sort_predecessors(predecessors)
  else
    predecessors
  end
end

#fork(walk_progress, paths, sorted_predecessors) ⇒ Object 



381
382
383
384
385
386
387
388
389
390
391
392
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 381

def fork(walk_progress, paths, sorted_predecessors)
  progs = [walk_progress]
  walk_progress.fork(sorted_predecessors[0])
  sorted_predecessors[1..].each do |prd|
    alternate = walk_progress.dup
    alternate.fork(prd)
    paths << alternate
    progs << alternate
  end

  progs.each { |pg| pg.push_and_node(pg.curr_item) }
end

#predecessors_for_state(context, walk_progress) ⇒ Object

Determine predecessors of current item according the walk progess state. If needed, update also the state.

Parameters:



250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 250

def predecessors_for_state(context, walk_progress)
  case walk_progress.state
  when :Waiting, :New
    predecessors = predecessors_of(walk_progress.curr_item, walk_progress.parents)
    last_parent = walk_progress.parents.last
    context.stop_delegation(last_parent, walk_progress, :Waiting)
    walk_progress.state = :Running

  when :Running
    predecessors = predecessors_of(walk_progress.curr_item, walk_progress.parents)

  when :Forking
    predecessors = [walk_progress.predecessor]
    walk_progress.predecessor = nil
    walk_progress.state = :Running
  end

  walk_progress.state = :Complete if predecessors.empty?
  predecessors
end

#predecessors_of(anEItem, parents) ⇒ Object 



289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 289

def predecessors_of(anEItem, parents)
  # Rule: if anEItem has itself as predecessor AND parents contains
  # only a start item, then remove anEItem from its own predecessor(s).
  if (parents.size == 1) && anEItem.predecessors.include?(anEItem)
    # raise StandardError unless parents[0].match(anEItem)
    unless parents[0].match(anEItem)
      raise StandardError

    end

    preds = anEItem.predecessors.dup
    preds.delete(anEItem)
    preds
  else
    anEItem.predecessors
  end
end

#predictor_backwards(walk_progress, context, predecessors) ⇒ Object 



352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 352

def predictor_backwards(walk_progress, context, predecessors)
  index_empty = predecessors.find_index { |entry| entry.dotted_item.empty? }
  if index_empty
    entry_empty = predecessors.delete_at(index_empty)
    walk_progress.add_node_empty(entry_empty)
    raise StandardError unless predecessors.empty? # Uncovered case

    walk_progress.curr_item = entry_empty
    return
  end
  if predecessors.size == 1
    walk_progress.curr_item = predecessors[0]
  else
    # curr_item has multiple predecessors from distinct rules
    # look in lineage the latest entry that matches one of the ancestors AND
    # has a free slot for the current symbol
    matches = walk_progress.match_parent?(predecessors, true)
    if matches.empty?
      walk_progress.state = :Complete
    else
      (matching_pred, stack_offset) = matches.first
      walk_progress.curr_item = matching_pred
      unless stack_offset.zero?
        context.pop_multiple_parents(walk_progress, stack_offset)
      end
    end
  end
end

#scanner_backwards(walk_progress, context, predecessors, curr_token) ⇒ Object 



307
308
309
310
311
312
313
314
315
316
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 307

def scanner_backwards(walk_progress, context, predecessors, curr_token)
  context.add_terminal_node(walk_progress, curr_token)
  if predecessors.size == 1
    walk_progress.curr_item = predecessors[0]
    walk_progress.state = :Waiting
  else
    # TODO: challenge assumption single predecessor
    raise StandardError
  end
end

#sort_predecessors(predecessors) ⇒ Object 



285
286
287
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 285

def sort_predecessors(predecessors)
  predecessors
end

#step_back(walk_progress, context, paths) ⇒ Object

For the given walk_progress, perform the visit of predecessors of the chart entry designated as the current one.

Parameters:



213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 213

def step_back(walk_progress, context, paths)
  loop do
    predecessors = predecessors_for_state(context, walk_progress)
    break if walk_progress.state == :Complete

    case walk_progress.curr_item.algo
    when :completer
      completer_backwards(walk_progress, context, paths, predecessors)
      break if walk_progress.state == :Delegating

    when :scanner
      curr_token = chart.tokens[walk_progress.curr_rank - 1]
      scanner_backwards(walk_progress, context, predecessors, curr_token)
      break

    when :predictor
      unless walk_progress.parents.last.partial?
        last_parent = walk_progress.parents.pop
        context.stop_delegation(last_parent, walk_progress, :Running)
        if last_parent.is_a?(OrNode)
          break if context.join_or_node(walk_progress, last_parent)
        end
      end
      predictor_backwards(walk_progress, context, predecessors)
      break if walk_progress.state == :Complete
    else
      raise StandardError
    end
  end

  walk_progress
end

#visit_start_item(progress, paths, start_item) ⇒ Object

Start the visit of with the success (accept) chart entry. Build the root node(s) of parse tree/forest

Parameters:



179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 179

def visit_start_item(progress, paths, start_item)
  preds = disambiguate_predecessors(progress, start_item.predecessors)
  if preds.size == 1
    progress.push_and_node(start_item)
  else
    # Multiple predecessors...
    if start_item.rule.rhs.size == 1
      progress.push_and_node(start_item)
      progress.push_or_node(start_item.origin, preds.size)
    else
      progress.parents << OrNode.new(start_item.lhs, start_item.origin, progress.curr_rank, preds.size)
    end
    progress.curr_item = start_item
    fork(progress, paths, preds)
  end
end

#walk(start_item) ⇒ Object

Parameters:



150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
 
# File 'lib/dendroid/parsing/chart_walker.rb', line 150

def walk(start_item)
  curr_rank = chart.size - 1
  progress = WalkProgress.new(curr_rank, start_item, [])
  paths = [progress]
  visit_start_item(progress, paths, start_item)
  ctx = WalkContext.new

  loop do # Iterate over rank values
    pass = :primary
    loop do # Iterate over paths until all are ready for previous rank
      all_paths_advance(ctx, paths, pass)
      # TODO: handle path removal
      break if paths.none? { |pg| pg.state == :Running || pg.state == :Forking }

      pass = :secondary
    end
    break if paths.all? { |prg| prg.state == :Complete }

    ctx.entry2node.clear
  end

  progress.parents[0]
end