| #!/usr/bin/ruby |
| # encoding: utf-8 |
| |
| =begin LICENSE |
| |
| [The "BSD licence"] |
| Copyright (c) 2009-2010 Kyle Yetter |
| All rights reserved. |
| |
| Redistribution and use in source and binary forms, with or without |
| modification, are permitted provided that the following conditions |
| are met: |
| |
| 1. Redistributions of source code must retain the above copyright |
| notice, this list of conditions and the following disclaimer. |
| 2. Redistributions in binary form must reproduce the above copyright |
| notice, this list of conditions and the following disclaimer in the |
| documentation and/or other materials provided with the distribution. |
| 3. The name of the author may not be used to endorse or promote products |
| derived from this software without specific prior written permission. |
| |
| THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
| IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
| IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
| INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
| THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| =end |
| |
| module ANTLR3 |
| |
| =begin rdoc 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 <i>regular languages</i>. For more background on the subject, |
| check out http://en.wikipedia.org/wiki/Deterministic_finite-state_machine or |
| check out general ANTLR documentation at http://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 |
| <i>start state</i> 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 <i>accept state</i>, an |
| alternative has been chosen successfully and the prediction procedure ends. If |
| the current state is not an <i>accept state</i>, the prediction has failed and |
| there is <i>no viable alternative</i>. |
| |
| 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[s]:: |
| The smallest value of the next input symbol that has |
| a transition for state +s+ |
| MAX[s]:: |
| The largest value of the next input symbol that has |
| a transition for state +s+ |
| TRANSITION[s]:: |
| A list that defines the next state number based upon |
| the current input symbol. |
| EOT[s]:: |
| If positive, it specifies a state transition in |
| situations where a non-matching input symbol does |
| not indicate failure. |
| SPECIAL[s]:: |
| 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[s]:: |
| If positive and there are no possible state |
| transitions, this is the alternative number |
| that has been predicted |
| EOF[s]:: |
| 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. |
| |
| =end |
| |
| class DFA |
| include Constants |
| include Error |
| |
| attr_reader :recognizer, :decision_number, :eot, :eof, :min, :max, |
| :accept, :special, :transition, :special_block |
| |
| class << self |
| attr_reader :decision, :eot, :eof, :min, :max, |
| :accept, :special, :transition |
| |
| 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 |
| |
| end |
| |
| 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 |
| |
| if RUBY_VERSION =~ /^1\.9/ |
| |
| 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 |
| |
| else |
| |
| 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 |
| # 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 |
| |
| end |
| |
| 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 |
| |
| def error( except ) |
| # overridable debugging hook |
| end |
| |
| def special_state_transition( state, input ) |
| return -1 |
| end |
| |
| def description |
| return "n/a" |
| end |
| end |
| end |
