# Best way to parse optional grammar rules?

I started to write a hand written parser just for fun. For simple rules it is working, but I have problem with the optional grammar rules. I marked the optional rules with a question mark.

Here is a simple rule:

``````rule1:  "AA"? "AB"? "AC"? "AD"
``````

So AA, AB and AC string is optional, but AD is required.

I need an algorithm and not a regex tool or something like that. I can solve this with brute force method (so trying every possible combination of the rules) but I think there is a better way to do this.

• What kind of parser are you writing? LL1? Recursive descent? – psr Oct 31 '11 at 23:17
• It is a recursive descent variant – Industrial-antidepressant Oct 31 '11 at 23:23
• You can quite naturally handle these kinds of rules in various parsing algorithms, Earley being one of them, but I'm not aware of a similar method for LL parsing. – Alex ten Brink Oct 31 '11 at 23:30
• What's the problem? All the parsec-like libraries, for example, provide a `maybe` combinator. – SK-logic Nov 1 '11 at 12:08
• I probably should have said this in my answer, but unless you're doing this to learn there is rarely a good reason not to use tools for this stuff. They are easier to learn than you might expect and this is an area where the amount of tools out there is enormous. – psr Nov 1 '11 at 16:18

Normally your lexer would distinguish "AA", from "AB", etc. If that's an issue I can elaborate.

If the lexer does, you have the partial grammar:

Rule1 → "AA" Rule1B

Rule1 → Rule1B

Rule1B → "AB" Rule1C

Rule1B → Rule1C