1"""ANTLR3 runtime package""" 2 3# begin[licence] 4# 5# [The "BSD licence"] 6# Copyright (c) 2005-2012 Terence Parr 7# All rights reserved. 8# 9# Redistribution and use in source and binary forms, with or without 10# modification, are permitted provided that the following conditions 11# are met: 12# 1. Redistributions of source code must retain the above copyright 13# notice, this list of conditions and the following disclaimer. 14# 2. Redistributions in binary form must reproduce the above copyright 15# notice, this list of conditions and the following disclaimer in the 16# documentation and/or other materials provided with the distribution. 17# 3. The name of the author may not be used to endorse or promote products 18# derived from this software without specific prior written permission. 19# 20# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 21# IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 22# OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 23# IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 24# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 25# NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 29# THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30# 31# end[licence] 32 33from .constants import EOF 34from .exceptions import NoViableAltException, BacktrackingFailed 35 36 37class DFA(object): 38 """@brief A DFA implemented as a set of transition tables. 39 40 Any state that has a semantic predicate edge is special; those states 41 are generated with if-then-else structures in a specialStateTransition() 42 which is generated by cyclicDFA template. 43 44 """ 45 46 def __init__( 47 self, 48 recognizer, decisionNumber, 49 eot, eof, min, max, accept, special, transition 50 ): 51 ## Which recognizer encloses this DFA? Needed to check backtracking 52 self.recognizer = recognizer 53 54 self.decisionNumber = decisionNumber 55 self.eot = eot 56 self.eof = eof 57 self.min = min 58 self.max = max 59 self.accept = accept 60 self.special = special 61 self.transition = transition 62 63 64 def predict(self, input): 65 """ 66 From the input stream, predict what alternative will succeed 67 using this DFA (representing the covering regular approximation 68 to the underlying CFL). Return an alternative number 1..n. Throw 69 an exception upon error. 70 """ 71 mark = input.mark() 72 s = 0 # we always start at s0 73 try: 74 for _ in range(50000): 75 specialState = self.special[s] 76 if specialState >= 0: 77 s = self.specialStateTransition(specialState, input) 78 if s == -1: 79 self.noViableAlt(s, input) 80 return 0 81 input.consume() 82 continue 83 84 if self.accept[s] >= 1: 85 return self.accept[s] 86 87 # look for a normal char transition 88 c = input.LA(1) 89 90 if c >= self.min[s] and c <= self.max[s]: 91 # move to next state 92 snext = self.transition[s][c-self.min[s]] 93 94 if snext < 0: 95 # was in range but not a normal transition 96 # must check EOT, which is like the else clause. 97 # eot[s]>=0 indicates that an EOT edge goes to another 98 # state. 99 if self.eot[s] >= 0: # EOT Transition to accept state? 100 s = self.eot[s] 101 input.consume() 102 # TODO: I had this as return accept[eot[s]] 103 # which assumed here that the EOT edge always 104 # went to an accept...faster to do this, but 105 # what about predicated edges coming from EOT 106 # target? 107 continue 108 109 self.noViableAlt(s, input) 110 return 0 111 112 s = snext 113 input.consume() 114 continue 115 116 if self.eot[s] >= 0: 117 s = self.eot[s] 118 input.consume() 119 continue 120 121 # EOF Transition to accept state? 122 if c == EOF and self.eof[s] >= 0: 123 return self.accept[self.eof[s]] 124 125 # not in range and not EOF/EOT, must be invalid symbol 126 self.noViableAlt(s, input) 127 return 0 128 129 else: 130 raise RuntimeError("DFA bang!") 131 132 finally: 133 input.rewind(mark) 134 135 136 def noViableAlt(self, s, input): 137 if self.recognizer._state.backtracking > 0: 138 raise BacktrackingFailed 139 140 nvae = NoViableAltException( 141 self.getDescription(), 142 self.decisionNumber, 143 s, 144 input 145 ) 146 147 self.error(nvae) 148 raise nvae 149 150 151 def error(self, nvae): 152 """A hook for debugging interface""" 153 pass 154 155 156 def specialStateTransition(self, s, input): 157 return -1 158 159 160 def getDescription(self): 161 return "n/a" 162 163 164## def specialTransition(self, state, symbol): 165## return 0 166 167 168 @classmethod 169 def unpack(cls, string): 170 """@brief Unpack the runlength encoded table data. 171 172 Terence implemented packed table initializers, because Java has a 173 size restriction on .class files and the lookup tables can grow 174 pretty large. The generated JavaLexer.java of the Java.g example 175 would be about 15MB with uncompressed array initializers. 176 177 Python does not have any size restrictions, but the compilation of 178 such large source files seems to be pretty memory hungry. The memory 179 consumption of the python process grew to >1.5GB when importing a 180 15MB lexer, eating all my swap space and I was to impacient to see, 181 if it could finish at all. With packed initializers that are unpacked 182 at import time of the lexer module, everything works like a charm. 183 184 """ 185 186 ret = [] 187 for i in range(0, len(string) - 1, 2): 188 (n, v) = ord(string[i]), ord(string[i + 1]) 189 190 if v == 0xFFFF: 191 v = -1 192 193 ret += [v] * n 194 195 return ret 196