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