Re: C and LL (1)

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;
      else
            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
    GOLDParser@DevinCook.com
    http://www.devincook.com/GOLDParser

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