Polishing precedence

Introducing generics (or template — at this stage the implementation does not matter) was like opening Pandora box. Benign angle brackets added so much local ambiguity that using regular NLT features I couldn’t parse the code (OK, I admit, I try to avoid forking whenever I can).

Consider such code:

if X<Y...

Is it just basic conditional, and should be read as:

if (X<Y) ...

or is it first part of generic expression:

if (X<Y>) ...

There are more operators involved here — what to do in case of “+” and “<” conflict? And what to do in case of two “<”? To keep long story short I refined the way the operators are picked up and also introduced more precise pattern to define resolution of shift/reduce conflict, for example:

rs shift LANGLE expression(AND OR EXOR) expression;

This translates to rule — make a shift when incoming symbol (lookahead) is left angle bracket and there is AND, OR, or EXOR operator on stack and there is conflict between expression and expression. Such pattern makes the code:

if 5<3 and 2<7 then

to parse as:

if (5<3) and (2<7) then

One note: without template syntax setting the priority of basic operator precedence (like in yacc) was enough.

I had to drop one feature I added some time ago, naively thinking it could limit the number of the conflicts. Until today when there was empty reduce rule conflicting with shift rule NLT reduced first and then shifted. With template syntax I finally found counter example — consider defining new class:

class Foo _ : Bar

(underscore denotes template arguments placement), and passing named argument to a function:

foo(x _ : 5);

Here underscore denotes a problem — we have identifier (exactly like previously) and possibly empty template (because of the grammar). The question is should we make this empty template or not? Of course not, you cannot write:

foo(x<String> : 5);

but with mechanism of creating reduce+shift sequence it was exactly what happened — fixed!

Tagged , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: