Re: LL(1) problem

Carl Cerecke <cdc25@it.canterbury.ac.nz>
5 May 2003 23:33:29 -0400

          From comp.compilers

Related articles
LL(1) problem albert@shqiperia.com (Albert) (2003-04-27)
Re: LL(1) problem cdc25@it.canterbury.ac.nz (Carl Cerecke) (2003-05-05)
Re: LL(1) problem vbdis@aol.com (2003-05-05)
Re: LL(1) problem slk15@earthlink.net (SLK Parsers) (2003-05-06)
| List of all articles for this month |

From: Carl Cerecke <cdc25@it.canterbury.ac.nz>
Newsgroups: comp.compilers
Date: 5 May 2003 23:33:29 -0400
Organization: TelstraClear
References: 03-04-091
Keywords: LL(1), parse
Posted-Date: 05 May 2003 23:33:29 EDT

Albert wrote:


<LL(1) problem with the folowing rules>


> Factor = LogicalConstant | LiteralExpression | MemberAccess | ident |
> "(" Expression ")" | "bosh".
> MemberAccess = (ClassName | "ky") "." ident [ "(" [ArgList] ")" ].
  > ClassName = [PackageName] "." ident .
  > PackageName = ident ":" ident { ":" ident }.




The problem is that, within the Factor function, you can't decide
between Factor -> ident and Factor -> MemberAccess because both
can start with "ident".


Some solutions are:
1. Use LALR parsing. It won't have the problem, but is probably a bigger
change than you want to make.


2. Note that, for MemberAccess to start with an ident, the ident must be
the start of a PackageName. You can, therefore, look up the identifer
in the symbol table to see if it is a package name (Assuming the ident
in Factor->ident is not allowed to be a package name) and make the
decision based on that.


3. Using the information from 2, the symbol following the ident will be
a ":" only if it is a PackageName. So you can simply look ahead one
symbol when lloking at an identifier and choose MemberAccess if you see
a ":", and Factor->ident otherwise. In other words, your language is
LL(2).


Cheers,
Carl.


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.