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

Direct Known Subclasses

AlternativeItem

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(aRule, aPosition) ⇒ DottedItem

Constructor.

Parameters:



33
34
35
36
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 33

def initialize(aRule, aPosition)
  @rule = aRule
  @position = valid_position(aPosition)
end

Instance Attribute Details

#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::Production (readonly)

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) 


112
113
114
115
116
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 112

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

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

#empty? ⇒ Boolean

Indicate whether the rhs of the rule is empty

Returns:

  • (Boolean) 


48
49
50
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 48

def empty?
  rule.empty?
end

#expecting?(aSymbol) ⇒ Boolean

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

Parameters:

Returns:

  • (Boolean) 


94
95
96
97
98
99
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 94

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 end of rhs

Returns:

  • (Boolean) 


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

def final_pos?
  empty? || position == rule.body.size
end

#initial_pos? ⇒ Boolean

Indicate whether the dot is at the start of rhs

Returns:

  • (Boolean) 


63
64
65
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 63

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

#intermediate_pos? ⇒ Boolean

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

Returns:

  • (Boolean) 


77
78
79
80
81
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 77

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

  position < rule.body.size
end

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

Return the symbol right after the dot (if any)

Returns:



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

def next_symbol
  return nil if empty? || completed?

  rule.body[position]
end

#pre_scan? ⇒ Boolean

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

Returns:

  • (Boolean) 


104
105
106
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 104

def pre_scan?
  next_symbol&.terminal?
end

#state ⇒ Symbol

Terminology inspired from Luger’s book

Returns:

  • (Symbol) —

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



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

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

  position == rule.body.size ? :completed : :partial
end

#to_s ⇒ String

Return a String representation of the dotted item.

Returns:

  • (String) 


40
41
42
43
44
 
# File 'lib/dendroid/grm_analysis/dotted_item.rb', line 40

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