Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
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 '13 at 4:55
    
Thanks. Are there any empirical results on this topic? (Maybe some links) –  skvadrik Jan 26 '13 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 '13 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 '13 at 13:20

1 Answer 1

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)

share|improve this answer
    
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. –  Raphael Jan 26 '13 at 18:06
    
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). –  vonbrand Jan 27 '13 at 0:16
    
Concerning the first comment, this is what [1] is all about and is only true for the NP-complete ones (the ones with backtracking). –  cberg Jan 27 '13 at 10:54
    
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. –  skvadrik Jan 27 '13 at 13:32
    
Again, saying "parsing regular expressions" I mean only DFA and not all the extensions used in many regexp libs. –  skvadrik Jan 27 '13 at 13:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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