Class: Rley::Parser::GFGParsing

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(theGFG) ⇒ GFGParsing

Constructor

Parameters:



38
39
40
41
42
43
44
45
 
# File 'lib/rley/parser/gfg_parsing.rb', line 38

def initialize(theGFG)
  super()
  @gf_graph = theGFG
  @tokens = []
  @chart = GFGChart.new(gf_graph)
  @antecedence = Hash.new { |hash, key| hash[key] = [] }
  antecedence[chart[0].first]
end

Instance Attribute Details

#antecedence ⇒ Hash{ParseEntry => Array<ParseEntry>} (readonly)

A Hash with pairs of the form: parse entry => [ antecedent parse entries ] It associates to a every parse entry its antecedent(s), that is, the parse entry/ies that causes the key parse entry to be created with one the gfg rules

Returns:



31
32
33
 
# File 'lib/rley/parser/gfg_parsing.rb', line 31

def antecedence
  @antecedence
end

#chart ⇒ Parser::GFGChart (readonly)

The link to the chart object

Returns:



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

def chart
  @chart
end

#failure_reason ⇒ ErrorReason (readonly)

Returns The reason of a parse failure.

Returns:



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

def failure_reason
  @failure_reason
end

#gf_graph ⇒ GFG::GrmFlowGraph (readonly)

The link to the grammar flow graph

Returns:



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

def gf_graph
  @gf_graph
end

#tokens ⇒ Array<Lexical::Token> (readonly)

The sequence of input token to parse

Returns:



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

def tokens
  @tokens
end

Instance Method Details

#accepting_entry ⇒ Object

Retrieve the accepting parse entry that represents a complete, successful parse After a successful parse, the last chart entry set has an end parse entry that involves the start symbol



211
212
213
 
# File 'lib/rley/parser/gfg_parsing.rb', line 211

def accepting_entry
  return chart.accepting_entry
end

#ambiguous? ⇒ Boolean

Return true if there are more than one complete state for the same lhs and same origin in any state set.

Returns:

  • (Boolean) 


195
196
197
198
 
# File 'lib/rley/parser/gfg_parsing.rb', line 195

def ambiguous?
  found = chart.sets.find { |set| !set.ambiguities.empty? }
  !found.nil?
end

#call_rule(anEntry, aPosition) ⇒ Object

Let the current sigma set be the ith parse entry set. This method is invoked when an entry is added to the parse entry set and is of the form [A => alpha . B beta, k]. Then the entry [.B, i] is added to the current sigma set. Gist: when an entry expects the non-terminal symbol B, then add an entry with start vertex .B



53
54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/rley/parser/gfg_parsing.rb', line 53

def call_rule(anEntry, aPosition)
  next_symbol = anEntry.next_symbol
  start_vertex = gf_graph.start_vertex_for[next_symbol]
  pos = aPosition
  size_before = chart[pos].size
  apply_rule(anEntry, start_vertex, pos, pos, :call_rule)

  if next_symbol.nullable? && anEntry.dotted_entry?
    size_after = chart[pos].size
    # ...apply the Nullable rule, if not already invoked for this entry
    nullable_rule(anEntry, aPosition) if size_after == size_before
  end
end

#count_edges ⇒ Object 



243
244
245
 
# File 'lib/rley/parser/gfg_parsing.rb', line 243

def count_edges
  chart.count_edges
end

#count_entries ⇒ Object 



239
240
241
 
# File 'lib/rley/parser/gfg_parsing.rb', line 239

def count_entries
  chart.count_entries
end

#count_states ⇒ Object 



235
236
237
 
# File 'lib/rley/parser/gfg_parsing.rb', line 235

def count_states
  chart.count_states
end

#done ⇒ Object

A notification that the parsing reached an end



221
222
223
224
225
 
# File 'lib/rley/parser/gfg_parsing.rb', line 221

def done
  # Parse not successful and no reason identified
  # Assuming that parse failed because of a premature end
  premature_end unless success? || failure_reason
end

#end_rule(anEntry, aPosition) ⇒ Object

This method is invoked when an entry of the form [B., k] is added to a parse entry set with index j. then for every entry of the form [A => α . B γ, i] in the kth sigma set the entry [A => α B . γ, i] is added to the jth sigma set.



136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
# File 'lib/rley/parser/gfg_parsing.rb', line 136

def end_rule(anEntry, aPosition)
  nterm_k = anEntry.vertex.non_terminal
  origin_k = anEntry.origin
  set_k = chart[origin_k]

  # Retrieve all the entries that expect the non-terminal
  expecting_nterm_k = set_k.entries4n_term(nterm_k)
  expecting_nterm_k.each do |ntry|
    # Get the vertices after the expected non-terminal
    vertex_after_terminal = ntry.vertex.shortcut.successor
    origin = ntry.origin
    pos = aPosition
    apply_rule(anEntry, vertex_after_terminal, origin, pos, :end_rule)
  end
end

#exit_rule(anEntry, aPosition) ⇒ Object

This method must be invoked when an entry is added to a parse entry set and is of the form [B => γ ., k] (the dot is at the end of the production. Then entry [B., k] is added to the current entry set. Gist: for an entry corresponding to a reduced production, add an entry for each exit edge in the graph.



126
127
128
129
130
 
# File 'lib/rley/parser/gfg_parsing.rb', line 126

def exit_rule(anEntry, aPosition)
  lhs = anEntry.vertex.lhs
  end_vertex = gf_graph.end_vertex_for[lhs]
  apply_rule(anEntry, end_vertex, anEntry.origin, aPosition, :exit_rule)
end

#faulty(aReason) ⇒ Object

Mark the parse as erroneous



216
217
218
 
# File 'lib/rley/parser/gfg_parsing.rb', line 216

def faulty(aReason)
  @failure_reason = aReason
end

#initial_entry ⇒ Object

Retrieve the very first parse entry added to the chart. This entry corresponds to the start vertex of the GF graph with origin equal to zero.



203
204
205
 
# File 'lib/rley/parser/gfg_parsing.rb', line 203

def initial_entry
  chart.initial_entry
end

#nullable_rule(anEntry, aPosition) ⇒ Object

Let the current sigma set be the ith parse entry set. This method is invoked when a dotted entry is added to the parse entry set of the from [A => alpha . B beta, k] and B is nullable Then the following entries are added to the current sigma set: [.B, i] [B => ., i] TODO: what if indirectly nullable? [B., i] [A => alpha B . beta, k]



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
 
# File 'lib/rley/parser/gfg_parsing.rb', line 76

def nullable_rule(anEntry, aPosition)
  # Terminology:
  # .B : start node
  # B => . rhs : entry node
  # B => rhs . : exit node
  # B. : end node
  next_symbol = anEntry.next_symbol
  pos = aPosition
  start = gf_graph.start_vertex_for[next_symbol]
  start_entry = apply_rule(anEntry, start, pos, pos, :nullable_rule)

  end_vertex = gf_graph.end_vertex_for[next_symbol]

  start.edges.each do |edge|
    succ = edge.successor # succ always an ItemVertex
    if succ.dotted_item.production.nullable?
      succ_entry = apply_rule(start_entry, succ, pos, pos, :nullable_rule)
      next unless succ_entry.exit_entry?

      apply_rule(succ_entry, end_vertex, pos, pos, :nullable_rule)
    end
  end

  curr_vertex = anEntry.vertex
  next_vertex = curr_vertex.shortcut.successor
  end_entry = push_entry(end_vertex, pos, pos, :nullable_rule)
  apply_rule(end_entry, next_vertex, anEntry.origin, pos, :nullable_rule)
end

#scan_rule(aPosition, aToken) ⇒ Object

Given that the terminal t is at the specified position, Locate all entries in the current sigma set that expect t: [A => α . t γ, i] and allow them to cross the edge, adding the node on the back side of the edge as an entry to the next sigma set: add an entry to the next sigma set [A => α t . γ, i + 1] returns true if next token matches the expectations, false otherwise.



159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
 
# File 'lib/rley/parser/gfg_parsing.rb', line 159

def scan_rule(aPosition, aToken)
  tokens << aToken
  terminal = aToken.terminal

  # Retrieve all the entries that expect the given terminal
  expecting_term = chart[aPosition].entries4term(terminal)

  # ... if the terminal isn't expected then we have an error
  if expecting_term.empty?
    unexpected_token(aPosition)
    return false
  end

  expecting_term.each do |ntry|
    # Get the vertices after the expected terminal
    ntry.vertex.edges.each do |an_edge|
      vertex_after_terminal = an_edge.successor
      origin = ntry.origin
      pos = aPosition + 1
      apply_rule(ntry, vertex_after_terminal, origin, pos, :scan_rule)
    end
  end

  true
end

#start_rule(anEntry, aPosition) ⇒ Object

Let the current sigma set be the ith parse entry set. This method is invoked when an entry is added to a parse entry set and the entry is of the form [.B, i]. then for every rule B => γ in the grammar an entry [B => . γ, i] is added to the current sigma set. Gist: for an entry corresponding to a start vertex, add an entry for each entry edge in the graph.



112
113
114
115
116
117
118
119
 
# File 'lib/rley/parser/gfg_parsing.rb', line 112

def start_rule(anEntry, aPosition)
  return unless anEntry.origin == aPosition

  anEntry.vertex.edges.each do |a_start_edge|
    successor = a_start_edge.successor
    apply_rule(anEntry, successor, aPosition, aPosition, :start_rule)
  end
end

#success? ⇒ Boolean

Return true if the parse was successful (= input tokens followed the syntax specified by the grammar)

Returns:

  • (Boolean) 


187
188
189
190
191
 
# File 'lib/rley/parser/gfg_parsing.rb', line 187

def success?
  return false if @failure_reason

  chart.accepting_entry ? true : false
end

#tidy_up! ⇒ Object

Clean and normalize the object. Call this method when the parsing is complete.



229
230
231
232
233
 
# File 'lib/rley/parser/gfg_parsing.rb', line 229

def tidy_up!
  antecedence.each_key do |entry|
    antecedence[entry].uniq!
  end
end

#to_s ⇒ String

Returns A human readable representation of itself.

Returns:

  • (String) —

    A human readable representation of itself.



248
249
250
251
252
253
254
255
 
# File 'lib/rley/parser/gfg_parsing.rb', line 248

def to_s
  result = +''
  result << "success? #{success?}\n"
  result << "chart:\n"
  result << chart.to_s

  result
end