Class: Rley::Parser::GFGEarleyParser

Inherits:
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 BaseParser

#dotted_items, #grammar

Instance Method Summary collapse

Methods included from GrmItemsBuilder

#build_dotted_items

Constructor Details

#initialize(aGrammar) ⇒ GFGEarleyParser

Returns a new instance of GFGEarleyParser.



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

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

Instance Attribute Details

#gf_graph ⇒ Object (readonly)

The Grammar Flow graph for the given grammar



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

def gf_graph
  @gf_graph
end

Instance Method Details

#parse(aTokenSequence) ⇒ Parsing

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

Parameters:

  • aTokenSequence (Array) —

    Array of Tokens objects returned by a

Returns:

  • (Parsing) —

    an object that embeds the parse results.



21
22
23
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
 
# File 'lib/rley/parser/gfg_earley_parser.rb', line 21

def parse(aTokenSequence)
  result = GFGParsing.new(gf_graph, aTokenSequence)
  last_token_index = aTokenSequence.size
  if last_token_index == 0 && !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