3 ms·
This looks like a reasonable implementation of a Type-3 star-free grammar. I think it's a shame the author eschewed the idea of making it bijective with e.g. Py
by hythloday 14y ago
This looks like a reasonable implementation of a Type-3 star-free grammar. I think it's a shame the author eschewed the idea of making it bijective with e.g. Python's string.format or Java's MessageFormat.format - is there a formatting library in Javascript that outputs strings from a "{var_name}" and "`var_name`" template style?
The linkbait title ("Too lazy to write Regular Expressions?") definitely rubs me the wrong way. The syntax for Perl-compatible regular expressions is horrendous - it's difficult to identify the isomorphism with the underlying ndfa, which in my view is the most intuitive representation, it's practically uncomposable, and it's far more dense with non-alphanumeric characters than any programming language other than something like J.
I guess what I was hoping for when I clicked this is what you might call a "lexer combinator" - something like (Python syntax):
>>> combinator = Literal('/') + Group("year", OneOrMore(Digit())) +
... Literal('/') + Group("month", OneOrMore(Digit())) +
... Literal('/') + Group("day", OneOrMore(Digit())) +
... Group("title", OneOrMore(Letter())) + Literal('.html')
...
>>> lex(combinator, '/2012/08/12/test.html')
{'title': 'test', 'month': '08', 'day': '12', 'year': '2012'}
>>> qs_combinator = combinator + Literal('?') +
... Group("qs", ZeroOrMore(
... Group("key", OneOrMore(Letter())) + Literal('=') + Group("value", OneOrMore(Letter()))))
...
>>> lex(qs_combinator, '/2012/08/12/test.html?show=full')
{'title': 'test', 'qs': [{'value': 'full', 'key': 'show'}], 'month': '08', 'day': '12', 'year': '2012'}
Obviously there are opportunities to make that less verbose, though I don't know if you can ever make it as close to PCRE syntax as parser combinators get to EBNF--perhaps maybe you could do something like 'a'*1 to represent 'a'+ in PCRE. Does such a library exist?
- Erwin 14y agoThis may be of some interest to you: http://lfw.org/python/rxb.py http://lfw.org/python/rxb.py -- it hasn't caught on since 1996 though. I've seen some swear to OMeta which is the parser used in the VPRI "simple OS" product, powerful enough to implement a bare-bones TCP/IP implementation as essentially drawings; http://www.moserware.com/2008/04/towards-moores-law-software-part-3-of-3.html http://www.moserware.com/2008/04/towards-moores-law-software...
- hythloday 14y agoThat second link is beautiful. Thanks!
- maxerickson 14y agoI haven't used it, but I believe Pyparsing does much or what you are describing. The declarative naming is more like 'OneOrMore(Digit)("year")'.
- lihaoyi 14y agoScala's Parser-Combinators are about as good as you are going to get http://www.scala-blogs.org/2009/04/combinators-for-pretty-printers-part-1.html http://www.scala-blogs.org/2009/04/combinators-for-pretty-pr.... Consider the grammar for simple math expressions: expr ::= sum sum ::= product { ("+" | "-") product } product ::= power { ("*" | "/") power } power ::= factor [ "^" factor ] factor ::= "(" expr ")" | variable | constant variable ::= identifier constant ::= floatLiteral It's pure-Scala is def expr = sum def sum = product ~ rep(("+" | "-") ~ product) def product = power ~ rep(("*" | "/") ~ power) def power = factor ~ opt("^" ~ factor) def factor = "(" ~ expr ~ ")" | variable | constant def variable = ident def constant = floatLit And since it's pure-Scala, you get all the benefit of static typing (error detection, auto-complete, etc) when writing your parser. There's also no extra compile step: your parser compiles with the rest of your program and is just a java Object with a parseAll() method. Lastly, it's a superset of PEG, which means that its behavior and limitations are all pretty well-studied academically and well-defined (which is more than can be said of most hacked-together regex solutions!). Pyparsing is pretty cool as well, for python, but it's somewhat more verbose since python isn't as DSL-friendly as scala: http://pyparsing.wikispaces.com/HowToUsePyparsing http://pyparsing.wikispaces.com/HowToUsePyparsing EDIT: a (different) example from Pyparsing: integer = Word( nums ) variable = Word( alphas, max=1 ) arithOp = Word( "+-*/", max=1 ) equation = variable + "=" + integer + arithOp + integer As far as I can tell, Pyparsing is also a superset of PEG.