Parsing Techniques

The techniques listed here are things you might want to try. They're definitely not things you must do, only things that have helped in the past.

Everything goes on a stack

Almost everything in a programming language can nest. In your parser, namespaces, blocks, declarations, expressions, references, and any number of things I can't think of will want to nest. The answer to nesting, of course, is a stack. Some stacks are obvious: lexical scope, and blocks. But what about declarations?

   class Foo {
      int bar(int x, int y) {
         extern class Other { 
            attribute int x;
            attribute int y;
            void setX(int x) :method;
            void setY(int y) :method;
            pmc get_instance();
         }

         pmc other = Other::get_instance();
         other.setX(x);
         other.setY(y);
      }
   }

That code contains a class decl (Foo), which has a symbol decl (bar), which has a parameter-list-decl, which contains two param-decls. The bar symbol eventually gets recoded as a function definition, containing an extern class(!) decl containing 2 attribute decls and 3 more function decls.

When your parser is telling you that you need another stack, be willing to listen. Not everything can, or should, go on the same stack.

Encapsulate or defer actions

Remember when building PAST trees that the parser is "experimenting" with your rule. Maybe this is an expression, but maybe it's an anonymous declaration.

As a result, you may build a very complex parse tree only to have the parser decide it's wrong, and discard it. Consider having some "sequence points" in your grammar where you can be sure that the parser has correctly identified whatever it is you are building.

Consider a variable declaration. If you store the variable declaration in a lexical block, and the parser decides that those curly braces don't really indicate a block, there's no harm. The connection from declaration to block was encapsulated in the block itself, so discarding the block's PAST tree discards the variable declaration.

But if you interpret a variable declaration as some kind of global, and jam a symbol into a namespace, then what will you do if the parse fails? The parser might find a valid alternative, but you've already injected a bogus symbol into the symtable someplace.

For a dynamic language, the best way to deal with this might be to ignore it -- let autovivification solve the problem. Or, you may want to create a "transaction" block representing changes to the namespace, and merge that block when the parser returns to some higher level (the sequence points mentioned before: a completed function decl, for example).

Use 'state' variables to avoid special cases

For handling non-local conditions, like "first time this occurs" or "first one in file", use a state variable instead of trying to build a complex pattern. This can be used to start parsing with a "default" configuration that skips certain productions.

   rule TOP {
      {{ $P0 = box 1
          set_global '$Top_of_file', $P0
      }}

      <section>*
      {*}
   }

   rule section {
      [ <section_header>

      || # Note: Section Header is OPTIONAL at top of file
         <?{{ $P0 = get_global '$Top_of_file'
            .return($P0)
         }}>
      ]
      # Not at TOF anymore.
      {{ $P0 = box 0
         set_global '$Top_of_file', $P0
      }}

      # ... rest of rule
   }

Use 'mode' variables to unify rules

One problem with creating several rules that are slightly different is the need to maintain the slightly-different action methods underlying them. It may be a better idea to unify the various rules with some variables storing 'mode' information about the parse.

Consider the case of declaring a variable. In many instances, a storage class (such as 'static') may be specified on the variable declaration. But when declaring a function parameter list, that makes no sense. One alternative is to have separate rules:

   rule variable_decl {
      <storage_class> 
      <type> 
      <init_declarator>
   }

   rule parameter_decl {
      <type> 
      <init_declarator>
   }

Or, if your language is self-similar, you may use a mode:

   rule decl {
      [ <!DECL_MODE_PARAM> <storage_class>? ]?
      <type>
      <init_declarator>
   }

The first line, above, looks like [ A B ]? where B happens to be an optional rule. That structure essentially means that if A is present, B is required also. It's a useful pattern for guard conditions.

The mode rule is a special token that just executes some inline PIR code:

token DECL_MODE_PARAM {
   <?{{
      $P0 = get_global '@Decl_mode_stack'
      $S0 = $P0[0]
      if 'parameter' == $S0 goto yes
      .return (0)
   yes:
      .return (1)
   }}>
}

Report errors via special subrules

In cases where a partial match of a rule has occurred, add error checking alternatives.

  rule compound_stmt {
    '{'
      [ <declaration> | <statement> ]*
    [ '}' || <error: "Missing '}' in compound statement"> ]
    {*}
  }

Note that the parser may try several alternatives, so don't try to insert error messages too early in the rule. In the example above, the '{' is the key indicator of a compound statement. It makes no sense to try to report a "Compound statement missing '{'" error, since the failure of the rule may tell the parser to try some other, valid subrule. But once the block is opened, it will obviously have to be closed.

Note also that there is no error() method by default. You can start out using panic(), but you'll want to attach a less dramatic mechanism to your parser eventually.

Performance

Use whitespace caching

Build an "offset cache" into your ws rule using the code below, so that it will remember the last whitespace it recognized. This can help when several alternations are trying to match some text in the same place.

token ws {
  | <?{{  $P0 = get_global '$!ws'
          if null $P0 goto noshort
          $P1 = $P0.'to'()
          $P2 = match.'to'()
          if $P1 != $P2 goto noshort
          .return (1)
        noshort:
          set_global '$!ws', match
          .return (0)
  }}>
  | <!ww> <ws_all>+
  | <ws_all>*
}

"Hoist" prefixes

If several rules can be uniquely distinguished by a simple prefix, hoist the prefix into a parent rule.

rule built_in_function {
   [ <?before <t_builtin_name> 
   || <.fail>
   ]

   [ <builtin_sine>    {*} #= sine
   | <builtin_cosine>  {*} #= cosine
   | <builtin_tangent> {*} #= tangent
   ...
   ]
}

token t_builtin_name {
   [ 'sin' | 'cos' | 'tan' | ... ] # Any of the builtins
   >> # At end-of-word
}

The more completely you hoist, the more code you eliminate. Ideally you'll save the keyword for later use, maybe restructuring the rule to build the function call in pieces. (Put it on a stack!)

Debugging

Place the following in a rule to dump the current match object

{{ _dumper(match) }}

Place the following in a rule to dump the call stack of rule that got you to this point

{{ backtrace }}

use the <panic> rule to die and dump a backtrace of your current location in the parse rules

<panic>