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?()
  return 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()
  return 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:



92
93
94
 
# File 'lib/rley/base/dotted_item.rb', line 92

def next_symbol()
  return 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) 


99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
 
# File 'lib/rley/base/dotted_item.rb', line 99

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
82
83
84
85
86
87
 
# File 'lib/rley/base/dotted_item.rb', line 78

def prev_symbol()
  before_position = prev_position
  result = if before_position.nil?
             nil
           else
             production.rhs[before_position]
           end

  return result
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?()
  return 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) 


119
120
121
122
123
124
125
126
 
# File 'lib/rley/base/dotted_item.rb', line 119

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

  to_the_left = prev_position
  return false if to_the_left.nil?

  return 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(' ')

  return prefix + suffix
end