Should that grammar be:
Expr = "A" | "(" Expr* ")" | ""
so that (()) is s a valid match? Because then Expr can be an empty string also?Typically Star (*) means zero or more while Plus (+) means one or more.
Re:My First Fifteen Compilers
by Technetium_Hat on Friday July 12, 2019 @10:13AM
(#20420871)
`Expr*` means zero or more, so the empty string is implicit.
Regardless of whether you are writing a grammar or a recursive descent parser, start with a really simple language say:
Which is balanced parentheses with the token that is the exact character "A" possibly appearing. All of these are valid matches: The parse tree should be such that each node is a list where each element is either an A token or another parse tree node. Once you can parse that, then you can start moving on to more complicated grammars; a possible complication is to add "B" as a valid expression, with the caveat that B cannot be the sibling of a parenthesized expression. That is: is valid, but is not valid.I used single characters as the primitive here, so perhaps the next step would be to add a tokenizer. "B" has special rules, so it will be the keyword "bananas". A will be any other alphabetic token.
If all of the above is already doable, then perhaps I've misunderstood where your hangup is. Let me know, perhaps I can help.