# 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?

-
 It's usually the case that algorithms handling a vastly more complicated situation are slower. You definitely shouldn't expect a formal proof of anything, though, since (1) it really depends on the model of computation and (2) lower bounds are impossible. Instead, people conduct experiments and let their empirical results be known. – Yuval Filmus Jan 26 at 4:55 Thanks. Are there any empirical results on this topic? (Maybe some links) – skvadrik Jan 26 at 7:43 Note that parsing regular languages (via DFA, I assume) and using regexps (the practical ones) is not the same thing. Which do you want to consider? Also, are we allowed to preprocess something (e.g. create a DFA)? – Raphael♦ Jan 26 at 18:04 I'm trying to compare parsing regular languages using DFA and parsing regular languages using LR/SLR/LALR: if the second way can be more efficient (faster), then why should we use DFA at all. (I don't quite understand where are you going to use preprocessing). – skvadrik Jan 27 at 13:20

I believe the reason for favoring regular expressions over LALR(1) grammars for accepting simple grammars stems from the time needed to build an LALR(1) automaton. Let $m$ denote the size of the grammar which is used to build the automata for accepting the language defined by said grammar. If you need to build up the accepting automaton during runtime you will probably want to use regular expressions because building up an LALR(1) automaton will take $O(m\cdot 2^m)$ which does not include the necessary testing if the input grammar even is LALR(1) ($O(m^3)$). Regular expressions instead can be build up quite easily, the check can occur during conversion (see [1] , re2post).