Class: Rley::Parser::GFGEarleyParser

Inherits:
Base::BaseParser show all
Defined in:
lib/rley/parser/gfg_earley_parser.rb

Overview

Implementation of a parser that uses the Earley parsing algorithm.

Instance Attribute Summary collapse

Attributes inherited from Base::BaseParser

#dotted_items, #grammar

Instance Method Summary collapse

Methods included from Base::GrmItemsBuilder

#build_dotted_items

Constructor Details

#initialize(aGrammar) ⇒ GFGEarleyParser

Constructor.

Parameters:



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

def initialize(aGrammar)
  super(aGrammar)
  @gf_graph = GFG::GrmFlowGraph.new(dotted_items)
end

Instance Attribute Details

#gf_graph ⇒ GFG::GrmFlowGraph (readonly)

The Grammar Flow graph generated from the provided grammar.

Returns:



11
12
13
 
# File 'lib/rley/parser/gfg_earley_parser.rb', line 11

def gf_graph
  @gf_graph
end

Instance Method Details

#parse(aTokenSequence) ⇒ GFGParsing

Parse a sequence of input tokens. tokenizer/scanner/lexer.

Parameters:

  • aTokenSequence (Array) —

    Array of Tokens objects returned by a

Returns:

  • (GFGParsing) —

    an object that embeds the parse results.



24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/rley/parser/gfg_earley_parser.rb', line 24

def parse(aTokenSequence)
  result = GFGParsing.new(gf_graph, aTokenSequence)
  last_token_index = aTokenSequence.size
  if last_token_index.zero? && !grammar.start_symbol.nullable?
    return unexpected_empty_input(result)
  end

  (0..last_token_index).each do |i|
    result.chart[i].each do |entry|
      # Is entry of the form? [A => alpha . B beta, k]...
      next_symbol = entry.next_symbol
      if next_symbol && next_symbol.kind_of?(Syntax::NonTerminal)
        # ...apply the Call rule
        call_rule(result, entry, i)
      end

      exit_rule(result, entry, i) if entry.exit_entry?
      start_rule(result, entry, i) if entry.start_entry?
      end_rule(result, entry, i) if entry.end_entry?
    end
    if i < last_token_index
      scan_success = scan_rule(result, i)
      break unless scan_success
    end
  end
  result.done # End of parsing process
  return result
end