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:



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

def initialize(theGFG)
  @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:



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

def antecedence
  @antecedence
end

#chart ⇒ GFGChart (readonly)

The link to the chart object

Returns:



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

def chart
  @chart
end

#failure_reason ⇒ ErrorReason (readonly)

Returns The reason of a parse failure.

Returns:



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

def failure_reason
  @failure_reason
end

#gf_graph ⇒ GFG::GrmFlowGraph (readonly)

The link to the grammar flow graph

Returns:



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

def gf_graph
  @gf_graph
end

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

The sequence of input token to parse

Returns:



21
22
23
 
# File 'lib/rley/parser/gfg_parsing.rb', line 21

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



214
215
216
 
# File 'lib/rley/parser/gfg_parsing.rb', line 214

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) 


184
185
186
187
 
# File 'lib/rley/parser/gfg_parsing.rb', line 184

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



50
51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/rley/parser/gfg_parsing.rb', line 50

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

#done ⇒ Object

A notification that the parsing reached an end



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

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.



126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
 
# File 'lib/rley/parser/gfg_parsing.rb', line 126

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.



116
117
118
119
120
 
# File 'lib/rley/parser/gfg_parsing.rb', line 116

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



219
220
221
 
# File 'lib/rley/parser/gfg_parsing.rb', line 219

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.



206
207
208
 
# File 'lib/rley/parser/gfg_parsing.rb', line 206

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]



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_parsing.rb', line 73

def nullable_rule(anEntry, aPosition)
  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)
      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) 


191
192
193
194
195
196
197
198
199
200
201
 
# File 'lib/rley/parser/gfg_parsing.rb', line 191

def parse_forest()
  msg = " Method Rley::Parser::GFGParsing.parse_forest is deprecated, call\n Rley::Engine::to_pforest. It will be removed June 1st\n or version 0.6.1 (whichever is first)\n"
  # 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.



149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
 
# File 'lib/rley/parser/gfg_parsing.rb', line 149

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.



102
103
104
105
106
107
108
109
 
# File 'lib/rley/parser/gfg_parsing.rb', line 102

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) 


177
178
179
180
 
# File 'lib/rley/parser/gfg_parsing.rb', line 177

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.



232
233
234
235
236
 
# File 'lib/rley/parser/gfg_parsing.rb', line 232

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