Bug 231381, fix for LPG backtracking parser performance problem

12 files changed, 1033 insertions, 30 deletions

diff --git a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/core/dom/lrparser/lpgextensions/FixedBacktrackingParser.java b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/core/dom/lrparser/lpgextensions/FixedBacktrackingParser.java
new file mode 100644
index 00000000000..e002668fdba
--- /dev/null
+++ b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/core/dom/lrparser/lpgextensions/FixedBacktrackingParser.java
@@ -0,0 +1,703 @@
+/*******************************************************************************
+ * Copyright (c) 2006, 2008 IBM Corporation and others.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *     IBM Corporation - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.cdt.core.dom.lrparser.lpgextensions;
+
+import lpg.lpgjavaruntime.BadParseException;
+import lpg.lpgjavaruntime.BadParseSymFileException;
+import lpg.lpgjavaruntime.ConfigurationElement;
+import lpg.lpgjavaruntime.ConfigurationStack;
+import lpg.lpgjavaruntime.IntTuple;
+import lpg.lpgjavaruntime.Monitor;
+import lpg.lpgjavaruntime.NotBacktrackParseTableException;
+import lpg.lpgjavaruntime.ParseTable;
+import lpg.lpgjavaruntime.PrsStream;
+import lpg.lpgjavaruntime.RuleAction;
+import lpg.lpgjavaruntime.Stacks;
+import lpg.lpgjavaruntime.TokenStream;
+
+public class FixedBacktrackingParser extends Stacks
+{
+    private Monitor monitor = null;
+    private int START_STATE,
+                NUM_RULES,
+                LA_STATE_OFFSET,
+                EOFT_SYMBOL,
+                ERROR_SYMBOL,
+                ACCEPT_ACTION,
+                ERROR_ACTION;
+
+    private int lastToken,
+                currentAction;
+    private TokenStream tokStream;
+    private ParseTable prs;
+    private RuleAction ra;
+    private IntTuple action = new IntTuple(1 << 10),
+                     tokens;
+    private int actionStack[];
+    private boolean skipTokens = false;	// true if error productions are used to skip tokens
+
+    //
+    // Override the getToken function in Stacks.
+    //
+    public final int getToken(int i)
+    {
+        return tokens.get(locationStack[stateStackTop + (i - 1)]);
+    }
+
+    public final int getCurrentRule()     { return currentAction; }
+    public final int getFirstToken()      { return tokStream.getFirstErrorToken(getToken(1)); }
+    public final int getFirstToken(int i) { return tokStream.getFirstErrorToken(getToken(i)); }
+    public final int getLastToken()       { return tokStream.getLastErrorToken(lastToken); }
+    public final int getLastToken(int i)  { int l = (i >= prs.rhs(currentAction)
+                                                        ? lastToken
+                                                        : tokens.get(locationStack[stateStackTop + i] - 1));
+                                            return tokStream.getLastErrorToken(l);
+                                          }
+
+    public FixedBacktrackingParser(TokenStream tokStream, ParseTable prs, RuleAction ra) throws BadParseSymFileException,
+                                                                                           NotBacktrackParseTableException
+    {
+        this.tokStream = (PrsStream) tokStream;
+        this.prs = prs;
+        this.ra = ra;
+
+        START_STATE = prs.getStartState();
+        NUM_RULES = prs.getNumRules();
+        LA_STATE_OFFSET = prs.getLaStateOffset();
+        EOFT_SYMBOL = prs.getEoftSymbol();
+        ERROR_SYMBOL = prs.getErrorSymbol();
+        ACCEPT_ACTION = prs.getAcceptAction();
+        ERROR_ACTION = prs.getErrorAction();
+
+        if (! prs.isValidForParser()) throw new BadParseSymFileException();
+        if (! prs.getBacktrack()) throw new NotBacktrackParseTableException();
+    }
+
+    public FixedBacktrackingParser(Monitor monitor, TokenStream tokStream, ParseTable prs, RuleAction ra) throws BadParseSymFileException,
+                                                                                                            NotBacktrackParseTableException
+    {
+        this(tokStream, prs, ra);
+        this.monitor = monitor;
+    }
+
+    //
+    // Allocate or reallocate all the stacks. Their sizes should always be the same.
+    //
+    public void reallocateOtherStacks(int start_token_index)
+    {
+        // assert(super.stateStack != null);
+        if (this.actionStack == null)
+        {
+            this.actionStack = new int[super.stateStack.length];
+            super.locationStack = new int[super.stateStack.length];
+            super.parseStack = new Object[super.stateStack.length];
+
+            actionStack[0] = 0;
+            locationStack[0] = start_token_index;
+        }
+        else if (this.actionStack.length < super.stateStack.length)
+        {
+            int old_length = this.actionStack.length;
+
+            System.arraycopy(this.actionStack, 0, this.actionStack = new int[super.stateStack.length], 0, old_length);
+            System.arraycopy(super.locationStack, 0, super.locationStack = new int[super.stateStack.length], 0, old_length);
+            System.arraycopy(super.parseStack, 0, super.parseStack = new Object[super.stateStack.length], 0, old_length);
+        }
+        return;
+    }
+
+    //
+    // Parse without attempting any Error token recovery
+    //
+    public Object parse() throws BadParseException
+    {
+        // without an argument parse() will ignore error productions
+    	return parse(0);
+    }
+
+    //
+    // Parse input allowing up to max_error_count Error token recoveries.
+    // When max_error_count is 0, no Error token recoveries occur.
+    // When max_error is > 0, it limits the number of Error token recoveries.
+    // When max_error is < 0, the number of error token recoveries is unlimited.
+    // Also, such recoveries only require one token to be parsed beyond the recovery point.
+    // (normally two tokens beyond the recovery point must be parsed)
+    // Thus, a negative max_error_count should be used when error productions are used to 
+    // skip tokens.
+    //
+    public Object parse(int max_error_count) throws BadParseException
+    {
+        action.reset();
+        tokStream.reset(); // Position at first token.
+        reallocateStateStack();
+        stateStackTop = 0;
+        stateStack[0] = START_STATE;
+        skipTokens = max_error_count < 0;
+
+        //
+        // The tuple tokens will eventually contain the sequence 
+        // of tokens that resulted in a successful parse. We leave
+        // it up to the "Stream" implementer to define the predecessor
+        // of the first token as he sees fit.
+        //
+        tokens = new IntTuple(tokStream.getStreamLength());
+        tokens.add(tokStream.getPrevious(tokStream.peek()));
+
+        int repair_token = 0,
+            start_token_index = tokStream.peek(),
+            start_action_index = action.size(), // obviously 0
+            temp_stack[] = new int[1];
+        temp_stack[0] = START_STATE;
+        int initial_error_token = backtrackParse(repair_token);
+        for (int error_token = initial_error_token, count = 0;
+             error_token != 0;
+             error_token = backtrackParse(repair_token), count++)
+        {
+            if (count == max_error_count)
+                throw new BadParseException(initial_error_token);
+            action.reset(start_action_index);
+            tokStream.reset(start_token_index);
+            stateStackTop = temp_stack.length - 1;
+            System.arraycopy(temp_stack, 0, stateStack, 0, temp_stack.length);
+            reallocateOtherStacks(start_token_index);
+
+            backtrackParseUpToError(repair_token, error_token);
+
+            for (stateStackTop = findRecoveryStateIndex(stateStackTop);
+                 stateStackTop >= 0;
+                 stateStackTop = findRecoveryStateIndex(stateStackTop - 1))
+            {
+                int recovery_token = tokens.get(locationStack[stateStackTop] - 1);
+                repair_token = errorRepair((recovery_token >= start_token_index ? recovery_token : error_token), error_token);
+                if (repair_token != 0)
+                    break;
+            }
+
+            if (stateStackTop < 0)
+                throw new BadParseException(initial_error_token);
+
+            temp_stack = new int[stateStackTop + 1];
+            System.arraycopy(stateStack, 0, temp_stack, 0, temp_stack.length);
+
+            start_action_index = action.size();
+            start_token_index = tokStream.peek();
+        }
+
+        if (repair_token != 0)
+            tokens.add(repair_token);
+        int t;
+        for (t = start_token_index; tokStream.getKind(t) != EOFT_SYMBOL; t = tokStream.getNext(t))
+            tokens.add(t);
+        tokens.add(t);
+
+        return parseActions();
+    }
+
+    //
+    // Process reductions and continue...
+    //
+    private final void process_reductions()
+    {
+        do
+        {
+            stateStackTop -= (prs.rhs(currentAction) - 1);
+            ra.ruleAction(currentAction);
+            currentAction = prs.ntAction(stateStack[stateStackTop], prs.lhs(currentAction));
+        } while(currentAction <= NUM_RULES);
+        return;
+    }
+
+    //
+    // Now do the final parse of the input based on the actions in
+    // the list "action" and the sequence of tokens in list "tokens".
+    //
+    private Object parseActions() throws BadParseException
+    {
+        int ti = -1,
+            curtok;
+        lastToken = tokens.get(++ti);
+        curtok = tokens.get(++ti);
+        allocateOtherStacks();
+
+        //
+        // Reparse the input...
+        //
+        stateStackTop = -1;
+        currentAction = START_STATE;
+        for (int i = 0; i < action.size(); i++)
+        {
+            //
+            // if the parser needs to stop processing,
+            // it may do so here.
+            //
+            if (monitor != null && monitor.isCancelled())
+                return null;
+
+            stateStack[++stateStackTop] = currentAction;
+            locationStack[stateStackTop] = ti;
+
+            currentAction = action.get(i);
+            if (currentAction <= NUM_RULES)  // a reduce action?
+            {
+                stateStackTop--; // make reduction look like shift-reduction
+                process_reductions();
+            }
+            else                   // a shift or shift-reduce action
+            {
+                lastToken = curtok;
+                curtok = tokens.get(++ti);
+                if (currentAction > ERROR_ACTION) // a shift-reduce action?
+                {
+                    currentAction -= ERROR_ACTION;
+                    process_reductions();
+                }
+            }
+        }
+
+        return parseStack[0];
+    }
+
+    //
+    // Process reductions and continue...
+    //
+    private int process_backtrack_reductions(int act)
+    {
+        do
+        {
+            stateStackTop -= (prs.rhs(act) - 1);
+            act = prs.ntAction(stateStack[stateStackTop], prs.lhs(act));
+        } while(act <= NUM_RULES);
+
+        return act;
+    }
+
+    //
+    // Parse the input until either the parse completes successfully or
+    // an error is encountered. This function returns an integer that
+    // represents the last action that was executed by the parser. If
+    // the parse was succesful, then the tuple "action" contains the
+    // successful sequence of actions that was executed.
+    //
+    private int backtrackParse(int initial_token)
+    {
+        //
+        // Allocate configuration stack.
+        //
+        ConfigurationStack configuration_stack = new ConfigurationStack(prs);
+
+        //
+        // Keep parsing until we successfully reach the end of file or
+        // an error is encountered. The list of actions executed will
+        // be stored in the "action" tuple.
+        //
+        int error_token = 0,
+            maxStackTop = stateStackTop,
+            start_token = tokStream.peek(),
+            curtok = (initial_token > 0 ? initial_token : tokStream.getToken()),
+            current_kind = tokStream.getKind(curtok),
+            act = tAction(stateStack[stateStackTop], current_kind);
+
+        //
+        // The main driver loop
+        //
+        for (;;)
+        {
+            //
+            // if the parser needs to stop processing,
+            // it may do so here.
+            //
+            if (monitor != null && monitor.isCancelled())
+                return 0;
+
+            if (act <= NUM_RULES)
+            {
+                action.add(act); // save this reduce action
+                stateStackTop--;
+                act = process_backtrack_reductions(act);
+            }
+            else if (act > ERROR_ACTION)
+            {
+                action.add(act);     // save this shift-reduce action
+                curtok = tokStream.getToken();
+                current_kind = tokStream.getKind(curtok);
+                act = process_backtrack_reductions(act - ERROR_ACTION);
+            }
+            else if (act < ACCEPT_ACTION)
+            {
+                action.add(act);    // save this shift action
+                curtok = tokStream.getToken();
+                current_kind = tokStream.getKind(curtok);
+            }
+            else if (act == ERROR_ACTION)
+            {
+                error_token = (error_token > curtok ? error_token : curtok);
+
+                ConfigurationElement configuration = configuration_stack.pop();
+                if (configuration == null)
+                     act = ERROR_ACTION;
+                else
+                {
+                    action.reset(configuration.action_length);
+                    act = configuration.act;
+                    curtok = configuration.curtok;
+                    current_kind = tokStream.getKind(curtok);
+                    tokStream.reset(curtok == initial_token
+                                            ? start_token
+                                            : tokStream.getNext(curtok));
+                    stateStackTop = configuration.stack_top;
+                    configuration.retrieveStack(stateStack);
+                    continue;
+                }
+                break;
+            }
+            else if (act > ACCEPT_ACTION)
+            {
+                if (configuration_stack.findConfiguration(stateStack, stateStackTop, curtok))
+                    act = ERROR_ACTION;
+                else
+                {
+                    configuration_stack.push(stateStack, stateStackTop, act + 1, curtok, action.size());
+                    act = prs.baseAction(act);
+                    maxStackTop = stateStackTop > maxStackTop ? stateStackTop : maxStackTop;
+                }
+                continue;
+            }
+            else break; // assert(act == ACCEPT_ACTION);
+            try
+            {
+                stateStack[++stateStackTop] = act;
+            }
+            catch(IndexOutOfBoundsException e)
+            {
+                reallocateStateStack();
+                stateStack[stateStackTop] = act;
+            }
+
+            act = tAction(act, current_kind);
+        }
+
+        //System.out.println("****Number of configurations: " + configuration_stack.configurationSize());
+        //System.out.println("****Number of elements in stack tree: " + configuration_stack.numStateElements());
+        //System.out.println("****Number of elements in stacks: " + configuration_stack.stacksSize());
+        //System.out.println("****Number of actions: " + action.size());
+        //System.out.println("****Max Stack Size = " + maxStackTop);
+        //System.out.flush();
+        return (act == ERROR_ACTION ? error_token : 0);
+    }
+
+    private void backtrackParseUpToError(int initial_token, int error_token)
+    {
+        //
+        // Allocate configuration stack.
+        //
+        ConfigurationStack configuration_stack = new ConfigurationStack(prs);
+
+        //
+        // Keep parsing until we successfully reach the end of file or
+        // an error is encountered. The list of actions executed will
+        // be stored in the "action" tuple.
+        //
+        int start_token = tokStream.peek(),
+            curtok = (initial_token > 0 ? initial_token : tokStream.getToken()),
+            current_kind = tokStream.getKind(curtok),
+            act = tAction(stateStack[stateStackTop], current_kind);
+
+        tokens.add(curtok);
+        locationStack[stateStackTop] = tokens.size();
+        actionStack[stateStackTop] = action.size();
+
+        for (;;)
+        {
+            //
+            // if the parser needs to stop processing,
+            // it may do so here.
+            //
+            if (monitor != null && monitor.isCancelled())
+                return;
+
+            if (act <= NUM_RULES)
+            {
+                action.add(act); // save this reduce action
+                stateStackTop--;
+                act = process_backtrack_reductions(act);
+            }
+            else if (act > ERROR_ACTION)
+            {
+                action.add(act);     // save this shift-reduce action
+                curtok = tokStream.getToken();
+                current_kind = tokStream.getKind(curtok);
+                tokens.add(curtok);
+                act = process_backtrack_reductions(act - ERROR_ACTION);
+            }
+            else if (act < ACCEPT_ACTION)
+            {
+                action.add(act);     // save this shift action
+                curtok = tokStream.getToken();
+                current_kind = tokStream.getKind(curtok);
+                tokens.add(curtok);
+            }
+            else if (act == ERROR_ACTION)
+            {
+                if (curtok != error_token)
+                {
+                    ConfigurationElement configuration = configuration_stack.pop();
+                    if (configuration == null)
+                        act = ERROR_ACTION;
+                    else
+                    {
+                        action.reset(configuration.action_length);
+                        act = configuration.act;
+                        int next_token_index = configuration.curtok;
+                        tokens.reset(next_token_index);
+                        curtok = tokens.get(next_token_index - 1);
+                        current_kind = tokStream.getKind(curtok);
+                        tokStream.reset(curtok == initial_token
+                                                ? start_token
+                                                : tokStream.getNext(curtok));
+                        stateStackTop = configuration.stack_top;
+                        configuration.retrieveStack(stateStack);
+                        locationStack[stateStackTop] = tokens.size();
+                        actionStack[stateStackTop] = action.size();
+                        continue;
+                    }
+                }
+                break;
+            }
+            else if (act > ACCEPT_ACTION)
+            {
+                if (configuration_stack.findConfiguration(stateStack, stateStackTop, tokens.size()))
+                    act = ERROR_ACTION;
+                else
+                {
+                    configuration_stack.push(stateStack, stateStackTop, act + 1, tokens.size(), action.size());
+                    act = prs.baseAction(act);
+                }
+                continue;
+            }
+            else break; // assert(act == ACCEPT_ACTION);
+
+            stateStack[++stateStackTop] = act; // no need to check if out of bounds
+            locationStack[stateStackTop] = tokens.size();
+            actionStack[stateStackTop] = action.size();
+            act = tAction(act, current_kind);
+        }
+
+        // assert(curtok == error_token);
+
+        return;
+    }
+
+    private boolean repairable(int error_token)
+    {
+        //
+        // Allocate configuration stack.
+        //
+        ConfigurationStack configuration_stack = new ConfigurationStack(prs);
+
+        //
+        // Keep parsing until we successfully reach the end of file or
+        // an error is encountered. The list of actions executed will
+        // be stored in the "action" tuple.
+        //
+        int start_token = tokStream.peek(),
+            final_token = tokStream.getStreamLength(), // unreachable
+            curtok = 0,
+            current_kind = ERROR_SYMBOL,
+            act = tAction(stateStack[stateStackTop], current_kind);
+
+        for (;;)
+        {
+            if (act <= NUM_RULES)
+            {
+                stateStackTop--;
+                act = process_backtrack_reductions(act);
+            }
+            else if (act > ERROR_ACTION)
+            {
+                curtok = tokStream.getToken();
+                if (curtok > final_token) return true;
+                current_kind = tokStream.getKind(curtok);
+                act = process_backtrack_reductions(act - ERROR_ACTION);
+            }
+            else if (act < ACCEPT_ACTION)
+            {
+                curtok = tokStream.getToken();
+                if (curtok > final_token) return true;
+                current_kind = tokStream.getKind(curtok);
+            }
+            else if (act == ERROR_ACTION)
+            {
+                ConfigurationElement configuration = configuration_stack.pop();
+                if (configuration == null)
+                     act = ERROR_ACTION;
+                else
+                {
+                    stateStackTop = configuration.stack_top;
+                    configuration.retrieveStack(stateStack);
+                    act = configuration.act;
+                    curtok = configuration.curtok;
+                    if (curtok == 0)
+                    {
+                        current_kind = ERROR_SYMBOL;
+                        tokStream.reset(start_token);
+                    }
+                    else
+                    {
+                        current_kind = tokStream.getKind(curtok);
+                        tokStream.reset(tokStream.getNext(curtok));
+                    }
+                    continue;
+                }
+                break;
+            }
+            else if (act > ACCEPT_ACTION)
+            {
+                if (configuration_stack.findConfiguration(stateStack, stateStackTop, curtok))
+                    act = ERROR_ACTION;
+                else
+                {
+                    configuration_stack.push(stateStack, stateStackTop, act + 1, curtok, 0);
+                    act = prs.baseAction(act);
+                }
+                continue;
+            }
+            else break; // assert(act == ACCEPT_ACTION);
+            try
+            {
+                //
+                // We consider a configuration to be acceptable for recovery
+                // if we are able to consume enough symbols in the remainining
+                // tokens to reach another potential recovery point past the
+                // original error token.
+                //
+                if ((curtok > error_token) && (final_token == tokStream.getStreamLength()))
+                {
+                    //
+                    // If the ERROR_SYMBOL is a valid Action Adjunct in the state
+                    // "act" then we set the terminating token as the successor of
+                    // the current token. I.e., we have to be able to parse at least
+                    // two tokens past the resynch point before we claim victory.
+                    //
+                    if (recoverableState(act))
+                        final_token = skipTokens ? curtok : tokStream.getNext(curtok);
+                }
+
+                stateStack[++stateStackTop] = act;
+            }
+            catch(IndexOutOfBoundsException e)
+            {
+                reallocateStateStack();
+                stateStack[stateStackTop] = act;
+            }
+
+            act = tAction(act, current_kind);
+        }
+
+        //
+        // If we can reach the end of the input successfully, we claim victory.
+        //
+        return (act == ACCEPT_ACTION);
+    }
+
+    private boolean recoverableState(int state)
+    {
+        for (int k = prs.asi(state); prs.asr(k) != 0; k++)
+        {
+           if (prs.asr(k) == ERROR_SYMBOL)
+                return true;
+        }
+        return false;
+    }
+
+    private int findRecoveryStateIndex(int start_index)
+    {
+        int i;
+        for (i = start_index; i >= 0; i--)
+        {
+            //
+            // If the ERROR_SYMBOL is an Action Adjunct in state stateStack[i]
+            // then chose i as the index of the state to recover on.
+            //
+            if (recoverableState(stateStack[i]))
+                break;
+        }
+
+        if (i >= 0) // if a recoverable state, remove null reductions, if any.
+        {
+            int k;
+            for (k = i - 1; k >= 0; k--)
+            {
+                if (locationStack[k] != locationStack[i])
+                    break;
+            }
+            i = k + 1;
+        }
+
+        return i;
+    }
+
+    private int errorRepair(int recovery_token, int error_token)
+    {
+        int temp_stack[] = new int[stateStackTop + 1];
+        System.arraycopy(stateStack, 0, temp_stack, 0, temp_stack.length);
+        for (;
+             tokStream.getKind(recovery_token) != EOFT_SYMBOL;
+             recovery_token = tokStream.getNext(recovery_token))
+        {
+            tokStream.reset(recovery_token);
+            if (repairable(error_token))
+                break;
+            stateStackTop = temp_stack.length - 1;
+            System.arraycopy(temp_stack, 0, stateStack, 0, temp_stack.length);
+        }
+
+        if (tokStream.getKind(recovery_token) == EOFT_SYMBOL)
+        {
+            tokStream.reset(recovery_token);
+            if (! repairable(error_token))
+            {
+                stateStackTop = temp_stack.length - 1;
+                System.arraycopy(temp_stack, 0, stateStack, 0, temp_stack.length);
+                return 0;
+            }
+        }
+
+        //
+        //
+        //
+        stateStackTop = temp_stack.length - 1;
+        System.arraycopy(temp_stack, 0, stateStack, 0, temp_stack.length);
+        tokStream.reset(recovery_token);
+        tokens.reset(locationStack[stateStackTop] - 1);
+        action.reset(actionStack[stateStackTop]);
+
+        return tokStream.makeErrorToken(tokens.get(locationStack[stateStackTop] - 1),
+                                        tokStream.getPrevious(recovery_token),
+                                        error_token,
+                                        ERROR_SYMBOL);
+    }
+
+    private int tAction(int act, int sym)
+    {
+        act = prs.tAction(act, sym);
+        if (act > LA_STATE_OFFSET)
+        {
+            int next_token = tokStream.peek();
+            act = prs.lookAhead(act - LA_STATE_OFFSET, tokStream.getKind(next_token));
+            while(act > LA_STATE_OFFSET)
+            {
+                next_token = tokStream.getNext(next_token);
+                act = prs.lookAhead(act - LA_STATE_OFFSET, tokStream.getKind(next_token));
+            }
+        }
+        return act;
+    }
+}
diff --git a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/core/dom/lrparser/lpgextensions/FixedBtParserTemplateD.g b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/core/dom/lrparser/lpgextensions/FixedBtParserTemplateD.g
new file mode 100644
index 00000000000..fc1ef554201
--- /dev/null
+++ b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/core/dom/lrparser/lpgextensions/FixedBtParserTemplateD.g
@@ -0,0 +1,290 @@
+----------------------------------------------------------------------------------
+-- Copyright (c) 2006, 2008 IBM Corporation and others.
+-- All rights reserved. This program and the accompanying materials
+-- are made available under the terms of the Eclipse Public License v1.0
+-- which accompanies this distribution, and is available at
+-- http://www.eclipse.org/legal/epl_v10.html
+--
+-- Contributors:
+--     IBM Corporation - initial API and implementation
+----------------------------------------------------------------------------------
+
+--
+-- In a parser using this template, the following macro may be redefined:
+--
+--     $additional_interfaces
+--     $ast_class
+--
+-- B E G I N N I N G   O F   T E M P L A T E   btParserTemplateD
+--
+%Options programming_language=java,margin=4,backtrack
+%Options table,error_maps,scopes
+%options prefix=TK_,
+%options action=("*.java", "/.", "./")
+%options ParseTable=lpg.lpgjavaruntime.ParseTable
+
+--
+-- This template requires that the name of the EOF token be set
+-- to EOF_TOKEN to be consistent with LexerTemplateD and LexerTemplateE
+--
+$EOF
+    EOF_TOKEN
+$End
+
+$ERROR
+    ERROR_TOKEN
+$End
+
+$Define
+
+    $Header
+    /.
+                //
+                // Rule $rule_number:  $rule_text
+                //./
+
+    $BeginAction
+    /. $Header
+                case $rule_number: {./
+
+    $EndAction
+    /.          break;
+                }./
+
+    $BeginJava
+    /.$BeginAction
+                    $symbol_declarations./
+
+    $EndJava /.$EndAction./
+
+    $NoAction
+    /. $Header
+                case $rule_number:
+                    break;./
+
+    $BadAction
+    /. $Header
+                case $rule_number:
+                    throw new Error("No action specified for rule " + $rule_number);./
+
+    $NullAction
+    /. $Header
+                case $rule_number:
+                    setResult(null);
+                    break;./
+
+    $BeginActions
+    /.
+        public void ruleAction(int ruleNumber)
+        {
+            switch (ruleNumber)
+            {./
+
+    $SplitActions
+    /.
+	            default:
+	                ruleAction$rule_number(ruleNumber);
+	                break;
+	        }
+	        return;
+	    }
+	
+	    public void ruleAction$rule_number(int ruleNumber)
+	    {
+	        switch (ruleNumber)
+	        {./
+
+    $EndActions
+    /.
+                default:
+                    break;
+            }
+            return;
+        }./
+
+    --
+    -- Macros that may be needed in a parser using this template
+    --
+    $additional_interfaces /../
+    $ast_class /.$ast_type./
+
+    --
+    -- Old deprecated macros that should NEVER be used.
+    --
+    $setSym1 /. // macro setSym1 is deprecated. Use function setResult
+                getParser().setSym1./
+    $setResult /. // macro setResult is deprecated. Use function setResult
+                 getParser().setSym1./
+    $getSym /. // macro getSym is deprecated. Use function getRhsSym
+              getParser().getSym./
+    $getToken /. // macro getToken is deprecated. Use function getRhsTokenIndex
+                getParser().getToken./
+    $getIToken /. // macro getIToken is deprecated. Use function getRhsIToken
+                 super.getIToken./
+    $getLeftSpan /. // macro getLeftSpan is deprecated. Use function getLeftSpan
+                   getParser().getFirstToken./
+    $getRightSpan /. // macro getRightSpan is deprecated. Use function getRightSpan
+                    getParser().getLastToken./
+$End
+
+$Globals
+    /.import lpg.lpgjavaruntime.*;
+    ./
+$End
+
+$Headers
+    /.
+    public class $action_type extends PrsStream implements RuleAction$additional_interfaces
+    {
+        private static ParseTable prs = new $prs_type();
+        private FixedBacktrackingParser btParser;
+
+        public FixedBacktrackingParser getParser() { return btParser; }
+        private void setResult(Object object) { btParser.setSym1(object); }
+        public Object getRhsSym(int i) { return btParser.getSym(i); }
+
+        public int getRhsTokenIndex(int i) { return btParser.getToken(i); }
+        public IToken getRhsIToken(int i) { return super.getIToken(getRhsTokenIndex(i)); }
+        
+        public int getRhsFirstTokenIndex(int i) { return btParser.getFirstToken(i); }
+        public IToken getRhsFirstIToken(int i) { return super.getIToken(getRhsFirstTokenIndex(i)); }
+
+        public int getRhsLastTokenIndex(int i) { return btParser.getLastToken(i); }
+        public IToken getRhsLastIToken(int i) { return super.getIToken(getRhsLastTokenIndex(i)); }
+
+        public int getLeftSpan() { return btParser.getFirstToken(); }
+        public IToken getLeftIToken()  { return super.getIToken(getLeftSpan()); }
+
+        public int getRightSpan() { return btParser.getLastToken(); }
+        public IToken getRightIToken() { return super.getIToken(getRightSpan()); }
+
+        public int getRhsErrorTokenIndex(int i)
+        {
+            int index = btParser.getToken(i);
+            IToken err = super.getIToken(index);
+            return (err instanceof ErrorToken ? index : 0);
+        }
+        public ErrorToken getRhsErrorIToken(int i)
+        {
+            int index = btParser.getToken(i);
+            IToken err = super.getIToken(index);
+            return (ErrorToken) (err instanceof ErrorToken ? err : null);
+        }
+
+        public $action_type(LexStream lexStream)
+        {
+            super(lexStream);
+
+            try
+            {
+                super.remapTerminalSymbols(orderedTerminalSymbols(), $prs_type.EOFT_SYMBOL);
+            }
+            catch(NullExportedSymbolsException e) {
+            }
+            catch(NullTerminalSymbolsException e) {
+            }
+            catch(UnimplementedTerminalsException e)
+            {
+                java.util.ArrayList unimplemented_symbols = e.getSymbols();
+                System.out.println("The Lexer will not scan the following token(s):");
+                for (int i = 0; i < unimplemented_symbols.size(); i++)
+                {
+                    Integer id = (Integer) unimplemented_symbols.get(i);
+                    System.out.println("    " + $sym_type.orderedTerminalSymbols[id.intValue()]);               
+                }
+                System.out.println();                        
+            }
+            catch(UndefinedEofSymbolException e)
+            {
+                throw new Error(new UndefinedEofSymbolException
+                                    ("The Lexer does not implement the Eof symbol " +
+                                     $sym_type.orderedTerminalSymbols[$prs_type.EOFT_SYMBOL]));
+            } 
+        }
+
+        public String[] orderedTerminalSymbols() { return $sym_type.orderedTerminalSymbols; }
+        public String getTokenKindName(int kind) { return $sym_type.orderedTerminalSymbols[kind]; }
+        public int getEOFTokenKind() { return $prs_type.EOFT_SYMBOL; }
+        public PrsStream getParseStream() { return (PrsStream) this; }
+        
+        //
+        // Report error message for given error_token.
+        //
+        public final void reportErrorTokenMessage(int error_token, String msg)
+        {
+            int firsttok = super.getFirstErrorToken(error_token),
+                lasttok = super.getLastErrorToken(error_token);
+            String location = super.getFileName() + ':' +
+                              (firsttok > lasttok
+                                        ? (super.getEndLine(lasttok) + ":" + super.getEndColumn(lasttok))
+                                        : (super.getLine(error_token) + ":" +
+                                           super.getColumn(error_token) + ":" +
+                                           super.getEndLine(error_token) + ":" +
+                                           super.getEndColumn(error_token)))
+                              + ": ";
+            super.reportError((firsttok > lasttok ? ParseErrorCodes.INSERTION_CODE : ParseErrorCodes.SUBSTITUTION_CODE), location, msg);
+        }
+
+        public $ast_class parser()
+        {
+            return parser(null, 0);
+        }
+        
+        public $ast_class parser(Monitor monitor)
+        {
+            return parser(monitor, 0);
+        }
+        
+        public $ast_class parser(int error_repair_count)
+        {
+            return parser(null, error_repair_count);
+        }
+
+        public $ast_class parser(Monitor monitor, int error_repair_count)
+        {
+            try
+            {
+                btParser = new FixedBacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
+            }
+            catch (NotBacktrackParseTableException e)
+            {
+                throw new Error(new NotBacktrackParseTableException
+                                    ("Regenerate $prs_type.java with -BACKTRACK option"));
+            }
+            catch (BadParseSymFileException e)
+            {
+                throw new Error(new BadParseSymFileException("Bad Parser Symbol File -- $sym_type.java"));
+            }
+
+            try
+            {
+                return ($ast_class) btParser.parse(error_repair_count);
+            }
+            catch (BadParseException e)
+            {
+                reset(e.error_token); // point to error token
+                DiagnoseParser diagnoseParser = new DiagnoseParser(this, prs);
+                diagnoseParser.diagnose(e.error_token);
+            }
+
+            return null;
+        }
+
+    ./
+
+$End
+
+$Rules
+    /.$BeginActions./
+$End
+
+$Trailers
+    /.
+        $EndActions
+    }
+    ./
+$End
+
+--
+-- E N D   O F   T E M P L A T E
+--
diff --git a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/c99/C99ExpressionParser.java b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/c99/C99ExpressionParser.java
index 1f440da1ec4..0bb87602f03 100644
--- a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/c99/C99ExpressionParser.java
+++ b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/c99/C99ExpressionParser.java
@@ -19,6 +19,7 @@ import java.util.*;
 import org.eclipse.cdt.core.dom.ast.*;
 import org.eclipse.cdt.core.dom.lrparser.IParser;
 import org.eclipse.cdt.core.dom.lrparser.IParserActionTokenProvider;
+import org.eclipse.cdt.core.dom.lrparser.lpgextensions.FixedBacktrackingParser;
 
 import org.eclipse.cdt.core.dom.lrparser.action.ITokenMap;
 import org.eclipse.cdt.core.dom.lrparser.action.TokenMap;
@@ -29,9 +30,9 @@ import org.eclipse.cdt.core.dom.lrparser.action.c99.C99BuildASTParserAction;
 public class C99ExpressionParser extends PrsStream implements RuleAction , IParserActionTokenProvider, IParser   
 {
     private static ParseTable prs = new C99ExpressionParserprs();
-    private BacktrackingParser btParser;
+    private FixedBacktrackingParser btParser;
 
-    public BacktrackingParser getParser() { return btParser; }
+    public FixedBacktrackingParser getParser() { return btParser; }
     private void setResult(Object object) { btParser.setSym1(object); }
     public Object getRhsSym(int i) { return btParser.getSym(i); }
 
@@ -136,7 +137,7 @@ public class C99ExpressionParser extends PrsStream implements RuleAction , IPars
     {
         try
         {
-            btParser = new BacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
+            btParser = new FixedBacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
         }
         catch (NotBacktrackParseTableException e)
         {
diff --git a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/c99/C99NoCastExpressionParser.java b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/c99/C99NoCastExpressionParser.java
index 0c4ecf68d21..69c3b52f1dc 100644
--- a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/c99/C99NoCastExpressionParser.java
+++ b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/c99/C99NoCastExpressionParser.java
@@ -19,6 +19,7 @@ import java.util.*;
 import org.eclipse.cdt.core.dom.ast.*;
 import org.eclipse.cdt.core.dom.lrparser.IParser;
 import org.eclipse.cdt.core.dom.lrparser.IParserActionTokenProvider;
+import org.eclipse.cdt.core.dom.lrparser.lpgextensions.FixedBacktrackingParser;
 
 import org.eclipse.cdt.core.dom.lrparser.action.ITokenMap;
 import org.eclipse.cdt.core.dom.lrparser.action.TokenMap;
@@ -29,9 +30,9 @@ import org.eclipse.cdt.core.dom.lrparser.action.c99.C99BuildASTParserAction;
 public class C99NoCastExpressionParser extends PrsStream implements RuleAction , IParserActionTokenProvider, IParser   
 {
     private static ParseTable prs = new C99NoCastExpressionParserprs();
-    private BacktrackingParser btParser;
+    private FixedBacktrackingParser btParser;
 
-    public BacktrackingParser getParser() { return btParser; }
+    public FixedBacktrackingParser getParser() { return btParser; }
     private void setResult(Object object) { btParser.setSym1(object); }
     public Object getRhsSym(int i) { return btParser.getSym(i); }
 
@@ -136,7 +137,7 @@ public class C99NoCastExpressionParser extends PrsStream implements RuleAction ,
     {
         try
         {
-            btParser = new BacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
+            btParser = new FixedBacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
         }
         catch (NotBacktrackParseTableException e)
         {
diff --git a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/c99/C99Parser.java b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/c99/C99Parser.java
index b636ce52e02..4ede761463c 100644
--- a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/c99/C99Parser.java
+++ b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/c99/C99Parser.java
@@ -19,6 +19,7 @@ import java.util.*;
 import org.eclipse.cdt.core.dom.ast.*;
 import org.eclipse.cdt.core.dom.lrparser.IParser;
 import org.eclipse.cdt.core.dom.lrparser.IParserActionTokenProvider;
+import org.eclipse.cdt.core.dom.lrparser.lpgextensions.FixedBacktrackingParser;
 
 import org.eclipse.cdt.core.dom.lrparser.action.ITokenMap;
 import org.eclipse.cdt.core.dom.lrparser.action.TokenMap;
@@ -29,9 +30,9 @@ import org.eclipse.cdt.core.dom.lrparser.action.c99.C99BuildASTParserAction;
 public class C99Parser extends PrsStream implements RuleAction , IParserActionTokenProvider, IParser   
 {
     private static ParseTable prs = new C99Parserprs();
-    private BacktrackingParser btParser;
+    private FixedBacktrackingParser btParser;
 
-    public BacktrackingParser getParser() { return btParser; }
+    public FixedBacktrackingParser getParser() { return btParser; }
     private void setResult(Object object) { btParser.setSym1(object); }
     public Object getRhsSym(int i) { return btParser.getSym(i); }
 
@@ -136,7 +137,7 @@ public class C99Parser extends PrsStream implements RuleAction , IParserActionTo
     {
         try
         {
-            btParser = new BacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
+            btParser = new FixedBacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
         }
         catch (NotBacktrackParseTableException e)
         {
diff --git a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/c99/C99SizeofExpressionParser.java b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/c99/C99SizeofExpressionParser.java
index fc986e8087d..8e62cf5d5f1 100644
--- a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/c99/C99SizeofExpressionParser.java
+++ b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/c99/C99SizeofExpressionParser.java
@@ -19,6 +19,7 @@ import java.util.*;
 import org.eclipse.cdt.core.dom.ast.*;
 import org.eclipse.cdt.core.dom.lrparser.IParser;
 import org.eclipse.cdt.core.dom.lrparser.IParserActionTokenProvider;
+import org.eclipse.cdt.core.dom.lrparser.lpgextensions.FixedBacktrackingParser;
 
 import org.eclipse.cdt.core.dom.lrparser.action.ITokenMap;
 import org.eclipse.cdt.core.dom.lrparser.action.TokenMap;
@@ -29,9 +30,9 @@ import org.eclipse.cdt.core.dom.lrparser.action.c99.C99BuildASTParserAction;
 public class C99SizeofExpressionParser extends PrsStream implements RuleAction , IParserActionTokenProvider, IParser   
 {
     private static ParseTable prs = new C99SizeofExpressionParserprs();
-    private BacktrackingParser btParser;
+    private FixedBacktrackingParser btParser;
 
-    public BacktrackingParser getParser() { return btParser; }
+    public FixedBacktrackingParser getParser() { return btParser; }
     private void setResult(Object object) { btParser.setSym1(object); }
     public Object getRhsSym(int i) { return btParser.getSym(i); }
 
@@ -136,7 +137,7 @@ public class C99SizeofExpressionParser extends PrsStream implements RuleAction ,
     {
         try
         {
-            btParser = new BacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
+            btParser = new FixedBacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
         }
         catch (NotBacktrackParseTableException e)
         {
diff --git a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPExpressionParser.java b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPExpressionParser.java
index 267833ab074..415d3b03355 100644
--- a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPExpressionParser.java
+++ b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPExpressionParser.java
@@ -23,6 +23,7 @@ import org.eclipse.cdt.core.dom.lrparser.action.cpp.CPPASTNodeFactory;
 import org.eclipse.cdt.core.dom.lrparser.action.cpp.CPPBuildASTParserAction;
 import org.eclipse.cdt.core.dom.lrparser.IParser;
 import org.eclipse.cdt.core.dom.lrparser.IParserActionTokenProvider;
+import org.eclipse.cdt.core.dom.lrparser.lpgextensions.FixedBacktrackingParser;
 
 import org.eclipse.cdt.core.dom.lrparser.action.ITokenMap;
 import org.eclipse.cdt.core.dom.lrparser.action.TokenMap;
@@ -30,9 +31,9 @@ import org.eclipse.cdt.core.dom.lrparser.action.TokenMap;
 public class CPPExpressionParser extends PrsStream implements RuleAction , IParserActionTokenProvider, IParser 
 {
     private static ParseTable prs = new CPPExpressionParserprs();
-    private BacktrackingParser btParser;
+    private FixedBacktrackingParser btParser;
 
-    public BacktrackingParser getParser() { return btParser; }
+    public FixedBacktrackingParser getParser() { return btParser; }
     private void setResult(Object object) { btParser.setSym1(object); }
     public Object getRhsSym(int i) { return btParser.getSym(i); }
 
@@ -137,7 +138,7 @@ public class CPPExpressionParser extends PrsStream implements RuleAction , IPars
     {
         try
         {
-            btParser = new BacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
+            btParser = new FixedBacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
         }
         catch (NotBacktrackParseTableException e)
         {
diff --git a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPNoCastExpressionParser.java b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPNoCastExpressionParser.java
index e8dc72f8eca..d7922ea9cfd 100644
--- a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPNoCastExpressionParser.java
+++ b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPNoCastExpressionParser.java
@@ -23,6 +23,7 @@ import org.eclipse.cdt.core.dom.lrparser.action.cpp.CPPASTNodeFactory;
 import org.eclipse.cdt.core.dom.lrparser.action.cpp.CPPBuildASTParserAction;
 import org.eclipse.cdt.core.dom.lrparser.IParser;
 import org.eclipse.cdt.core.dom.lrparser.IParserActionTokenProvider;
+import org.eclipse.cdt.core.dom.lrparser.lpgextensions.FixedBacktrackingParser;
 
 import org.eclipse.cdt.core.dom.lrparser.action.ITokenMap;
 import org.eclipse.cdt.core.dom.lrparser.action.TokenMap;
@@ -30,9 +31,9 @@ import org.eclipse.cdt.core.dom.lrparser.action.TokenMap;
 public class CPPNoCastExpressionParser extends PrsStream implements RuleAction , IParserActionTokenProvider, IParser 
 {
     private static ParseTable prs = new CPPNoCastExpressionParserprs();
-    private BacktrackingParser btParser;
+    private FixedBacktrackingParser btParser;
 
-    public BacktrackingParser getParser() { return btParser; }
+    public FixedBacktrackingParser getParser() { return btParser; }
     private void setResult(Object object) { btParser.setSym1(object); }
     public Object getRhsSym(int i) { return btParser.getSym(i); }
 
@@ -137,7 +138,7 @@ public class CPPNoCastExpressionParser extends PrsStream implements RuleAction ,
     {
         try
         {
-            btParser = new BacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
+            btParser = new FixedBacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
         }
         catch (NotBacktrackParseTableException e)
         {
diff --git a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPNoFunctionDeclaratorParser.java b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPNoFunctionDeclaratorParser.java
index db291b008c9..571d02b67ff 100644
--- a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPNoFunctionDeclaratorParser.java
+++ b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPNoFunctionDeclaratorParser.java
@@ -23,6 +23,7 @@ import org.eclipse.cdt.core.dom.lrparser.action.cpp.CPPASTNodeFactory;
 import org.eclipse.cdt.core.dom.lrparser.action.cpp.CPPBuildASTParserAction;
 import org.eclipse.cdt.core.dom.lrparser.IParser;
 import org.eclipse.cdt.core.dom.lrparser.IParserActionTokenProvider;
+import org.eclipse.cdt.core.dom.lrparser.lpgextensions.FixedBacktrackingParser;
 
 import org.eclipse.cdt.core.dom.lrparser.action.ITokenMap;
 import org.eclipse.cdt.core.dom.lrparser.action.TokenMap;
@@ -30,9 +31,9 @@ import org.eclipse.cdt.core.dom.lrparser.action.TokenMap;
 public class CPPNoFunctionDeclaratorParser extends PrsStream implements RuleAction , IParserActionTokenProvider, IParser 
 {
     private static ParseTable prs = new CPPNoFunctionDeclaratorParserprs();
-    private BacktrackingParser btParser;
+    private FixedBacktrackingParser btParser;
 
-    public BacktrackingParser getParser() { return btParser; }
+    public FixedBacktrackingParser getParser() { return btParser; }
     private void setResult(Object object) { btParser.setSym1(object); }
     public Object getRhsSym(int i) { return btParser.getSym(i); }
 
@@ -137,7 +138,7 @@ public class CPPNoFunctionDeclaratorParser extends PrsStream implements RuleActi
     {
         try
         {
-            btParser = new BacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
+            btParser = new FixedBacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
         }
         catch (NotBacktrackParseTableException e)
         {
diff --git a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPParser.java b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPParser.java
index e3d4d178639..eae00527536 100644
--- a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPParser.java
+++ b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPParser.java
@@ -23,6 +23,7 @@ import org.eclipse.cdt.core.dom.lrparser.action.cpp.CPPASTNodeFactory;
 import org.eclipse.cdt.core.dom.lrparser.action.cpp.CPPBuildASTParserAction;
 import org.eclipse.cdt.core.dom.lrparser.IParser;
 import org.eclipse.cdt.core.dom.lrparser.IParserActionTokenProvider;
+import org.eclipse.cdt.core.dom.lrparser.lpgextensions.FixedBacktrackingParser;
 
 import org.eclipse.cdt.core.dom.lrparser.action.ITokenMap;
 import org.eclipse.cdt.core.dom.lrparser.action.TokenMap;
@@ -30,9 +31,9 @@ import org.eclipse.cdt.core.dom.lrparser.action.TokenMap;
 public class CPPParser extends PrsStream implements RuleAction , IParserActionTokenProvider, IParser 
 {
     private static ParseTable prs = new CPPParserprs();
-    private BacktrackingParser btParser;
+    private FixedBacktrackingParser btParser;
 
-    public BacktrackingParser getParser() { return btParser; }
+    public FixedBacktrackingParser getParser() { return btParser; }
     private void setResult(Object object) { btParser.setSym1(object); }
     public Object getRhsSym(int i) { return btParser.getSym(i); }
 
@@ -137,7 +138,7 @@ public class CPPParser extends PrsStream implements RuleAction , IParserActionTo
     {
         try
         {
-            btParser = new BacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
+            btParser = new FixedBacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
         }
         catch (NotBacktrackParseTableException e)
         {
diff --git a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPSizeofExpressionParser.java b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPSizeofExpressionParser.java
index 51271d9ff41..44d163d3420 100644
--- a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPSizeofExpressionParser.java
+++ b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPSizeofExpressionParser.java
@@ -23,6 +23,7 @@ import org.eclipse.cdt.core.dom.lrparser.action.cpp.CPPASTNodeFactory;
 import org.eclipse.cdt.core.dom.lrparser.action.cpp.CPPBuildASTParserAction;
 import org.eclipse.cdt.core.dom.lrparser.IParser;
 import org.eclipse.cdt.core.dom.lrparser.IParserActionTokenProvider;
+import org.eclipse.cdt.core.dom.lrparser.lpgextensions.FixedBacktrackingParser;
 
 import org.eclipse.cdt.core.dom.lrparser.action.ITokenMap;
 import org.eclipse.cdt.core.dom.lrparser.action.TokenMap;
@@ -30,9 +31,9 @@ import org.eclipse.cdt.core.dom.lrparser.action.TokenMap;
 public class CPPSizeofExpressionParser extends PrsStream implements RuleAction , IParserActionTokenProvider, IParser 
 {
     private static ParseTable prs = new CPPSizeofExpressionParserprs();
-    private BacktrackingParser btParser;
+    private FixedBacktrackingParser btParser;
 
-    public BacktrackingParser getParser() { return btParser; }
+    public FixedBacktrackingParser getParser() { return btParser; }
     private void setResult(Object object) { btParser.setSym1(object); }
     public Object getRhsSym(int i) { return btParser.getSym(i); }
 
@@ -137,7 +138,7 @@ public class CPPSizeofExpressionParser extends PrsStream implements RuleAction ,
     {
         try
         {
-            btParser = new BacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
+            btParser = new FixedBacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
         }
         catch (NotBacktrackParseTableException e)
         {
diff --git a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPTemplateTypeParameterParser.java b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPTemplateTypeParameterParser.java
index 8f133de8686..c448715fcb7 100644
--- a/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPTemplateTypeParameterParser.java
+++ b/lrparser/org.eclipse.cdt.core.lrparser/src/org/eclipse/cdt/internal/core/dom/lrparser/cpp/CPPTemplateTypeParameterParser.java
@@ -23,6 +23,7 @@ import org.eclipse.cdt.core.dom.lrparser.action.cpp.CPPASTNodeFactory;
 import org.eclipse.cdt.core.dom.lrparser.action.cpp.CPPBuildASTParserAction;
 import org.eclipse.cdt.core.dom.lrparser.IParser;
 import org.eclipse.cdt.core.dom.lrparser.IParserActionTokenProvider;
+import org.eclipse.cdt.core.dom.lrparser.lpgextensions.FixedBacktrackingParser;
 
 import org.eclipse.cdt.core.dom.lrparser.action.ITokenMap;
 import org.eclipse.cdt.core.dom.lrparser.action.TokenMap;
@@ -30,9 +31,9 @@ import org.eclipse.cdt.core.dom.lrparser.action.TokenMap;
 public class CPPTemplateTypeParameterParser extends PrsStream implements RuleAction , IParserActionTokenProvider, IParser 
 {
     private static ParseTable prs = new CPPTemplateTypeParameterParserprs();
-    private BacktrackingParser btParser;
+    private FixedBacktrackingParser btParser;
 
-    public BacktrackingParser getParser() { return btParser; }
+    public FixedBacktrackingParser getParser() { return btParser; }
     private void setResult(Object object) { btParser.setSym1(object); }
     public Object getRhsSym(int i) { return btParser.getSym(i); }
 
@@ -137,7 +138,7 @@ public class CPPTemplateTypeParameterParser extends PrsStream implements RuleAct
     {
         try
         {
-            btParser = new BacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
+            btParser = new FixedBacktrackingParser(monitor, (TokenStream) this, prs, (RuleAction) this);
         }
         catch (NotBacktrackParseTableException e)
         {