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: (r₁ x R₁| r₂ x R₂...)*. 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.