The ambiguity checker can reach a bit further into the C99 search space, going 6 deep before it runs out of memory. All conflicts in C99 are resolved, but C++ awaits. It needs more work before it can truly do a depth first search or at least iteratively deepening. Once that is taken care of, the only real issue will be the massive search space.

This of course, would be much more useful if the GLR generator subsystem of the wormhole parser generator weren’t currently broken, but nobody’s perfect.

If you didn’t already know, checking for grammar ambiguities in the general case is a fool’s errand, because it has been proven undecidable (the algorithm to decide if a grammar is ambiguous will run forever on some grammars, and we can’t even decide if it will run forever or not).  Despite the exponential growth of our search, this doesn’t mean we are stuck with nothing.  The exact length of what can be checked depends on the available system resources, and effective branching factor of the language, but by using the GLR algorithm and turning it into a next symbol generator, we are able to check billions of permutations resulting is finding ambiguities up to dozens of symbols long, sufficient for many modern languages.

Like many parsers, the GLR algorithm is an LR based parser will build a parse tree from a series of tokens.  Unlike most though, it is able to handle ambiguous grammars.  Of practical interest, this means that a GLR parser can handle the ambiguous grammar of C++.  It accomplishes this, in concept, keeping a multitude of stacks, each representing one of the many possible parses of the input.  Naturally, the more ambiguous any particular input, the greater the performance hit for using this approach.

To explain what goes on inside a GLR parser.  We’ll consider what happens when processing a single input token.  As a prerequisite, you need an LR table, produced from a suitable grammar, such as the wormhole parser generator.

Before we dive into the algorithm, we need to understand the structure of the data. GLR carries it’s stacks in something called the graph structured stack.   The parser represents it’s “stacks” as a series of graph nodes, each node represents a state, and is connected to it’s stack predecessors, and each association between nodes carries along the parse tree for that particular part of the stack.  The structure of the parse tree isn’t important, but it is just important to know that it is carried there.

struct node

{

int state;

link links[];

};

struct link

{

node *prev;

parsetree *t;

int reject;

};

For instance, the stack (C, B, A) with states (1, 2, 3) respectively could be declared by hand with these structures.

node C = {1, { {0, 0} } };

node B = {2, { {&C, 0} } };

node A = {3, { {&B,0} } };

The A is on the top of the stack, while C is on the bottom.  Now, if we wanted to declare an additional stack (C, B, D) with states (1, 2, 3) respectively, we need only add a node D and hook it to B, like this.

node D = {4, { {&B,0} } };

The stacks are in compact form, with the shared parts (C, B) requiring only one set of data.  Similarly, we could simultaneously declare stacks (C, E, A), (C, B, A), (C, E, D), (C, B, D) like this:

node C = {1, { {0, 0} } };

node B = {2, { {&C, 0} } };

node E = {5, { {&C,0} } };

node A = {3, { {&B,0}, {&E, 0} } };

node D = {4, { {&B,0}, {&E, 0} } };

Hopefully now it is clear how graph structured stacks work.  When we want to record the fact that we have these four stacks, we need to have an array with the tops of the stacks, in this case D and A.  In the GLR algorithm, we call this the activestacks.

node *activestacks[];

Like we said earlier, let’s consider what happens when we add a single token.  Now, if this were just a plain LR algorithm, we would have a single stack, and adding a token would either cause us to shift the token onto the stack (push a new state on the stack) a reduce (pop some elements from the stack, combine them into a single element, and  push the combined element onto the stack, followed by possible additional reduce actions until finally we shift the token onto the stack) or if the token is the end-of-input token (designated $) we might accept the input as complete or if that token is unexpected at that point in the parse, we might get an error in which case we simply drop the stack with the error from the activestacks list.  We’ll ignore errors, and only consider valid input tokens.

Well, GLR works the same way, except we need to handle all of the stacks at the same time, and sometimes, we need to handle multiple actions at the same time, where we have to shift and reduce at the same time, a situation which is considered a grammar construction error to LR algorithms, but which instead produces an additional stack in GLR.  GLR differs in another way too, since it handles ambiguous grammars as well, it necessarily had reject productions as well.   That is, in addition to the usual production definition, a production can be marked as a reject production, in which case if the production’s non-terminal is reduced in a regular production as well, it will be ignored instead.

floating : [number] ‘.’ [number] ;

floating: ‘.’                                              %reject ;

In this example, (1.1, 1., .1, .) are all valid reductions of floating.  However ‘.’ by itself makes a poor floating point number, so we added the reject production, and so ‘.’ will be ignored as a floating value.

Let’s not get ahead of ourselves.  Our entry point where we start our update is a function, update_states.

void update_states(int nexttoken);

update_states first job is to try to process the activestates and figure out if the nexttoken calls for us to shift or reduce.  Since we’ll be updating activestates, we immediately take a copy of them, this copy is called the for_actor.  Once those states are updated, we want to evaluate reject productions (if we evaluate reject productions before all states are evaluated, some reductions can go without being rejected).

node *for_actor[];

copy the contents of activestates into for_actor

node *for_actor_delayed[];

for_actor_delayed is initially empty

For each stack head in for_actor, we look up the actions for the state on the top of the stack(s).  shift actions call for us to “push” onto the stack.  In this context though, push means create a new node, with a link that points to the previous top of the stack, and to propagate that new node such that it appears within activestates during the next call to update_states.  Simply adding the new node to activestates is problematic.  If we try to mix new states in with old, we can’t say which are meant to survive into the next round.  Moreover, we can potentially end up adding duplicate states from other stacks in this same round.  If we try to fix this by doing a find-or-create solution, we may find nodes with matching states from the previous round, in which case we can corrupt the stack by having nodes which link to themselves.    Of course, the solution is very simple, just delay the shift until the reductions are complete, and then use a find-or-create style lookup on a seperate list.  Until we are ready to act on the shifts, we simply hold them in a list called the for_shifter list.

struct lrshift
{
pnode *prevstate;
int shiftto;
};

lrshift for_shifter[];

Moving on.  When the action is to reduce, we pull N states off the top of the stack (N = the number of symbols in the production we are reducing), combine them into a single node, and then push them onto the stack (shift the production) awaiting further action based on the current input token.  Since we are already processing the for_actor list, we simply put any new states at the end of that list, and things work out naturally.  However, this is where things start to get a little messy.  To “pull N states off the top of the stack” we have to deal with the fact that any one stack can represent a multitude of stacks.  To handle this properly, we need to make a list of all possible states of the proper length preceding the top of the stack.  We keep a reducepath to hold onto that list, and then call a function recursively, exploring the alternative paths N nodes deep.  For each of the accumulated paths, we merge reducepath into any previously accumulated paths, and call reducer to do the real reduction action.  We’ll explain reducer shortly, but for the moment the code looks roughly like this:

void update_states(int nexttoken)

{

node *for_actor[] = activestates;

node *for_actor_delayed[]

lrshif for_shifter[]

while for_actor or for_actor_delayed are not empty

{

if  for_actor is empty, remove a node from for_actor_delayed and put into for_actor

for each node in for_actor

{

for each action from the node.state on input nexttoken

{

if the action is shift, add to for_shifter

if the action is reduce (accept, reject), call do_reductions(node, N = the number of symbols in the production being reduced, p = the production we are reducing)

}

}

empty for_actor

}

(Apply the shifts in for_shifter)

(Drop rejected paths)

}

void do_reductions(node *state, int count, production p)

{

if( count > 0 )

{

(This is the part that expands all the possible stacks preceding state)

add state.t to the end of reducepath

do_reductions(state.prev, count-1)

remove the last element of reducepath

}

(We fall through to this once we accumulate a stack of size N)

create a new parsenode, containing the contents of reducepath, but do not alter reducepath.

if we are handling an accept action, store and/or merge the parsenode into the accept parse tree and return.

(Remember, state is actually N nodes deep in the stack now)

int next_state = the number of the state to shift to from state state.state on the input p

call reducer(state, next_state)
}

void reducer(node *state, int next_state);

So now that we see how to get all of the possible stacks from a given state and put them into reducepath we need to talk about what we do with it.  If the action is in fact an accept action, we can stop.  Generally, we’ll store the reducepath as the accept parse tree.  In GLR, there are potentially more than one way to accept a parse string.  If there is already an accept parse tree, we merge the tree with the previous accept parse tree.  Otherwise, we call reducer.

reducer tries to create a new node and link path from state (which is N deep on the stack) to a node with node.state = next_state.  reducer will do a find-or-create for such a state activestacks and a find-or-create in the node for a link to the state.  If we are rejecting, then new nodes receive a reject flag, links (new and old alike) receive a reject flag.  We search for them in activestacks because we might have already created such a state.  When new nodes are created from reduction, they are put into for_actor for evaluation, and when they are created from rejection they are put into for_actor_delayed so they can be sure to reject at the right time.

When the link to state is found to exist already, it means that we have found an ambiguity, and the previously existing parsetree link.t must be merged with the new parsetree formed by the merged reducepath.  On the other hand, adding a link to state can create a number of new stacks that simply didn’t exist before.  This simply means that there are new ways to reduce previously inspected stacks.  It also means that we must run reducer on all of the new stacks created by the addition of the new link.  To do this, we simply create a new function do_new_reductions that behaves much like do_reductions, except will only bother to call reducer if the stack contains the new link, otherwise it is ignored, and we run this new function on all of the nodes in activestacks.

If there are new ways to reduce previously inspected stacks, then there are new ways to reject them also, and I have found that under some circumstances, despite the presence of for_actor_delayed, the standard GLR algorithm does not apply all rejects (or, depending on how you look at it, sometimes my reject rules are malformed).  Right now, I wish I could remember the exact circumstances.  I believe it was something like this using the SGLR variant:

id : /[a-z]+/

keyword : ‘keyword’

id : keyword    %reject

To correct for this, an equivalent of do_new_reductions, more aptly named do_new_rejections must be created.  Like do_new_reductions, do_new_rejections cares only about new stacks that contain the new link.  However, do_new_rejections is only interested in finding previous reductions, so it will do find, to find states and links, but not create.  When it finds a link, and it will try to remove any previously merged parsetree from ambiguous parsetrees, and mark clearly rejected reduction links as rejected.  Finally, it will call do_new_rejections instead of reducer, since it is not interested in creating new states.

Finally, after all of this, we get back to update_states.  One we are done processing for_actor, we need to process the shifts (just find-or-create the state in the lrshift structure, and link it to the lrshift.prevnode), and put the results somewhere.  Since it’s handily empty, we put the resulting states into for_actor_delayed.  After adding each state, we drop rejected stacks.  This just means we walk the graph structured stack and remove links with either the rejected flag or that link to rejected states, and since reducer has been keeping the flags updated for us, this is a cinch.

As the final detail, we must assign for_actor_delayed back onto activestacks, and the cycle is complete.  Repeat calling update_stacks until out of input, and you’ve got a parser.

The source for this algorithm can be found by perusing the wormhole parser generator.  Feel free to leave comments and ask questions.