5 ms·
Slight terminological quibble: Regular expressions are strings formatted using a special pattern notation that allow you to describe and parse text. "Parse" i
by philwelch 16y ago
Slight terminological quibble:
Regular expressions are strings formatted using a special pattern notation that allow you to describe and parse text.
"Parse" is a questionable word choice. A proper Regular Expression can only describe patterns found in "regular languages", though modern backtracking regex engines have a bit more power. Parsing implies a parser, which means matching a grammar somewhat more sophisticated than a regex engine can handle.
- brianwillis 16y agoAgreed. I cringed when I read that line. Parsers can do things that regular expressions can't (paren matching, for example). Yet I've seen people try using regular expressions when a parser would be a better choice. There seems to be this emerging pattern in my career where I stumble across all the people in the world who have decided to try and validate HTML using regular expressions.
- gjm11 16y ago> try and validate HTML using regular expressions http://stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/1732454#1732454 http://stackoverflow.com/questions/1732348/regex-match-open-...
- brianwillis 16y agoOK. I take it back. Any problems that I have ever had in my life have now been put into perspective. That poor bastard.
- michaelfairley 16y agoRegular expressions in modern programming languages and the regular expressions you learned about in your automata theory class are not the same thing. The back references present in the regular expressions discussed in the article make the entire system capable of handling even NP-complete problems. So yes, regular expressions (in the more common use of the term) can "parse".
- philwelch 16y agoI did allude to that, but regular expressions are still not quite up to the tasks you would use a parser for.
- Goosey 16y agoI can only hope this challenge inspires a spiteful hacker to create a full grammar parser in a regular expression. It won't be me, but I love how these types of comments can sometimes spawn the most interesting toy projects. :)
- riffraff 16y agoYou may enjoy this http://www.a-k-r.org/abnf/ http://www.a-k-r.org/abnf/
- mfukar 16y agoThe back references present in the regular expressions discussed in the article make the entire system capable of handling even NP-complete problems. Really? So, we can parse HTML with regular expressions nowadays? I think a more appropriate word choice would be "recognize" instead of "parse", with regard to the OP of the thread.
- riffraff 16y agoI don't think there is anything in "parse" that implies relation to a specific type-N grammar, why do you think so? (the oxford american heritage dictionary seem to agree, but I'm not a native speaker)
- barrkel 16y agoI don't agree, technically. A parser is a program which analyses text and determines its grammatical structure according to a formal grammar, and tests its membership in the language described by the grammar. Regular languages can be described by regular grammars, and regular expressions are a notation for regular grammars. So you can indeed parse text with reference to a regular expression. Most people would call a parser which only used strictly regular expressions a lexical analyser, lexer or tokenizer, but this is only a convention to simplify language definition and parser implementation when using simple techniques like LALR or LL. But other uses may not need that level of sophistication. For example, a packet analyser in a router might use a dynamically updated state machine (a DFA), built from multiple regular expressions, for efficient dispatching of packets based on rules. I don't think it would be wrong to describe that component of the router as a packet parser. For example, this (to me) blindingly obvious patent seems to be using a modified DFA to make routing decisions, and calls it a parser: http://www.freepatentsonline.com/7623468.html http://www.freepatentsonline.com/7623468.html
- philwelch 16y agoTechnically, you're probably right. There's no hard-and-fast definition of "to parse" that requires the grammar to be particularly sophisticated. It is still not the best word choice because "parse" has a particular connotation, though.