quxer

quxer generates dependency-free C99-compliant PEG packrat parsers from text
files in a domain-specific language similar to EBNF. Semantic actions may be
optionally embeded to construct an abstract syntax tree. The backend of the
parser writer was used to boostrap the parser, so the core of the program is
self-hosted.

Compilation

Compile quxer with the standard cmake procedure:

mkdir build && cd build
CC=gcc cmake ..
make

The parsers quxer generates must also be compiled with internal.c/h in
shared.

Example

quxer is self-hosted, so a brief rundown of its inner workings are a good
example of its usage. Internally and prior to generation, grammars are
represented as a set of parser trees comprised of operators, terminals,
nonterminals, etc. A procedure traverses these trees with a bunch of templates
to write the resulting source file. Writing grammars symbolically in C is
tedious, so the challenge is to convert a text file into the symbolic
representation. PEGs themselves can be used to solve this problem! The following
grammar parses the grammar of PEGs and adds semantic actions to produce the
symbolic representation (technically, a wrapper around it):

~grammar     = (ws r : rule)+ ws {{ result = ast_grammar(r, countr); }}
~ws          = (" " / "\n" / "\t")*
~wsp         = (" " / "\n" / "\t")+
~rule        = "~" <name> ws "=" ws b : body {{
  result = ast_rule(c(0), *b);
}}
~name        = [A-Za-z0-9_]+
~body        = o : alt {{ result = *o; }}
~alt         = first : seq (ws "/" ws rest : seq)* {{
  result = ast_Alt(first, rest, countrest + 1);
}}
~seq         = first : operator (wsp rest : operator)* {{
  result = ast_Seq(first, rest, countrest + 1);
}}
~operator    = o : prefix (ws <code>)? {{
  if (ccount) { result = ast_with_code(c(0), *o); } else { result = *o; }
}}
             / o : postfix (ws <code>)? {{
  if (ccount) { result = ast_with_code(c(0), *o); } else { result = *o; }
}}
             / o : group (ws <code>)? {{
  if (ccount) { result = ast_with_code(c(0), *o); } else { result = *o; }
}}
~prefix      = and ws o : group {{ result = ast_And(*o); }}
             / not ws o : group {{ result = ast_Not(*o); }}
~and         = "&"
~not         = "!"
~postfix     = o : group ws star {{ result = ast_Star(*o); }}
             / o : group ws plus {{ result = ast_Plus(*o); }}
             / o : group ws option {{ result = ast_Option(*o); }}
~star        = "*"
~plus        = "+"
~option      = "?"
~group       = "(" ws o : body ws ")" {{ result = *o; }}
             / "<" ws o : body ws ">" {{ result = ast_Capture(*o); }}
             / o : final {{ result = *o; }}
~final       = o : nonterminal {{ result = *o; }}
             / o : literal {{ result = *o; }}
             / o : cclass {{ result = *o; }}
             / o : dot {{ result = *o; }}
~nonterminal = <name> ws ":" ws <name> {{
  result = ast_AliasedNontm(c(1), c(0));
}}
             / <name> {{
  result = ast_Nontm(c(0));
}}
~literal     = "\"" <(&"\\" . . / !"\"" .)*> "\"" {{
  result = ast_Literal(c(0));
}}
~cclass      = "[" <(&"\\" . . / !"]" .)*> "]" {{
  result = ast_CClass(c(0));
}}
~dot         = "." {{ result = ast_dot(); }}
~code        = "{{" (&"\\" . . / !"}}" .)* "}}"

This grammar was first written symbolically (in src/peg/pegspec.c) but the
current parser.c was generated directly from this text.

Explanation

There are many resources for PEGs online to explain the basic stuff. Otherwise:

• Semantic actions are delimited by {{ ... }}.
• Rule definitions are prefixed with ~ but are referenced with their base name
  (this makes the grammar simpler).
• Nonterminals can be referenced in semantic actions with the syntax alias : nonterminal. A single nonterminal node may parse multiple times (if its
  within a * or + operator), so alias is an array of the AST type. Its
  length is given by countalias. Results are stored by assigning result.
• You can capture by bracketing with < ... >. Captures are anonymous and done
  sequantially. The n-th capture (of type uint8_t*) is given by c(n), its
  start index s(n), and its end index e(n). The number of captures is given by
  ccount.
• quxer employs a visitor pattern, that is, semantic actions are not evaluated
  until parsing is complete. Consequently semantic actions cannot provide live
  updates on the parser’s progress.
• When all is said and done, you can run your parser with parse_file(char* filename). This links against internal.h which will start parsing at the
  first grammar rule.

  TODO

• Add failure traces
• Add support for live actions