4 ms·

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

by waps 13y ago

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 with regexes. It's complex, terse, fast, and the code that will be running your match is probably better debugged than any code you could hope to produce (it's most programmers' understanding of regexes that could use some debugging). Regexes also just make sense if you know the theory behind the state machines. So how about this way of writing the regex : regex = r"""(?x) # Extended syntax (ignores \n and whitespace, allows comments) # Regex to match email addresses \b # Word boundary (?P<username>\w+) # Username part @ (?P<domain>[\w.]+) # Domain \b # Word boundary """ # Example use import re m = re.match(regex, "john@snow") print m.group('username') # john print m.group('domain') # snow I find parser combinators very hard to use. I wrote parser combinator libraries in C and one in java thinking it'd be easier to use than a parser generator like ANTLR, and I've since rethought the process. ANTLR studio is just so useful for writing a parser to example data. There's also the concern that parsers are strictly more expressive than regexes. If you need that, then regexes are simply out. However, most parser generators allow you to easily combine regex(-like) tokenization with parsing.

danieldk 13y ago
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) simplified expressions (like yours above) that do not implement the relevant standard; (2) write unreadable expressions; (3) 'compose' expressions through string interpolation, which can become unreadable quite quickly (I've seen enough in production code). I wrote parser combinator libraries in C and one in java thinking it'd be easier to use than a parser generator like ANTLR, However yacc (which I assume you used for C) and ANTLR are hardly the state-of-the-art of parser combinators. Try parsec or attoparsec sometime. There's also the concern that parsers are strictly more expressive than regexes. Not only that, (sub-)parsers are fully typed, making it much easier and safer to combine parsers. E.g., here I know exactly what this parser will give me (namely a Bar): foo :: Parser Bar
- waps 13y ago
  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.
  - enigmo 13y ago
    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.

by waps 13y ago

danieldk 13y ago

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) simplified expressions (like yours above) that do not implement the relevant standard; (2) write unreadable expressions; (3) 'compose' expressions through string interpolation, which can become unreadable quite quickly (I've seen enough in production code). I wrote parser combinator libraries in C and one in java thinking it'd be easier to use than a parser generator like ANTLR, However yacc (which I assume you used for C) and ANTLR are hardly the state-of-the-art of parser combinators. Try parsec or attoparsec sometime. There's also the concern that parsers are strictly more expressive than regexes. Not only that, (sub-)parsers are fully typed, making it much easier and safer to combine parsers. E.g., here I know exactly what this parser will give me (namely a Bar): foo :: Parser Bar

waps 13y ago
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.
- enigmo 13y ago
  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.