Download An Eclipse-Based Integrated Development Environment for Curry

4.1 Theoretical Foundations
Left-factoring
A common problem for LL-parsing is that productions have same prefixes. If the length
of a common prefix of two productions is greater or equal to the lookahead constant
k, the parser is not able to make a decision which of those productions to take (in
corresponding situations). Usually, it is possible to rewrite the production rules to
postpone the decision. This transformation is called left-factoring.
In general left-factoring can be applied as follows: Let A → αβ1 |αβ2 be two productions. We rewrite them as follows:
1
2
A → αA′
A′ → β1 |β2
This transformation allows the parser to make the decision when necessary information
is available.
Backtracking
Backtracking is an approach to extend the decision-making ability of top-down parsers.
The idea of this approach is to test possible alternatives subsequently for their applicability. If an alternative has been tested successfully, the parser make the appropriate
decision. The problem with backtracking is that, in the worst case, it may take time
that is exponential in the input length.
There is also a method to realize backtracking that guarantees linear parsing time, in
return, it has very huge memory consumption [FK02].
LL(*) Parsing
LL(*) is a top-down parsing strategy which focuses on expressiveness rather than on
pure performance. [PF11] introduces the concept as follows:
LL(*) stands for LL(k) parsing with dynamic lookahead k ≥ 1. The key idea is to use
regular-expressions rather than fixed constant or backtracking with a full parser to do
lookahead. This can be done by trying to construct a deterministic finite automaton
(DFA) for each non-terminal in the grammar to distinguish between between alternative
productions. If no suitable DFA for a non-terminal can be found, a backtracking strategy
is used. As a consequence, LL(*) parsers can use arbitrary lookahead and, finally, fail
over to backtracking depending on the complexity of the parsing decision. Although, the
parsers decide on a strategy dynamically according to the input sequence. This means
that just because a decision might have to scan arbitrarily far ahead or backtrack does
not mean that it will at parse-time. In practice, LL(*) parsers only look ahead one or
two tokens ahead on average despite needing to backtrack occasionally.
27