Search code examples
regexparsinglalr

Regular vs LALR(1): what is faster

Supposing we have two grammars which define the same languge: regular one and LALR(1) one.

Both regular and LALR(1) algorithms are O(n) where n is input length.

Regexps are usually preferred for parsing regular languages. Why? Is there a formal proof (or maybe that's obvious) that they are faster?

Solution

  • You should prefer stackless automaton over pushdown one as there is much more developed maths for regular language automatons.

    We are able to perform determinization for both types of automaton, but we are unable to perform efficient minimization of PDA. The well known fact is that for every PDA there exists equivalent one with the only state. This means that we should minimize it with respect to transitions count/max stack depth/some other criteria.

    Also the problem of checking whether two different PDAs are equivalent with respect to the language they recognize is undecidable.