Top  Previous  Next

Grammar tests > LL(1)-Test


Recursive descent parsing requires that the grammar of the parsed language satisfy the LL(1) property. This means that at any point in the grammar the parser must be able to decide on the bases of a single look-ahead symbol which of several possible alternatives have to be selected.  For example, the following production is not LL(1):


ident ":=" Expression

| ident ( "(" ExpressionList ")" )?


Both alternatives start with the symbol "ident", and the parser cannot distinguish between them if it comes across a statement, and finds an "ident" as the next input symbol. However, the production can easily be transformed into




":=" Expression

|  ( "(" ExpressionList ")"  )?



where all alternatives start with distinct symbols. There are LL(1) conflicts that are not as easy to detect as in the above example.  For a programmer, it can be hard to find them if he has no tool to check the grammar.  The result would be a parser that in some situations selects a wrong alternative. The TextTransformer checks if the grammar satisfies the LL(1) property and gives appropriate error messages that show how to correct any violations.


If LL(1) conflict can't be resolved by restructuring the grammar, you can use the IF...ELSE...END or WHILE...END structures.




This page belongs to the TextTransformer Documentation

Home  Content  German