Class: ANTLR3::DFA

Inherits:
Object
  • Object
show all
Includes:
Constants, Error
Defined in:
lib/antlr3/dfa.rb

Overview

DFA is a class that implements a finite state machine that chooses between alternatives in a rule based upon lookahead symbols from an input stream.

Deterministic Finite Automata (DFA) are finite state machines that are capable of recognizing regular languages. For more background on the subject, check out en.wikipedia.org/wiki/Deterministic_finite-state_machine or check out general ANTLR documentation at www.antlr.org

ANTLR implements most of its decision logic directly using code branching structures in methods. However, for certain types of decisions, ANTLR will generate a special DFA class definition to implement a decision.

Conceptually, these state machines are defined by a number of states, each state represented by an integer indexed upward from zero. State number 0 is the start state of the machine; every prediction will begin in state 0. At each step, the machine examines the next symbol on the input stream, checks the value against the transition parameters associated with the current state, and either moves to a new state number to repeat the process or decides that the machine cannot transition any further. If the machine cannot transition any further and the current state is defined as an accept state, an alternative has been chosen successfully and the prediction procedure ends. If the current state is not an accept state, the prediction has failed and there is no viable alternative.

In generated code, ANTLR defines DFA states using seven parameters, each defined as a member of seven seperate array constants – MIN, MAX, EOT, EOF, SPECIAL, ACCEPT, and TRANSITION. The parameters that characterize state s are defined by the value of these lists at index s.

MIN

The smallest value of the next input symbol that has a transition for state s

MAX

The largest value of the next input symbol that has a transition for state s

TRANSITION

A list that defines the next state number based upon the current input symbol.

EOT

If positive, it specifies a state transition in situations where a non-matching input symbol does not indicate failure.

SPECIAL

If positive, it indicates that the prediction algorithm must defer to a special code block to determine the next state. The value is used by the special state code to determine the next state.

ACCEPT

If positive and there are no possible state transitions, this is the alternative number that has been predicted

EOF

If positive and the input stream has been exhausted, this is the alternative number that has been predicted.

For more information on the prediction algorithm, check out the #predict method below.

Direct Known Subclasses

Template::GroupFile::Lexer::DFA12

Constant Summary

Constants included from Constants

Constants::BUILT_IN_TOKEN_NAMES, Constants::DEFAULT, Constants::DOWN, Constants::EOF, Constants::EOF_TOKEN, Constants::EOR_TOKEN_TYPE, Constants::HIDDEN, Constants::INVALID, Constants::INVALID_NODE, Constants::INVALID_TOKEN, Constants::MEMO_RULE_FAILED, Constants::MEMO_RULE_UNKNOWN, Constants::MIN_TOKEN_TYPE, Constants::SKIP_TOKEN, Constants::UP

Class Attribute Summary collapse

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Error

EarlyExit, FailedPredicate, MismatchedNotSet, MismatchedRange, MismatchedSet, MismatchedToken, MismatchedTreeNode, MissingToken, NoViableAlternative, RewriteCardinalityError, RewriteEarlyExit, RewriteEmptyStream, UnwantedToken

Constructor Details

#initialize(recognizer, decision_number = nil, eot = nil, eof = nil, min = nil, max = nil, accept = nil, special = nil, transition = nil, &special_block) ⇒ DFA

Returns a new instance of DFA.



144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
 
# File 'lib/antlr3/dfa.rb', line 144

def initialize( recognizer, decision_number = nil,
               eot = nil, eof = nil, min = nil, max = nil,
               accept = nil, special = nil,
               transition = nil, &special_block )
  @recognizer = recognizer
  @decision_number = decision_number || self.class.decision
  @eot = eot || self.class::EOT #.eot
  @eof = eof || self.class::EOF #.eof
  @min = min || self.class::MIN #.min
  @max = max || self.class::MAX #.max
  @accept = accept || self.class::ACCEPT #.accept
  @special = special || self.class::SPECIAL #.special
  @transition = transition || self.class::TRANSITION #.transition
  @special_block = special_block
rescue NameError => e
  raise unless e.message =~ /uninitialized constant/
  constant = e.name
  message = Util.tidy( <<-END )
  | No #{ constant } information provided.
  | DFA cannot be instantiated without providing state array information.
  | When DFAs are generated by ANTLR, this information should already be
  | provided in the DFA subclass constants.
  END
end

Class Attribute Details

.accept ⇒ Object (readonly)

Returns the value of attribute accept.



108
109
110
 
# File 'lib/antlr3/dfa.rb', line 108

def accept
  @accept
end

.decision ⇒ Object (readonly)

Returns the value of attribute decision.



108
109
110
 
# File 'lib/antlr3/dfa.rb', line 108

def decision
  @decision
end

.eof ⇒ Object (readonly)

Returns the value of attribute eof.



108
109
110
 
# File 'lib/antlr3/dfa.rb', line 108

def eof
  @eof
end

.eot ⇒ Object (readonly)

Returns the value of attribute eot.



108
109
110
 
# File 'lib/antlr3/dfa.rb', line 108

def eot
  @eot
end

.max ⇒ Object (readonly)

Returns the value of attribute max.



108
109
110
 
# File 'lib/antlr3/dfa.rb', line 108

def max
  @max
end

.min ⇒ Object (readonly)

Returns the value of attribute min.



108
109
110
 
# File 'lib/antlr3/dfa.rb', line 108

def min
  @min
end

.special ⇒ Object (readonly)

Returns the value of attribute special.



108
109
110
 
# File 'lib/antlr3/dfa.rb', line 108

def special
  @special
end

.transition ⇒ Object (readonly)

Returns the value of attribute transition.



108
109
110
 
# File 'lib/antlr3/dfa.rb', line 108

def transition
  @transition
end

Instance Attribute Details

#accept ⇒ Object (readonly)

Returns the value of attribute accept.



104
105
106
 
# File 'lib/antlr3/dfa.rb', line 104

def accept
  @accept
end

#decision_number ⇒ Object (readonly)

Returns the value of attribute decision_number.



104
105
106
 
# File 'lib/antlr3/dfa.rb', line 104

def decision_number
  @decision_number
end

#eof ⇒ Object (readonly)

Returns the value of attribute eof.



104
105
106
 
# File 'lib/antlr3/dfa.rb', line 104

def eof
  @eof
end

#eot ⇒ Object (readonly)

Returns the value of attribute eot.



104
105
106
 
# File 'lib/antlr3/dfa.rb', line 104

def eot
  @eot
end

#max ⇒ Object (readonly)

Returns the value of attribute max.



104
105
106
 
# File 'lib/antlr3/dfa.rb', line 104

def max
  @max
end

#min ⇒ Object (readonly)

Returns the value of attribute min.



104
105
106
 
# File 'lib/antlr3/dfa.rb', line 104

def min
  @min
end

#recognizer ⇒ Object (readonly)

Returns the value of attribute recognizer.



104
105
106
 
# File 'lib/antlr3/dfa.rb', line 104

def recognizer
  @recognizer
end

#special ⇒ Object (readonly)

Returns the value of attribute special.



104
105
106
 
# File 'lib/antlr3/dfa.rb', line 104

def special
  @special
end

#special_block ⇒ Object (readonly)

Returns the value of attribute special_block.



104
105
106
 
# File 'lib/antlr3/dfa.rb', line 104

def special_block
  @special_block
end

#transition ⇒ Object (readonly)

Returns the value of attribute transition.



104
105
106
 
# File 'lib/antlr3/dfa.rb', line 104

def transition
  @transition
end

Class Method Details

.unpack(*data) ⇒ Object 



111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
 
# File 'lib/antlr3/dfa.rb', line 111

def unpack( *data )
  data.empty? and return [].freeze
  
  n = data.length / 2
  size = 0
  n.times { |i| size += data[ 2*i ] }
  if size > 1024
    values = Hash.new( 0 )
    data.each_slice( 2 ) do |count, value|
      values[ value ] += count
    end
    default = values.keys.max_by { |v| values[ v ] }
    
    unpacked = Hash.new( default )
    position = 0
    data.each_slice( 2 ) do |count, value|
      unless value == default
        count.times { |i| unpacked[ position + i ] = value }
      end
      position += count
    end
  else
    unpacked = []
    data.each_slice( 2 ) do |count, value|
      unpacked.fill( value, unpacked.length, count )
    end
  end
  
  return unpacked
end

Instance Method Details

#description ⇒ Object 



316
317
318
 
# File 'lib/antlr3/dfa.rb', line 316

def description
  return "n/a"
end

#error(except) ⇒ Object 



308
309
310
 
# File 'lib/antlr3/dfa.rb', line 308

def error( except )
  # overridable debugging hook
end

#no_viable_alternative(state, input) ⇒ Object

Raises:



301
302
303
304
305
306
 
# File 'lib/antlr3/dfa.rb', line 301

def no_viable_alternative( state, input )
  raise( BacktrackingFailed ) if @recognizer.state.backtracking > 0
  except = NoViableAlternative.new( description, @decision_number, state, input )
  error( except )
  raise( except )
end

#predict(input) ⇒ Object 



171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
 
# File 'lib/antlr3/dfa.rb', line 171

def predict( input )
  mark = input.mark
  state = 0
  
  50000.times do
    special_state = @special[ state ]
    if special_state >= 0
      state = @special_block.call( special_state )
      if state == -1
        no_viable_alternative( state, input )
        return 0
      end
      input.consume
      next
    end
    @accept[ state ] >= 1 and return @accept[ state ]
    
    # look for a normal char transition
    
    c = input.peek.ord
    # the @min and @max arrays contain the bounds of the character (or token type)
    # ranges for the transition decisions
    if c.between?( @min[ state ], @max[ state ] )
      # c - @min[state] is the position of the character within the range
      # so for a range like ?a..?z, a match of ?a would be 0,
      # ?c would be 2, and ?z would be 25
      next_state = @transition[ state ][ c - @min[ state ] ]
      if next_state < 0
        if @eot[ state ] >= 0
          state = @eot[ state ]
          input.consume
          next
        end
        no_viable_alternative( state, input )
        return 0
      end
      
      state = next_state
      input.consume
      next
    end
    
    if @eot[ state ] >= 0
      state = @eot[ state ]
      input.consume()
      next
    end
    
    ( c == EOF && @eof[ state ] >= 0 ) and return @accept[ @eof[ state ] ]
    no_viable_alternative( state, input )
    return 0
  end
  
  ANTLR3.bug!( Util.tidy( <<-END ) )
  | DFA BANG!
  |   The prediction loop has exceeded a maximum limit of 50000 iterations
  | ----
  | decision: #@decision_number
  | description: #{ description }
  END
ensure
  input.rewind( mark )
end

#special_state_transition(state, input) ⇒ Object 



312
313
314
 
# File 'lib/antlr3/dfa.rb', line 312

def special_state_transition( state, input )
  return -1
end