title: Recursive Descent Parser Stack Overflow
body: <p>I have the following code for a parser that accepts a linked list as a parameter from a parent class. It throws a stack overflow error after I input the expression.</p>
  
  <p>I pass the input expression from a jTextField in a Swing GUI class, then return the boolean result to a jLabel in the same class. What could be causing the stack overflow error? Help please, Thanks!!</p>
  
  <p>Example input:</p>
  
  <p>1+2+3</p>
  
  <p>(1+2)/(3+4)</p>
  
  <pre><code>import java.util.LinkedList;
  
  class Token {
      public static final int PLUS_MINUS = 0;
      public static final int MULTIPLY_DIVIDE = 1;
      public static final int EXPONENT = 2;
      public static final int NUMBER = 3;
      public static final int IDENTIFIER = 4;
      public static final int OPEN = 5;
      public static final int CLOSE = 6;
      //public static final int NEGATIVE = 7;
  
      public final int token; // FIELDS TO HOLD DATA PER TOKEN
      public final String sequence;
  
      public Token (int token, String sequence) {
          super();
          this.token = token;
          this.sequence = sequence;
      }
  }
  
  public class Parser {
  
      private Token next; // POINTER FOR NEXT TOKEN
      private LinkedList&lt;Token&gt; tokens; // LIST OF TOKENS PRODUCED BY TOKENIZER
      private int counter = 0;
  
      public Parser(LinkedList tokens) 
      {
          this.tokens = (LinkedList&lt;Token&gt;) tokens.clone(); // GET LINKEDLIST
          this.tokens.getFirst(); // ASSIGNS FIRST ELEMENT OF LINKEDLIST
      }
  
  
      //////// START OF PARSING METHODS ////////
  
      /*
          GRAMMAR:
          E -&gt; E+T | E-T | T | -E
          T -&gt; T*X | T/X | X
          X -&gt; X^F | F
          F -&gt; (E) | NUMBERS | IDENTIFIERS
                          F -&gt; (E) | N | I
                          N -&gt; D | ND
                          I -&gt; IDENTIFIERS
      */
  
      public boolean Parse ()
      {
          return E(); // INVOKE START SYMBOL
      }
  
      private boolean term (int token) // GETS NEXT TOKEN
      {
          boolean flag = false;
  
          if(next.token == token)
              flag = true;
  
          counter++; // INCREMENT COUNTER
  
          if(counter &lt; tokens.size()) // POINT TO NEXT TOKEN
              next = tokens.get(counter);
  
          return flag;
      }
  
      ///////// START OF LIST OF PRODUCTIONS /////////
  
      //////// E -&gt; E+T | E-T | T | -E ////////
  
      private boolean E() 
      {
          return E1() || E2() || E3();
      }
  
      private boolean E1 ()
      {
          // E -&gt; E+T | E-T
  
          int flag = counter;
          boolean result = true;
  
          if(!(E() &amp;&amp; term(Token.PLUS_MINUS) &amp;&amp; T() ))
          {
              counter = flag; // BACKTRACK
  
              if(counter &lt; tokens.size()) // POINT TO PREVIOUS TOKEN
                  next = tokens.get(counter);
  
              result = false;
          }
          return result;
      }
  
      private boolean E2 ()
      {
          // E -&gt; T
  
          int flag = counter;
          boolean result = true;
  
          if(!T())
          {
              counter = flag; // BACKTRACK
  
              if(counter &lt; tokens.size()) // POINT TO PREVIOUS TOKEN
                  next = tokens.get(counter);
  
              result = false;
          }
          return result;
      }
  
      private boolean E3 ()
      {
          // E -&gt; -E
  
          int flag = counter;
          boolean result = true;
  
          if(!(term(Token.PLUS_MINUS) &amp;&amp; E() ))
          {
              counter = flag; // BACKTRACK
  
              if(counter &lt; tokens.size()) // POINT TO PREVIOUS TOKEN
                  next = tokens.get(counter);
  
              result = false;
          }
          return result;
      }
  
  
      //////// T -&gt; T*X | T/X | X ////////
  
      private boolean T()
      {
          return T1() || T2();
      }
  
      private boolean T1 ()
      {
          // T -&gt; T*X | T/X
  
          int flag = counter;
          boolean result = true;
  
          if(!(T() &amp;&amp; term(Token.MULTIPLY_DIVIDE) &amp;&amp; X() ))
          {
              counter = flag; // BACKTRACK
  
              if(counter &lt; tokens.size()) // POINT TO PREVIOUS TOKEN
                  next = tokens.get(counter);
  
              result = false;
          }
          return result;
      }
  
      private boolean T2 ()
      {
          // T -&gt; X
  
          int flag = counter;
          boolean result = true;
  
          if(!X())
          {
              counter = flag; // BACKTRACK
  
              if(counter &lt; tokens.size()) // POINT TO PREVIOUS TOKEN
                  next = tokens.get(counter);
  
              result = false;
          }
          return result;
      }
  
  
      //////// X -&gt; X^F | F ////////
  
      private boolean X()
      {
          return X1() || X2();
      }
  
      private boolean X1()
      {
          // X-&gt; X^F
  
          int flag = counter;
          boolean result = true;
  
          if(!(X() &amp;&amp; term(Token.EXPONENT) &amp;&amp; F()))
          {
              counter = flag; // BACKTRACK
  
              if(counter &lt; tokens.size()) // POINT TO PREVIOUS TOKEN
                  next = tokens.get(counter);
  
              result = false;
          }
          return result;
      }
  
      private boolean X2()
      {
          // X-&gt; F
  
          int flag = counter;
          boolean result = true;
  
          if(!F())
          {
              counter = flag; // BACKTRACK
  
              if(counter &lt; tokens.size()) // POINT TO PREVIOUS TOKEN
                  next = tokens.get(counter);
  
              result = false;
          }
          return result;
      }
  
  
      //////// F -&gt; (E) | NUMBERS | IDENTIFIERS ////////
      private boolean F()
      {
          return F1() || F2() || F3();
      }
  
      private boolean F1()
      {
          // F -&gt; (E)
  
          int flag = counter;
          boolean result = true;
  
          if(!(term(Token.OPEN) &amp;&amp; E() &amp;&amp; term(Token.CLOSE)))
          {
              counter = flag; // BACKTRACK
  
              if(counter &lt; tokens.size()) // POINT TO PREVIOUS TOKEN
                  next = tokens.get(counter);
  
              result = false;
          }
          return result;
      }
  
      private boolean F2()
      {
          // F -&gt; NUMBERS
  
          int flag = counter;
          boolean result = true;
  
          if(!term(Token.NUMBER))
          {
              counter = flag; // BACKTRACK
  
              if(counter &lt; tokens.size()) // POINT TO PREVIOUS TOKEN
                  next = tokens.get(counter);
  
              result = false;
          }
          return result;
      }
  
      private boolean F3()
      {
          // F -&gt; IDENTIFIERS
  
          int flag = counter;
          boolean result = true;
  
          if(!term(Token.IDENTIFIER))
          {
              counter = flag; // BACKTRACK
  
              if(counter &lt; tokens.size()) // POINT TO PREVIOUS TOKEN
                  next = tokens.get(counter);
  
              result = false;
          }
          return result;
      }
  }
  </code></pre>