Class: Antelope::Generation::Constructor

Inherits:
Object
  • Object
show all
Includes:
First, Follow, Nullable
Defined in:
lib/antelope/generation/constructor.rb,
lib/antelope/generation/constructor/first.rb,
lib/antelope/generation/constructor/follow.rb,
lib/antelope/generation/constructor/nullable.rb

Overview

Constructs the lookahead sets for all of the rules in the grammar.

Defined Under Namespace

Modules: First, Follow, Nullable

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Follow

#follow, #generate_follow_set

Methods included from First

#first, #first_array, #firstifying

Methods included from Nullable

#nullable?, #nullifying

Constructor Details

#initialize(grammar) ⇒ Constructor

Initialize.

Parameters:

  • grammar (Grammar::Grammar) —

    the grammar.



32
33
34
35
36
 
# File 'lib/antelope/generation/constructor.rb', line 32

def initialize(grammar)
  @productions = Set.new
  @grammar = grammar
  super()
end

Instance Attribute Details

#grammar ⇒ Grammar::Grammar (readonly)

The grammar.

Returns:

  • (Grammar::Grammar) 


22
23
24
 
# File 'lib/antelope/generation/constructor.rb', line 22

def grammar
  @grammar
end

#productions ⇒ Set<Grammar::Production> (readonly)

The augmented productions generated by the constructor.

Returns:



27
28
29
 
# File 'lib/antelope/generation/constructor.rb', line 27

def productions
  @productions
end

Instance Method Details

#augment_rules(state) ⇒ void

This method returns an undefined value.

Augments every final rule. For every rule in the current state that has a position of zero, it follows the rule through the DFA until the ending state; it then modifies the ending state's lookahead set to be the FOLLOW set of the nonterminal it reduces to.

Parameters:

See Also:



99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
 
# File 'lib/antelope/generation/constructor.rb', line 99

def augment_rules(state)
  state.rules.each do |rule|
    next unless rule.position.zero?
    current_state = state

    label = rule.left.dup
    label.from = state
    label.to = state.transitions[label.name]

    rule.right.each do |part|
      transition = current_state.transitions[part.name]
      current_state = transition
    end

    final = current_state.rule_for(rule)

    final.lookahead = Set.new unless final.lookahead
    final.lookahead.merge follow(label)
  end
end

#augment_state(state) ⇒ void

This method returns an undefined value.

Augments the given state. On every rule within that state that has a position of zero, it follows the rule throughout the DFA until the end; it marks every nonterminal it encounters with the transitions it took on that nonterminal.

Parameters:



60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/antelope/generation/constructor.rb', line 60

def augment_state(state)
  state.rules.select { |x| x.position.zero? }.each do |rule|
    production = rule.production.clone
    production.items = []

    current_state = state
    old_state = state

    production.label.from = state
    production.label.to   = state.transitions[rule.left.name]

    rule.right.each_with_index do |part, pos|
      transition = current_state.transitions[part.name]
      new_item = part.dup

      if part.nonterminal?
        new_item.from = current_state
        new_item.to   = transition
      end

      production.items << new_item

      old_state = current_state
      current_state = transition
    end

    productions << production
  end
end

#call ⇒ void

This method returns an undefined value.

Performs the construction. First, it goes through every state and augments the state. It then goes through every rule and augments it.

See Also:



45
46
47
48
49
50
51
 
# File 'lib/antelope/generation/constructor.rb', line 45

def call
  grammar.states.each do |state|
    augment_state(state)
  end.each do |state|
    augment_rules(state)
  end
end

#incorrect_argument!(arg, *types) ⇒ Object (private)

Raises:

  • (ArgumentError) 


122
123
124
 
# File 'lib/antelope/generation/constructor.rb', line 122

def incorrect_argument!(arg, *types)
  raise ArgumentError, "Expected one of #{types.join(', ')}, got #{arg.class}"
end