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.

ex.: "AAABAD" is matching, "AAAD" is matching, "AAAB" is not matching, "AD" is matching, ...

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
  • 1
    What's the problem? All the parsec-like libraries, for example, provide a maybe combinator. – SK-logic Nov 1 '11 at 12:08
  • 1
    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

Rule1C → "AC" "AD"

Rule1C → "AD"

This might not be that efficient, but it's relatively clear. I believe you will need recursive descent with backtracking for this though.

  • I don't understand this. How can these rules deal with "AAABAD"? – Industrial-antidepressant Oct 31 '11 at 23:37
  • I missed that case, and was trying to rewrite accordingly but someone else was editing at the same time so it took a while. – psr Nov 1 '11 at 0:04
  • Oh, I understand now... This can be a solution. But I think there can be a "character base" solution somehow. – Industrial-antidepressant Nov 1 '11 at 0:11
  • 1
    @Industrial-antidepressant, you may want to read about PEGs: en.wikipedia.org/wiki/Parsing_expression_grammar – SK-logic Nov 1 '11 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.