Class: Dendroid::GrmAnalysis::DottedItem

Inherits:
Object
  • Object
show all
Defined in:
lib/dendroid/grm_analysis/dotted_item.rb

Overview

For a given production rule, a dotted item represents a recognition state. The dot partitions the rhs of the rule in two parts: a) the left part consists of the symbols in the rhs that are matched by the input tokens. b) 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. An item with the dot not at the beginning is sometimes referred to as a kernel item

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(aRule, aPosition, index) ⇒ DottedItem

Constructor.

Parameters:

  • aRule (Dendroid::Syntax::Rule)
  • aPosition (Integer) —

    Position of the dot in rhs of production.

  • index (Integer) —

    the rank of the alternative at hand



37
38
39
40
41
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 37

def initialize(aRule, aPosition, index)
  @alt_index = index
  @rule = WeakRef.new(aRule)
  @position = valid_position(aPosition)
end

Instance Attribute Details

#alt_index ⇒ Integer (readonly)

Returns the alternative number.

Returns:

  • (Integer) —

    the alternative number



31
32
33
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 31

def alt_index
  @alt_index
end

#position ⇒ Integer (readonly)

Returns the dot position.

Returns:

  • (Integer) —

    the dot position



28
29
30
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 28

def position
  @position
end

#rule ⇒ Dendroid::Syntax::Rule (readonly)

(Weak) reference to the production rule

Returns:



25
26
27
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 25

def rule
  @rule
end

Instance Method Details

#==(other) ⇒ Boolean

Test for equality with another dotted item. Two dotted items are equal if they refer to the same rule and have both the same rhs and dot positions.

Returns:

  • (Boolean) 


127
128
129
130
131
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 127

def ==(other)
  return true if eql?(other)

  (position == other.position) && rule.eql?(other.rule) && (alt_index == other.alt_index)
end

#empty? ⇒ Boolean

Indicate whether the rhs of the alternative is empty

Returns:

  • (Boolean) 


55
56
57
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 55

def empty?
  rule.alternatives[alt_index].empty?
end

#expecting?(aSymbol) ⇒ Boolean

Check whether the given symbol is the same as after the dot.

Parameters:

Returns:

  • (Boolean) 


109
110
111
112
113
114
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 109

def expecting?(aSymbol)
  actual = next_symbol
  return false if actual.nil?

  actual == aSymbol
end

#final_pos? ⇒ Boolean Also known as: completed?

Indicate whether the dot is at the start of rhs

Returns:

  • (Boolean) 


75
76
77
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 75

def final_pos?
  empty? || position == rule.alternatives[alt_index].size
end

#initial_pos? ⇒ Boolean

Indicate whether the dot is at the start of rhs

Returns:

  • (Boolean) 


61
62
63
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 61

def initial_pos?
  position.zero? || empty?
end

#intermediate_pos? ⇒ Boolean

Indicate the dot isn’t at start nor at end position

Returns:

  • (Boolean) 


67
68
69
70
71
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 67

def intermediate_pos?
  return false if empty? || position.zero?

  position < rule.alternatives[alt_index].size
end

#next_symbol ⇒ Dendroid::Syntax::GrmSymbol, NilClass

Return the symbol right after the dot (if any)

Returns:



92
93
94
95
96
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 92

def next_symbol
  return nil if empty? || completed?

  rule.alternatives[alt_index].members[position]
end

#pre_scan? ⇒ Boolean

Check whether the dotted item is a shift item. In other words, it expects a terminal to be the next symbol

Returns:

  • (Boolean) 


119
120
121
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 119

def pre_scan?
  next_symbol&.terminal?
end

#prev_symbol ⇒ Dendroid::Syntax::GrmSymbol, NilClass

Return the symbol right before the dot (if any)

Returns:



100
101
102
103
104
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 100

def prev_symbol
  return nil if empty? || position.zero?

  rule.alternatives[alt_index].members[position - 1]
end

#state ⇒ Symbol

Terminology inspired from Luger’s book

Returns:

  • (Symbol) —

    one of: :initial, :initial_and_completed, :partial, :completed



83
84
85
86
87
88
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 83

def state
  return :initial_and_completed if empty?
  return :initial if position.zero?

  position == rule.alternatives[alt_index].size ? :completed : :partial
end

#to_s ⇒ String Also known as: inspect

Return a String representation of the alternative item.

Returns:

  • (String) 


45
46
47
48
49
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 45

def to_s
  rhs_names = rule.alternatives[alt_index].members.map(&:to_s)
  dotted_rhs = rhs_names.insert(position, '.')
  "#{rule.head} => #{dotted_rhs.join(' ')}"
end