CODEWITHSUNDEEP
javaparsingrecursion
thehandyman
thehandyman

Reputation: 939

Recursive descent parsing for boolean grammar

I'm attempting to learn compilers and recursive descent parsing by example. This is not a homework assignment. I've tried looking at a few of the other answers, but am having trouble understanding them.

The example I'm using is a boolean expression parser that returns the areas where the expression is valid and invalid.

Valid syntax is whitespace, parentheses, AND, OR, and lowercase words. Lowercase words need to be separated by boolean operators (i.e. cat AND mouse).

Some examples of how this would work: 

"cat AND mouse" = "cat <v>AND</v> mouse"
"cat AND mouse OR" = "cat <v>AND</v> mouse <i>OR</i>"
"pet OR ((domestic AND cat)" = "pet <v>OR</v> <i>(</i><v>(</v>domestic <v>AND</v> cat <v>)</v>"
"cat food" = "cat <i>?</i> food"

As you can see, what I want to output is whether each parenthesis and boolean operator is valid by surrounding it with either a "v" tag for valid or an "i" tag for invalid.

I believe the grammar for the language looks like this (please correct me if I'm wrong):

Expression -> 1 or more clauses
Clause -> lowercase_term | (lowercase_term bool_op lowercase_term)
Lowercase_Term -> 1 or more letters from [a-z]
Bool_Op -> AND | OR

However, I'm not too sure how to go about making a recursive descent parser from this. I'm assuming it needs to be a tree of some sort, but just not sure.

For reference, I'm doing this in Java, but pseudocode or any language code that will help me understand this will be very much appreciated!

Upvotes: 0

Views: 1501

Answers (2)

user6823513
user6823513

Reputation:

Here you can read and try the examples, I explained there how to parse and interpret arithmetic expressions using recursive descent parsing technique:

https://leanpub.com/pic/read#leanpub-auto-chapter-2---parsing-and-calculating-expressions

Recursive descent parsing is -almost- most intuitive parsing technique. It is pretty enough to write your own hand coded interpreter, not with only arithmetic expressions, also with loops, if-else statements, etc.

Here is my hand coded toy interpreter I have written using recursive descent parsing technique:

https://github.com/mehmetcoskun/contra

It is open source, you can download and tweak.

Upvotes: -1

Udo Borkowski
Udo Borkowski

Reputation: 311

Have a look at How To Build A Boolean Expression Evaluator - Using a recursive descent parser and the interpreter pattern. This looks very much like the stuff you are asking for.

Regarding detecting the "valid" vs. the "invalid" part of the input: a simple approach would be: first try to parse the complete text. If this works the full text is valid. Otherwise parse the text up the second last character etc. until you finally find a prefix of the input that is valid. All text following is then "invalid".

Upvotes: 1

Related Questions