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(tokenCount, aGFGraph) ⇒ GFGChart

Returns a new instance of GFGChart.

Parameters:

  • tokenCount (Integer) —

    The number of lexemes in the input to parse.

  • aGFGraph (GFG::GrmFlowGraph) —

    The GFG for the grammar in use.



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

def initialize(tokenCount, aGFGraph)
  @sets = Array.new(tokenCount + 1) { |_| ParseEntrySet.new }
  push_entry(aGFGraph.start_vertex, 0, 0, :start_rule)
end

Instance Attribute Details

#sets ⇒ Array<ParseEntrySet> (readonly)

Returns entry sets (one per input token + 1).

Returns:

  • (Array<ParseEntrySet>) —

    entry sets (one per input token + 1)



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

def sets
  @sets
end

Instance Method Details

#[](index) ⇒ ParseEntrySet

Returns Access the entry set at given position.

Parameters:

  • index (Integer)

Returns:



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

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

#accepting_entry ⇒ ParseEntry

Retrieve the entry that corresponds to a complete and successful parse

Returns:



69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
# File 'lib/rley/parser/gfg_chart.rb', line 69

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

Returns:



63
64
65
 
# File 'lib/rley/parser/gfg_chart.rb', line 63

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

#last_index ⇒ Integer

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

Returns:

  • (Integer) 


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

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

Parameters:

  • anIndex (Integer) —

    The rank of the token in the input stream.

Returns:

  • (ParseEntry) —

    the passed parse entry if it is pushed



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

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)
  pushed = self[anIndex].push_entry(new_entry)

  return pushed
end

#start_symbol ⇒ Syntax::NonTerminal

Returns the start symbol of the grammar.

Returns:



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

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