Parsing a BNF grammar language with java

[nickclarson]

Build a program to take a BNF grammar and generate sentences in the language specified by the grammar. The program will read the grammar and then it will allow interactively building a sentence in the language specified by the grammar. Assume the BNF is correct. All items in a rule are separated by white space. (You can require exactly one space between items). Each rule is exactly one line.
The BNF rules (referred to as a grammar) are stored in a file. Your program is to read and echo the grammar file, and then walk the user through the process of building a sentence.

Once the grammar is read, the program will prompt the user to build a sentence in the specified grammar. For example assume the grammar is:

  <s> ->  let <var> = <val>
  <val> -> <var> | <num>
  <var> -> a | b
  <num> -> 1 | 2 | 3

The program and the user could have the following interaction (user answers after the ?):

deriving <s> 
deriving <var>
specify number of choice: 1 a, 2 b
?2
deriving <val>
specify number of choice: 1 <var>, 2 <num>
?2
deriving <num>
specify number of choice: 1 1, 2 2, 3 3
?1
The derived sentence is:
let b = 1

Assume the left hand side (LHS) of the first rule specifies the start symbol. Demonstrate the program with at least two grammars and for each grammar at least two examples. You need to use recursion to run through a rule after you start. Otherwise, you have to keep a stack of states of where you are.

I am looking to do this in java and I have no idea where to begin. I'm guessing I need to use tokens for sure, and file input, but i'm not sure how to do the recursive part.

I figured I would ask for help on here, because it's been a helpful place in the past and I know there are some fellow CSers on here.

Any help/tips are greatly appreciated,

Nick

 

[OsamaBinBBQ]

You're right, this is very computer science-y. It's very interesting, but you might get better feedback on stackoverflow?

 

[jryan21]

Haha, I'll be on something similar in a few weeks, saw it today and remembered this thread.

You can use this to sketch it out, or convert from regex:
JFLAP

If you want to see examples, you can find pretty much anything you are looking for here:
Wapedia - Wiki: Comparison of parser generators

 

[feydr]

hahaha!!! wrong fucking site dood... if you are using java you want to check out antlr; otherwise go with lex/yacc..

but seriously -- go with SO or something else

 

[nickclarson]

for those of you who care, this is what I came up with. However I'm sure that there is an easier way to do it that I'm not familiar with. Also, It's not as commented as I want it to be, but if you have any questions let me know and I'll explain. The main reason I'm posting this is because jryan said he'd be doing something similar so I thought I would help out.

import java.io.*;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.regex.Pattern;
import java.util.ArrayList;

public class ParseBNF {
    
    String data="", first, next;
    String sentance = "";
    String regex = "<[^>]*>";

    StringTokenizer st;

    // constructor
    public ParseBNF (String file) {

	try {
	    BufferedReader buffer = new BufferedReader(new FileReader(file));
	    String line;
	    while((line = buffer.readLine())!=null) {
		System.out.print(line + "\n");
	        data += line + " \n ";
	    }
	}
	catch(Exception e)
	{
	    System.out.print("Exception:"  + e);
	}

	st = new StringTokenizer(data, " ");

	// store first tag for comparison
	next(st);
	first = next;
	next(st);

	System.out.print("\nderiving " + first + "\n");
	evaluate();

	System.out.print("\nthe derived sentance is:\n" + sentance + "\n");

    }

    public void next(StringTokenizer stuff) {
	next = stuff.nextToken();
    }

    public void evaluate() {

	next = st.nextToken();

	// make sure we only "recurse" through first line of grammar
	if(!next.equals("\n")) {
	    if(Pattern.matches(regex, next) == true) {
	        prompt(next);
		evaluate();
	    } else {
		sentance += next + " ";
		evaluate();
	    }
	}
    }

    // this method is where we ask the user for their choice
    public void prompt(String tag) {
	System.out.print("deriving: " + tag + "\n");
	System.out.print("specify number of choice: | ");

	String prev;
	StringTokenizer st2 = new StringTokenizer(data, " ");

	// find the correct starting line
	while(st2.hasMoreElements()) {
	    prev = next;
	    next = st2.nextToken();
	    if(prev.equals("\n") && tag.equals(next)) {
		break;
	    }
	}

	next(st2); next(st2);

	ArrayList<String> myArr = new ArrayList<String>();
	int i=1;
	while(st2.hasMoreElements()) {
	    if(next.equals("\n")) break;
	    if(!next.equals("|")) {
		System.out.print(i + ": " + next + " | ");
		myArr.add(next);
		i++;
	    }
	    next(st2);
	}

	Scanner console = new Scanner(System.in);
	System.out.print("\n? ");
	int choice = console.nextInt();

	if(Pattern.matches(regex, myArr.get(choice-1)) == true) {
	    prompt(myArr.get(choice-1));
	}else{
	    sentance += myArr.get(choice-1) + " ";
	}
	
    }

}

Then you just have to call the class with your grammar file like this:

new ParseBNF("grammar.txt");