nmfu

the "no memory for you" "parser" generator

nmfu attempts to turn a parser specified as a procedural matching thing into a state machine. It's much more obvious what it does if you read some of the examples.

It takes in a "program" containing various match expressions, control structures and actions and converts it into a DFA with actions on the transitions. This allows simple protocols (for example HTTP) to be parsed using an extremely small memory footprint and without requiring a separate task since it can be done character by character.

You can also define various output variables which can be manipulated inside the parser program, which can then be examined after parsing. See example/http.nmfu for a good example of using this functionality.

The rest of this README is a guide to using NMFU.

Parser Specification

NMFU source files support C-style line comments (text after // on a line is ignored until the end of the line)

Top-Level Constructs

At the top-level, all NMFU parsers consist of a set of output-variables, macro-definitions and the parser code itself.

The output-variables are specified with the output-declaration:

out_decl: "out" out_type IDENTIFIER ";"
        | "out" out_type IDENTIFIER "=" atom ";"

out_type: "bool" -> bool_type
        | "int" -> int_type
        | "enum" "{" IDENTIFIER ("," IDENTIFIER)+ "}" -> enum_type
        | "str" "[" NUMBER "]" -> str_type

For example:

out int content_length = 32;
out bool supports_gzip = false;

// note you can't set default values for strings and enums

out str[32] url;
out enum{GET,POST} method;

All strings have a defined maximum size, which includes the null-terminator.

Macros in NMFU are simple parse-tree level replacements. They do not support arguments, and look like:

macro_decl: "macro" IDENTIFIER "{" statement* "}"

For example:

macro ows() { // optional white space
   optional {
      " ";
   }
}

When macros are "called", or instantiated, all NMFU does is copy the contents of the parse tree from the macro declaration to the call-site. Note that although macros can call other macros, they cannot recurse or refer to macros defined after them in the source file.

Parser Declaration

The parser proper is declared with the parser-declaration,

parser_decl: "parser" "{" statement+ "}"

and contains a set of statements which are "executed" in order to parse the input.

Basic Statements

Basic statements are statements which do not have an associated code block, and which end with a semicolon.

simple_stmt: expr -> match_stmt
           | IDENTIFIER "=" expr -> assign_stmt
           | IDENTIFIER "+=" expr -> append_stmt
           | IDENTIFIER "(" (expr ("," expr)*)? ")" -> call_stmt
           | "break" IDENTIFIER? -> break_stmt
           | "finish" -> finish_stmt
           | "wait" expr -> wait_stmt

The most basic form of statement in NMFU is a match-statement, which matches any match-expression (explained in the next section).

The next two statements are the assign-statement and append_statement. The assign-statement parses an integer-expression (which are not limited to just integers, again explained in the next section). and assigns its result into the named output-variable. The append-statement instead appends whatever is matched by the match-expression into the named output-variable which must by a string type.

The call-stmt instantiates a macro. Note that there is currently no valid way to pass parameters to them, and as such the expressions provided will be ignored, although may in future be used as C-style macro arguments.

The break-statement is explained along with loops in a later section.

The finish-statement causes the parser to immediately stop and return a DONE status code, which should be interpreted by the calling application as a termination condition.

The wait-statement spins and consumes input until the match-expression provided matches successfully. Importantly, no event (including end of input!) can stop the wait statement, which makes it useful primarily in error handlers.

Expressions

There are three types of expressions in NMFU, match-expressions, integer-expressions and math-expressions.

A match-expression is anything that can consume input to the parser and check it:

?expr: atom // string match
     | regex // not an atom to simplify things
     | "end" -> end_expr
     | "(" expr+ ")" -> concat_expr

atom: STRING "i" -> string_case_const
    | STRING -> string_const

The simplest form of match-expression is the direct-match, which matches a literal string. It can optionally match with case insensitivity by suffixing the literal string with an "i".

The end-match-expression is a match expression which only matches the end of input.

The concat-expression matches any number of match-expressions in order.

The regex-expression matches a subset of regexes. The quirks of the regex dialect NMFU uses can be found in a later section.

An integer-expression is anything that can be directly assigned to an output variable, including strings:

?expr: atom 
     | "[" sum_expr "]"

atom: BOOL_CONST -> bool_const
    | NUMBER -> number_const
    | STRING -> string_const
    | IDENTIFIER -> enum_const

The only two kinds of integer-expressions are literal-expressions, which are just literal strings, integers, enumeration constants (which are resolved based on the context and which output-variable is being assigned) and booleans ("true"/"false"); and math-expressions, which are surrounded in square brackets:

?sum_expr: mul_expr (SUM_OP mul_expr)*
?mul_expr: math_atom (MUL_OP math_atom)*
?math_atom: NUMBER -> math_num
          | IDENTIFIER -> math_var
          | "$" IDENTIFIER -> builtin_math_var
          | "(" sum_expr ")"

(named sum_expr in the grammar)

math-expressions are effectively any arithmetic with either normal numbers, or references to output-variables (referencing their current value) or builtin-math-variables.

The current list of builtin-math-variables is:

For example:

content_length = [content_length * 10 + ($last - 48)]; // the codepoint for '0'

Block Statements

Block statements are statements which contain a block of other statements:

block_stmt: "loop" IDENTIFIER? "{" statement+ "}" -> loop_stmt
          | "case" "{" case_clause+ "}" -> case_stmt
          | "optional" "{" statement+ "}" -> optional_stmt
          | "try" "{" statement+ "}" catch_block -> try_stmt

catch_block: "catch" catch_options? "{" statement* "}"

case_clause: case_predicate ("," case_predicate)* "->" "{" statement* "}"
case_predicate: "else" -> else_predicate
              | expr -> expr_predicate

catch_options: "(" CATCH_OPTION ("," CATCH_OPTION)* ")" 

CATCH_OPTION: /nomatch|outofspace/

loop-statements repeat their block forever until broken out of using a break-statement. loop-statements can optionally have names, which can be referred to in the break-statement to break out of nested loops. If a bare break-statement is encountered, the innermost loop is broken from.

optional-statements either execute their contents if the first match within them matches, otherwise do nothing. It is an error to have anything that does not match as the first statement in an optional-statement.

case-statements match one or more match-expressions and upon successful matching of one of those expressions execute a given block.

For example:

case {
   "GET" -> {method = GET;}
   "POST" -> {method = POST;}
   "PUT","PATCH" -> {wait "\r\n"; result=INVALID_METHOD; finish;}
   else, "OPTIONS" -> {}
}

The special constant "else" means anything not matched by any of the other clauses.

try-except-statements can redirect certain error conditions to the beginning of a different block. They follow the general structure of

try {
   // ... some set of statements ...
}
catch {
   // ... an error handler ...
}

The specific error conditions which they match can be limited by placing a parenthesized comma-separated list of catch-options after the "catch" token, like

try {
   url = /\w+/;
}
catch (outofspace) {
   // ... something to deal with this ...
}

NMFU Regexes

The regex grammar in NMFU is

regex: "/" regex_component* "/"

regex_char_class: "\\" REGEX_CHARCLASS

?regex_component: REGEX_UNIMPORTANT -> regex_raw_match // creates multiple char classes
                | regex_char_class // creates a char class
                | regex_component REGEX_OP -> regex_operation
                | "(" regex_component+ ")" -> regex_group
                | regex_component "{" NUMBER "}" -> regex_exact_repeat
                | regex_component "{" NUMBER "," NUMBER "}" -> regex_range_repeat
                | regex_component "{" NUMBER "," "}" -> regex_at_least_repeat
                | "[^" regex_set_element+ "]" -> regex_inverted_set // creates an inverted char class
                | "[" regex_set_element+ "]" -> regex_set // creates a char class
                | "." -> regex_any // creates an inverted char class
                | regex_component "|" regex_component ("|" regex_component)* -> regex_alternation

?regex_set_element: REGEX_CHARGROUP_ELEMENT_RAW
                  | REGEX_CHARGROUP_ELEMENT_RAW "-" REGEX_CHARGROUP_ELEMENT_RAW -> regex_set_range
                  | regex_char_class

REGEX_UNIMPORTANT: /[^.?*()\[\]\\+{}|\/]|\\\.|\\\*|\\\(|\\\)|\\\[|\\\]|\\\+|\\\\|\\\{|\\\}|\\\||\\\//
REGEX_OP: /[+*?]/
REGEX_CHARGROUP_ELEMENT_RAW: /[^\-\]\\\/]|\\-|\\\]|\\\\|\\\//
REGEX_CHARCLASS: /[wWdDsSntr ]/

although it should be noted that the {1-4} style syntax is not currently implemented.

NMFU regexes support the following common features:

• matching characters
• matching character classes (\w, \S, \d)
• matching character sets ([ab], [a-z\w], [^b])
• the plus, star and question operators
• the wildcard dot
• groups
• alternation (also called OR) ((abc)|(def))

There are some key differences though:

• There is no direct way to match the end of input, even with the normal regex syntax $ (it just matches the literal $)

• The wildcard dot matches every single input except end

• Alternation operates on single characters or groups. This can cause incompatibilities, for example:

  /abc|def/; // matches ab, c or d, then ef, not abc or def.
  

  which must instead be written as

  /(abc)|(def)/;
  

• Groups are non-capturing, in the sense that they serve no function other than to logically group components together

• The space character must be escaped, due to limitations in the lexer.

Generated C API

The output of NMFU is a C source file and header pair. All declarations within the header are prefixed with the output name provided to NMFU.

The generated API contains two or three functions, depending on whether or not dynamic memory was used in the parser. These are:

• {parser_name}_result_t {parser_name}_start({parser_name}_state_t * state);
• {parser_name}_result_t {parser_name}_feed (uint8_t inval, bool is_end, {parser_name}_state_t * state);
• void {parser_name}_free ({parser_name}_state_t * state); (only generated if dynamic memory is used)

These are used to initialize the parser state, send an input character (or end-of-input condition) to the parser, and free any allocated resources for the parser (if present).

The generated {parser_name}_state_t struct contains the member c within which all of the declared output-variables are accessible. Additionally, the length of all string variables can be found under members with the name {out_var_name}_counter.

For example, the generated state structure for

out str[32] url;
out bool accept_gzip = false;
out bool has_etag = false;
out str[32] etag;
out enum{GET,POST} method;
out enum{OK,BADR,URLL,ETAGL,BADM} result;
out int content_size = 0;

looks like:

// state object
struct http_state {
    struct {
        char url[32];
        bool accept_gzip;
        bool has_etag;
        char etag[32];
        http_out_method_t method;
        http_out_result_t result;
        int32_t content_size;
    } c;
    uint8_t url_counter;
    uint8_t etag_counter;
    uint8_t state;
};
typedef struct http_state http_state_t;

Additional enumeration types for every declared enum output-variable are also generated, using the name {parser_name}_out_{out_var_name}_t. The names of the constants use, in all-capitals, {parser_name}_{out_var_name}_{enum_constant}; for example HTTP_RESULT_URLL.

One additional enumeration is always defined, called {parser_name}_result_t which contains the various result codes from NMFU-generated functions. These contain the values {parser_name}_DONE, {parser_name}_OK and {parser_name}_FAIL, for example HTTP_OK.

• OK means that more input should be sent.
• FAIL means that the parser has entered a failing state. This is the default behaviour if no try-except-statement is present.
• DONE means that either a finish-statement executed or the parser has reached the end of it's statements.

Example Usage

A basic usage of a generated parser looks something like

http_state_t state;
http_start(&state); // could potentially return something other than OK if, for example, if the first statement in the parser was "finish" for some reason.

http_feed('G', false, &state);
http_feed('E', false, &state);
http_feed('T', false, &state);

// ...

http_result_t code = http_feed(0 /* value unimportant, conventionally zero */, true, &state);

// ... do something with the code and state ...

http_free(&state);

A more complete example is present in example/http_test.c.

Plugins

There is a vim plugin available which adds syntax highlighting for .nmfu files at mincrmatt12/nmfu-vim.

License

NMFU is licensed under the GPLv3. Copyright (C) 2020 Matthew Mirvish.