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 



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.



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