[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: grammar questions



Indrek Mandre wrote:
> Unfortunately it's not that easy. The two kind of 'if' statements are
> different statements, adding an optional colon won't do much good.
> 
> You can't mix colon and noncolon keywords. And what more, the
> colon is something like '{', it allows you to group more statements
> together. And you forgot the 'endif'.
> ...
> ---now a real nut to crack - mixing (valid theoreticly, tho
>        not in current php language implementation using bison):---
> 
> if (a):
>   if (c) x = y;
> elseif (b):
>   z = d;
> endif;

This is an example of a language which is not LR(k) for any k.

What's the problem?  It is that when the parsers sees "elseif", it
cannot decide whether the elseif belongs to "if(a):" or to "if(c)".  To
decide, it has to know if there will be a ":" after "(b)".  But "(b)"
could theoretically be arbitrarily long "(x+y>z*x*m...)".

Note that there's necessarily a shift/reduce conflict.  You cannot shift
"elseif" to detect later that it has a colon.  Nor can you reduce "if
(c) x = y;" to later discover that there's no colon. [Just imagine
nested "if"s, if it helps you].

You will have to make a choice.  The best you can do is automatically
associate an "elseif" with the closest enclosing "if()" or "if():".

So, in the case of your example, you would get a parsing error, because
it would be parsed as:
if (a):
  if (c) 
    x = y;
  elseif (b): *** parse error: ":" is invalid in this context.
...

This is not easy to do cleanly, but it is feasible.

Etienne
PS: This one was not easy to visualize...
-- 
----------------------------------------------------------------------
Etienne M. Gagnon, M.Sc.                     e-mail: egagnon@j-meg.com
Author of SableCC:                             http://www.sablecc.org/
and SableVM:                                   http://www.sablevm.org/