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:



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

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

Instance Attribute Details

#constraints ⇒ Array<Array<Syntax::MatchClosest>> (readonly)

Returns:



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

def constraints
  @constraints
end

#sets ⇒ Array<ParseEntrySet> (readonly)

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

Returns:

  • (Array<ParseEntrySet>) —

    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:

  • index (Integer)

Returns:



34
35
36
 
# File 'lib/rley/parser/gfg_chart.rb', line 34

def [](index)
  sets[index]
end

#accepting_entry ⇒ ParseEntry

Retrieve the entry that corresponds to a complete and successful parse

Returns:



122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
 
# File 'lib/rley/parser/gfg_chart.rb', line 122

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:

  • (Integer) —

    The total number of edges.



159
160
161
162
163
 
# File 'lib/rley/parser/gfg_chart.rb', line 159

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:

  • (Integer) —

    The total number of entries.



151
152
153
154
155
156
 
# File 'lib/rley/parser/gfg_chart.rb', line 151

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:

  • (Integer) —

    The number of states.



146
147
148
 
# File 'lib/rley/parser/gfg_chart.rb', line 146

def count_states
  sets.size
end

#initial_entry ⇒ ParseEntry

Retrieve the first parse entry added to this chart

Returns:



116
117
118
 
# File 'lib/rley/parser/gfg_chart.rb', line 116

def initial_entry
  sets[0].first
end

#last_index ⇒ Integer

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

Returns:

  • (Integer) 


40
41
42
43
44
45
46
47
 
# File 'lib/rley/parser/gfg_chart.rb', line 40

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:

  • anIndex (Integer) —

    The rank of the token in the input stream.

Returns:

  • (ParseEntry) —

    the passed parse entry if it is pushed



64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
# File 'lib/rley/parser/gfg_chart.rb', line 64

def push_entry(aVertex, anOrigin, anIndex, reason)
  # puts "push_entry:"
  # puts "  aVertex #{aVertex.inspect}"
  # puts "  anOrigin: #{anOrigin}"
  # puts "  anIndex: #{anIndex}"
  # puts "  _reason: #{_reason}"
  if anIndex == sets.size
    if reason == :scan_rule
      add_entry_set
    else
      err_msg = "Internal error: unexpected push reason #{reason}"
      raise StandardError, err_msg
    end
  end

  reject = false
  unless constraints[anIndex].empty?
    constraints[anIndex].each do |ct|
      case ct
        when Syntax::MatchClosest
          not_found = sets[anIndex][0].prev_symbol != aVertex.prev_symbol
          next if not_found

          some_mismatch = ct.entries.find do |en|
            (en.vertex.dotted_item.production == aVertex.dotted_item.production) &&
              (en.origin != anOrigin)
          end
          reject = true if some_mismatch
      end
    end
  end

  return nil if reject

  new_entry = ParseEntry.new(aVertex, anOrigin)
  result = self[anIndex].push_entry(new_entry)

  if aVertex.kind_of?(GFG::ItemVertex) && aVertex.dotted_item.constraint
    ct = aVertex.dotted_item.constraint

    case ct
      when Syntax::MatchClosest
        update_match_closest(ct, anIndex)
    end
    constraints[anIndex] << ct
  end

  result
end

#search_entries(atIndex, criteria) ⇒ Object

Retrieve all entries that have a given terminal before the dot.

Parameters:

  • criteria (Hash{Symbol => String}) 


168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
 
# File 'lib/rley/parser/gfg_chart.rb', line 168

def search_entries(atIndex, criteria)
  entries = sets[atIndex].entries
  keyword = criteria.keys[0]
  found = []
  entries.each do |e|
    case keyword
      when :before # terminal before dot
        term_name = criteria[keyword]
        if e.dotted_entry? && e.vertex.dotted_item.position > -2
          found << e if e.prev_symbol&.name == term_name
        end
    end
  end

  found
end

#start_symbol ⇒ Syntax::NonTerminal

Returns the start symbol of the grammar.

Returns:



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

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

#to_s ⇒ Object

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



186
187
188
189
190
191
192
193
194
195
196
 
# File 'lib/rley/parser/gfg_chart.rb', line 186

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