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

    Default BNF grammar using recursive descent parsing

    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!!

    Java Code:
    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
    CodesAway's Avatar
    CodesAway is offline Senior Member
    Join Date
    Sep 2009
    Location
    Texas
    Posts
    238
    Rep Power
    5

    Default

    First thing I noticed is that in your E() method, you have three branches that all call method T to see whether to precede. This shouldn't be done, since if T() is false the first time, T() should be false the second, and the third as well. The same problem occurs in your T function, where you call P() for each of the three branches.

    Second thing I noticed is that even if a method returns false, if it "partially" matches, then the "cursor" is moved forward, but if the method returns false, then the "cursor" shouldn't move at all, correct?


    For example, given your test input "a=a+b-c*d", here are the steps

    1) Call A
    2) A calls I
    3) I checks to see if the current character is a letter between 'a' and 'z'
    3a) It is an 'a', so you advance the cursor and return true
    4) Back in A, I is true, so you check for an '='
    4a) It is, so you call E
    5) In E, you call T
    6) In T, you call P
    7) In P, you call I
    8) You check for a letter between 'a' and 'z'. The next character is 'a', so true
    8a) Advance cursor, and return true
    9) Back in P, I returns true
    9a) So, P returns true
    10) Back in T, P is true, so you check for a '*'. This is false, since a '+' occurs
    10b) T returns false!
    10c) It should return true, since the third branch for T says that P is a valid match. However, your code doesn't try this branch. Your code, instead, uses an "if-else" branching, whereas parsing tries ALL branches.
    CodesAway - codesaway.info
    writing tools that make writing code a little easier

  3. #3
    Join Date
    Oct 2009
    Posts
    5
    Rep Power
    0

Similar Threads

  1. help with BNF Grammar program using recursive descent parsing
    By carolain79@hotmail.com in forum New To Java
    Replies: 1
    Last Post: 10-21-2009, 08:00 PM
  2. Grammar Checker
    By zaz_rin in forum New To Java
    Replies: 1
    Last Post: 07-19-2009, 02:01 PM
  3. Output correct grammar
    By JordashTalon in forum New To Java
    Replies: 2
    Last Post: 03-06-2009, 12:22 AM
  4. Recursive Counting
    By zlwilly in forum New To Java
    Replies: 1
    Last Post: 01-29-2009, 08:42 PM
  5. Recursive Anagram
    By zoe in forum Advanced Java
    Replies: 1
    Last Post: 08-07-2007, 06:15 AM

Posting Permissions

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