class Rley::GFG::GrmFlowGraph

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