public
Last active

recursive descent parser for a very simple tree grammar; see http://stackoverflow.com/questions/14085626

  • Download Gist
parser.c
C
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
#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
};
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.