views:

41

answers:

1

I cannot for the life of me figure out why Alternative is left recursive. It really throws a wrench into my parser.

Alternative :: 
    [empty] 
    Alternative Term 

Here is a note in the semantics portion of the spec that is not exactly clear. Maybe the reasoning would be revealed once I understand this?

NOTE Consecutive Terms try to simultaneously match consecutive portions of the input String. If the left Alternative, the right Term, and the sequel of the regular expression all have choice points, all choices in the sequel are tried before moving on to the next choice in the right Term, and all choices in the right Term are tried before moving on to the next choice in the left Alternative.

What kind of parser can properly handle a left recursive grammar?

+1  A: 

Because for certain types of parser left-recursion is much better (e.g. for yacc - see section 6.2 here for an explanation).

If it's causing trouble for your particular parser, then by all means swap it over - it doesn't affect the definition of the language in any way.

psmears
I believe that my parser is known as a recursive descent parser and I am wondering what type of parser would be used without swapping the symbols. *PS: In case you haven't noticed I am new to this.*
ChaosPandion
The parser I mentioned in my answer, yacc, is an LALR(1) parser (see http://en.wikipedia.org/wiki/LALR_parser).
psmears
I am going to accept this answer as I had previously switched the symbols around and ran in to no issues. I just wasn't sure if it could lead to unintended consequences in my final implementation.
ChaosPandion