How do I write a parser in C or Objective-C withou

Question

I am trying to make a calculator in C or Objective-C that accepts a string along the lines of

8/2+4(3*9)^2

and returns the answer 2920. I would prefer not to use a generator like Lex or Yacc, so I want to code it from the ground up. How should I go about doing this? Other than the Dragon book, are there any recommended texts that cover this subject matter?

Answer 1

Dave DeLong's DDMathParser class may save you a lot of time and trouble.

Answer 2

Try this:

http://en.wikipedia.org/wiki/Shunting-yard_algorithm

Answer 3

using Objective-C NSLinguisticTagger may be a good solution

- (void)enumerateTagsInRange:(NSRange)range 
                      scheme:(NSString *)tagScheme
                     options:(NSLinguisticTaggerOptions)opts 
                  usingBlock:(void (^)(NSString *tag, NSRange tokenRange, NSRange sentenceRange, BOOL *stop))block

Answer 4

I did this in CSE340: Introduction to Programming Lanugages in my Junior year of CS in college. So if you really want to code up a parser from scratch, be prepared that it could be "a semester long project."

You'll need to tokenize, parse, build an abstract expression tree, evaluate, etc.

We used Louden's Programming Languages: Principles and Practice. I liked it. Though it didn't do the best job of walking you through the implementation process.

Of course, this would be more than "coding up from scratch." You'd need to make a grammar, then build a parser to process the rules...aside from a learning activity, I'm not sure why you'd wanna do this.

Answer 5

The shunting yard algorithm has already been mentioned. The other classic one is simple recursive descent. Here's a fairly short one I wrote many years ago:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void expression(void);

void show(int ch) { 
    putchar(ch);
    putchar(' ');
}

int token() { 
    int ch;
    while (isspace(ch=getchar()))
        ;
    return ch;
}

void factor() { 
    int ch = token();
    if (ch == '(') {
        expression();
        ch = token();
        if (ch != ')') {
            fprintf(stderr, "Syntax error. Expected close paren, found: %c\n", ch);
            exit(EXIT_FAILURE);
        }
    }
    else
        show(ch);
}

void term() { 
    int ch;
    factor();
    ch = token();
    if (ch == '*' || ch == '/') {
        term();
        show(ch);
    }
    else
        ungetc(ch, stdin);
}

void expression() {
    int ch;
    term();
    ch = token();
    if (ch == '-' || ch=='+') {
        expression();
        show(ch);
    }
    else 
        ungetc(ch, stdin);
}

int main(int argc, char **argv) {
    expression();
    return 0;
}

Note that this particular one just parses input, and converts it to RPN form. If you want to interpret the result instead, you'd replace printing out each operand/operator with actually evaluating the result of that part of the expression.

Answer 6

I think this close to what you want: http://www.codeproject.com/KB/recipes/alxparser.aspx