7 ms·

Regular expressions match regular languages (hence the name). If your language involves pairs of things (e.g HTML), it's not regular. Perl hacked support for th

• ExpiredLink 11y ago
  IOW, study the implementation to understand the interface.
  • kps 11y ago
    More like, know what the notation is a notation of to understand the notation.
• ginko 11y ago
  >Use a proper context-free grammar parser if you need to parse a context free grammar, you know? The thing is that regular expression are supported as language feature or as standard library in pretty much every language. If you want to build a proper parser, you'll have to jump through a lot more hoops. For instance for C++ I've tried tons of different lexer and parser generators and they all suck for various reasons. (Verbose syntax, uses global variables, C only, lexer not compatible with parser and vice versa,..) Most people seem to end up writing their own parsers from scratch. The only time I've ever seen parsing done right is with Parsec for Haskell.
  • hacker_9 11y ago
    It's a mistake to write your own parser because they can get so complex so quickly to even do basic stuff, and you'll lose sight of the original goal of the project. See Prolog - a whole programming language built around the idea of parsing language (albeit NLP)! I suggest you take alook at Antrl4 for a powerful but easy to use parser plus lexer combo.
    • ginko 11y ago
      I tried Antlr, even bought the book, and at least for C++ I found it pretty unworkable. Even with the book the documentation felt very incomplete. Maybe things work better on the Java side.
      • bro-stick 11y ago
        Antlr is shit; it will waste your time for anything real. Bison+flex (once you figure out the quirks, undocumented assumptions and flags) and treetop are usable. https://www.gnu.org/software/bison/manual/ https://www.gnu.org/software/bison/manual/ http://flex.sourceforge.net/manual/ http://flex.sourceforge.net/manual/ http://treetop.rubyforge.org http://treetop.rubyforge.org Disclaimer: A long time ago in a galaxy, far, far away, I wrote an optimizing Java-to-MIPS compiler (sans GC, so leaky heap) in C++ using Flex/Bison and again in Java using JavaCC.
    • bro-stick 11y ago
      Most apps link against PCRE.
  • dankohn1 11y ago
    Obligatory "You can't parse HTML with Regex" link: http://stackoverflow.com/a/1732454/1935918 http://stackoverflow.com/a/1732454/1935918
    • wodenokoto 11y ago
      I really hate that link. Not only is it uninformative, I disagree with it. If you know the shape of your html data, parsing it with regular expressions can be much easier than with a dedicated parser.
• eru 11y ago
  That's too optimistic. Here's a challenge for you: write a (grep) regular expression that checks a decimal number for divisibility by 7. That's totally a regular language, but I doubt you'll find a legible way to express it.
  • hacker_9 11y ago
    What does that have to do with the language syntax..
    • TeMPOraL 11y ago
      Regexes we use are an extended form of so-called "regular expressions", which describe regular languages and finite automata, and in that part of maths, a language that accepts binary numbers divisible by N is a very common toy problem.
  • 3dfan 11y ago
    If the number N can be converted to a string of length N, this regex checks if it's divisible by 7: ^(.......)+$
    • meric 11y ago
      That would work, use base 1 representation.
    • eru 11y ago
      That's not a solution. I asked for a something that checks decimal numbers. A real solution looks uglier: check out https://github.com/matthiasgoergens/Div7 https://github.com/matthiasgoergens/Div7, it starts ((((((6(2|9)8|6(2|9)1|5)(5(2|9)8|5(2|9)1|4)(5(2|9)7 [...] (Unless you can convert from decimal to unary in regex, too. I doubt you can, regular languages are too weak for that.)
  • agumonkey 11y ago
    Obligatory prime regex link: http://www.catonmat.net/blog/perl-regex-that-matches-prime-numbers/ http://www.catonmat.net/blog/perl-regex-that-matches-prime-n...
• joosters 11y ago
  I use regexes all the time for parsing data on a variety of 3rd-party websites. Just because they aren't perfect at matching every potential theoretical situation doesn't mean they shouldn't be used. In practice, regexes can be a simple and reliable way to grab data out of HTML. Don't dismiss them out of hand! Another point, generally overlooked by the theoretical purists, is that HTML in the wild is rarely correct, and your perfect HTML parser will barf when trying to process it. Regexes on the other hand don't have to care about exact syntax and can cope with horribly mangled data.
  • inglor 11y ago
    Good HTML Parsers typically use engines of browsers and will actually match websites very well. They'll let you use selectors and not regex and are a lot more accurate. It also won't break if the website adds a single attribute or a quirky value.
    • joosters 11y ago
      Nor will regexes...
  • lojack 11y ago
    But what's the comparative advantage over a faster, easier to comprehend, and more correct html parser?
    • mordechai9000 11y ago
      I think the word parsing is being used in some cases that are better described as web scraping. If you are just scraping a little data, a regex can be a quick and easy way to get what you need and get on with your life. If you actually care about the html structure, regexes are not sufficient. They are still useful for matching tokens though.
  • olavk 11y ago
    It is not a question of "theoretical purity", it is a fact that it is simply not possible in the real world to parse a html document using only a regex. But this is often misunderstood as saying they regex shouldn't be used in parsing. Regex'es are quite useful as a part of a parsing process, eg. to locate the tags and attributes and separate them from text. This is the scanning or tokenization step. But after this, you need to create a hierarchical data model corresponding the DOM, and you need to do that outside of a regex. A regex outputs only a string or flat list of strings (in all regex libraries I know of), it does not output a hierarchical data structure, so it follows that you need something more than a single regex to parse a hierarchical data structure like a programming language or a html document. Only exception would be if you need to extract very specific data items which are not hierarchical in nature. Eg. you want to extract only the specified character encoding or something like that. Your point about the "perfect HTML parser" is kind of missing the point, since regexes does not magically solve the problem of imperfect HTML either. A perfect HTML parser would be one which implement HTML spec fully, including the error recovery rules. These are quite complex, eg, if you reach a <p> then an open <h1> is implicitly closed, but an open <i> is not. Try implementing this logic in a single regex! ("Regexes does not care about perfect syntax" - what does that even mean? A regex match exactly what you tell it to match, just like a parser parses what you program it to parse.)
• cameldrv 11y ago
  Except nobody uses strict regexes anymore. In particular, without the minimal match (*?) operator, they're of limited utility in real-world situations. It's easy to tell people to use a context-free grammar parser, but the ones that I know of require a lot more setup than a one-liner regex. There's probably an opportunity for someone to really improve the practice of programming by coming up with a compact language to specify and match structures in CFGs, or some subset of them.
  • ulrikrasmussen 11y ago
    Minimal match is still OK, that will only affect disambiguation and won't allow you to write a pattern that does not denote a regular language.
  • paulmd 11y ago
    JSON-Schema and XML-Schema provide the "specify and match" functionality, in the sense of deciding whether or not a given instance of a document conforms to a defined standard. For simple regex-style queries there are XPath and JSONPath expressions. If you want to actually touch them as plain objects it's a very straightforward task of implementing a data provider to marshal the objects. In Java this is provided by libraries such as Jackson (JSON) and JAXB (XML). These basically work just like Hibernate. JSON and XML cover many of the real-world use cases of parsing such CFGs. If you make your data fit into one of those boxes it's very straightforward to validate or marshal them according to those schema protocols. They obviously do have a greater complexity than just writing a regex, but that's kind of the nature of using a more expressive language, and it's by no means an insurmountable increase.
• jameshart 11y ago
  Not sure I understand the relevance of this comment to the post in question. Unless your objection is that using capture groups in this way is an example of 'cramming in extended functionality'? On the other hand, this post has spawned the usual regex thread including a zalgo link and a pointer to a regex that finds prime numbers, so I guess you've done your part to perpetuate regex mythology.
• nmadden 11y ago
  I agree with the general gist of your post, but I should point out that all finite languages are regular. So while potentially infinite HTML documents cannot be parsed by regular expressions, they don't turn up very often.
  • colanderman 11y ago
    You're missing the distinction between a finite language, and an arbitrarily large finite production of an infinite language. No-one cares about "infinite HTML documents". I don't even think the Chomskyan hierarchy concerns itself with languages with "infinite" productions. All you have to worry about is infinite languages -- i.e., languages with arbitrarily large productions. There's a key difference between "infinite" and "arbitrarily large": the latter is quantifiable. While indeed to can build a regular expression to match any finite subset of HTML, it can only match HTML documents up to some fixed size. I can always give you a (finite!) document that is one tag deeper that your regex will choke on. "But recursive parsers have the same issue!" you say. "Their stack will run out of memory at some point!" Yes, but they have a key difference: the amount of stack (memory) they require is bounded by the size of the document. This is not true for a regular expression! In fact, not only would a regular expression to match a given subset of HTML require memory exponentially proportional† to the size of the document, the automata itself would be similarly massive! I really wish someone came up with and promulgated a concise handy built-in ubiquitious equivalent of regular expressions for, say, PEGs. The closest I've seen are DCGs in Prolog. Would make so many parsing problems more easy to do correctly! † It's possible I'm wrong about this since it's early morning and I'm basing this off my intuition rather than a proof. The part about the automata itself being exponential w/r/t the size of the document is definitely true though.
    • nmadden 11y ago
      You can't always give me a larger HTML document - eventually you will run out of usable universe. Yes, I should have said 'bounded by some finite maximum size' rather than just finite, but it's not a great leap to see that in reality all documents will be bounded by such a maximum. Finite state automata do indeed need an exponentially larger number of states compared to a pushdown automata, I made no claim as to efficiency. The point remains - for all practical purposes, you can consider all languages to be regular and using a stack is merely an optimisation.
• ised 11y ago
  "There is no such thing as an unmaintainable/illegible basic regex..." To someone who knows BRE. I am one of those people. It's ERE and PCRE I do not understand very well. Sharing solutions to common problems using BRE on HN always seems to trigger (unwarranted) criticism using either of the exact words you mention, or synonyms for them. "Unmaintainable" (by who?). "Illegible" (to who?). I "maintain" 100's of BRE scripts. They are perfecty legible to me. None of them are so complex I cannot re-write them in a short time. It is the structure of the input that is complex and which takes time to recall. I also use lex, a common utility found on almost all UNIX derived OS; this article seems to ignore that option. I like to think it's faster than Perl or Python, but I cannot say for sure.
  • kevin_thibedeau 11y ago
    > I like to think it's faster than Perl or Python, but I cannot say for sure. It is. I implemented an assembly language parser with pyparsing. It worked okay but the function call overhead with a combinator-based parser handling both the lexing and grammar was murder. I replaced it with regexes and got a 6x speedup. Not something I would do with a complex grammar though. Native code would obviously blow this away in speed but it is fast enough now.
    • bro-stick 11y ago
      PCRE JIT http://pcre.org/current/doc/html/pcre2jit.html http://pcre.org/current/doc/html/pcre2jit.html
• 0x400614 11y ago
  When quoting the article please put quotes around the text, or use the `>` character for each line you quote. Thank you.