Hacker News Reader

Comment by alnayyir | Hacker News Reader

Regex is the only real sensible way to validate strings until something better is found. Even if you just wrote code to do it manually, you'd really just be writing a verbose and poorly implemented finite state machine that globbed symbols together, which in the end, would just be inferior to writing a well tested Regex string.

Regex can be easier to read if you have something do a graphical expansion for you. Otherwise, it's write-once, read-never.

View on HN

> Regex is the only real sensible way to validate strings until something better is found.

There are plenty of ‘better’ (in the sense of ‘more powerful’) string-validation techniques. For example, lots of grammars are expressed in BNF; the languages that can be so expressed are (if I remember my Chomsky hierarchy correctly) the context-free grammars, a strictly larger class than the regular languages. The extra power comes from the fact that they have the expressive power of a finite-state automaton augmented by an (infinite) stack. (It's fair to argue that it's not ‘really’ infinite, since a computer's memory is finite; but, in that sense, real-life computers will never be Turing complete.)

(Of course, common ‘regular-expression’ libraries aren't actually regular any more, because of added features like capture groups. I don't know if they recognise all CFG's, though; I suspect not.)

Given this, why would we use regular expressions? Well, by intentionally sacrificing power, we can achieve faster matching (http://swtch.com/~rsc/regexp/regexp1.html) and, probably, lower memory usage. Sometimes this trade-off is worth it, even if it means that the match must be somewhat fuzzy; but sometimes one needs a precise match, and regexes just aren't up to the job.

> Given this, why would we use regular expressions? If I can get a way with a simple regexp I will use it. If it starts getting complicated I would use something else.(e.g. top down parser or a combination)

> If I can get a way with a simple regexp I will use it. If it starts getting complicated I would use something else.(e.g. top down parser or a combination)

Isn't that what I said?

(If understood correctly) You based it in speed and memory efficiency. I rather base it on having something simple and readable.

That's just silly. Depending on what's in the string, writing a parser might be much better than a regex. Lots of parser libraries already out there, too.

I can agree with this sentiment, there's also nothing wrong with writing a parser that breaks the input up into pieces and validates those individual parts using specialized regular expressions.

Especially when the spec itself is in EBNF.

True, though it's EBNF with a bunch of explanatory text and annotations.

What would be interesting, but I can't find with some googling: Has someone implemented a parser-generator based on the spec? The ideal would be that the parser specification looks a lot like the RFC, since then you'd have more confidence it was actually correct (and it'd be easier to maintain for future changes).

My comment above is a regex derived straightforwardly from the spec. Not a full parser, though.

There was a long post on the topic of 'regex-vs-parser' for email on reddit a while back. I hope I'm pointing to the correct person, but he wrote a parser in Haskell that validates against RFC5322: http://hackage.haskell.org/package/email-validate

By all means, use a CFG or a PEG for parsing emails.

While you do that, I'll do something that doesn't involve tweezers and code.

Roberto Ierusalimschy of Lua fame often uses this example of how PEGs (parsing expression grammars) can be much easier than regexps for some tasks.

http://lua-users.org/lists/lua-l/2009-10/msg00817.html

If I remember correctly my theory of languages course a parser (implemented in a turing machine) is more powerful than a reggex (which is a finite state machine).

Reply on news.ycombinator.com