Class: Rley::Base::DottedItem

Inherits:
Object
  • Object
show all
Defined in:
lib/rley/base/dotted_item.rb

Overview

A dotted item is a parse state for a given production/grammar rule It partitions the rhs of the rule in two parts. The left part consists of the symbols in the rules that are matched by the input tokens. The right part consists of symbols that are predicted to match the input tokens. The terminology stems from the traditional way to visualize the partition by using a fat dot character as a separator between the left and right parts An item with the dot at the beginning (i.e. before any rhs symbol) is called a predicted item. An item with the dot at the end (i.e. after all rhs symbols) is called a reduce item. An item with a dot in front of a terminal is called a shift item.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(aProduction, aPosition) ⇒ DottedItem

Returns a new instance of DottedItem.

Parameters:

  • aProduction (Syntax::Production)
  • aPosition (Integer) —

    Position of the dot in rhs of production.



33
34
35
36
 
# File 'lib/rley/base/dotted_item.rb', line 33

def initialize(aProduction, aPosition)
  @production = aProduction
  @position = valid_position(aPosition)
end

Instance Attribute Details

#position ⇒ Integer (readonly)

Index of the next symbol (from the rhs) after the 'dot'. If the dot is at the end of the rhs (i.e.) there is no next symbol, then the position takes the value -1. It the rhs is empty, then the position is -2

Returns:

  • (Integer) 


29
30
31
 
# File 'lib/rley/base/dotted_item.rb', line 29

def position
  @position
end

#production ⇒ Syntax::Production (readonly)

Production rule

Returns:



22
23
24
 
# File 'lib/rley/base/dotted_item.rb', line 22

def production
  @production
end

Instance Method Details

#at_start? ⇒ Boolean Also known as: predicted_item?

Return true if the dot position is at the start of the rhs.

Returns:

  • (Boolean) 


55
56
57
 
# File 'lib/rley/base/dotted_item.rb', line 55

def at_start?
  position.zero? || position == -2
end

#lhs ⇒ Syntax::NonTerminal

The non-terminal symbol that is on the left-side of the production

Returns:



71
72
73
 
# File 'lib/rley/base/dotted_item.rb', line 71

def lhs
  production.lhs
end

#next_symbol ⇒ Syntax::GrmSymbol, NilClass

Return the symbol after the dot. nil is returned if the dot is at the end

Returns:



86
87
88
 
# File 'lib/rley/base/dotted_item.rb', line 86

def next_symbol
  position.negative? ? nil : production.rhs[position]
end

#prev_position ⇒ Integer

Calculate the position of the dot if were moved by one step on the left.

Returns:

  • (Integer) 


93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
 
# File 'lib/rley/base/dotted_item.rb', line 93

def prev_position
  unless @k_prev_position
    case position
      when -2, 0
        result = nil
      when -1
        result = production.rhs.size == 1 ? 0 : production.rhs.size - 1
      else
        result = position - 1
    end
    @k_prev_position = [result]
  end

  @k_prev_position[0]
end

#prev_symbol ⇒ Syntax::GrmSymbol, NilClass

Return the symbol before the dot. nil is returned if the dot is at the start of the rhs

Returns:



78
79
80
81
 
# File 'lib/rley/base/dotted_item.rb', line 78

def prev_symbol
  before_position = prev_position
  before_position.nil? ? nil : production.rhs[before_position]
end

#reduce_item? ⇒ Boolean

A dotted item is called a reduce item if the dot is at the end.

Returns:

  • (Boolean) 


65
66
67
 
# File 'lib/rley/base/dotted_item.rb', line 65

def reduce_item?
  position.negative? # Either -1 or -2
end

#successor_of?(another) ⇒ Boolean

Return true if this dotted item has a dot one place to the right compared to the dotted item argument.

Parameters:

Returns:

  • (Boolean) 


113
114
115
116
117
118
119
120
 
# File 'lib/rley/base/dotted_item.rb', line 113

def successor_of?(another)
  return false if production != another.production

  to_the_left = prev_position
  return false if to_the_left.nil?

  to_the_left == another.position
end

#to_s ⇒ String

Return a String representation of the dotted item.

Returns:

  • (String) 


40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/rley/base/dotted_item.rb', line 40

def to_s
  prefix = "#{production.lhs} => "
  text_values = production.rhs.map(&:to_s)
  if position.negative?
    text_values << '.'
  else
    text_values.insert(position, '.')
  end
  suffix = text_values.join(' ')

  prefix + suffix
end