Skip to content

Instantly share code, notes, and snippets.

@probaldhar
Forked from mayoff/parser.c
Created September 7, 2017 15:18
Show Gist options
  • Save probaldhar/70543c4b3da65fe38fb6c85a6750fdd6 to your computer and use it in GitHub Desktop.
Save probaldhar/70543c4b3da65fe38fb6c85a6750fdd6 to your computer and use it in GitHub Desktop.
recursive descent parser for a very simple tree grammar; see http://stackoverflow.com/questions/14085626
#include <stdio.h>
#include <stdlib.h>
typedef struct BinaryTree {
char info;
struct BinaryTree *left, *right, *father;
} BinaryTree;
typedef struct {
BinaryTree *node;
char const *error;
int offset;
} ParseResult;
ParseResult nodeFromExpression(char const *expression, int offset) {
if (!expression[offset]) {
return (ParseResult){
.error = "end of string where info expected",
.offset = offset
};
}
char info = expression[offset++];
if (info == '$') {
return (ParseResult){
.node = NULL,
.offset = offset
};
}
BinaryTree *leftChild = NULL;
BinaryTree *rightChild = NULL;
if (expression[offset] == '(') {
ParseResult leftResult = nodeFromExpression(expression, offset);
if (leftResult.error)
return leftResult;
offset = leftResult.offset;
if (expression[offset] != ',') {
return (ParseResult){
.error = "comma expected",
.offset = offset
};
}
++offset;
ParseResult rightResult = nodeFromExpression(expression, offset);
if (rightResult.error) {
free(leftResult.node);
return rightResult;
}
offset = rightResult.offset;
if (expression[offset] != ')') {
free(leftResult.node);
free(rightResult.node);
return (ParseResult){
.error = "right parenthesis expected",
.offset = offset
};
}
++offset;
leftChild = leftResult.node;
rightChild = rightResult.node;
}
BinaryTree *node = (BinaryTree *)calloc(1, sizeof *node);
node->info = info;
node->left = leftChild;
node->right = rightChild;
if (leftChild) {
leftChild->father = node;
}
if (rightChild) {
rightChild->father = node;
}
return (ParseResult){
.node = node,
.offset = offset
};
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment