user840718 user840718 - 1 year ago 263
Java Question

Convert BNF grammar to Java

How can I convert this simple (recursive) grammar to Java?

C --> a | not C | C and C | C or C ;

This question is not meant what tool I have to use to parse a grammar (like Javacc or Antlr), but the way to model this simple grammar using the object-oriented paradigm.

Answer Source

I don't think there's a single way to model this using OOP and that there are many equally valid ways you could go about approaching this. The following is one reasonable strategy for thinking about what this might look like in code.

Usually, when parsing an expression, your goal is to reconstruct an abstract syntax tree for the input. That tree structure has different types of nodes based on the different productions that are possible, and in Java you'd probably represent them with some polymorphic type. For example, you might have a base class ASTNode that has children ANode, NotNode, AndNode, and OrNode. These last three types would store pointers to the subexpressions that make up the compound expression.

Once you have these types, you'd then need to put together some sort of parser - and possibly a scanner - that would take the input and construct the appropriate tree from it. Since you're looking at a grammar that consists of different operators with different precedences, you could use a simple precedence parser like Dijkstra's shunting-yard algorithm to do the parsing. That algorithm is relatively straightforward to implement.

At that point it really depends on what you want to do with the AST. If you want to evaluate the expression depending on what inputs are provided, for example, you could add an abstract method evaluate to the ASTNode type and then have each derived type provide an implementation that performs the appropriate operation. You could also consider using the visitor pattern to build visitors that walk the AST and perform appropriate operations at each step.

I'm not sure whether this would be helpful, but a while back I wrote something very similar to what you're looking at to generate truth tables for propositional logic for a class I often teach. The tool itself is available here, and the source files, which are decently well-commented, are available here. It's written in JavaScript rather than Java, but it shows off all the pieces described above - the AST node type, the shunting-yard algorithm to do parsing, and overridden methods to evaluate the different expressions.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download