[antlr-interest] RFC re/ Left factoring and Syntactic Predicate

[Ric Klaren]

On 7/7/05, Martin Probst <mail at martin-probst.com> wrote:
> > Syntactic predicates are performance killers. Only use them during
> > prototyping and when you really cannot do something else. Or if you have
> > other reasons like readability etc.
> 
> The question is: are predicates worse than a higher k? There are quite
> often situations where you only need a higher k in one or two places of
> your grammar - increasing k overall would probably lead to a decreasing
> performance overall?

ANTLR usually only uses the minimal required k for a local decisions.
High k is only really bad for the time antlr itself needs to process
the grammar. In general you can increase k in your grammar and not see
one thing change in the generated output (there might be a few
degenerative cases not sure).

Note that a syntactic predicate parses your input at least twice to
come to a decision, once to see if it's the right thing and then the
actual parsing of the chosen alternative. Or worse inside the run of
one syn pred another may be triggered and so on.

The performance hit of a predicate depends on
- how often is the predicate needed?
- how deep does the predicate recurse before coming to a conclusion?
The nearer the leaves of your grammar the smaller the hit.
- did you specify a complete rule as predicate or only a prefix of the
rule that is sufficient to make the decision. During prototyping it's
easy to just dump in (rule) => rule but for production you might want
to reduce to (prefix_of_rule) => rule. Note that antlr does not check
if prefix_of_rule is really a prefix of the rule. Thus introducing
'funny' behaviour.
- The input to the parser. By smart ordering of syn preds you may tune
your parser to the most common input.

Cheers,

Ric