title: Top Down Parsing - Java
body: <p>I have been assigned a project to implement a top-down backtracking parser for any grammar which contains only one nonterminal on the RHS of its rewrite rules (e.g S -> aaSb | aaSa | aSa)</p>
  
  <p>So far, I have three methods, including <code>main</code>, that are used to handle checking the validity of an input string.</p>
  
  <p>My goal is to, using a <code>char[][]</code> array for the grammar, check each character in the input string against the grammar, and return <code>true</code> if the string is contained within the grammar.</p>
  
  <pre><code>public class TDBP {
      public static void main(String[] args) {
          char[][] g = new char[][] 
              { {'a', 'a', 'S', 'b'}, 
                {'a', 'a', 'S', 'a'}, 
                {'a', 'S', 'a'}, 
                {'\0'} };
  
          SP(g);
      }
      public static void SP(char[][] g) {
          Scanner s = new Scanner(System.in);
          boolean again = true; int pn = 0;
          String test;
  
          while(again) {
              System.out.print("Next string? ");
              test = s.nextLine();
  
              if(S(pn, test, g))
                  System.out.println("String is in the language");
              else
                  System.out.println("String is not in the language");
  
              if(s.nextLine() == "\n") again = false;
          }
  
          s.close();
      }
      public static boolean S(int pn, String test, char[][] g) {
          char[] c = test.toCharArray();
          boolean exists = false;
  
          for(int i = pn; i &lt; g.length; i++) {
              for(int j = 0; j &lt; g[i].length; j++) {
                  if(c[j] == 'S')
                      S(++pn, test, g);
                  if(c[j] == g[i][j])
                      exists = true;
              }
          }
  
          return exists;
      }
  }
  </code></pre>
  
  <p>In my algorithm, <code>pn</code> is an integer to keep track of which production in the grammar I am currently looking at, and to make sure that I don't scan the same grammar twice (e.g a <code>pn</code> of 1 in above grammar would correspond to <code>aaSa</code>). Also, I have <code>\0</code> represent the empty string.</p>
  
  <p>Am I parsing the string correctly?</p>
  
  <p>Thank you!</p>