← Back to branch summary

~nchohan/appscale/zk3.3.4

« back to all changes in this revision

Viewing changes to AppServer/google/appengine/_internal/antlr3/recognizers.py

  • Committer: Chris Bunch
  • Date: 2012-02-17 08:19:21 UTC
  • mfrom: (787.2.3 appscale-raj-merge)
  • Revision ID: cgb@cs.ucsb.edu-20120217081921-pakidyksaenlpzur
merged with main branch, gaining rabbitmq and upgrades for hbase, cassandra, and hypertable, as well as upgrading to gae 1.6.1 for python and go

Show diffs side-by-side

added added

removed removed

Lines of Context:
AppServer/google/appengine/_internal/antlr3/recognizers.py
 
1
"""ANTLR3 runtime package"""
 
2
 
 
3
# begin[licence]
 
4
#
 
5
# [The "BSD licence"]
 
6
# Copyright (c) 2005-2008 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
 
 
33
import sys
 
34
import inspect
 
35
 
 
36
from google.appengine._internal.antlr3 import runtime_version, runtime_version_str
 
37
from google.appengine._internal.antlr3.constants import DEFAULT_CHANNEL, HIDDEN_CHANNEL, EOF, EOR_TOKEN_TYPE, INVALID_TOKEN_TYPE
 
38
from google.appengine._internal.antlr3.exceptions import RecognitionException, MismatchedTokenException, MismatchedRangeException, MismatchedTreeNodeException, NoViableAltException, EarlyExitException, MismatchedSetException, MismatchedNotSetException, FailedPredicateException, BacktrackingFailed, UnwantedTokenException, MissingTokenException
 
39
from google.appengine._internal.antlr3.tokens import CommonToken, EOF_TOKEN, SKIP_TOKEN
 
40
from google.appengine._internal.antlr3.compat import set, frozenset, reversed
 
41
 
 
42
 
 
43
class RecognizerSharedState(object):
 
44
    """
 
45
    The set of fields needed by an abstract recognizer to recognize input
 
46
    and recover from errors etc...  As a separate state object, it can be
 
47
    shared among multiple grammars; e.g., when one grammar imports another.
 
48
 
 
49
    These fields are publically visible but the actual state pointer per
 
50
    parser is protected.
 
51
    """
 
52
 
 
53
    def __init__(self):
 
54
        # Track the set of token types that can follow any rule invocation.
 
55
        # Stack grows upwards.
 
56
        self.following = []
 
57
 
 
58
        # This is true when we see an error and before having successfully
 
59
        # matched a token.  Prevents generation of more than one error message
 
60
        # per error.
 
61
        self.errorRecovery = False
 
62
 
 
63
        # The index into the input stream where the last error occurred.
 
64
        # This is used to prevent infinite loops where an error is found
 
65
        # but no token is consumed during recovery...another error is found,
 
66
        # ad naseum.  This is a failsafe mechanism to guarantee that at least
 
67
        # one token/tree node is consumed for two errors.
 
68
        self.lastErrorIndex = -1
 
69
 
 
70
        # If 0, no backtracking is going on.  Safe to exec actions etc...
 
71
        # If >0 then it's the level of backtracking.
 
72
        self.backtracking = 0
 
73
 
 
74
        # An array[size num rules] of Map<Integer,Integer> that tracks
 
75
        # the stop token index for each rule.  ruleMemo[ruleIndex] is
 
76
        # the memoization table for ruleIndex.  For key ruleStartIndex, you
 
77
        # get back the stop token for associated rule or MEMO_RULE_FAILED.
 
78
        #
 
79
        # This is only used if rule memoization is on (which it is by default).
 
80
        self.ruleMemo = None
 
81
 
 
82
        ## Did the recognizer encounter a syntax error?  Track how many.
 
83
        self.syntaxErrors = 0
 
84
 
 
85
 
 
86
        # LEXER FIELDS (must be in same state object to avoid casting
 
87
        # constantly in generated code and Lexer object) :(
 
88
 
 
89
 
 
90
        ## The goal of all lexer rules/methods is to create a token object.
 
91
        # This is an instance variable as multiple rules may collaborate to
 
92
        # create a single token.  nextToken will return this object after
 
93
        # matching lexer rule(s).  If you subclass to allow multiple token
 
94
        # emissions, then set this to the last token to be matched or
 
95
        # something nonnull so that the auto token emit mechanism will not
 
96
        # emit another token.
 
97
        self.token = None
 
98
 
 
99
        ## What character index in the stream did the current token start at?
 
100
        # Needed, for example, to get the text for current token.  Set at
 
101
        # the start of nextToken.
 
102
        self.tokenStartCharIndex = -1
 
103
 
 
104
        ## The line on which the first character of the token resides
 
105
        self.tokenStartLine = None
 
106
 
 
107
        ## The character position of first character within the line
 
108
        self.tokenStartCharPositionInLine = None
 
109
 
 
110
        ## The channel number for the current token
 
111
        self.channel = None
 
112
 
 
113
        ## The token type for the current token
 
114
        self.type = None
 
115
 
 
116
        ## You can set the text for the current token to override what is in
 
117
        # the input char buffer.  Use setText() or can set this instance var.
 
118
        self.text = None
 
119
 
 
120
 
 
121
class BaseRecognizer(object):
 
122
    """
 
123
    @brief Common recognizer functionality.
 
124
 
 
125
    A generic recognizer that can handle recognizers generated from
 
126
    lexer, parser, and tree grammars.  This is all the parsing
 
127
    support code essentially; most of it is error recovery stuff and
 
128
    backtracking.
 
129
    """
 
130
 
 
131
    MEMO_RULE_FAILED = -2
 
132
    MEMO_RULE_UNKNOWN = -1
 
133
 
 
134
    # copies from Token object for convenience in actions
 
135
    DEFAULT_TOKEN_CHANNEL = DEFAULT_CHANNEL
 
136
 
 
137
    # for convenience in actions
 
138
    HIDDEN = HIDDEN_CHANNEL
 
139
 
 
140
    # overridden by generated subclasses
 
141
    tokenNames = None
 
142
 
 
143
    # The antlr_version attribute has been introduced in 3.1. If it is not
 
144
    # overwritten in the generated recognizer, we assume a default of 3.0.1.
 
145
    antlr_version = (3, 0, 1, 0)
 
146
    antlr_version_str = "3.0.1"
 
147
 
 
148
    def __init__(self, state=None):
 
149
        # Input stream of the recognizer. Must be initialized by a subclass.
 
150
        self.input = None
 
151
 
 
152
        ## State of a lexer, parser, or tree parser are collected into a state
 
153
        # object so the state can be shared.  This sharing is needed to
 
154
        # have one grammar import others and share same error variables
 
155
        # and other state variables.  It's a kind of explicit multiple
 
156
        # inheritance via delegation of methods and shared state.
 
157
        if state is None:
 
158
            state = RecognizerSharedState()
 
159
        self._state = state
 
160
 
 
161
        if self.antlr_version > runtime_version:
 
162
            raise RuntimeError(
 
163
                "ANTLR version mismatch: "
 
164
                "The recognizer has been generated by V%s, but this runtime "
 
165
                "is V%s. Please use the V%s runtime or higher."
 
166
                % (self.antlr_version_str,
 
167
                   runtime_version_str,
 
168
                   self.antlr_version_str))
 
169
        elif (self.antlr_version < (3, 1, 0, 0) and
 
170
              self.antlr_version != runtime_version):
 
171
            # FIXME: make the runtime compatible with 3.0.1 codegen
 
172
            # and remove this block.
 
173
            raise RuntimeError(
 
174
                "ANTLR version mismatch: "
 
175
                "The recognizer has been generated by V%s, but this runtime "
 
176
                "is V%s. Please use the V%s runtime."
 
177
                % (self.antlr_version_str,
 
178
                   runtime_version_str,
 
179
                   self.antlr_version_str))
 
180
 
 
181
    # this one only exists to shut up pylint :(
 
182
    def setInput(self, input):
 
183
        self.input = input
 
184
 
 
185
 
 
186
    def reset(self):
 
187
        """
 
188
        reset the parser's state; subclasses must rewinds the input stream
 
189
        """
 
190
 
 
191
        # wack everything related to error recovery
 
192
        if self._state is None:
 
193
            # no shared state work to do
 
194
            return
 
195
 
 
196
        self._state.following = []
 
197
        self._state.errorRecovery = False
 
198
        self._state.lastErrorIndex = -1
 
199
        self._state.syntaxErrors = 0
 
200
        # wack everything related to backtracking and memoization
 
201
        self._state.backtracking = 0
 
202
        if self._state.ruleMemo is not None:
 
203
            self._state.ruleMemo = {}
 
204
 
 
205
 
 
206
    def match(self, input, ttype, follow):
 
207
        """
 
208
        Match current input symbol against ttype.  Attempt
 
209
        single token insertion or deletion error recovery.  If
 
210
        that fails, throw MismatchedTokenException.
 
211
 
 
212
        To turn off single token insertion or deletion error
 
213
        recovery, override mismatchRecover() and have it call
 
214
        plain mismatch(), which does not recover.  Then any error
 
215
        in a rule will cause an exception and immediate exit from
 
216
        rule.  Rule would recover by resynchronizing to the set of
 
217
        symbols that can follow rule ref.
 
218
        """
 
219
 
 
220
        matchedSymbol = self.getCurrentInputSymbol(input)
 
221
        if self.input.LA(1) == ttype:
 
222
            self.input.consume()
 
223
            self._state.errorRecovery = False
 
224
            return matchedSymbol
 
225
 
 
226
        if self._state.backtracking > 0:
 
227
            # FIXME: need to return matchedSymbol here as well. damn!!
 
228
            raise BacktrackingFailed
 
229
 
 
230
        matchedSymbol = self.recoverFromMismatchedToken(input, ttype, follow)
 
231
        return matchedSymbol
 
232
 
 
233
 
 
234
    def matchAny(self, input):
 
235
        """Match the wildcard: in a symbol"""
 
236
 
 
237
        self._state.errorRecovery = False
 
238
        self.input.consume()
 
239
 
 
240
 
 
241
    def mismatchIsUnwantedToken(self, input, ttype):
 
242
        return input.LA(2) == ttype
 
243
 
 
244
 
 
245
    def mismatchIsMissingToken(self, input, follow):
 
246
        if follow is None:
 
247
            # we have no information about the follow; we can only consume
 
248
            # a single token and hope for the best
 
249
            return False
 
250
 
 
251
        # compute what can follow this grammar element reference
 
252
        if EOR_TOKEN_TYPE in follow:
 
253
            if len(self._state.following) > 0:
 
254
                # remove EOR if we're not the start symbol
 
255
                follow = follow - set([EOR_TOKEN_TYPE])
 
256
 
 
257
            viableTokensFollowingThisRule = self.computeContextSensitiveRuleFOLLOW()
 
258
            follow = follow | viableTokensFollowingThisRule
 
259
 
 
260
        # if current token is consistent with what could come after set
 
261
        # then we know we're missing a token; error recovery is free to
 
262
        # "insert" the missing token
 
263
        if input.LA(1) in follow or EOR_TOKEN_TYPE in follow:
 
264
            return True
 
265
 
 
266
        return False
 
267
 
 
268
 
 
269
    def mismatch(self, input, ttype, follow):
 
270
        """
 
271
        Factor out what to do upon token mismatch so tree parsers can behave
 
272
        differently.  Override and call mismatchRecover(input, ttype, follow)
 
273
        to get single token insertion and deletion. Use this to turn of
 
274
        single token insertion and deletion. Override mismatchRecover
 
275
        to call this instead.
 
276
        """
 
277
 
 
278
        if self.mismatchIsUnwantedToken(input, ttype):
 
279
            raise UnwantedTokenException(ttype, input)
 
280
 
 
281
        elif self.mismatchIsMissingToken(input, follow):
 
282
            raise MissingTokenException(ttype, input, None)
 
283
 
 
284
        raise MismatchedTokenException(ttype, input)
 
285
 
 
286
 
 
287
##     def mismatchRecover(self, input, ttype, follow):
 
288
##         if self.mismatchIsUnwantedToken(input, ttype):
 
289
##             mte = UnwantedTokenException(ttype, input)
 
290
 
 
291
##         elif self.mismatchIsMissingToken(input, follow):
 
292
##             mte = MissingTokenException(ttype, input)
 
293
 
 
294
##         else:
 
295
##             mte = MismatchedTokenException(ttype, input)
 
296
 
 
297
##         self.recoverFromMismatchedToken(input, mte, ttype, follow)
 
298
 
 
299
 
 
300
    def reportError(self, e):
 
301
        """Report a recognition problem.
 
302
 
 
303
        This method sets errorRecovery to indicate the parser is recovering
 
304
        not parsing.  Once in recovery mode, no errors are generated.
 
305
        To get out of recovery mode, the parser must successfully match
 
306
        a token (after a resync).  So it will go:
 
307
 
 
308
        1. error occurs
 
309
        2. enter recovery mode, report error
 
310
        3. consume until token found in resynch set
 
311
        4. try to resume parsing
 
312
        5. next match() will reset errorRecovery mode
 
313
 
 
314
        If you override, make sure to update syntaxErrors if you care about
 
315
        that.
 
316
 
 
317
        """
 
318
 
 
319
        # if we've already reported an error and have not matched a token
 
320
        # yet successfully, don't report any errors.
 
321
        if self._state.errorRecovery:
 
322
            return
 
323
 
 
324
        self._state.syntaxErrors += 1 # don't count spurious
 
325
        self._state.errorRecovery = True
 
326
 
 
327
        self.displayRecognitionError(self.tokenNames, e)
 
328
 
 
329
 
 
330
    def displayRecognitionError(self, tokenNames, e):
 
331
        hdr = self.getErrorHeader(e)
 
332
        msg = self.getErrorMessage(e, tokenNames)
 
333
        self.emitErrorMessage(hdr+" "+msg)
 
334
 
 
335
 
 
336
    def getErrorMessage(self, e, tokenNames):
 
337
        """
 
338
        What error message should be generated for the various
 
339
        exception types?
 
340
 
 
341
        Not very object-oriented code, but I like having all error message
 
342
        generation within one method rather than spread among all of the
 
343
        exception classes. This also makes it much easier for the exception
 
344
        handling because the exception classes do not have to have pointers back
 
345
        to this object to access utility routines and so on. Also, changing
 
346
        the message for an exception type would be difficult because you
 
347
        would have to subclassing exception, but then somehow get ANTLR
 
348
        to make those kinds of exception objects instead of the default.
 
349
        This looks weird, but trust me--it makes the most sense in terms
 
350
        of flexibility.
 
351
 
 
352
        For grammar debugging, you will want to override this to add
 
353
        more information such as the stack frame with
 
354
        getRuleInvocationStack(e, this.getClass().getName()) and,
 
355
        for no viable alts, the decision description and state etc...
 
356
 
 
357
        Override this to change the message generated for one or more
 
358
        exception types.
 
359
        """
 
360
 
 
361
        if isinstance(e, UnwantedTokenException):
 
362
            tokenName = "<unknown>"
 
363
            if e.expecting == EOF:
 
364
                tokenName = "EOF"
 
365
 
 
366
            else:
 
367
                tokenName = self.tokenNames[e.expecting]
 
368
 
 
369
            msg = "extraneous input %s expecting %s" % (
 
370
                self.getTokenErrorDisplay(e.getUnexpectedToken()),
 
371
                tokenName
 
372
                )
 
373
 
 
374
        elif isinstance(e, MissingTokenException):
 
375
            tokenName = "<unknown>"
 
376
            if e.expecting == EOF:
 
377
                tokenName = "EOF"
 
378
 
 
379
            else:
 
380
                tokenName = self.tokenNames[e.expecting]
 
381
 
 
382
            msg = "missing %s at %s" % (
 
383
                tokenName, self.getTokenErrorDisplay(e.token)
 
384
                )
 
385
 
 
386
        elif isinstance(e, MismatchedTokenException):
 
387
            tokenName = "<unknown>"
 
388
            if e.expecting == EOF:
 
389
                tokenName = "EOF"
 
390
            else:
 
391
                tokenName = self.tokenNames[e.expecting]
 
392
 
 
393
            msg = "mismatched input " + self.getTokenErrorDisplay(e.token) + " expecting " + tokenName
 
394
 
 
395
        elif isinstance(e, MismatchedTreeNodeException):
 
396
            tokenName = "<unknown>"
 
397
            if e.expecting == EOF:
 
398
                tokenName = "EOF"
 
399
            else:
 
400
                tokenName = self.tokenNames[e.expecting]
 
401
 
 
402
            msg = "mismatched tree node: %s expecting %s" % (e.node, tokenName)
 
403
 
 
404
        elif isinstance(e, NoViableAltException):
 
405
            msg = "no viable alternative at input " + self.getTokenErrorDisplay(e.token)
 
406
 
 
407
        elif isinstance(e, EarlyExitException):
 
408
            msg = "required (...)+ loop did not match anything at input " + self.getTokenErrorDisplay(e.token)
 
409
 
 
410
        elif isinstance(e, MismatchedSetException):
 
411
            msg = "mismatched input " + self.getTokenErrorDisplay(e.token) + " expecting set " + repr(e.expecting)
 
412
 
 
413
        elif isinstance(e, MismatchedNotSetException):
 
414
            msg = "mismatched input " + self.getTokenErrorDisplay(e.token) + " expecting set " + repr(e.expecting)
 
415
 
 
416
        elif isinstance(e, FailedPredicateException):
 
417
            msg = "rule " + e.ruleName + " failed predicate: {" + e.predicateText + "}?"
 
418
 
 
419
        else:
 
420
            msg = str(e)
 
421
 
 
422
        return msg
 
423
 
 
424
 
 
425
    def getNumberOfSyntaxErrors(self):
 
426
        """
 
427
        Get number of recognition errors (lexer, parser, tree parser).  Each
 
428
        recognizer tracks its own number.  So parser and lexer each have
 
429
        separate count.  Does not count the spurious errors found between
 
430
        an error and next valid token match
 
431
 
 
432
        See also reportError()
 
433
        """
 
434
        return self._state.syntaxErrors
 
435
 
 
436
 
 
437
    def getErrorHeader(self, e):
 
438
        """
 
439
        What is the error header, normally line/character position information?
 
440
        """
 
441
 
 
442
        return "line %d:%d" % (e.line, e.charPositionInLine)
 
443
 
 
444
 
 
445
    def getTokenErrorDisplay(self, t):
 
446
        """
 
447
        How should a token be displayed in an error message? The default
 
448
        is to display just the text, but during development you might
 
449
        want to have a lot of information spit out.  Override in that case
 
450
        to use t.toString() (which, for CommonToken, dumps everything about
 
451
        the token). This is better than forcing you to override a method in
 
452
        your token objects because you don't have to go modify your lexer
 
453
        so that it creates a new Java type.
 
454
        """
 
455
 
 
456
        s = t.text
 
457
        if s is None:
 
458
            if t.type == EOF:
 
459
                s = "<EOF>"
 
460
            else:
 
461
                s = "<"+t.type+">"
 
462
 
 
463
        return repr(s)
 
464
 
 
465
 
 
466
    def emitErrorMessage(self, msg):
 
467
        """Override this method to change where error messages go"""
 
468
        sys.stderr.write(msg + '\n')
 
469
 
 
470
 
 
471
    def recover(self, input, re):
 
472
        """
 
473
        Recover from an error found on the input stream.  This is
 
474
        for NoViableAlt and mismatched symbol exceptions.  If you enable
 
475
        single token insertion and deletion, this will usually not
 
476
        handle mismatched symbol exceptions but there could be a mismatched
 
477
        token that the match() routine could not recover from.
 
478
        """
 
479
 
 
480
        # PROBLEM? what if input stream is not the same as last time
 
481
        # perhaps make lastErrorIndex a member of input
 
482
        if self._state.lastErrorIndex == input.index():
 
483
            # uh oh, another error at same token index; must be a case
 
484
            # where LT(1) is in the recovery token set so nothing is
 
485
            # consumed; consume a single token so at least to prevent
 
486
            # an infinite loop; this is a failsafe.
 
487
            input.consume()
 
488
 
 
489
        self._state.lastErrorIndex = input.index()
 
490
        followSet = self.computeErrorRecoverySet()
 
491
 
 
492
        self.beginResync()
 
493
        self.consumeUntil(input, followSet)
 
494
        self.endResync()
 
495
 
 
496
 
 
497
    def beginResync(self):
 
498
        """
 
499
        A hook to listen in on the token consumption during error recovery.
 
500
        The DebugParser subclasses this to fire events to the listenter.
 
501
        """
 
502
 
 
503
        pass
 
504
 
 
505
 
 
506
    def endResync(self):
 
507
        """
 
508
        A hook to listen in on the token consumption during error recovery.
 
509
        The DebugParser subclasses this to fire events to the listenter.
 
510
        """
 
511
 
 
512
        pass
 
513
 
 
514
 
 
515
    def computeErrorRecoverySet(self):
 
516
        """
 
517
        Compute the error recovery set for the current rule.  During
 
518
        rule invocation, the parser pushes the set of tokens that can
 
519
        follow that rule reference on the stack; this amounts to
 
520
        computing FIRST of what follows the rule reference in the
 
521
        enclosing rule. This local follow set only includes tokens
 
522
        from within the rule; i.e., the FIRST computation done by
 
523
        ANTLR stops at the end of a rule.
 
524
 
 
525
        EXAMPLE
 
526
 
 
527
        When you find a "no viable alt exception", the input is not
 
528
        consistent with any of the alternatives for rule r.  The best
 
529
        thing to do is to consume tokens until you see something that
 
530
        can legally follow a call to r *or* any rule that called r.
 
531
        You don't want the exact set of viable next tokens because the
 
532
        input might just be missing a token--you might consume the
 
533
        rest of the input looking for one of the missing tokens.
 
534
 
 
535
        Consider grammar:
 
536
 
 
537
        a : '[' b ']'
 
538
          | '(' b ')'
 
539
          ;
 
540
        b : c '^' INT ;
 
541
        c : ID
 
542
          | INT
 
543
          ;
 
544
 
 
545
        At each rule invocation, the set of tokens that could follow
 
546
        that rule is pushed on a stack.  Here are the various "local"
 
547
        follow sets:
 
548
 
 
549
        FOLLOW(b1_in_a) = FIRST(']') = ']'
 
550
        FOLLOW(b2_in_a) = FIRST(')') = ')'
 
551
        FOLLOW(c_in_b) = FIRST('^') = '^'
 
552
 
 
553
        Upon erroneous input "[]", the call chain is
 
554
 
 
555
        a -> b -> c
 
556
 
 
557
        and, hence, the follow context stack is:
 
558
 
 
559
        depth  local follow set     after call to rule
 
560
          0         \<EOF>                    a (from main())
 
561
          1          ']'                     b
 
562
          3          '^'                     c
 
563
 
 
564
        Notice that ')' is not included, because b would have to have
 
565
        been called from a different context in rule a for ')' to be
 
566
        included.
 
567
 
 
568
        For error recovery, we cannot consider FOLLOW(c)
 
569
        (context-sensitive or otherwise).  We need the combined set of
 
570
        all context-sensitive FOLLOW sets--the set of all tokens that
 
571
        could follow any reference in the call chain.  We need to
 
572
        resync to one of those tokens.  Note that FOLLOW(c)='^' and if
 
573
        we resync'd to that token, we'd consume until EOF.  We need to
 
574
        sync to context-sensitive FOLLOWs for a, b, and c: {']','^'}.
 
575
        In this case, for input "[]", LA(1) is in this set so we would
 
576
        not consume anything and after printing an error rule c would
 
577
        return normally.  It would not find the required '^' though.
 
578
        At this point, it gets a mismatched token error and throws an
 
579
        exception (since LA(1) is not in the viable following token
 
580
        set).  The rule exception handler tries to recover, but finds
 
581
        the same recovery set and doesn't consume anything.  Rule b
 
582
        exits normally returning to rule a.  Now it finds the ']' (and
 
583
        with the successful match exits errorRecovery mode).
 
584
 
 
585
        So, you cna see that the parser walks up call chain looking
 
586
        for the token that was a member of the recovery set.
 
587
 
 
588
        Errors are not generated in errorRecovery mode.
 
589
 
 
590
        ANTLR's error recovery mechanism is based upon original ideas:
 
591
 
 
592
        "Algorithms + Data Structures = Programs" by Niklaus Wirth
 
593
 
 
594
        and
 
595
 
 
596
        "A note on error recovery in recursive descent parsers":
 
597
        http://portal.acm.org/citation.cfm?id=947902.947905
 
598
 
 
599
        Later, Josef Grosch had some good ideas:
 
600
 
 
601
        "Efficient and Comfortable Error Recovery in Recursive Descent
 
602
        Parsers":
 
603
        ftp://www.cocolab.com/products/cocktail/doca4.ps/ell.ps.zip
 
604
 
 
605
        Like Grosch I implemented local FOLLOW sets that are combined
 
606
        at run-time upon error to avoid overhead during parsing.
 
607
        """
 
608
 
 
609
        return self.combineFollows(False)
 
610
 
 
611
 
 
612
    def computeContextSensitiveRuleFOLLOW(self):
 
613
        """
 
614
        Compute the context-sensitive FOLLOW set for current rule.
 
615
        This is set of token types that can follow a specific rule
 
616
        reference given a specific call chain.  You get the set of
 
617
        viable tokens that can possibly come next (lookahead depth 1)
 
618
        given the current call chain.  Contrast this with the
 
619
        definition of plain FOLLOW for rule r:
 
620
 
 
621
         FOLLOW(r)={x | S=>*alpha r beta in G and x in FIRST(beta)}
 
622
 
 
623
        where x in T* and alpha, beta in V*; T is set of terminals and
 
624
        V is the set of terminals and nonterminals.  In other words,
 
625
        FOLLOW(r) is the set of all tokens that can possibly follow
 
626
        references to r in *any* sentential form (context).  At
 
627
        runtime, however, we know precisely which context applies as
 
628
        we have the call chain.  We may compute the exact (rather
 
629
        than covering superset) set of following tokens.
 
630
 
 
631
        For example, consider grammar:
 
632
 
 
633
        stat : ID '=' expr ';'      // FOLLOW(stat)=={EOF}
 
634
             | "return" expr '.'
 
635
             ;
 
636
        expr : atom ('+' atom)* ;   // FOLLOW(expr)=={';','.',')'}
 
637
        atom : INT                  // FOLLOW(atom)=={'+',')',';','.'}
 
638
             | '(' expr ')'
 
639
             ;
 
640
 
 
641
        The FOLLOW sets are all inclusive whereas context-sensitive
 
642
        FOLLOW sets are precisely what could follow a rule reference.
 
643
        For input input "i=(3);", here is the derivation:
 
644
 
 
645
        stat => ID '=' expr ';'
 
646
             => ID '=' atom ('+' atom)* ';'
 
647
             => ID '=' '(' expr ')' ('+' atom)* ';'
 
648
             => ID '=' '(' atom ')' ('+' atom)* ';'
 
649
             => ID '=' '(' INT ')' ('+' atom)* ';'
 
650
             => ID '=' '(' INT ')' ';'
 
651
 
 
652
        At the "3" token, you'd have a call chain of
 
653
 
 
654
          stat -> expr -> atom -> expr -> atom
 
655
 
 
656
        What can follow that specific nested ref to atom?  Exactly ')'
 
657
        as you can see by looking at the derivation of this specific
 
658
        input.  Contrast this with the FOLLOW(atom)={'+',')',';','.'}.
 
659
 
 
660
        You want the exact viable token set when recovering from a
 
661
        token mismatch.  Upon token mismatch, if LA(1) is member of
 
662
        the viable next token set, then you know there is most likely
 
663
        a missing token in the input stream.  "Insert" one by just not
 
664
        throwing an exception.
 
665
        """
 
666
 
 
667
        return self.combineFollows(True)
 
668
 
 
669
 
 
670
    def combineFollows(self, exact):
 
671
        followSet = set()
 
672
        for idx, localFollowSet in reversed(list(enumerate(self._state.following))):
 
673
            followSet |= localFollowSet
 
674
            if exact:
 
675
                # can we see end of rule?
 
676
                if EOR_TOKEN_TYPE in localFollowSet:
 
677
                    # Only leave EOR in set if at top (start rule); this lets
 
678
                    # us know if have to include follow(start rule); i.e., EOF
 
679
                    if idx > 0:
 
680
                        followSet.remove(EOR_TOKEN_TYPE)
 
681
 
 
682
                else:
 
683
                    # can't see end of rule, quit
 
684
                    break
 
685
 
 
686
        return followSet
 
687
 
 
688
 
 
689
    def recoverFromMismatchedToken(self, input, ttype, follow):
 
690
        """Attempt to recover from a single missing or extra token.
 
691
 
 
692
        EXTRA TOKEN
 
693
 
 
694
        LA(1) is not what we are looking for.  If LA(2) has the right token,
 
695
        however, then assume LA(1) is some extra spurious token.  Delete it
 
696
        and LA(2) as if we were doing a normal match(), which advances the
 
697
        input.
 
698
 
 
699
        MISSING TOKEN
 
700
 
 
701
        If current token is consistent with what could come after
 
702
        ttype then it is ok to 'insert' the missing token, else throw
 
703
        exception For example, Input 'i=(3;' is clearly missing the
 
704
        ')'.  When the parser returns from the nested call to expr, it
 
705
        will have call chain:
 
706
 
 
707
          stat -> expr -> atom
 
708
 
 
709
        and it will be trying to match the ')' at this point in the
 
710
        derivation:
 
711
 
 
712
             => ID '=' '(' INT ')' ('+' atom)* ';'
 
713
                                ^
 
714
        match() will see that ';' doesn't match ')' and report a
 
715
        mismatched token error.  To recover, it sees that LA(1)==';'
 
716
        is in the set of tokens that can follow the ')' token
 
717
        reference in rule atom.  It can assume that you forgot the ')'.
 
718
        """
 
719
 
 
720
        e = None
 
721
 
 
722
        # if next token is what we are looking for then "delete" this token
 
723
        if self. mismatchIsUnwantedToken(input, ttype):
 
724
            e = UnwantedTokenException(ttype, input)
 
725
 
 
726
            self.beginResync()
 
727
            input.consume() # simply delete extra token
 
728
            self.endResync()
 
729
 
 
730
            # report after consuming so AW sees the token in the exception
 
731
            self.reportError(e)
 
732
 
 
733
            # we want to return the token we're actually matching
 
734
            matchedSymbol = self.getCurrentInputSymbol(input)
 
735
 
 
736
            # move past ttype token as if all were ok
 
737
            input.consume()
 
738
            return matchedSymbol
 
739
 
 
740
        # can't recover with single token deletion, try insertion
 
741
        if self.mismatchIsMissingToken(input, follow):
 
742
            inserted = self.getMissingSymbol(input, e, ttype, follow)
 
743
            e = MissingTokenException(ttype, input, inserted)
 
744
 
 
745
            # report after inserting so AW sees the token in the exception
 
746
            self.reportError(e)
 
747
            return inserted
 
748
 
 
749
        # even that didn't work; must throw the exception
 
750
        e = MismatchedTokenException(ttype, input)
 
751
        raise e
 
752
 
 
753
 
 
754
    def recoverFromMismatchedSet(self, input, e, follow):
 
755
        """Not currently used"""
 
756
 
 
757
        if self.mismatchIsMissingToken(input, follow):
 
758
            self.reportError(e)
 
759
            # we don't know how to conjure up a token for sets yet
 
760
            return self.getMissingSymbol(input, e, INVALID_TOKEN_TYPE, follow)
 
761
 
 
762
        # TODO do single token deletion like above for Token mismatch
 
763
        raise e
 
764
 
 
765
 
 
766
    def getCurrentInputSymbol(self, input):
 
767
        """
 
768
        Match needs to return the current input symbol, which gets put
 
769
        into the label for the associated token ref; e.g., x=ID.  Token
 
770
        and tree parsers need to return different objects. Rather than test
 
771
        for input stream type or change the IntStream interface, I use
 
772
        a simple method to ask the recognizer to tell me what the current
 
773
        input symbol is.
 
774
 
 
775
        This is ignored for lexers.
 
776
        """
 
777
 
 
778
        return None
 
779
 
 
780
 
 
781
    def getMissingSymbol(self, input, e, expectedTokenType, follow):
 
782
        """Conjure up a missing token during error recovery.
 
783
 
 
784
        The recognizer attempts to recover from single missing
 
785
        symbols. But, actions might refer to that missing symbol.
 
786
        For example, x=ID {f($x);}. The action clearly assumes
 
787
        that there has been an identifier matched previously and that
 
788
        $x points at that token. If that token is missing, but
 
789
        the next token in the stream is what we want we assume that
 
790
        this token is missing and we keep going. Because we
 
791
        have to return some token to replace the missing token,
 
792
        we have to conjure one up. This method gives the user control
 
793
        over the tokens returned for missing tokens. Mostly,
 
794
        you will want to create something special for identifier
 
795
        tokens. For literals such as '{' and ',', the default
 
796
        action in the parser or tree parser works. It simply creates
 
797
        a CommonToken of the appropriate type. The text will be the token.
 
798
        If you change what tokens must be created by the lexer,
 
799
        override this method to create the appropriate tokens.
 
800
        """
 
801
 
 
802
        return None
 
803
 
 
804
 
 
805
##     def recoverFromMissingElement(self, input, e, follow):
 
806
##         """
 
807
##         This code is factored out from mismatched token and mismatched set
 
808
##         recovery.  It handles "single token insertion" error recovery for
 
809
##         both.  No tokens are consumed to recover from insertions.  Return
 
810
##         true if recovery was possible else return false.
 
811
##         """
 
812
 
 
813
##         if self.mismatchIsMissingToken(input, follow):
 
814
##             self.reportError(e)
 
815
##             return True
 
816
 
 
817
##         # nothing to do; throw exception
 
818
##         return False
 
819
 
 
820
 
 
821
    def consumeUntil(self, input, tokenTypes):
 
822
        """
 
823
        Consume tokens until one matches the given token or token set
 
824
 
 
825
        tokenTypes can be a single token type or a set of token types
 
826
 
 
827
        """
 
828
 
 
829
        if not isinstance(tokenTypes, (set, frozenset)):
 
830
            tokenTypes = frozenset([tokenTypes])
 
831
 
 
832
        ttype = input.LA(1)
 
833
        while ttype != EOF and ttype not in tokenTypes:
 
834
            input.consume()
 
835
            ttype = input.LA(1)
 
836
 
 
837
 
 
838
    def getRuleInvocationStack(self):
 
839
        """
 
840
        Return List<String> of the rules in your parser instance
 
841
        leading up to a call to this method.  You could override if
 
842
        you want more details such as the file/line info of where
 
843
        in the parser java code a rule is invoked.
 
844
 
 
845
        This is very useful for error messages and for context-sensitive
 
846
        error recovery.
 
847
 
 
848
        You must be careful, if you subclass a generated recognizers.
 
849
        The default implementation will only search the module of self
 
850
        for rules, but the subclass will not contain any rules.
 
851
        You probably want to override this method to look like
 
852
 
 
853
        def getRuleInvocationStack(self):
 
854
            return self._getRuleInvocationStack(<class>.__module__)
 
855
 
 
856
        where <class> is the class of the generated recognizer, e.g.
 
857
        the superclass of self.
 
858
        """
 
859
 
 
860
        return self._getRuleInvocationStack(self.__module__)
 
861
 
 
862
 
 
863
    def _getRuleInvocationStack(cls, module):
 
864
        """
 
865
        A more general version of getRuleInvocationStack where you can
 
866
        pass in, for example, a RecognitionException to get it's rule
 
867
        stack trace.  This routine is shared with all recognizers, hence,
 
868
        static.
 
869
 
 
870
        TODO: move to a utility class or something; weird having lexer call
 
871
        this
 
872
        """
 
873
 
 
874
        # mmmhhh,... perhaps look at the first argument
 
875
        # (f_locals[co_varnames[0]]?) and test if it's a (sub)class of
 
876
        # requested recognizer...
 
877
 
 
878
        rules = []
 
879
        for frame in reversed(inspect.stack()):
 
880
            code = frame[0].f_code
 
881
            codeMod = inspect.getmodule(code)
 
882
            if codeMod is None:
 
883
                continue
 
884
 
 
885
            # skip frames not in requested module
 
886
            if codeMod.__name__ != module:
 
887
                continue
 
888
 
 
889
            # skip some unwanted names
 
890
            if code.co_name in ('nextToken', '<module>'):
 
891
                continue
 
892
 
 
893
            rules.append(code.co_name)
 
894
 
 
895
        return rules
 
896
 
 
897
    _getRuleInvocationStack = classmethod(_getRuleInvocationStack)
 
898
 
 
899
 
 
900
    def getBacktrackingLevel(self):
 
901
        return self._state.backtracking
 
902
 
 
903
 
 
904
    def getGrammarFileName(self):
 
905
        """For debugging and other purposes, might want the grammar name.
 
906
 
 
907
        Have ANTLR generate an implementation for this method.
 
908
        """
 
909
 
 
910
        return self.grammarFileName
 
911
 
 
912
 
 
913
    def getSourceName(self):
 
914
        raise NotImplementedError
 
915
 
 
916
 
 
917
    def toStrings(self, tokens):
 
918
        """A convenience method for use most often with template rewrites.
 
919
 
 
920
        Convert a List<Token> to List<String>
 
921
        """
 
922
 
 
923
        if tokens is None:
 
924
            return None
 
925
 
 
926
        return [token.text for token in tokens]
 
927
 
 
928
 
 
929
    def getRuleMemoization(self, ruleIndex, ruleStartIndex):
 
930
        """
 
931
        Given a rule number and a start token index number, return
 
932
        MEMO_RULE_UNKNOWN if the rule has not parsed input starting from
 
933
        start index.  If this rule has parsed input starting from the
 
934
        start index before, then return where the rule stopped parsing.
 
935
        It returns the index of the last token matched by the rule.
 
936
        """
 
937
 
 
938
        if ruleIndex not in self._state.ruleMemo:
 
939
            self._state.ruleMemo[ruleIndex] = {}
 
940
 
 
941
        return self._state.ruleMemo[ruleIndex].get(
 
942
            ruleStartIndex, self.MEMO_RULE_UNKNOWN
 
943
            )
 
944
 
 
945
 
 
946
    def alreadyParsedRule(self, input, ruleIndex):
 
947
        """
 
948
        Has this rule already parsed input at the current index in the
 
949
        input stream?  Return the stop token index or MEMO_RULE_UNKNOWN.
 
950
        If we attempted but failed to parse properly before, return
 
951
        MEMO_RULE_FAILED.
 
952
 
 
953
        This method has a side-effect: if we have seen this input for
 
954
        this rule and successfully parsed before, then seek ahead to
 
955
        1 past the stop token matched for this rule last time.
 
956
        """
 
957
 
 
958
        stopIndex = self.getRuleMemoization(ruleIndex, input.index())
 
959
        if stopIndex == self.MEMO_RULE_UNKNOWN:
 
960
            return False
 
961
 
 
962
        if stopIndex == self.MEMO_RULE_FAILED:
 
963
            raise BacktrackingFailed
 
964
 
 
965
        else:
 
966
            input.seek(stopIndex + 1)
 
967
 
 
968
        return True
 
969
 
 
970
 
 
971
    def memoize(self, input, ruleIndex, ruleStartIndex, success):
 
972
        """
 
973
        Record whether or not this rule parsed the input at this position
 
974
        successfully.
 
975
        """
 
976
 
 
977
        if success:
 
978
            stopTokenIndex = input.index() - 1
 
979
        else:
 
980
            stopTokenIndex = self.MEMO_RULE_FAILED
 
981
 
 
982
        if ruleIndex in self._state.ruleMemo:
 
983
            self._state.ruleMemo[ruleIndex][ruleStartIndex] = stopTokenIndex
 
984
 
 
985
 
 
986
    def traceIn(self, ruleName, ruleIndex, inputSymbol):
 
987
        sys.stdout.write("enter %s %s" % (ruleName, inputSymbol))
 
988
 
 
989
##         if self._state.failed:
 
990
##             sys.stdout.write(" failed=%s" % self._state.failed)
 
991
 
 
992
        if self._state.backtracking > 0:
 
993
            sys.stdout.write(" backtracking=%s" % self._state.backtracking)
 
994
 
 
995
        sys.stdout.write('\n')
 
996
 
 
997
 
 
998
    def traceOut(self, ruleName, ruleIndex, inputSymbol):
 
999
        sys.stdout.write("exit %s %s" % (ruleName, inputSymbol))
 
1000
 
 
1001
##         if self._state.failed:
 
1002
##             sys.stdout.write(" failed=%s" % self._state.failed)
 
1003
 
 
1004
        if self._state.backtracking > 0:
 
1005
            sys.stdout.write(" backtracking=%s" % self._state.backtracking)
 
1006
 
 
1007
        sys.stdout.write('\n')
 
1008
 
 
1009
 
 
1010
 
 
1011
class TokenSource(object):
 
1012
    """
 
1013
    @brief Abstract baseclass for token producers.
 
1014
 
 
1015
    A source of tokens must provide a sequence of tokens via nextToken()
 
1016
    and also must reveal it's source of characters; CommonToken's text is
 
1017
    computed from a CharStream; it only store indices into the char stream.
 
1018
 
 
1019
    Errors from the lexer are never passed to the parser.  Either you want
 
1020
    to keep going or you do not upon token recognition error.  If you do not
 
1021
    want to continue lexing then you do not want to continue parsing.  Just
 
1022
    throw an exception not under RecognitionException and Java will naturally
 
1023
    toss you all the way out of the recognizers.  If you want to continue
 
1024
    lexing then you should not throw an exception to the parser--it has already
 
1025
    requested a token.  Keep lexing until you get a valid one.  Just report
 
1026
    errors and keep going, looking for a valid token.
 
1027
    """
 
1028
 
 
1029
    def nextToken(self):
 
1030
        """Return a Token object from your input stream (usually a CharStream).
 
1031
 
 
1032
        Do not fail/return upon lexing error; keep chewing on the characters
 
1033
        until you get a good one; errors are not passed through to the parser.
 
1034
        """
 
1035
 
 
1036
        raise NotImplementedError
 
1037
 
 
1038
 
 
1039
    def __iter__(self):
 
1040
        """The TokenSource is an interator.
 
1041
 
 
1042
        The iteration will not include the final EOF token, see also the note
 
1043
        for the next() method.
 
1044
 
 
1045
        """
 
1046
 
 
1047
        return self
 
1048
 
 
1049
 
 
1050
    def next(self):
 
1051
        """Return next token or raise StopIteration.
 
1052
 
 
1053
        Note that this will raise StopIteration when hitting the EOF token,
 
1054
        so EOF will not be part of the iteration.
 
1055
 
 
1056
        """
 
1057
 
 
1058
        token = self.nextToken()
 
1059
        if token is None or token.type == EOF:
 
1060
            raise StopIteration
 
1061
        return token
 
1062
 
 
1063
 
 
1064
class Lexer(BaseRecognizer, TokenSource):
 
1065
    """
 
1066
    @brief Baseclass for generated lexer classes.
 
1067
 
 
1068
    A lexer is recognizer that draws input symbols from a character stream.
 
1069
    lexer grammars result in a subclass of this object. A Lexer object
 
1070
    uses simplified match() and error recovery mechanisms in the interest
 
1071
    of speed.
 
1072
    """
 
1073
 
 
1074
    def __init__(self, input, state=None):
 
1075
        BaseRecognizer.__init__(self, state)
 
1076
        TokenSource.__init__(self)
 
1077
 
 
1078
        # Where is the lexer drawing characters from?
 
1079
        self.input = input
 
1080
 
 
1081
 
 
1082
    def reset(self):
 
1083
        BaseRecognizer.reset(self) # reset all recognizer state variables
 
1084
 
 
1085
        if self.input is not None:
 
1086
            # rewind the input
 
1087
            self.input.seek(0)
 
1088
 
 
1089
        if self._state is None:
 
1090
            # no shared state work to do
 
1091
            return
 
1092
 
 
1093
        # wack Lexer state variables
 
1094
        self._state.token = None
 
1095
        self._state.type = INVALID_TOKEN_TYPE
 
1096
        self._state.channel = DEFAULT_CHANNEL
 
1097
        self._state.tokenStartCharIndex = -1
 
1098
        self._state.tokenStartLine = -1
 
1099
        self._state.tokenStartCharPositionInLine = -1
 
1100
        self._state.text = None
 
1101
 
 
1102
 
 
1103
    def nextToken(self):
 
1104
        """
 
1105
        Return a token from this source; i.e., match a token on the char
 
1106
        stream.
 
1107
        """
 
1108
 
 
1109
        while 1:
 
1110
            self._state.token = None
 
1111
            self._state.channel = DEFAULT_CHANNEL
 
1112
            self._state.tokenStartCharIndex = self.input.index()
 
1113
            self._state.tokenStartCharPositionInLine = self.input.charPositionInLine
 
1114
            self._state.tokenStartLine = self.input.line
 
1115
            self._state.text = None
 
1116
            if self.input.LA(1) == EOF:
 
1117
                return EOF_TOKEN
 
1118
 
 
1119
            try:
 
1120
                self.mTokens()
 
1121
 
 
1122
                if self._state.token is None:
 
1123
                    self.emit()
 
1124
 
 
1125
                elif self._state.token == SKIP_TOKEN:
 
1126
                    continue
 
1127
 
 
1128
                return self._state.token
 
1129
 
 
1130
            except NoViableAltException, re:
 
1131
                self.reportError(re)
 
1132
                self.recover(re) # throw out current char and try again
 
1133
 
 
1134
            except RecognitionException, re:
 
1135
                self.reportError(re)
 
1136
                # match() routine has already called recover()
 
1137
 
 
1138
 
 
1139
    def skip(self):
 
1140
        """
 
1141
        Instruct the lexer to skip creating a token for current lexer rule
 
1142
        and look for another token.  nextToken() knows to keep looking when
 
1143
        a lexer rule finishes with token set to SKIP_TOKEN.  Recall that
 
1144
        if token==null at end of any token rule, it creates one for you
 
1145
        and emits it.
 
1146
        """
 
1147
 
 
1148
        self._state.token = SKIP_TOKEN
 
1149
 
 
1150
 
 
1151
    def mTokens(self):
 
1152
        """This is the lexer entry point that sets instance var 'token'"""
 
1153
 
 
1154
        # abstract method
 
1155
        raise NotImplementedError
 
1156
 
 
1157
 
 
1158
    def setCharStream(self, input):
 
1159
        """Set the char stream and reset the lexer"""
 
1160
        self.input = None
 
1161
        self.reset()
 
1162
        self.input = input
 
1163
 
 
1164
 
 
1165
    def getSourceName(self):
 
1166
        return self.input.getSourceName()
 
1167
 
 
1168
 
 
1169
    def emit(self, token=None):
 
1170
        """
 
1171
        The standard method called to automatically emit a token at the
 
1172
        outermost lexical rule.  The token object should point into the
 
1173
        char buffer start..stop.  If there is a text override in 'text',
 
1174
        use that to set the token's text.  Override this method to emit
 
1175
        custom Token objects.
 
1176
 
 
1177
        If you are building trees, then you should also override
 
1178
        Parser or TreeParser.getMissingSymbol().
 
1179
        """
 
1180
 
 
1181
        if token is None:
 
1182
            token = CommonToken(
 
1183
                input=self.input,
 
1184
                type=self._state.type,
 
1185
                channel=self._state.channel,
 
1186
                start=self._state.tokenStartCharIndex,
 
1187
                stop=self.getCharIndex()-1
 
1188
                )
 
1189
            token.line = self._state.tokenStartLine
 
1190
            token.text = self._state.text
 
1191
            token.charPositionInLine = self._state.tokenStartCharPositionInLine
 
1192
 
 
1193
        self._state.token = token
 
1194
 
 
1195
        return token
 
1196
 
 
1197
 
 
1198
    def match(self, s):
 
1199
        if isinstance(s, basestring):
 
1200
            for c in s:
 
1201
                if self.input.LA(1) != ord(c):
 
1202
                    if self._state.backtracking > 0:
 
1203
                        raise BacktrackingFailed
 
1204
 
 
1205
                    mte = MismatchedTokenException(c, self.input)
 
1206
                    self.recover(mte)
 
1207
                    raise mte
 
1208
 
 
1209
                self.input.consume()
 
1210
 
 
1211
        else:
 
1212
            if self.input.LA(1) != s:
 
1213
                if self._state.backtracking > 0:
 
1214
                    raise BacktrackingFailed
 
1215
 
 
1216
                mte = MismatchedTokenException(unichr(s), self.input)
 
1217
                self.recover(mte) # don't really recover; just consume in lexer
 
1218
                raise mte
 
1219
 
 
1220
            self.input.consume()
 
1221
 
 
1222
 
 
1223
    def matchAny(self):
 
1224
        self.input.consume()
 
1225
 
 
1226
 
 
1227
    def matchRange(self, a, b):
 
1228
        if self.input.LA(1) < a or self.input.LA(1) > b:
 
1229
            if self._state.backtracking > 0:
 
1230
                raise BacktrackingFailed
 
1231
 
 
1232
            mre = MismatchedRangeException(unichr(a), unichr(b), self.input)
 
1233
            self.recover(mre)
 
1234
            raise mre
 
1235
 
 
1236
        self.input.consume()
 
1237
 
 
1238
 
 
1239
    def getLine(self):
 
1240
        return self.input.line
 
1241
 
 
1242
 
 
1243
    def getCharPositionInLine(self):
 
1244
        return self.input.charPositionInLine
 
1245
 
 
1246
 
 
1247
    def getCharIndex(self):
 
1248
        """What is the index of the current character of lookahead?"""
 
1249
 
 
1250
        return self.input.index()
 
1251
 
 
1252
 
 
1253
    def getText(self):
 
1254
        """
 
1255
        Return the text matched so far for the current token or any
 
1256
        text override.
 
1257
        """
 
1258
        if self._state.text is not None:
 
1259
            return self._state.text
 
1260
 
 
1261
        return self.input.substring(
 
1262
            self._state.tokenStartCharIndex,
 
1263
            self.getCharIndex()-1
 
1264
            )
 
1265
 
 
1266
 
 
1267
    def setText(self, text):
 
1268
        """
 
1269
        Set the complete text of this token; it wipes any previous
 
1270
        changes to the text.
 
1271
        """
 
1272
        self._state.text = text
 
1273
 
 
1274
 
 
1275
    text = property(getText, setText)
 
1276
 
 
1277
 
 
1278
    def reportError(self, e):
 
1279
        ## TODO: not thought about recovery in lexer yet.
 
1280
 
 
1281
        ## # if we've already reported an error and have not matched a token
 
1282
        ## # yet successfully, don't report any errors.
 
1283
        ## if self.errorRecovery:
 
1284
        ##     #System.err.print("[SPURIOUS] ");
 
1285
        ##     return;
 
1286
        ##
 
1287
        ## self.errorRecovery = True
 
1288
 
 
1289
        self.displayRecognitionError(self.tokenNames, e)
 
1290
 
 
1291
 
 
1292
    def getErrorMessage(self, e, tokenNames):
 
1293
        msg = None
 
1294
 
 
1295
        if isinstance(e, MismatchedTokenException):
 
1296
            msg = "mismatched character " + self.getCharErrorDisplay(e.c) + " expecting " + self.getCharErrorDisplay(e.expecting)
 
1297
 
 
1298
        elif isinstance(e, NoViableAltException):
 
1299
            msg = "no viable alternative at character " + self.getCharErrorDisplay(e.c)
 
1300
 
 
1301
        elif isinstance(e, EarlyExitException):
 
1302
            msg = "required (...)+ loop did not match anything at character " + self.getCharErrorDisplay(e.c)
 
1303
 
 
1304
        elif isinstance(e, MismatchedNotSetException):
 
1305
            msg = "mismatched character " + self.getCharErrorDisplay(e.c) + " expecting set " + repr(e.expecting)
 
1306
 
 
1307
        elif isinstance(e, MismatchedSetException):
 
1308
            msg = "mismatched character " + self.getCharErrorDisplay(e.c) + " expecting set " + repr(e.expecting)
 
1309
 
 
1310
        elif isinstance(e, MismatchedRangeException):
 
1311
            msg = "mismatched character " + self.getCharErrorDisplay(e.c) + " expecting set " + self.getCharErrorDisplay(e.a) + ".." + self.getCharErrorDisplay(e.b)
 
1312
 
 
1313
        else:
 
1314
            msg = BaseRecognizer.getErrorMessage(self, e, tokenNames)
 
1315
 
 
1316
        return msg
 
1317
 
 
1318
 
 
1319
    def getCharErrorDisplay(self, c):
 
1320
        if c == EOF:
 
1321
            c = '<EOF>'
 
1322
        return repr(c)
 
1323
 
 
1324
 
 
1325
    def recover(self, re):
 
1326
        """
 
1327
        Lexers can normally match any char in it's vocabulary after matching
 
1328
        a token, so do the easy thing and just kill a character and hope
 
1329
        it all works out.  You can instead use the rule invocation stack
 
1330
        to do sophisticated error recovery if you are in a fragment rule.
 
1331
        """
 
1332
 
 
1333
        self.input.consume()
 
1334
 
 
1335
 
 
1336
    def traceIn(self, ruleName, ruleIndex):
 
1337
        inputSymbol = "%s line=%d:%s" % (self.input.LT(1),
 
1338
                                         self.getLine(),
 
1339
                                         self.getCharPositionInLine()
 
1340
                                         )
 
1341
 
 
1342
        BaseRecognizer.traceIn(self, ruleName, ruleIndex, inputSymbol)
 
1343
 
 
1344
 
 
1345
    def traceOut(self, ruleName, ruleIndex):
 
1346
        inputSymbol = "%s line=%d:%s" % (self.input.LT(1),
 
1347
                                         self.getLine(),
 
1348
                                         self.getCharPositionInLine()
 
1349
                                         )
 
1350
 
 
1351
        BaseRecognizer.traceOut(self, ruleName, ruleIndex, inputSymbol)
 
1352
 
 
1353
 
 
1354
 
 
1355
class Parser(BaseRecognizer):
 
1356
    """
 
1357
    @brief Baseclass for generated parser classes.
 
1358
    """
 
1359
 
 
1360
    def __init__(self, lexer, state=None):
 
1361
        BaseRecognizer.__init__(self, state)
 
1362
 
 
1363
        self.setTokenStream(lexer)
 
1364
 
 
1365
 
 
1366
    def reset(self):
 
1367
        BaseRecognizer.reset(self) # reset all recognizer state variables
 
1368
        if self.input is not None:
 
1369
            self.input.seek(0) # rewind the input
 
1370
 
 
1371
 
 
1372
    def getCurrentInputSymbol(self, input):
 
1373
        return input.LT(1)
 
1374
 
 
1375
 
 
1376
    def getMissingSymbol(self, input, e, expectedTokenType, follow):
 
1377
        if expectedTokenType == EOF:
 
1378
            tokenText = "<missing EOF>"
 
1379
        else:
 
1380
            tokenText = "<missing " + self.tokenNames[expectedTokenType] + ">"
 
1381
        t = CommonToken(type=expectedTokenType, text=tokenText)
 
1382
        current = input.LT(1)
 
1383
        if current.type == EOF:
 
1384
            current = input.LT(-1)
 
1385
 
 
1386
        if current is not None:
 
1387
            t.line = current.line
 
1388
            t.charPositionInLine = current.charPositionInLine
 
1389
        t.channel = DEFAULT_CHANNEL
 
1390
        return t
 
1391
 
 
1392
 
 
1393
    def setTokenStream(self, input):
 
1394
        """Set the token stream and reset the parser"""
 
1395
 
 
1396
        self.input = None
 
1397
        self.reset()
 
1398
        self.input = input
 
1399
 
 
1400
 
 
1401
    def getTokenStream(self):
 
1402
        return self.input
 
1403
 
 
1404
 
 
1405
    def getSourceName(self):
 
1406
        return self.input.getSourceName()
 
1407
 
 
1408
 
 
1409
    def traceIn(self, ruleName, ruleIndex):
 
1410
        BaseRecognizer.traceIn(self, ruleName, ruleIndex, self.input.LT(1))
 
1411
 
 
1412
 
 
1413
    def traceOut(self, ruleName, ruleIndex):
 
1414
        BaseRecognizer.traceOut(self, ruleName, ruleIndex, self.input.LT(1))
 
1415
 
 
1416
 
 
1417
class RuleReturnScope(object):
 
1418
    """
 
1419
    Rules can return start/stop info as well as possible trees and templates.
 
1420
    """
 
1421
 
 
1422
    def getStart(self):
 
1423
        """Return the start token or tree."""
 
1424
        return None
 
1425
 
 
1426
 
 
1427
    def getStop(self):
 
1428
        """Return the stop token or tree."""
 
1429
        return None
 
1430
 
 
1431
 
 
1432
    def getTree(self):
 
1433
        """Has a value potentially if output=AST."""
 
1434
        return None
 
1435
 
 
1436
 
 
1437
    def getTemplate(self):
 
1438
        """Has a value potentially if output=template."""
 
1439
        return None
 
1440
 
 
1441
 
 
1442
class ParserRuleReturnScope(RuleReturnScope):
 
1443
    """
 
1444
    Rules that return more than a single value must return an object
 
1445
    containing all the values.  Besides the properties defined in
 
1446
    RuleLabelScope.predefinedRulePropertiesScope there may be user-defined
 
1447
    return values.  This class simply defines the minimum properties that
 
1448
    are always defined and methods to access the others that might be
 
1449
    available depending on output option such as template and tree.
 
1450
 
 
1451
    Note text is not an actual property of the return value, it is computed
 
1452
    from start and stop using the input stream's toString() method.  I
 
1453
    could add a ctor to this so that we can pass in and store the input
 
1454
    stream, but I'm not sure we want to do that.  It would seem to be undefined
 
1455
    to get the .text property anyway if the rule matches tokens from multiple
 
1456
    input streams.
 
1457
 
 
1458
    I do not use getters for fields of objects that are used simply to
 
1459
    group values such as this aggregate.  The getters/setters are there to
 
1460
    satisfy the superclass interface.
 
1461
    """
 
1462
 
 
1463
    def __init__(self):
 
1464
        self.start = None
 
1465
        self.stop = None
 
1466
 
 
1467
 
 
1468
    def getStart(self):
 
1469
        return self.start
 
1470
 
 
1471
 
 
1472
    def getStop(self):
 
1473
        return self.stop
 
1474