Next: Comparison with plex
Up: a
Previous: Implementation
Look Ahead
The implementation of look ahead given in the previous section is
simple, straightforward and flexible, but has a number of drawbacks
(if look ahead is greater than 0):
- the implementation is inefficient since sequences of characters
are scanned more than once (during look ahead and during the actual
recognition).
- look ahead is performed even in cases where no ambiguity arises.
- the number of tokens of look-ahead needs to be specified by the
programmer.
A more efficient implementation of look-ahead would complicate both
the code generation phase and the resulting Prolog code
considerably. We argue that a more fruitful approach would
be to solve the problem in the automaton construction part as
follows. Each rule R in the Elex script can be considered as
defining a transduction from the language defined by the regular
expression r to the name of that specific rule:
r x R. The
transduction specified by an Elex script can then be described as the
Kleene closure of the union of each of these transductions:
(r1 x R1| r2 x R2...)*. The resulting transducer can then be
subject to a determinization algorithm for transducers
[3],
[7]. In cases where the resulting transducer is not
determinizable a number of static criteria must be defined which forces
determinizability (such as a static counterpart of the longest match
preference). If this proposal can be implemented, then each of the
drawbacks listed above disappear. As a result, both the code generation
part and the resulting code can remain both simple, straightforward and
efficient. An implementation of this proposal is
foreseen for the next release of Elex.
Next: Comparison with plex
Up: a
Previous: Implementation
Noord G.J.M. van
1998-09-25