Class: Rley::GFG::GrmFlowGraph

Inherits:
Object
  • Object
show all
Defined in:
lib/rley/gfg/grm_flow_graph.rb

Overview

A Grammar Flow Graph (GFG) represents the parsing states of productions rules from a context-free grammar. This representation is based on a directed graph structure. The parsing process can then be re-formulated as a path problem in the graph. The theory behind GFGs can be found in papers. The first article on GFG can be found here: https://apps.cs.utexas.edu/tech_reports/reports/tr/TR-2102.pdf There are three types of vertex in a GFG: start vertex, end vertex and item vertex. For each non-terminal symbol N of the grammar, there is: a start vertex with label '.N' an end vertex with label 'N.' For each production rule of the grammar: N => s1 s2 s3 (...) sk I.e. a rule with k grammar symbols in its right-handed side. For such a rule there will be k + 1 item vertices. By convention, the first item vertex is labelled as 'N => . s1 s2 s3 (...) sk' the second item vertex is labelled as 'N => s1 . s2 s3 (...) sk' the third item vertex is labelled as 'N => s1 s2 . s3 (...) sk' and so on. In other words, the labels are obtained by moving a dot in successive positions in the rhs. The dot represents the parse progress for the production rule. Symbols on the left of the dot represent the symbols that were successfully matched in the input. A GFG has three types of directed edges linking the vertices. call edge, return edge and scan edge.

Defined Under Namespace

Classes: Branching

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(theDottedItems) ⇒ GrmFlowGraph

Constructor. of the grammar.

Parameters:

  • theDottedItems (Array<DottedItem>) —

    an array of the dotted items



56
57
58
59
60
61
62
 
# File 'lib/rley/gfg/grm_flow_graph.rb', line 56

def initialize(theDottedItems)
  @vertices = []
  @start_vertex_for = {}
  @end_vertex_for = {}

  build_graph(theDottedItems)
end

Instance Attribute Details

#end_vertex_for ⇒ Object (readonly)

A Hash with pairs of the form: non-terminal symbol => end node



51
52
53
 
# File 'lib/rley/gfg/grm_flow_graph.rb', line 51

def end_vertex_for
  @end_vertex_for
end

#start_vertex ⇒ StartVertex (readonly)

The vertex marked as start node of the graph

Returns:



45
46
47
 
# File 'lib/rley/gfg/grm_flow_graph.rb', line 45

def start_vertex
  @start_vertex
end

#start_vertex_for ⇒ Object (readonly)

A Hash with pairs of the form: non-terminal symbol => start node



48
49
50
 
# File 'lib/rley/gfg/grm_flow_graph.rb', line 48

def start_vertex_for
  @start_vertex_for
end

#vertices ⇒ Array<Vertex> (readonly)

Returns The set of all vertices in the graph.

Returns:

  • (Array<Vertex>) —

    The set of all vertices in the graph



41
42
43
 
# File 'lib/rley/gfg/grm_flow_graph.rb', line 41

def vertices
  @vertices
end

Instance Method Details

#diagnose ⇒ Object

Perform a diagnosis of the grammar elements (symbols and rules) in order to detect: If one wants to remove useless rules, then do first: elimination of non-generating symbols then elimination of unreachable symbols



95
96
97
 
# File 'lib/rley/gfg/grm_flow_graph.rb', line 95

def diagnose
  mark_unreachable_symbols
end

#find_vertex(aVertexLabel) ⇒ Vertex

Retrieve the vertex with given vertex label.

Parameters:

  • aVertexLabel (String) —

    the label of a vertex from the graph

Returns:

  • (Vertex) —

    the vertex with the given label, otherwise nil.



86
87
88
 
# File 'lib/rley/gfg/grm_flow_graph.rb', line 86

def find_vertex(aVertexLabel)
  vertices.find { |a_vertex| a_vertex.label == aVertexLabel }
end

#inspect ⇒ String

Returns a string containing a human-readable representation of the production.

Returns:

  • (String) 


67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
 
# File 'lib/rley/gfg/grm_flow_graph.rb', line 67

def inspect
  result = +"#<#{self.class.name}:#{object_id}"
  result << ' @vertices=['
  list = vertices.map { |v| "#<#{v.selfie}>" }
  result << list.join(', ')
  result << '] '
  edges = []
  vertices.each do |v|
    edges << v.edges do |e|
      result << "#{v.object_id} #{e.inspect}"
    end
  end
  result << "edges=[#{edges.join(",\n ")}]>"
  result
end

#traverse_df(aStartVertex, &_visitAction) {|last_one| ... } ⇒ Object

Walk over all the vertices of the graph that are reachable from a given start vertex. This is a depth-first graph traversal. rubocop: disable Lint/Loop

Parameters:

  • aStartVertex (StartVertex) —

    the depth-first traversal begins from here

  • _visitAction (Proc) —

    block called when a new graph vertex is found

Yields:

  • (last_one) 


125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
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
174
175
176
 
# File 'lib/rley/gfg/grm_flow_graph.rb', line 125

def traverse_df(aStartVertex, &_visitAction)
  visited = Set.new
  stack = []
  visitee = aStartVertex
  curr_edge = nil

  begin
    # print_vertex( 'Traversing', visitee)

    first_time = !visited.include?(visitee)
    if first_time
      yield(visitee)
      visited << visitee
    end

    case visitee
      when Rley::GFG::StartVertex
        if first_time
          stack.push(Branching.new(visitee, curr_edge))
          curr_edge = stack.last.next_edge
        elsif curr_edge.nil?
          # Error probably caused by missing terminal symbol object
          msg = "Undefined grammar symbol #{visitee.label.sub(/^\./, '')}"
          raise StandardError, msg
        else
          # Skip both start and end vertices
          # Retrieve the corresponding return edge
          curr_edge = get_matching_return(curr_edge)
        end

      when Rley::GFG::EndVertex
        if stack.last.done?
          popped = stack.pop
          break if stack.empty?

          # puts "Popped!"
          return_key = popped.in_edge.key.sub(/^CALL/, 'RET')
          curr_edge = visitee.edges.find { |e| e.key == return_key }
        else
          curr_edge = stack.last.next_edge
        end

      else
        # All other vertex types have only one successor
        curr_edge = visitee.edges[0]
    end
    visitee = curr_edge.successor unless curr_edge.nil?
  end until stack.empty?
  # Now process the end vertex matching the initial start vertex
  last_one = end_vertex_for[aStartVertex.non_terminal]
  yield(last_one) unless visited.include?(last_one)
end