Class: Rley::Parser::GFGChart

Inherits:
Object
  • Object
show all
Defined in:
lib/rley/parser/gfg_chart.rb

Overview

Also called a parse table. It is a Grammar Flow Graph implementation. Assuming that n == number of input tokens, the chart is an array with n + 1 entry sets.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(aGFGraph) ⇒ GFGChart 



16
17
18
19
 
# File 'lib/rley/parser/gfg_chart.rb', line 16

def initialize( aGFGraph)
  @sets = [ ParseEntrySet.new ]
  push_entry(aGFGraph.start_vertex, 0, 0, :start_rule)
end

Instance Attribute Details

#sets ⇒ Array<ParseEntrySet> (readonly) 



13
14
15
 
# File 'lib/rley/parser/gfg_chart.rb', line 13

def sets
  @sets
end

Instance Method Details

#[](index) ⇒ ParseEntrySet 



28
29
30
 
# File 'lib/rley/parser/gfg_chart.rb', line 28

def [](index)
  return sets[index]
end

#accepting_entry ⇒ ParseEntry

Retrieve the entry that corresponds to a complete and successful parse



73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
 
# File 'lib/rley/parser/gfg_chart.rb', line 73

def accepting_entry()
  # Success can be detected as follows:
  # The last chart entry set has at least one complete parse entry
  # for the start symbol with an origin == 0

  # Retrieve all the end entries (i.e. of the form
  last_entries = sets[last_index].entries.select(&:end_entry?)
  # last_entries.each_with_index do |entry, index|
  #  if entry.nil?
  #    puts "Nil entry at index #{index}"
  #  else
  #    puts entry
  #  end
  # end

  # ... now find the end vertex for start symbol and with origin at zero.
  success_entries = last_entries.select do |entry|
    entry.origin.zero? && entry.vertex.non_terminal == start_symbol
  end

  return success_entries.first
end

#initial_entry ⇒ ParseEntry

Retrieve the first parse entry added to this chart



67
68
69
 
# File 'lib/rley/parser/gfg_chart.rb', line 67

def initial_entry()
  return sets[0].first
end

#last_index ⇒ Integer

Return the index value of the last non-empty entry set.



34
35
36
37
38
39
40
41
42
43
 
# File 'lib/rley/parser/gfg_chart.rb', line 34

def last_index()
  first_empty = sets.find_index(&:empty?)
  index = if first_empty.nil?
            sets.size - 1
          else
            first_empty.zero? ? 0 : first_empty - 1
          end

  return index
end

#push_entry(aVertex, anOrigin, anIndex, _reason) ⇒ ParseEntry

Push a parse entry for the chart entry with given index



48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
# File 'lib/rley/parser/gfg_chart.rb', line 48

def push_entry(aVertex, anOrigin, anIndex, _reason)
  # puts "push_entry:"
  # puts "  aVertex #{aVertex.inspect}"
  # puts "  anOrigin: #{anOrigin}"
  # puts "  anIndex: #{anIndex}"
  # puts "  _reason: #{_reason}"
  new_entry = ParseEntry.new(aVertex, anOrigin)
  if anIndex == sets.size
    err_msg = "Internal error: unexpected push reason #{_reason}"
    raise StandardError, err_msg if _reason != :scan_rule
    add_entry_set 
  end
  pushed = self[anIndex].push_entry(new_entry)

  return pushed
end

#start_symbol ⇒ Syntax::NonTerminal 



22
23
24
 
# File 'lib/rley/parser/gfg_chart.rb', line 22

def start_symbol()
  return sets.first.entries[0].vertex.non_terminal
end