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

Returns a new instance of GFGChart.

Parameters:

  • The GFG for the grammar in use.



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

def initialize(aGFGraph)
  @sets = [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:

  • entry sets (one per input token + 1)



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

def sets
  @sets
end

Instance Method Details

#[](index) ⇒ ParseEntrySet

Returns Access the entry set at given position.

Parameters:

Returns:

  • Access the entry set at given position.



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

def [](index)
  sets[index]
end

#accepting_entry ⇒ ParseEntry

Retrieve the entry that corresponds to a complete and successful parse

Returns:



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

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

  success_entries.first
end

#count_edges ⇒ Integer

Returns The total number of edges.

Returns:

  • The total number of edges.



109
110
111
112
113
 
# File 'lib/rley/parser/gfg_chart.rb', line 109

def count_edges
  sets.reduce(0) do |sub_result, a_set|
    sub_result += a_set.count_edges
  end
end

#count_entries ⇒ Integer

Returns The total number of entries.

Returns:

  • The total number of entries.



101
102
103
104
105
106
 
# File 'lib/rley/parser/gfg_chart.rb', line 101

def count_entries
  # rubocop: disable Lint/UselessAssignment
  sets.reduce(0) do |sub_result, a_set|
    sub_result += a_set.size
  end
end

#count_states ⇒ Integer

Returns The number of states.

Returns:

  • The number of states.



96
97
98
 
# File 'lib/rley/parser/gfg_chart.rb', line 96

def count_states
  sets.size
end

#initial_entry ⇒ ParseEntry

Retrieve the first parse entry added to this chart

Returns:



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

def initial_entry
  sets[0].first
end

#last_index ⇒ Integer

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

Returns:



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

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

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

Push a parse entry for the chart entry with given index

Parameters:

  • The rank of the token in the input stream.

Returns:

  • the passed parse entry if it is pushed



48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# 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
  self[anIndex].push_entry(new_entry)
end

#start_symbol ⇒ Syntax::NonTerminal

Returns the start symbol of the grammar.

Returns:

  • the start symbol of the grammar.



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

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

#to_s ⇒ Object

@ return [String] A human-readable representation of the chart.



117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/rley/parser/gfg_chart.rb', line 117

def to_s
  result = +''
  sets.each_with_index do |a_set, i|
    result << "State[#{i}]\n"
    a_set.entries.each do |item|
      result << "  #{item}\n"
    end
  end

  result
end