class ANTLR3::DFA

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.

Attributes

accept[R]
decision[R]
eof[R]
eot[R]
max[R]
min[R]
special[R]
transition[R]
accept[R]
decision_number[R]
eof[R]
eot[R]
max[R]
min[R]
recognizer[R]
special[R]
special_block[R]
transition[R]

Public Class Methods

new( recognizer, decision_number = nil, eot = nil, eof = nil, min = nil, max = nil, accept = nil, special = nil, transition = nil, &special_block ) click to toggle source
# 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
unpack( *data ) click to toggle source
# 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

Public Instance Methods

description() click to toggle source
# File lib/antlr3/dfa.rb, line 316
def description
  return "n/a"
end
error( except ) click to toggle source
# File lib/antlr3/dfa.rb, line 308
def error( except )
  # overridable debugging hook
end
no_viable_alternative( state, input ) click to toggle source
# 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 ) click to toggle source
# 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 ) click to toggle source
# File lib/antlr3/dfa.rb, line 312
def special_state_transition( state, input )
  return -1
end