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

Returns a new instance of GFGParsing.



31
32
33
34
35
36
37
 
# File 'lib/rley/parser/gfg_parsing.rb', line 31

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 ⇒ Object (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



25
26
27
 
# File 'lib/rley/parser/gfg_parsing.rb', line 25

def antecedence
  @antecedence
end

#chart ⇒ Object (readonly)

The link to the chart object



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

def chart
  @chart
end

#failure_reason ⇒ Object (readonly)

The reason of a parse failure



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

def failure_reason
  @failure_reason
end

#gf_graph ⇒ Object (readonly)

The link to the grammar flow graph



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

def gf_graph
  @gf_graph
end

#tokens ⇒ Object (readonly)

The sequence of input token to parse



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

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



172
173
174
 
# File 'lib/rley/parser/gfg_parsing.rb', line 172

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) 


140
141
142
143
 
# File 'lib/rley/parser/gfg_parsing.rb', line 140

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



45
46
47
48
49
50
 
# File 'lib/rley/parser/gfg_parsing.rb', line 45

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

#done ⇒ Object

A notification that the parsing reached an end



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

def done
  unless self.success? || self.failure_reason
    # Parse not successful and no reason identified
    # Assuming that parse failed because of a premature end
    premature_end
  end
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.



83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/rley/parser/gfg_parsing.rb', line 83

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.



73
74
75
76
77
 
# File 'lib/rley/parser/gfg_parsing.rb', line 73

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



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

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.



164
165
166
 
# File 'lib/rley/parser/gfg_parsing.rb', line 164

def initial_entry()
  return chart.initial_entry
end

#parse_forest ⇒ ParseForest

Factory method. Builds a ParseForest from the parse result.

Returns:

  • (ParseForest) 


147
148
149
150
151
 
# File 'lib/rley/parser/gfg_parsing.rb', line 147

def parse_forest()
  factory = ParseForestFactory.new(self)

  return factory.build_parse_forest
end

#parse_tree ⇒ ParseTree

Factory method. Builds a ParseTree from the parse result.

Returns:

  • (ParseTree) 


155
156
157
158
159
 
# File 'lib/rley/parser/gfg_parsing.rb', line 155

def parse_tree()
  factory = ParseTreeFactory.new(self)

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



106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
# File 'lib/rley/parser/gfg_parsing.rb', line 106

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.



59
60
61
62
63
64
65
66
 
# File 'lib/rley/parser/gfg_parsing.rb', line 59

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) 


134
135
136
 
# File 'lib/rley/parser/gfg_parsing.rb', line 134

def success?()
  return chart.accepting_entry ? true : false
end