Walter - Discrepancy between EqualExpression spec and implementation

[James Dunne]

Jarrett Billingsley wrote:
> "Jarrett Billingsley" <kb3ctd2 at yahoo.com> wrote in message 
> news:e5d40i$vp4$1 at digitaldaemon.com...
> 
>>I'm writing a small scripting language with a syntax based on D, and as 
>>such, I'm basing some of the parsing code off the the DMD frontend source. 
>>I've found a discrepancy between the spec and the code, though, and I'm 
>>not sure if it's a bug or if it was changed in the code on purpose and the 
>>spec just hasn't been updated.
> 
> 
> I just realized that most of the parsing functions follow this same pattern 
> (of not following the spec).  The only functions that seem to follow the 
> spec are parseAssignExp() and parseCondExp(). 
> 
> 

I've taken a serious look into this too :)  Here's my answer:

See the while loops implemented in most of those functions?

Grammar rule:
-------------
OrOrExpression:
	AndAndExpression
	OrOrExpression || AndAndExpression

DMD implementation:
-------------------
Expression *Parser::parseOrOrExp()
{   Expression *e;
     Expression *e2;
     Loc loc = this->loc;

     e = parseAndAndExp();
     while (token.value == TOKoror)
     {
	nextToken();
	e2 = parseAndAndExp();
	e = new OrOrExp(loc, e, e2);
     }
     return e;
}

So, on the first iteration we either get an AndAndExpression alone, or 
an OrOrExpression with the left expression being an AndAndExpression and 
the right expression being an AndAndExpression.

The left-recursive descent rule 'OrOrExpression || AndAndExpression' 
means to loop over the left side until a subsequent token is NOT the 
'||' token.  Thus, we can only get an OrOrExpression out of two 
AndAndExpressions next to each other, separated by the '||' token, or 
just an AndAndExpression alone.  So, the code does implement the spec 
correctly.  All the other expression rules follow this pattern.

As to the exceptional case of AssignExpression:

Grammar rule:
-------------
AssignExpression:
	ConditionalExpression
	ConditionalExpression = AssignExpression
	ConditionalExpression += AssignExpression
	ConditionalExpression -= AssignExpression
	ConditionalExpression *= AssignExpression
	ConditionalExpression /= AssignExpression
	ConditionalExpression %= AssignExpression
	ConditionalExpression &= AssignExpression
	ConditionalExpression |= AssignExpression
	ConditionalExpression ^= AssignExpression
	ConditionalExpression ~= AssignExpression
	ConditionalExpression <<= AssignExpression
	ConditionalExpression >>= AssignExpression
	ConditionalExpression >>>= AssignExpression

DMD implementation:
(I've expanded out the #define shortcut for readability)
-------------------
Expression *Parser::parseAssignExp() {
     Expression *e;
     Expression *e2;
     Loc loc;

     e = parseCondExp();
     while (1) {
         loc = this->loc;
         switch (token.value) {
             case TOKassign:  nextToken(); e2 = parseAssignExp(); e = 
new AssignExp(loc,e,e2); continue;
             case TOKaddass:  nextToken(); e2 = parseAssignExp(); e = 
new AddAssignExp(loc,e,e2); continue;
             case TOKminass:  nextToken(); e2 = parseAssignExp(); e = 
new MinAssignExp(loc,e,e2); continue;
             case TOKmulass:  nextToken(); e2 = parseAssignExp(); e = 
new MulAssignExp(loc,e,e2); continue;
             case TOKdivass:  nextToken(); e2 = parseAssignExp(); e = 
new DivAssignExp(loc,e,e2); continue;
             case TOKmodass:  nextToken(); e2 = parseAssignExp(); e = 
new ModAssignExp(loc,e,e2); continue;
             case TOKandass:  nextToken(); e2 = parseAssignExp(); e = 
new AndAssignExp(loc,e,e2); continue;
             case TOKorass:   nextToken(); e2 = parseAssignExp(); e = 
new OrAssignExp(loc,e,e2); continue;
             case TOKxorass:  nextToken(); e2 = parseAssignExp(); e = 
new XorAssignExp(loc,e,e2); continue;
             case TOKshlass:  nextToken(); e2 = parseAssignExp(); e = 
new ShlAssignExp(loc,e,e2); continue;
             case TOKshrass:  nextToken(); e2 = parseAssignExp(); e = 
new ShrAssignExp(loc,e,e2); continue;
             case TOKushrass: nextToken(); e2 = parseAssignExp(); e = 
new UshrAssignExp(loc,e,e2); continue;
             case TOKcatass:  nextToken(); e2 = parseAssignExp(); e = 
new CatAssignExp(loc,e,e2); continue;

             default:
             break;
         }
         break;
     }
     return e;
}

Here, we see that e2 is always evaluated as an AssignExpression, thus 
this rule is right-recursive, not left-recursive as the other pattern. 
Again, note the while loop here.

I'm not sure how to make it clearer, but if you have any questions don't 
hesitate to ask.

P.S. - I've also used this code pattern as a template for my own 
language parser and it does work quite well.

-- 
Regards,
James Dunne