title: Recursive Descent Parser in Java
body: <p>I would like to preface this by saying this is a homework assignment for my third            Year Programming Languages Class, and I'm looking for some help with it. My assignment reads:</p>
  
  <blockquote>
    <p>Deadline:   February 22, 2013 at 11:55pm <br>
    Submission: Please upload the following to the CMS. <br><br>
    1. Source code <br>
    2. A screen shot of the execution of your program including the input file you used</p>
    
    <p>Use any programming language you prefer to write a recursive-descent parser that parses      the language generated by the following EBNF descriptions.  Your parser should detect whether or not the input program has any syntax errors.  It does not have to specify what and where the error is. </p>
  </blockquote>
  
  <pre><code>&lt;program&gt;   begin &lt;stmt_list&gt; end
  &lt;stmt_list&gt;  &lt;stmt&gt; {;&lt;stmt_list&gt;}
  &lt;stmt&gt;    &lt;assign_stmt&gt; | &lt;while_stmt&gt;
  &lt;assign_stmt&gt;  &lt;var&gt; = &lt;expr&gt;
  &lt;var&gt;  identifier  (An identifier is a string that begins with a letter followed by 0     or more letters and digits)
  &lt;expr&gt;  &lt;var&gt; { (+|-) &lt;var&gt;}           
  &lt;while_stmt&gt;   while (&lt;logic_expr&gt;)  &lt;stmt&gt;
  &lt;logic_expr&gt; ® &lt;var&gt; (&lt; | &gt;) &lt;var&gt;  (Assume that logic expressions have only less than     or greater than operators)
  </code></pre>
  
  <p>The symbols that look funny are just arrows pointing to the right.</p>
  
  <p>My problem at the moment is more logical then it is programming: in my first attempt, I read the entire input program in, saved it to a string, then parsed that string and converted every symbol to either a terminal, expr, or what have you.</p>
  
  <p>I eventually found that this way would not work because, A: I don't think that it is RDP, B: many of the non terminals are made of more then 1 statement. </p>
  
  <p>I gave up on that approach, and decided that before I waste more time programming, I would Pseudo everything out. My new idea was to make 1 method, for each non terminal symbol, and just parse the input string symbol by symbol, hoping between those methods. This approach seemed logical, but as I started writing the pseudocode I got very lost and confused as to what I needed to do.  <strong>How would I finish this code?</strong></p>
  
  <p>Here is some pseudocode for RDP:</p>
  
  <pre><code>intputString;
  
  public void parseProgram (Symbol.typeIsProgram) {
      if getNextSymbol == "begin" {
          if (intputString.substring (inputString.length()-3,
                  inputString.length()) == "end") {
              Symbol stmt_lsit = new Symbol (intputString)
              parseStmt_list(stmt_list);              
          } else {
              Out "error, prog must end with end"
          }
      } else {
          Out "error, prog must begin with begin"
      }   
  }
  
  public void parseStmt_list (Stmbol.typeIsStmt_list) {
      symbol = getNextSymbol;
      if (Symbol.typeIsVar) {
          parseVar(symbol)
      } else if (Symbol.typeIsWhile)  {
          // weve only capture if the first word return is a while, we dont have the whole while statement yet
          ParseWhile_stmt(symbol)
      } else { }
  }
  
  public void parseStmt () { }
  public void parseAssign_stmt () { }
  public void parseVar () { }
  public void parseExpr () { }
  public void parseWhile_stmt () { }
  public void parseLogic_expr () { }
  
  public Symbol getNextSymbol() {
      //returns the next symbol in input string and removes it from the input string
  }
  </code></pre>
  
  <p>Just an FYI a sample input program for my parser would be.</p>
  
  <pre><code>begin 
  total = var1 + var2; 
  while (var1 &lt; var2) 
  while ( var3 &gt; var4)
  var2 = var2 - var1 
  end
  </code></pre>