Results 1 to 2 of 2
  1. #1
    Join Date
    Oct 2009
    Posts
    5
    Rep Power
    0

    Default help with BNF Grammar program using recursive descent parsing

    Consider the following BNF grammar:

    A -> I = E
    E -> T + E | T - E | T
    T -> P * T | P / T | P
    P -> I | L | (E)
    I -> a | b | ... | y | z
    L -> 0 | 1 | ... | 8 | 9

    implement a recursive descent parser that recognizes strings in this language.

    An example session might look like this:

    String read from file: a=a+b-c*d
    The string "a=a+b-c*d" is in the language.
    String read from file: a=a**b++c
    The string "a=a**b++c" is not in the language.

    The problem with the following code is that for any string that I input even if it is in the language , it shows the message is not in the language, I dont know where the error in my code is.
    I would really appreciate your help!!


    public class BnfGrammar {


    public static void main(String[] args) {

    s = args.length == 1 ? args[0] : "a=a+b-c*d";

    if (A() && i == s.length()) {
    System.out.println("The string \"" + s + "\" is in the language.");
    }
    else {
    System.out.println("The string \"" + s + "\" is not in the language.");
    }
    }

    private static boolean A() {

    if (I()) {
    if (i < s.length() && s.charAt(i) == '=') {
    ++i;
    if (E()) {

    return true;

    }
    }
    }

    return false;
    }

    private static boolean E() {

    if(T()){
    if (i < s.length() && s.charAt(i) == '+') {
    ++i;
    if(E()){

    return true;
    }
    }
    }
    else if(T()){
    if (i < s.length() && s.charAt(i) == '-'){
    i++;
    if(E()){

    return true;
    }

    }

    }
    else if(T()){

    return true;
    }

    return false;
    }

    private static boolean T(){
    if (P()){
    if (i < s.length() && s.charAt(i) == '*'){
    i++;
    if(T()){

    return true;
    }
    }
    }
    else if(P()){
    if(i < s.length() && s.charAt(i) == '/'){
    i++;
    if(T()){

    return true;
    }
    }
    }
    else if(P()){

    return true;
    }

    return false;
    }

    private static boolean P(){
    if(I()){
    return true;
    }
    else if (L()){
    return true;
    }
    else if(i < s.length() && s.charAt(i) == '('){
    ++i;
    if (E()){
    if (i < s.length() && s.charAt(i) == ')') {
    ++i;
    return true;
    }
    }
    }


    return false;
    }

    private static boolean I() {

    if (i < s.length() && s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
    ++i;
    return true;
    }

    return false;
    }

    private static boolean L(){
    if (i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
    ++i;
    return true;
    }

    return false;

    }


    private static String s;
    private static int i;






    }

  2. #2
    travishein's Avatar
    travishein is offline Senior Member
    Join Date
    Sep 2009
    Location
    Canada
    Posts
    684
    Rep Power
    6

    Default

    The trick is to recognize what the 'terminal' nodes, or literal characters are, what would come from scanning the character stream. In this case,
    [a-z] [0-9] = + - * / ( )
    And then the non terminals become methods in the recursive descent parser.
    A E T P

    I implemented this as the concept of a 'token', similar to how lex and yacc would do it, except here the recursive descent methods just invoke getNextToken() and compare the token type to the expected value for the level in the recusive descent node. The token types are also just modeled as an enum.
    And for convenience of forum posting, I just rammed them all into one .java file.

    Java Code:
    import java.io.BufferedReader;
    import java.io.ByteArrayInputStream;
    import java.io.IOException;
    import java.io.InputStream;
    import java.io.InputStreamReader;
    
    /**
     *Created on Oct 21, 2009
     */
    
    /**
    A ::= I "=" E
    E ::= T "+" E | T "-" E | T
    T ::= P "*" T | P "/" T | P
    P ::= I | L | "("E")"
    I ::= [a..z]
    L ::= [0..9]
    */
    public class BNFGrammar {
      BufferedReader reader;
      
      public BNFGrammar(InputStream in) {
        this.reader = new BufferedReader(new InputStreamReader(in));
      }
       
      
      public Token getNextToken() {
        Token t = null;
        try {
          int value =reader.read(); 
          if (value > -1) {
            t = new Token(value);
          }
        }
        catch (IOException ex) { }
        return t;
      }
      
      /**
       * A ::= I "=" E
       * @return
       */
      protected boolean A() {
        if (!I()) {
          return false;
        }
        Token t = getNextToken();
        if (t == null) {
          return false;
        }
        if (!TokenType.OP_EQUALS.equals(t.type)) {
          return false;
        }
        if (!E()) {
          return false;
        }
        return true;
      }
      
      /**
       * E ::= T "+" E | T "-" E | T
       * @return
       */
      protected boolean E() {
        if (!T()) {
          return false;
        }
        Token t = getNextToken();
        if (t == null) {
          return true;
        }
    
        if (TokenType.OP_PLUS.equals(t.type) || TokenType.OP_MINUS.equals(t.type) ) {
          if (!E()) {
            return false;
          }
          return true;
        }
        
        return true;
        
      }
      
      /**
       * T ::= P "*" T | P "/" T | P
       * @return
       */
      protected boolean T() {
        if (!P()) {
          return false;
        }
        Token t = getNextToken();
        if (t == null) {
          return true;
        }
    
        if (TokenType.OP_MULTIPLY.equals(t.type) || TokenType.OP_DIVIDE.equals(t.type) ) {
          if (!T()) {
            return false;
          }
          return true;
        }
        
        return true;
      }
      
      /**
       * P ::= I | L | "("E")"
       */
      protected boolean P() {
        // because we don't have the push back ability we would have in an LALR parser,
        // we don't invoke the I, L functions recursively.
        Token t = getNextToken();
        if (t == null) {
          return false;
        }
        switch (t.type) {
          case I:
            return true;
            
          case L:
            return true;
            
          case PUNCT_LEFTPAREN:
            if (!E()) {
              return false;
            }
            Token t2 = getNextToken();
            if (t2 == null) {
              return false;
            }
            if (!TokenType.PUNCT_RIGHTPAREN.equals(t2.type)) {
              return false;
            }
            return true;
           
          default:
            return false;
        } // switch
      }
      
      /**
       * I ::= [a..z]
       * @return
       */
      protected boolean I() {
        Token t = getNextToken();
        if (t == null) {
          return false;
        }
        return TokenType.I.equals(t.type);
      }
      
      /**
       * L ::= [0..9]
       * @return
       */
      protected boolean L() {
        Token t = getNextToken();
        if (t == null) {
          return false;
        }
        return TokenType.L.equals(t.type);
      }
      
      /**
       * Invokes the parser. Expects the standard input to be the string to validate.
       * @param args
       */
      public static void main(String[] args) {
        
        
        if (args.length > 0) {
          String str = args[0];
          InputStream in = new ByteArrayInputStream(str.getBytes());
          BNFGrammar b = new BNFGrammar(in);
          boolean result = b.A();
          System.out.println("The string \"" + str + "\" is " + (result ? "" : "not ") + "in the language.");
        }
        else {
          //when no parameters specified, just use stdin.
          InputStream in = System.in;
          BNFGrammar b = new BNFGrammar(in);
          boolean result = b.A();
          System.exit(result ? 0 : 1);
        }
       
      }
         
    }
    
    class Token {
      public char value;
      public TokenType type;
      
      public Token(int in) {
        this.value = (char) in;
        this.type = TokenType.parse(String.valueOf(this.value));
      }
    }
    
    /**
     * The different kinds of literals we would read from the scanner.
     * @author thein
     *
     */
    enum TokenType {
      I("[a-z]"),
      L("[0-9]"),
      OP_EQUALS("\\="),
      OP_PLUS("\\+"),
      OP_MINUS("\\-"),
      OP_MULTIPLY("\\*"),
      OP_DIVIDE("\\/"),
      PUNCT_LEFTPAREN("\\("),
      PUNCT_RIGHTPAREN("\\)"),
      ;
      
      private TokenType(String ch) {
        this.charClass = ch;
      }
      String charClass;
      
      public static TokenType parse(String in) {
        for (TokenType type : TokenType.values()) {
          if (in.matches(type.charClass)) {
            return type;
          }
        }
        return null;
      }
      
    }
    My outputs:
    Java Code:
    $>java BNFGrammar a=a+b-c*d
    The string "a=a+b-c*d" is in the language.
    
    $>java BNFGrammar a=a**b++c
    The string "a=a**b++c" is not in the language.

    Let me know what mark I get for doing your assignment :)

Similar Threads

  1. Grammar Checker
    By zaz_rin in forum New To Java
    Replies: 1
    Last Post: 07-19-2009, 03:01 PM
  2. Output correct grammar
    By JordashTalon in forum New To Java
    Replies: 2
    Last Post: 03-06-2009, 01:22 AM
  3. Recursive Anagram
    By zoe in forum Advanced Java
    Replies: 1
    Last Post: 08-07-2007, 07:15 AM
  4. Help with recursive implementation
    By toby in forum Advanced Java
    Replies: 1
    Last Post: 08-07-2007, 06:57 AM
  5. problem with recursive binary search program
    By imran_khan in forum New To Java
    Replies: 3
    Last Post: 08-02-2007, 04:08 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •