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.



31
32
33
34
 
# File 'lib/rley/base/dotted_item.rb', line 31

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) 


27
28
29
 
# File 'lib/rley/base/dotted_item.rb', line 27

def position
  @position
end

#production ⇒ Syntax::Production (readonly)

Production rule

Returns:



20
21
22
 
# File 'lib/rley/base/dotted_item.rb', line 20

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) 


53
54
55
 
# File 'lib/rley/base/dotted_item.rb', line 53

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:



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

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:



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

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


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

def 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

  return result
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:



76
77
78
79
80
81
82
83
84
85
 
# File 'lib/rley/base/dotted_item.rb', line 76

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) 


63
64
65
 
# File 'lib/rley/base/dotted_item.rb', line 63

def reduce_item?()
  return position < 0 # 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) 


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

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) 


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

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

  return prefix + suffix
end