@if 0
# Preprocessor commands are prefixed by @ to avoid collision with comments
@elif debug
import sys
@endif

# Static definitions
YYEMPTY = -2
YYEOF = 0
YYINITDEPTH = 1000

LEXER_FUNCTIONS = 0

class Parser:
    def __init__(self, verbose=0):
        self.verbose = verbose
        
    def debug_mode(self, flag=None):
        if flag is None:
            return self.verbose

        if type(flag) != type(1):
            raise TypeError('an integer is required')
        self.verbose = flag
        return flag

    def parse(self, text):
        state_stack = [0]*YYINITDEPTH
        value_stack = [0]*YYINITDEPTH

        @if debug
        if self.verbose:
            self.announce("Starting parse\n")
        @endif
        
        lexer_pos = 0
        lexer_end = len(text)
        lexer_state = INITIAL
        lexer_last = 0
        yylval = ''

        yyline = 1
        yycolumn = 1
        
        yystate = 0
        yychar = YYEMPTY        # cause a token to be read
        
        # Initialize stack pointers
        # Waste one element of value and location stack
        # so that they stay on the same level as the state stack.
        # The wasted elements are never initialized.
        state_ptr = -1
        value_ptr = 0
        
        while 1:
            # Push a new state, which is found in yystate.
            # In all cases, when you get here, the value and location stacks
            # have just been pushed.  So pushing a state here evens the stacks.
            state_ptr = state_ptr + 1
            state_stack[state_ptr] = yystate
        
            @if debug
            if self.verbose:
                self.announce("Entering state %d\n", yystate)
            @endif
            
            # Do appropriate processing given the current state.
            # Read a lookahead token if we need one and don't already have one.
        
            # First try to decide what to do without reference to lookahead token.
            yyn = action_idx[yystate]
            if yyn == YYFLAG:
                yyn = default_action[yystate]
                if yyn == 0:
                    self.report_error(yystate, yyline, yycolumn, yylval)
                    return 1
                # Do a reduction. yyn is the number of a rule to reduce with.
                @if debug
                if self.verbose:
                    self.print_reduce(yyn)
                @endif
        
                state_ptr = state_ptr - rhs_size[yyn]
                value_ptr = value_ptr - rhs_size[yyn]
        
                if action_routines[yyn]:
                    yyval = action_routines[yyn](self, value_stack, value_ptr)
                    value_ptr = value_ptr + 1
                    value_stack[value_ptr] = yyval
                else:
                    value_ptr = value_ptr + 1

                @if debug
                if self.verbose:
                    self.print_state_stack(state_stack, state_ptr)
                @endif
        
                # Now "shift" the result of the reduction.
                # Determine what state that goes to, based on the state
                # we popped back to and the rule number reduced by.
        
                yyn = derives[yyn] - YYNTBASE
                yystate = goto_idx[yyn] + state_stack[state_ptr]
                if 0 <= yystate <= YYLAST and yycheck[yystate] == state_stack[state_ptr]:
                    yystate = yytable[yystate]
                else:
                    yystate = default_goto[yyn]
                continue
            
            # Not known => get a lookahead token if don't already have one.
        
            # yychar is either YYEMPTY, YYEOF or a valid token in external form
            if yychar == YYEMPTY:
                @if debug
                if self.verbose:
                    self.announce("Reading a token: ")
                @endif
                # Setup line and column numbers
                for ch in yylval:
                    if ch == '\n':
                        yyline = yyline + 1
                        yycolumn = 1
                    else:
                        yycolumn = yycolumn + 1

                ### Lexical analysis ###
                while lexer_last < lexer_end:
                    lexer_pos = lexer_last
                    @if posix
                    last_match = -1
                    for name, regex in patterns[lexer_state]:
                        match = regex.match(text, lexer_pos)
                        if match:
                            match_text = match.group()
                            match_size = len(match_text)
                            if match_size > last_match:
                                matched = (name, match_text)
                                last_match = match_size
                    if last_match == -1:
                    @else
                    try:
                        match = patterns[lexer_state].match(text, lexer_pos)
                        matched = reduce(lambda result, item:
                                         item[1] is None and result or item,
                                         match.groupdict().items(),
                                         (None, None))
                    except AttributeError:
                    @endif
                        # comes here when match is none, it is an error anyway
                        self.error('No action found for "%s"' % text[lexer_pos:])

                    lexer_last = lexer_last + len(matched[1])
                    lexer_action = pattern_actions[matched[0]]
                    
                    if lexer_action:
                        lexer_state = lexer_action[0] or lexer_state
                        @if debug
                        if self.verbose and lexer_action[0]:
                            self.announce("switching to start condition %d, ", lexer_state)
                        @endif
                        if len(lexer_action) > 1:
                            yylval = matched[1]
                            yychar = lexer_action[1] or ord(yylval)
                            @if debug
                            if self.verbose:
                                self.announce("accepting '%s' (%d)\n", yylval, yychar)
                            @endif
                            break
                        else:
                            # Just a state change, reprocess the text
                            lexer_last = lexer_pos
                    else:
                        # throw away matched text and update position
                        for ch in matched[1]:
                            if ch == '\n':
                                yyline = yyline + 1
                                yycolumn = 1
                            else:
                                yycolumn = yycolumn + 1
                    continue
                else:
                    # Reached end of input
                    yychar = YYEOF
            # Convert token to internal form (in yychar1) for indexing tables with

            if yychar <= 0:
                # This means end-of-input.
                yychar1 = 0
                @if debug
                if self.verbose:
                    self.announce("Now at end of input.\n")
                @endif
            else:
                yychar1 = YYTRANSLATE(yychar)
                @if debug
                if self.verbose:
                    self.announce("Next token is %d (%s)\n", yychar, token_names[yychar1])
                @endif
                yyn = yyn + yychar1

            if yyn < 0 or yyn > YYLAST or  yycheck[yyn] != yychar1:
                # comes here after end of input
                yyn = default_action[yystate]
                if yyn == 0:
                    self.report_error(yystate, yyline, yycolumn, yylval)
                    return None
                # Do a reduction. yyn is the number of a rule to reduce with.
                @if debug
                if self.verbose:
                    self.print_reduce(yyn)
                @endif
        
                state_ptr = state_ptr - rhs_size[yyn]
                value_ptr = value_ptr - rhs_size[yyn]
        
                if action_routines[yyn]:
                    yyval = action_routines[yyn](self, value_stack, value_ptr)
                    value_ptr = value_ptr + 1
                    value_stack[value_ptr] = yyval
                else:
                    value_ptr = value_ptr + 1

                @if debug
                if self.verbose:
                    self.print_state_stack(state_stack, state_ptr)
                @endif
        
                # Now "shift" the result of the reduction.
                # Determine what state that goes to, based on the state
                # we popped back to and the rule number reduced by.
        
                yyn = derives[yyn] - YYNTBASE
                yystate = goto_idx[yyn] + state_stack[state_ptr]
                if 0 <= yystate <= YYLAST and yycheck[yystate] == state_stack[state_ptr]:
                    yystate = yytable[yystate]
                else:
                    yystate = default_goto[yyn]
                continue
            
            yyn = yytable[yyn]
        
            # yyn is what to do for this token type in this state.
            # Negative => reduce, -yyn is rule number.
            # Positive => shift, yyn is new state.
            #   New state is final state => don't bother to shift
            #   just return success.
            # 0, or max negative number => error.
        
            if YYFLAG < yyn < 0:
                yyn = -yyn
                # Do a reduction. yyn is the number of a rule to reduce with.
                @if debug
                if self.verbose:
                    self.print_reduce(yyn)
                @endif
        
                state_ptr = state_ptr - rhs_size[yyn]
                value_ptr = value_ptr - rhs_size[yyn]
        
                if action_routines[yyn]:
                    yyval = action_routines[yyn](self, value_stack, value_ptr)
                    value_ptr = value_ptr + 1
                    value_stack[value_ptr] = yyval
                else:
                    value_ptr = value_ptr + 1

                @if debug
                if self.verbose:
                    self.print_state_stack(state_stack, state_ptr)
                @endif
        
                # Now "shift" the result of the reduction.
                # Determine what state that goes to, based on the state
                # we popped back to and the rule number reduced by.
        
                yyn = derives[yyn] - YYNTBASE
                yystate = goto_idx[yyn] + state_stack[state_ptr]
                if 0 <= yystate <= YYLAST and yycheck[yystate] == state_stack[state_ptr]:
                    yystate = yytable[yystate]
                else:
                    yystate = default_goto[yyn]
                continue
            elif yyn == YYFINAL:
                return value_stack[value_ptr-1]
            elif yyn <= 0:
                # Now it is either 0 or YYFLAG
                self.report_error(yystate, yyline, yycolumn, yylval)
                return None
            
            # Shift the lookahead token.
        
            @if debug
            if self.verbose:
                self.announce("Shifting token %d (%s), ", yychar, token_names[yychar1])
            @endif
 
            if yychar != YYEOF:
                yychar = YYEMPTY
            
            value_ptr = value_ptr + 1
            value_stack[value_ptr] = yylval
        
            yystate = yyn
            continue
        # should never get here
        return None
        
    def report_error(self, state, line, column, lval):
        ruleno = action_idx[state]
        msg = "parse error at line %d, column %d: matched '%s'" % (
            line, column, lval)
        if YYFLAG < ruleno < YYLAST:
            # Start X at -ruleno to avoid negative indexes in yycheck
            start = ruleno < 0 and -ruleno or 0
            first = 1
            for x in range(start, len(token_names)):
                if (x + ruleno) < len(yycheck) and yycheck[x + ruleno] == x:
                    if first:
                        msg = msg + ", expecting"
                        first = 0
                    else:
                        msg = msg + " or"
                    msg = msg + " '%s'" % token_names[x]
        self.error(msg)
        return
        
    def announce(self, format, *args):
        sys.stderr.write(format % args)
        return

    def error(self, format, *args):
        raise SyntaxError(format % args)

    def print_reduce(self, rule):
        sys.stderr.write("Reducing via rule %d (%s), " % (rule, rule_info[rule]))
        # print the symbols being reduced and their result.
        for token in rhs_tokens[rule]:
            sys.stderr.write("%s " % token_names[token])
        sys.stderr.write("-> %s\n" % token_names[derives[rule]])
        return

    def print_state_stack(self, stack, size):
        sys.stderr.write("state stack now")
        for i in range(size+1):
            sys.stderr.write(" %d" % stack[i])
        sys.stderr.write("\n")
        return

new = Parser