Parsing with tools.rd: idc.pad

[downs]

Justin Johansson wrote:
> > downs Wrote:
> >
>> >> Justin Johansson wrote:
>>> >>> Can D people please recommend suitable tools for generating a parser (in D) for an LL(1) grammar.  There's bound to be much better parser generator tools available nowadays, since my last foray into this area 10+ years ago with YACC.  I've heard of tools like bison, SableCC etc but apart from the names know nothing about them.
>>> >>>
>>> >>> (Note.  This question is not about writing a parser for D.  It is about writing a parser in D for another language which has an LL(1) grammar).
>>> >>>
>>> >>> Thanks in advance for all help.
>>> >>>
>>> >>> -- Justin Johansson
>>> >>>
>> >> In a completely different vein, tools.rd is a simplicistic recursive descent parser framework implemented at compiletime that I've used for most/all of my toy languages. It keeps things trivial - there's no lexing stage, it parses straight from input string. It's not that well documented, but if you want, give me a simple language description and I can write you a sample parser. It's probably the easiest to use though - just mix it in from D code  :)
> >
> > Hi downs,
> >
> > Thanks for the offer but since YACC is my prior background I'll probably go to the closest tool which is the modern variant for LL(1).  Still if you have a small sample to share I'm sure other D people will be delighted.
> >
> > <JJ/>
> >

Well for instance, take the PAD (Pastebin Adventure) component of my IRC bot, that can run simple text adventures from a variety of sources, like local Gobby sessions, Wikis and (originally) Pastebin.com:

http://dsource.org/projects/scrapple/browser/trunk/idc/pad

Let's look at http://dsource.org/projects/scrapple/browser/trunk/idc/pad/engine.d

L175: gotToken

Functions like this form the building blocks of tools.rd parsing. They always have the form "bool gotBlarghle(ref string st, out T result)" and return true if result could be parsed from st, otherwise false (in which case st is not modified).

gotToken trivially removes a token from the input text.

L200: bool accept(ref string st, string cmp): This function is called internally by the parser framework to decide if st starts with a comparison string, in which case it is removed and true returned. bool accept removes tokens from both strings and compares until a comparison fails (false, st not modified) or cmp is used up (true).

L230: The first use of the actual Parser DSL.

    return mixin(gotMatchExpr("s: log"));

This simply matches "log" against the input string s. Nothing fancy.

L282: Not related to the parser but still, IMHO, insanely cool.
    const string Table = `
              | bool          | int         | string               | float
      --------+---------------+-------------+----------------------+--------
      Boolean | b             | b           | b?q{true}p:q{false}p | ø
      Integer | i != 0        | i           | Format(i)            | i
      String  | s == q{true}p | atoi(s)     | s                    | atof(s)
      Float   | ø             | cast(int) f | Format(f)            | f`;

This table contains a conversion matrix for internal types to basic type. Two things are of interest:

1) q{}p is unrolled by .litstring_expand() into nested and escaped ""s. It's a backport of D2 nestable string literals to D1.

2) The table itself. tools.ctfe contains functionality to select rows, columns, and iterate the table in column-major order. This means the above table can be automatically translated into nested if/switch statements.

L487: A more instructive use of the parser framework.

  if (mixin(gotMatchExpr("st: [==$#eq=true$|!=$#neq=true$|<=$#eq=smaller=true$|>=$#eq=greater=true$|<$#smaller=true$|>$#greater=true$] "
    "$dg2 <- genExprMath$"
  ))) { ... }

Okay, first we have a conditional branch: [a|b|c|d]. This matches each of the possible branches against the input string in turn. Segments in $$ indicate variable matches and/or programmatic reactions. $#eq=smaller=true$ basically translates to "execute eq=smaller=true when this part of the parse string is successfully reached. ".

"$dg2 <- genExprMath$" means "Generate dg2 using the genExprMath function" It is assumed that this function follows the convention of bool(ref string, out typeof(dg2)).

It hasn't been used in that sample, but "y <- foo/x" means "pass x as an extra parameter to foo". And that's basically it.  :)

Oh, just for fun, here's the unrolled D syntax for the above expression:

(ref string s) {
  auto scratch = s;
  return (
    true && (ref string s) {
      auto scratch = s;
      return                (true && scratch.accept("==") && (((eq=true), true))) && ((s=scratch), true)
          || (((scratch=s), true) && scratch.accept("!=") && (((neq=true), true))) && ((s=scratch), true)
          || (((scratch=s), true) && scratch.accept("<=") && (((eq=smaller=true), true))) && ((s=scratch), true)
          || (((scratch=s), true) && scratch.accept(">=") && (((eq=greater=true), true))) && ((s=scratch), true)
          || (((scratch=s), true) && scratch.accept("<") && (((smaller=true), true))) && ((s=scratch), true)
          || (((scratch=s), true) && scratch.accept(">") && (((greater=true), true))) && ((s = scratch), true);
    }(scratch) && ( genExprMath(scratch, dg2 ))
  ) && ((s = scratch), true);
}(st)