Re: C and LL (1) (
5 Nov 2001 00:17:32 -0500

          From comp.compilers

Related articles
C and LL (1) (Pedro Pereira) (2001-10-23)
Re: C and LL (1) (Martin von Loewis) (2001-10-27)
Re: C and LL (1) (Andrew Wilson) (2001-10-27)
Re: C and LL (1) (2001-10-27)
Re: C and LL (1) (Martin von Loewis) (2001-10-28)
Re: C and LL (1) (2001-11-04)
Re: C and LL (1) (2001-11-05)
Re: C and LL (1) (Geoff Wozniak) (2001-11-08)
Re: C and LL (1) (Joachim Durchholz) (2001-11-11)
| List of all articles for this month |

From: (
Newsgroups: comp.compilers
Date: 5 Nov 2001 00:17:32 -0500
References: 01-10-121
Keywords: parse, LL(1)
Posted-Date: 05 Nov 2001 00:17:32 EST

The advantage to LL(1) parsing is that the algorithm and logic are
fairly simple. The logic of the parser can be combined directly with
the rules of the grammar. Tables can be created for efficiency, which
are also very easy to create.

For languages such as C, which are inherently ambiguous, a recursive
decent parser may require an extensive number of branches for each
level of recursion. As a result, it will take a large amount of time
to analyze the grammar as well as tax system resources.

In C, statements can be used in conjunction with other statements
without the use of a reserved-word that defines the extent of the
statement's scope. As a result, C is susceptible to the infamous
"hanging else" problem. The problem is caused when an if-statement is
used as the 'then' clause of another if-statement

For instance, in C the if-statement can be defined as follows:

<Statement> ::= if <Expression> <Statements>
                            | if <Expression> <Statements> else <Statements>

This allows the following statement to be constructed

if a < b
      if c < d
            a = b + d;
            b = a + c;

In the above statement, to which if-statement does the 'else' belong?
The grammar can be modified to handle this problem; however, this
creates additional possible states for the LL(1) parser.

In any case, I would recommend that you use a LALR(1) parser generator
such as YACC, JavaCC or the GOLD Parser (which I am plugging for
obvious reasons). LR(1) parsers are faster and less taxing of system
resources than the recursive decent parsers.

Anyway, good luck on your project.

- Devin Cook

Post a followup to this message

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