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, theTokens) ⇒ GFGParsing

Constructor

Parameters:

  • theGFG (GFG::GrmFlowGraph) —

    the Grammar Flow Graph

  • theTokens (Array<Token>) —

    the array of input tokens



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

def initialize(theGFG, theTokens)
  @gf_graph = theGFG
  @tokens = theTokens.dup
  @chart = GFGChart.new(tokens.size, 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



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

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) 


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

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



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

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
    nullable_rule(anEntry, aPosition) if size_after == size_before
  end
end

#done ⇒ Object

A notification that the parsing reached an end



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

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



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

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.



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

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]



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 74

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
    next if succ.dotted_item.production.generative?
    succ_entry = apply_rule(start_entry, succ, pos, pos, :nullable_rule)
    apply_rule(succ_entry, end_vertex, pos, pos, :nullable_rule)
  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) 


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

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

def scan_rule(aPosition)
  terminal = tokens[aPosition].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) 


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

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.



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

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