Monday, March 30, 2009

LL(k) Parser - Tail Ambiguity

One of the fun things of doing it yourself is you learn of some annoying hurdles, the hard way. The most recent of which is what I'm calling 'Tail ambiguity', which is basically a lock created by the required part of a rule after the parsing rule exits. A lock exists with the optional aspect of the parsing rule and the required aspect of (one of) the calling rule(s).

A simple example is if you have a rule encased in '(' and ')', between the two you call a second rule, which ends with an optional series of ')' sets, you would have to determine on the calling rule how many of those ')' elements belong to the optional part of the current rule and how many belong to that of the calling rule. Things get more complicated when you consider recursion on the first rule encased in parenthesis.

After pondering this constantly from when I encountered it (by making a toy grammar for kicks, without the intent to find it), I think I nearly have a solution, I just want to make sure before I spend a few days implementing something that may not work. I haven't even began to cover what happens when the optional tail of a rule is locked between multiple rules, and those calling rules have potentially more than one token locked between them. Let alone the lock that might occur with the token's pattern itself.

Good news is this only applies to the optional part of the rule, if you can call that good news; however, since such an assumption can't be made, I'll likely have to reduce this system similar to a standard look-ahead ambiguity and utilize the same logic. Except the problem here is it's not fixed like standard rules, it's mutable since the depth, specific rules, and so on are not constant. Which means I'll have to adjust my overall look-ahead concept and come up with a dynamic solution that can handle standard look-ahead locks and tail locks, and combine to make something else entirely.

Guess that's what I get for trying to make a non-backtracking LL(k) parser. Such are the joys of programming.

No comments: