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



224
225
226
 
# File 'lib/rley/parser/gfg_parsing.rb', line 224

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) 


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

def ambiguous?()
  found = chart.sets.find { |set| !set.ambiguities.empty? }
  return !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 



256
257
258
 
# File 'lib/rley/parser/gfg_parsing.rb', line 256

def count_edges
  chart.count_edges
end

#count_entries ⇒ Object 



252
253
254
 
# File 'lib/rley/parser/gfg_parsing.rb', line 252

def count_entries
  chart.count_entries
end

#count_states ⇒ Object 



248
249
250
 
# File 'lib/rley/parser/gfg_parsing.rb', line 248

def count_states
  chart.count_states
end

#done ⇒ Object

A notification that the parsing reached an end



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

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.



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

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.



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

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



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

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.



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

def initial_entry()
  return 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
 
# 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

#parse_forest ⇒ ParseForest

Factory method. Builds a ParseForest from the parse result.

Returns:

  • (ParseForest) 


201
202
203
204
205
206
207
208
209
210
211
 
# File 'lib/rley/parser/gfg_parsing.rb', line 201

def parse_forest()
  msg = <<-END_MSG
 Method Rley::Parser::GFGParsing.parse_forest is deprecated, call
 Rley::Engine::to_pforest. It will be removed June 1st
 or version 0.6.1 (whichever is first)
END_MSG
  # warn(msg)
  factory = ParseRep::ParseForestFactory.new(self)

  return factory.create
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.



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

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

  return 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.



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

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) 


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

def success?()
  return false if @failure_reason

  return chart.accepting_entry ? true : false
end

#tidy_up! ⇒ Object

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



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

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.



261
262
263
264
265
266
267
268
 
# File 'lib/rley/parser/gfg_parsing.rb', line 261

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

  result
end