Hapy Examples

HAPY EXAMPLES

Below are a few examples for the Hapy grammar specification interface. A quick-start instructions and a BNF-to-Hapy conversion table are available elsewhere.

Example: A simple value grammar -- value is a number, string, or name.

EBNF

value     = number | qw_string | name;
number    = DIGIT DIGIT*;
qw_string = '"' (CHARACTER - '"')* '"';
name      = ALPHA (ALPHA | DIGIT | '_')*;

Hapy

value      = number | qw_string | name;
number     = digit_r >> *digit_r;
qw_string  = quoted_r(anychar_r);
name       = alpha_r >> *(alpha_r | digit_r | '_');

Comments: Hapy expressions approximate EBNF syntax rather well while remaining compliant and portable C++ statements. The most obvious difference is the use of the shift operator (">>") to concatenate grammar symbols. The repetition symbol ("*" a.k.a. Kleene star) is placed in front of the expression rather than at the back.

The Hapy quoted string rule uses quoted_r function to improve readability but that function internal implementation matches the EBNF definition.

Here is an example illustrating both why one would want a backtracking parser (to handle arithmetic and other not-immediately-deterministic expressions), and how Hapy makes building such a parser simple by automatically handling unbounded left recursion so typical in simple expression grammars.

Example: Recursive expressions.

EBNF

expression = expression '+' expression |
             '(' expression ')' |
             value;

Hapy

expression = expression >> '+' >> expression |
             '(' >> expression >> ')' |
             value;

Comments: The importance of this example is that the programmar is not required to eliminate left recursion from EBNF. While such manual elimination is simple in this example, real-world cases may require a lot of energy. Many generated parsers would simply enter an infinite loop, crash or dump core, and not even warn the programmar that left recursion exists.

Hapy parsers handle left recursion by detecting absence of parsing progress and looking for other matching rules instead.

The Needle In Haystack example below detects the presence of a well-formed content in the noise of surrounding opaque data, illustrating the power of full backtracking support. This example may seem rather artificial, but is actually "based on a true story"!

Example: Needle In Haystack.

EBNF

grammar = CHARACTER* needle.
needle = ALPHA '=' DIGIT.

Hapy

rGrammar = *anychar_r >> rNeedle;
rNeedle = alpha_r >> '=' >> digit_r;

Comments: The above grammar is guaranteed to find a "needle", although it may take some time to do that for large inputs. If the input can be very large and speed is of importance, it is usually possible to speed Hapy parsers up by providing various optimization hints. Such optimizations can usually be postponed until the core grammar and the interpreter are well tested.

The kleene star (*anychar_r) rule is greedy. It will consume all input before backtracking in hope to find a matching "needle".

Looking for a complete example? The Primer document discusses how to build a complete expression calculator (doc/calc.cc), including the parsing tree interpreter.