The smallest cparse grammar that still teaches something. Parses arithmetic expressions like 1 + 2 * 3 or (4 + 5) * -6, respecting the usual precedence of * / over + - and permitting parenthesised subexpressions and unary minus.
Full source below (about 130 lines including a driver). Each section is unpacked afterwards.
The full program
#include <cparse/Parser.hh>
#include <cctype>
#include <iostream>
#include <optional>
#include <sstream>
#include <variant>
#include <vector>
using fedem::parser::ParseError;
class Calculator : public fedem::parser::Parser
{
public:
std::string getGrammarName() const noexcept override { return "toy-calc"; }
// Public entry point: parse a string, return the computed value or
// nullopt on error (with diagnostics in errors()).
std::optional<double> evaluate(std::string const& source)
{
auto ss = std::make_shared<std::istringstream>(source);
pushCursor("<expr>", ss);
if (!start()) return std::nullopt;
return result_;
}
protected:
bool start() override
{
skipWhiteSpaces();
if (!parseExpression(result_)) return false;
skipWhiteSpaces();
if (getCursor().safePeek() != '\032')
{
recordError(ParseError::Kind::Syntax,
"trailing characters after expression");
return false;
}
return true;
}
private:
// expression := term (('+' | '-') term)*
bool parseExpression(double& out)
{
if (!parseTerm(out)) return false;
skipWhiteSpaces();
while (true)
{
char const op = getCursor().safePeek();
if (op != '+' && op != '-') return true;
getCursor().get();
skipWhiteSpaces();
double rhs;
if (!parseTerm(rhs))
{
recordError(ParseError::Kind::Syntax,
std::string{"expected term after '"} + op + "'");
return false;
}
out = (op == '+') ? out + rhs : out - rhs;
skipWhiteSpaces();
}
}
// term := factor (('*' | '/') factor)*
bool parseTerm(double& out)
{
if (!parseFactor(out)) return false;
skipWhiteSpaces();
while (true)
{
char const op = getCursor().safePeek();
if (op != '*' && op != '/') return true;
getCursor().get();
skipWhiteSpaces();
double rhs;
if (!parseFactor(rhs))
{
recordError(ParseError::Kind::Syntax,
std::string{"expected factor after '"} + op + "'");
return false;
}
if (op == '/' && rhs == 0.0)
{
recordError(ParseError::Kind::Faulty, "division by zero");
return false;
}
out = (op == '*') ? out * rhs : out / rhs;
skipWhiteSpaces();
}
}
// factor := number | '(' expression ')' | '-' factor
bool parseFactor(double& out)
{
skipWhiteSpaces();
char const c = getCursor().safePeek();
if (c == '(')
{
getCursor().get();
enterScope();
if (!parseExpression(out)) return false;
skipWhiteSpaces();
if (!extractCharacter(')'))
{
recordError(ParseError::Kind::Syntax, "expected ')'");
return false;
}
leaveScope();
return true;
}
if (c == '-')
{
getCursor().get();
if (!parseFactor(out)) return false;
out = -out;
return true;
}
if (std::isdigit(static_cast<unsigned char>(c)) || c == '.')
{
return parseNumber(out);
}
recordError(ParseError::Kind::Syntax, "expected number, '(' or '-'");
return false;
}
bool parseNumber(double& out)
{
std::string s;
while (true)
{
char const c = getCursor().safePeek();
if (!std::isdigit(static_cast<unsigned char>(c)) && c != '.') break;
s += getCursor().safeGet();
}
if (s.empty()) return false;
try { out = std::stod(s); }
catch (...) {
recordError(ParseError::Kind::Type, "invalid number '" + s + "'");
return false;
}
return true;
}
double result_ = 0.0;
};
int main()
{
for (std::string line; std::getline(std::cin, line); )
{
if (line.empty()) continue;
Calculator c;
if (auto v = c.evaluate(line))
std::cout << *v << '\n';
else
for (auto const& e : c.errors())
std::cerr << e.filename << ':' << e.line << ':' << e.col
<< ": " << e.message << '\n';
}
}
The grammar
Standard textbook precedence expressed as three mutually recursive functions, each responsible for one precedence level:
expression := term (('+' | '-') term)*
term := factor (('*' | '/') factor)*
factor := number | '(' expression ')' | '-' factor
Same grammar as railroad diagrams — a rounded box is a literal token, a square box is a reference to another rule, read left to right:
parseExpression handles low-precedence + -. parseTerm handles higher-precedence * /. parseFactor handles the "atomic" units: numbers, parenthesised subexpressions, unary minus.
Recursion falls out naturally. Parenthesised subexpressions descend into parseExpression from inside parseFactor; unary minus descends into parseFactor from itself.
Reading the code
start() sets up and tears down the top-level parse. Skips leading whitespace, calls parseExpression, checks that nothing non-whitespace remains. The trailing-character check catches input like "1 + 2 garbage" — parseExpression accepts 1 + 2 and returns, but start() sees garbage still on the cursor and reports the syntax error.
The check compares safePeek() against '\032', the EOF sentinel. This is idiomatic — safePeek never throws at end of input, it just returns the sentinel.
safePeek() decides what to do next; get() commits. The pattern in every parseXxx function is: peek to see whether the next character kicks off the production we handle, and only call get() after we have committed to consuming it. This lets a production fail without consuming input, so a caller can try alternatives.
Errors are recorded with Kind::Syntax for the recoverable cases and Kind::Faulty for the semantic ones. Division by zero is semantically wrong but syntactically fine — it deserves Faulty, not Syntax.
enterScope/leaveScope marks the parentheses — but nothing reads them back here. The pairing exists so Parser::parse can tell a truncated file apart from a clean end-of-input: it catches the underlying end-of-input exception, checks openScopeDepth(), and reports an unterminated scope instead of a clean finish if a scope was still open. Two things keep that from applying to (1 + 2, a missing close paren: evaluate() calls start() directly, never parse(), so nothing ever consults the depth; and even where this codebase's other examples do call parse(), their reads all use safePeek()/safeGet(), which hand back an EOF sentinel character instead of throwing — so the exception parse() is waiting to catch never actually happens. A missing close paren still gets a clear diagnostic here regardless: parseFactor's own extractCharacter(')') check fails and records "expected ')'" at the position it expected one — see it for yourself in "Trying it" below.
pushCursor reads from memory. evaluate wraps the input string in an istringstream and pushes a cursor around it. The grammar helpers work identically whether the source is a file or a string; the only difference is where the cursor was constructed.
Trying it
Compile and run:
g++ -std=c++20 toy_calc.cpp $(pkg-config --cflags --libs cparse) -o calc
echo "1 + 2 * 3" | ./calc # → 7
echo "(4+5)*-6" | ./calc # → -54
echo "1 + " | ./calc # → error: expected number, '(' or '-'
# (then) error: expected term after '+'
echo "10/0" | ./calc # → error: division by zero
echo "(1 + 2" | ./calc # → error: expected ')'
What is deliberately absent
- No look-up table for operators. Two operator classes, three functions — the direct code is clearer than a table.
- No AST.
parseExpressionreturns the value by out-parameter. A real calculator would build an AST first and evaluate separately; the point here is to keep the grammar short. - No comment or whitespace override. The base
skipWhiteSpaces— any run ofstd::isspace— is exactly right for arithmetic expressions. No comments in this language.
See also
- Getting Started — the introductory walkthrough with an even simpler grammar (comma-separated integers).
- Grammar Patterns — the recurring patterns this example uses.
- Key/value config — the next example, which introduces scope tracking on a file-reading grammar.
- CSV-lite — an iterator-style variant.
