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

parser.c

    #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
        };
    }