I don't know Regex • Hacker News Board

Re: I don't know Regex

#51

Post by cheald » Wed, Sep 04, 2013, 2:18 AM UTC

joe_the_user wrote: post #50

cheald wrote: post #44

Earlier quoted context omitted.

Email addresses are specified by standard with a context-free grammar. While it may be possible to express certain CF grammars as regular grammars, you rapidly run into issues (such as optional bounding delimiter matching, or escaped delimiters) which are trivial to express with a stack, and frickin' hard to express without one. (This is, incidentally, the heart of the "don't try to parse XML with regexp" sentiment,…

At that rate, I can't see any good reason to use regexes for email ever. If you know context-free language, recursive-descent parsers are fairly simple to write and maintain without any special tools.

Well, if you want a spec-compliant email validator, then yeah, you probably want an actual parser. Most people are happy enough with a good-enough pattern match, though, which is substantially less code.

Re: I don't know Regex

#52

Post by waps » Wed, Sep 04, 2013, 4:59 AM UTC

microtonal wrote: post #48

waps wrote: post #45

Earlier quoted context omitted.

Just because it's a regex does not mean you can't document it. There are many regex tracers that can tell you exactly where a match fails. Plus regexes condense a lot of information in small spaces, which makes them easier (imho) to debug. Most other parsing syntaxes are one-offs, and very verbose. And your average parsing library is not going to be using boyer-moore state machine parsing like you can easily achieve…

Just because it's a regex does not mean you can't document it. You are certainly right. Especially, if you use a package for automata or transducers that allows you to apply common automaton operations (union, intersection, composition, etc.) to combine expressions. However, that's not how regular expressions are normally used or what the standard libraries for most languages support. So, people either write (1) simp…

I don't know Haskell so I haven't used parsec and attoparsec, beyond tutorials and running a few examples. I read the tutorials, then proceeded to make my own version in Java that works similarly (also typesafe). It's easy to make it work, but it always retains the same disadvantage : runtime evaluation.

Runtime evaluation means that your program figures out the structure of the grammar into it's internal "recursive" state machine every time (in some cases every time you evaluate a string). This means that your parser is effectively running on a very slow, very ad-hoc virtual machine inside your program. In the case of ANTLR (or yacc) the program itself has the required structure. Result, yacc parses happen at close to memory transfer rate (depends on the grammar and the semantic actions obviously), whereas parsec parses, well, you're lucky to get 10 MiB/s (similar grammar happened at > 1 GiB/s in java with ANTLR).

The difference is large enough that it quickly becomes very hard to ignore. Plus, I like the fact that the ANTLR syntax is more concise, which makes it easier to keep the whole parser in your head once you're used to the language. Furthermore there's the testing application that comes with ANTLR, ANTLR studio.

Re: I don't know Regex

#53

Post by Lindrian » Wed, Sep 04, 2013, 8:31 AM UTC

microtonal wrote: post #2

Which one is the simplest? I rest my case. Actually, I like neither. The code is easier to read, but the regex gives a broader overview. This is something where parser combinators can shine. E.g., from Haskell's email-validate: addrSpec = do localPart Source: http://hackage.haskell.org/packages/archive/email-validate/1... To end with a positive note: good work on the library! I think it will be useful for many people…

You could always comment the regex. My website provides a full and accurate explanation, step by step, of almost any given regex. Have a look here: http://regex101.com/r/dG4lP3

Re: I don't know Regex

#54

Post by enigmo » Wed, Sep 04, 2013, 3:19 PM UTC

waps wrote: post #52

microtonal wrote: post #48

Earlier quoted context omitted.

Just because it's a regex does not mean you can't document it. You are certainly right. Especially, if you use a package for automata or transducers that allows you to apply common automaton operations (union, intersection, composition, etc.) to combine expressions. However, that's not how regular expressions are normally used or what the standard libraries for most languages support. So, people either write (1) simp…

I don't know Haskell so I haven't used parsec and attoparsec, beyond tutorials and running a few examples. I read the tutorials, then proceeded to make my own version in Java that works similarly (also typesafe). It's easy to make it work, but it always retains the same disadvantage : runtime evaluation. Runtime evaluation means that your program figures out the structure of the grammar into it's internal "recursive"…

Attoparsec is a whole lot faster than Parsec. Orders of magnitude faster for many parsers.

There is a common problem with most of these parser combinator libraries in that they do no state machine optimization whatsoever... with the (sole?) exception of uu-parsinglib.

Applicative parsers, avoiding monadic extensions, readily support optimization and error checking much like flex/bison, Ragel and ANTLR. The cost of running these optimizations once per program execution (not parser evaluation) is fairly minimal and may not be noticeably slower than a precompiled parser.. particularly if the cost is amortized over many parses.

I do wish more of the parser combinator libraries actually did this though. And there are lexx/yacc-like tools for Haskell as well: Alex and Happy (famously used by GHC to parse Haskell source), and Ragel can be bolted in when performance is absolutely critical.

Re: I don't know Regex

#55

Post by islon » Wed, Sep 04, 2013, 3:27 PM UTC

Which one is the simplest? I rest my case.

Of course the regex is simpler as everyone who knows regexes will understand it.

If you don't know regex you should invest time on learning it. It's the same if you say:

    I don't know german, look at this german sentence builder, it's so much nicer!
    > builder.firstPersonPronom().verb("like").directObject(new SecondPersonPronom());
    > => "Ich mag dich"