2
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Jan 26, 2013 at 4:55
  • $\begingroup$ Thanks. Are there any empirical results on this topic? (Maybe some links) $\endgroup$
    – skvadrik
    Jan 26, 2013 at 7:43
  • $\begingroup$ 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)? $\endgroup$
    – Raphael ♦
    Jan 26, 2013 at 18:04
  • $\begingroup$ 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). $\endgroup$
    – skvadrik
    Jan 27, 2013 at 13:20

1 Answer 1

Reset to default
1
$\begingroup$

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).

Adding to the speed gained when building up different regular expressions during different program runs modern regular expressions, mostly PCRE, are NP-Complete, thus very powerful (see for instance [2]). Additionally, with most languages supporting regular expressions there also is an interactive environment to check if the regular expression really expresses your intention, which is more efficient from a programmer's perspective than to write the grammar, generate the parser and do a test and then reiterate the process. I believe this to be the main reason for using regular expressions over LALR(1) grammars.

If you are interested in the implementation and runtime aspects of grammars [3] might also be of interest to you.

[1] http://swtch.com/~rsc/regexp/

[2] http://nikic.github.com/2012/06/15/The-true-power-of-regular-expressions.html

[3] Gerhard Goos, William Waite, Compiler Construction, Springer, Jan 1984 ( symbolaris.com/course/Compilers/waitegoos.pdf)

Improve this answer
$\endgroup$
11
  • $\begingroup$ Actually, many regexp matching algorithms used in practice run into huge trouble if the regexp is ambiguous, so I don't think a general statement can be made here. $\endgroup$
    – Raphael ♦
    Jan 26, 2013 at 18:06
  • $\begingroup$ The time to build the automaton is inmaterial if you are going to the trouble. The DFA uses less resources (no memory for stack) and is faster (less operarions per symbol). $\endgroup$
    – vonbrand
    Jan 27, 2013 at 0:16
  • $\begingroup$ Concerning the first comment, this is what [1] is all about and is only true for the NP-complete ones (the ones with backtracking). $\endgroup$
    – cberg
    Jan 27, 2013 at 10:54
  • $\begingroup$ cberg, thank you for useful links! In my case, I've developed two parser generators: one that creates parsers for regular languages and one that creates parsers for LALR(1) languages. Speed of the generated parser is the main point for me. So I don't have the trouble of building parser anyway. I'm gonna held some experiments myself but before that I wanted know what people have already done. $\endgroup$
    – skvadrik
    Jan 27, 2013 at 13:32
  • $\begingroup$ Again, saying "parsing regular expressions" I mean only DFA and not all the extensions used in many regexp libs. $\endgroup$
    – skvadrik
    Jan 27, 2013 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.