Capstone: a calculator parser
A calculator is a small language: digits, operators and parentheses. The parser turns the text into a tree, and the next lesson evaluates that tree. The work is split the way every compiler splits it: a lexer produces tokens, a recursive-descent parser consumes them with the precedence of the operators.
The lexer
The lexer reads one token at a time: a number, an operator or a parenthesis. It skips spaces, accumulates digits into an integer, and reports a symbol by its character. A token type enum names the cases so the parser does not compare characters.
#include <ctype.h>
#include <stdio.h>
typedef enum { NUMBER, PLUS, MINUS, STAR, SLASH, LPAREN, RPAREN, END } Kind;
int main(void)
{
const char *input = "12+3*(4-5)";
Kind kind;
do {
while (isspace((unsigned char) *input)) {
input++;
}
if (isdigit((unsigned char) *input)) {
int value = 0;
while (isdigit((unsigned char) *input)) {
value = value * 10 + (*input - '0');
input++;
}
printf("number %d\n", value);
kind = NUMBER;
} else {
switch (*input) {
case '+':
kind = PLUS;
break;
case '-':
kind = MINUS;
break;
case '*':
kind = STAR;
break;
case '/':
kind = SLASH;
break;
case '(':
kind = LPAREN;
break;
case ')':
kind = RPAREN;
break;
default:
kind = END;
break;
}
if (kind != END) {
printf("symbol %c\n", *input);
input++;
}
}
} while (kind != END);
printf("end\n");
return 0;
}
gcc -Wall -Wextra lexer.c -o lexer
./lexer
number 12
symbol +
number 3
symbol *
symbol (
number 4
symbol -
number 5
symbol )
end
The digits become one number token, not one token per digit, which is the first decision a lexer makes. The parentheses are ordinary symbols at this level; their meaning appears in the parser. A character outside the language would return END and stop the loop, which is enough for this grammar.
The syntax tree
A node is a number or an operator with two children. The constructors allocate a node and fill it, and the printer writes the tree in prefix form, where the operator comes before its operands and the parentheses show the shape. Building the tree by hand first makes the parser easier to read.
#include <stdio.h>
#include <stdlib.h>
typedef enum { NUMBER, PLUS, STAR } Kind;
struct Node {
Kind kind;
int value;
struct Node *left;
struct Node *right;
};
static struct Node *number(int value)
{
struct Node *node = malloc(sizeof *node);
if (node == NULL) {
exit(1);
}
node->kind = NUMBER;
node->value = value;
node->left = NULL;
node->right = NULL;
return node;
}
static struct Node *binary(Kind kind, struct Node *left, struct Node *right)
{
struct Node *node = malloc(sizeof *node);
if (node == NULL) {
exit(1);
}
node->kind = kind;
node->value = 0;
node->left = left;
node->right = right;
return node;
}
static void print(const struct Node *node)
{
if (node->kind == NUMBER) {
printf("%d", node->value);
} else {
printf("(%c ", node->kind == PLUS ? '+' : '*');
print(node->left);
printf(" ");
print(node->right);
printf(")");
}
}
static void free_tree(struct Node *node)
{
if (node == NULL) {
return;
}
free_tree(node->left);
free_tree(node->right);
free(node);
}
int main(void)
{
struct Node *tree = binary(PLUS, number(1), binary(STAR, number(2), number(3)));
print(tree);
printf("\n");
free_tree(tree);
return 0;
}
gcc -Wall -Wextra nodes.c -o nodes
./nodes
(+ 1 (* 2 3))
The tree says that the multiplication is the right child of the addition, which is the precedence rule in data form. The printer is a recursive walk like the one in lesson 53; the evaluation in lesson 79 is another walk with arithmetic at the nodes.
Recursive descent
Three functions encode the precedence. expression handles + and -, term handles * and /, and factor handles a number or a parenthesised expression. Each function reads as many operators of its level as it can, which is why the higher level ends up deeper in the tree.
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
typedef enum { NUMBER, PLUS, MINUS, STAR, SLASH, LPAREN, RPAREN, END } Kind;
struct Node {
Kind kind;
int value;
struct Node *left;
struct Node *right;
};
static const char *cursor;
static Kind token;
static int number_value;
static void next_token(void)
{
while (isspace((unsigned char) *cursor)) {
cursor++;
}
if (isdigit((unsigned char) *cursor)) {
number_value = 0;
while (isdigit((unsigned char) *cursor)) {
number_value = number_value * 10 + (*cursor - '0');
cursor++;
}
token = NUMBER;
return;
}
switch (*cursor) {
case '+': token = PLUS; break;
case '-': token = MINUS; break;
case '*': token = STAR; break;
case '/': token = SLASH; break;
case '(': token = LPAREN; break;
case ')': token = RPAREN; break;
default: token = END; break;
}
if (token != END) {
cursor++;
}
}
static struct Node *make(Kind kind, int value, struct Node *left, struct Node *right)
{
struct Node *node = malloc(sizeof *node);
if (node == NULL) {
exit(1);
}
node->kind = kind;
node->value = value;
node->left = left;
node->right = right;
return node;
}
static struct Node *expression(void);
static struct Node *factor(void)
{
if (token == NUMBER) {
int value = number_value;
next_token();
return make(NUMBER, value, NULL, NULL);
}
if (token == LPAREN) {
next_token();
struct Node *inner = expression();
if (token == RPAREN) {
next_token();
}
return inner;
}
return NULL;
}
static struct Node *term(void)
{
struct Node *node = factor();
while (token == STAR || token == SLASH) {
Kind op = token;
next_token();
node = make(op, 0, node, factor());
}
return node;
}
static struct Node *expression(void)
{
struct Node *node = term();
while (token == PLUS || token == MINUS) {
Kind op = token;
next_token();
node = make(op, 0, node, term());
}
return node;
}
static void print(const struct Node *node)
{
if (node->kind == NUMBER) {
printf("%d", node->value);
return;
}
printf("(%c ", node->kind == PLUS ? '+' : node->kind == MINUS ? '-' : node->kind == STAR ? '*' : '/');
print(node->left);
printf(" ");
print(node->right);
printf(")");
}
static void free_tree(struct Node *node)
{
if (node == NULL) {
return;
}
free_tree(node->left);
free_tree(node->right);
free(node);
}
int main(void)
{
cursor = "1+2*3";
next_token();
struct Node *tree = expression();
print(tree);
printf("\n");
free_tree(tree);
return 0;
}
gcc -Wall -Wextra parse.c -o parse
./parse
(+ 1 (* 2 3))
The addition is the root because expression calls term for its left operand and stops at the plus; the multiplication is built inside the term before the plus is consumed. The same three functions handle every binary operator this calculator needs; a power operator would add a level between term and factor.
A parse error
A parser must report the position of the first token it cannot use. factor expects a number or an opening parenthesis; when the group is not closed, it expects ) and finds the end instead. The error message names the expectation and the offset, and the exit status is 1.
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
typedef enum { NUMBER, PLUS, MINUS, STAR, SLASH, LPAREN, RPAREN, END } Kind;
struct Node {
Kind kind;
int value;
struct Node *left;
struct Node *right;
};
static const char *begin;
static const char *cursor;
static Kind token;
static int number_value;
static void next_token(void)
{
while (isspace((unsigned char) *cursor)) {
cursor++;
}
if (isdigit((unsigned char) *cursor)) {
number_value = 0;
while (isdigit((unsigned char) *cursor)) {
number_value = number_value * 10 + (*cursor - '0');
cursor++;
}
token = NUMBER;
return;
}
switch (*cursor) {
case '+': token = PLUS; break;
case '-': token = MINUS; break;
case '*': token = STAR; break;
case '/': token = SLASH; break;
case '(': token = LPAREN; break;
case ')': token = RPAREN; break;
default: token = END; break;
}
if (token != END) {
cursor++;
}
}
static struct Node *make(Kind kind, int value, struct Node *left, struct Node *right)
{
struct Node *node = malloc(sizeof *node);
if (node == NULL) {
exit(1);
}
node->kind = kind;
node->value = value;
node->left = left;
node->right = right;
return node;
}
static void fail(const char *message)
{
printf("error: %s at offset %ld\n", message, (long) (cursor - begin));
exit(1);
}
static struct Node *expression(void);
static struct Node *factor(void)
{
if (token == NUMBER) {
int value = number_value;
next_token();
return make(NUMBER, value, NULL, NULL);
}
if (token == LPAREN) {
next_token();
struct Node *inner = expression();
if (token != RPAREN) {
fail("expected )");
}
next_token();
return inner;
}
fail("expected a number or (");
return NULL;
}
static struct Node *term(void)
{
struct Node *node = factor();
while (token == STAR || token == SLASH) {
Kind op = token;
next_token();
node = make(op, 0, node, factor());
}
return node;
}
static struct Node *expression(void)
{
struct Node *node = term();
while (token == PLUS || token == MINUS) {
Kind op = token;
next_token();
node = make(op, 0, node, term());
}
return node;
}
int main(void)
{
begin = "1+(2*3";
cursor = begin;
next_token();
struct Node *tree = expression();
printf("parsed\n");
free(tree);
return 0;
}
gcc -Wall -Wextra error.c -o error
./error; echo "status: $?"
error: expected ) at offset 6
status: 1
The offset points one past the last consumed token, at the end of the string, and the status 1 lets a script stop. The tree allocated before the failure is not freed because the process exits; a longer-lived parser would free the partial tree in the same function that reports the error.
A missing enum case
The token kinds are an enumeration, and a function that turns one into a name must handle every value. A switch that lists four of five kinds compiles with a warning, and the missing value falls through to the return after the switch, where the name may be wrong.
#include <stdio.h>
typedef enum { NUMBER, PLUS, MINUS, STAR, END } Kind;
static const char *name(Kind kind)
{
switch (kind) {
case NUMBER:
return "number";
case PLUS:
return "plus";
case MINUS:
return "minus";
case STAR:
return "star";
}
return "end";
}
int main(void)
{
printf("%s\n", name(PLUS));
return 0;
}
gcc -Wall -Wextra switchwarn.c -o switchwarn
switchwarn.c: In function 'name':
switchwarn.c:7:5: warning: enumeration value 'END' not handled in switch [-Wswitch]
7 | switch (kind) {
| ^~~~~~
The program still prints plus, because the missing case is not the one used, but the fallthrough return happens to produce "end" for the missing value and would be wrong for a new token. The warning is the check: list every enumerator, and let the compiler tell you when a token is added.
Exercises
- Add the / and - operators to the printed tree and test 8-2/2.
- Add unary minus so that -3+5 parses, and decide where it belongs in the factor function.
- Make the parser read the expression from argv[1] with lesson 75 and print the offset of an unexpected character.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
How does the lexer turn
12into a token?Answer
It accumulates digits into one number
The digit loop builds the integer and advances past all of them, so the parser sees one number token.
-
What does the prefix form
(+ 1 (* 2 3))show?Answer
The addition is the root and the product a child
The printer writes the operator before its operands, so the outer addition contains the multiplication.
-
Which function handles the higher-precedence operators?
Answer
term, called byexpressionexpressionhandles plus and minus,termhandles star and slash, andfactorhandles numbers and parentheses. -
What does the parser report when a group is not closed?
Answer
The expected token and its offset
failprints the expectation and the cursor offset, then exits with status 1. -
What does the lexer print for
12+3*(4-5)?Answer
number 12, symbols + * ( - ) and end
The digits become one number token and every operator or parenthesis becomes a symbol token.
-
What does the hand-built tree print?
Answer
(+ 1 (* 2 3))
The addition is the root, its right child is the multiplication, and the printer uses prefix notation.
-
What does the recursive-descent parser print for
1+2*3?Answer
(+ 1 (* 2 3))
expressionbuilds the addition and its right operand is the term2*3, so the product sits below the plus. -
What does the malformed input
1+(2*3report?Answer
error: expected ) at offset 6 and status 1
The factor expects the closing parenthesis, finds the end at offset 6, prints the message and exits 1.
-
What does
-Wswitchreport in the enum-name function?Answer
That the value
ENDhas no caseThe switch lists four of the five enumerators, and the warning names the missing one.
-
Why does the parser need
next_tokenafter a closing parenthesis?Answer
To move past it to the next token
The current token is the
), and the parser advances so the caller continues after the completed group.
The code on this page was run with gcc (Alpine 15.2.0) 15.2.0 on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev