leah blogs

Last week, I ported Monads in Perl to Ruby just for fun and learning. It’s amazing how one can port code without really understanding it, for programming languages the Chinese Room Argument certainly works.

When I converted all the code from the page, I reread some of my Haskell papers and got hooked by Yet Another Haskell Tutorial which has a good chapter on monads and their use. It also uses monads to build a parser combinator, which is an popular approach to parse in Haskell and other functional languages.

Rather quickly I had a direct port of something akin to Parsec. I needed a name and Martin DeMello proposed “rightyear”, the japanese pronunciation of lightyear, which is about a third parsec, of course. For testing, I wrote a parser to read something like a very primitive kind of XML. This is an easy example of a context-sensitive free grammar in Parsec:

xml = do{ name <- openTag
        ; content <- many xml
        ; endTag name
        ; return (Node name content) }
      <|> xmlText

And that’s the complete Rightyear parser:

class ParseXML < Parser
  def parse_xml
    parsing { xml.passthru eof }.run
  end
  def xml
    choice open_tag.bind { |name|
      many(xml).bind { |content|
        end_tag(name).bind { ret [name, content] }
      }
      }, text
  end
  def open_tag
    char(?<) >> one_or_more(char_matching { |c| c.chr =~ /\w/ }).bind { |t|
      char(?>).bindret t.join
    }
  end
  def end_tag(t)
    char(?<) >> char(?/) >> string(t) >> char(?>)
  end
  def text
    one_or_more(char_matching { |c| c.chr =~ /\w/ }).bind { |s| ret s.join }
  end
end

As you can see, Haskell’s do-notation doesn’t map very well to Ruby; it’s rather cumbersome to write. After a bit of twiddling, I found out that I didn’t actually need monads at all; instead I can use exceptions or throw/catch to trackback. Now, the parser looks like this:

class ParseXML < Rightyear::Parser
  def xml
    choice seq {
      name = open_tag
      content = many { xml }
      end_tag name
      [name, content]
    },
    seq { text }
  end
  def parse_xml
    v = xml; eof; v
  end
  def open_tag
    char(?<)
    t = text
    char(?>)
    t
  end
  def end_tag(t)
    char(?<); char(?/); string(t); char(?>)
  end
  def text
    one_or_more { char_matching { |c| c.chr =~ /\w/ }.chr }.join
  end
end

Which is a lot better for the eyes, no? It’s actually straight-forward to write parsers in this, but you need to ensure you don’t have left-recursion in your grammar, because that borks parser combinators in general. The big advantage over Bison and similar tools is that you easily can mix in your own code and can parse full LL(∞).

Unfortunately, the trackback via exceptions still is rather slow, it takes about 6 seconds to parse "1+#{'1+' * 6000}1" on my iBook. So consider this as an academical exercise for now; I learned a lot about monads and Haskell and how it sucks when you rewrite it in non-Haskell languages. :-)

People have been doing this in Tcl/Tk and Python, and even C too.

Further reading: Fast, Error Correcting Parser Combinators: A Short Tutorial (PDF) by S. Doaitse Swierstra and Pablo R. Azero Alcocer.

NP: Bob Dylan—Tonight I’ll Be Staying Here with You