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.



38
39
40
41
 
# File 'lib/rley/base/dotted_item.rb', line 38

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

Instance Attribute Details

#constraint ⇒ NilClass, Syntax::MatchClosest

A possible constraint between symbol on left of dot and the closest preceding given terminal

Returns:



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

def constraint
  @constraint
end

#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) 


60
61
62
 
# File 'lib/rley/base/dotted_item.rb', line 60

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:



76
77
78
 
# File 'lib/rley/base/dotted_item.rb', line 76

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:



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

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) 


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

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:



83
84
85
86
 
# File 'lib/rley/base/dotted_item.rb', line 83

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) 


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

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) 


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

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) 


45
46
47
48
49
50
51
52
53
54
55
56
 
# File 'lib/rley/base/dotted_item.rb', line 45

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