Parsing Techniques

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 identifier 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 injected a bogus symbol into the symtable someplace.

For a dynamic language, the best way to deal with this may be to ignore it -- let autovivification solve the problem. Alternatively, 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
    }}

    # ... rest of rule
  }

  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 mode 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.

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
}

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>