How do I write a parser in C or Objective-C without a parser generator?
Asked Answered
N

7

8

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?

Nanosecond answered 2/5, 2011 at 3:1 Comment(0)
D
1

Try this:

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

Deflocculate answered 2/5, 2011 at 3:9 Comment(0)
H
4

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

Honourable answered 2/5, 2011 at 3:16 Comment(0)
G
2

If I remember correctly, you can solve this problem with two stacks, one for the operators, the other for the operands.

// OPTR stack: store operators
// OPND stack: store operands
// OP: predefined set of operators
OperandType EvaluateExpression(){  

   InitStack(OPET);Push(OPTR,'#');  
   initStack(OPND);c=getchar();  
   while(c!='#'||GetTop(OPTR)!='#'){  
     if(!In(c,OP)){Push((OPND,c);c=getchar();} //Push to stack if not operator
     else 
       switch(Precede(GetTop(OPTR),c){
         //Top element in stack has a lower priority  
         case '<':
               Push(OPTR,c); c=getch();  
               break;
         case '=':
               Pop(OPTR,x); c=getch();  
               break;
         //Pop top element and push back the calculated result 
         case '>':
               Pop(OPTR,theta);  
               Pop(OPND,b); Pop(OPND,a);  
               Push(OPND,Operate(a,theta,b));  
               break;  
         } 
     } 
     return GetTop(OPND);
   }
Gettogether answered 2/5, 2011 at 3:5 Comment(0)
A
2

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.

Apomixis answered 2/5, 2011 at 3:17 Comment(1)
Shunting yard and recdes aren't mutually exclusive. In fact, they're commonly combined. Shunting yard is used for expressions (where recdes is inefficient) and recdes for everything else (since it's more powerful and general)Tyrontyrone
G
1

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

Getter answered 2/5, 2011 at 3:4 Comment(0)
D
1

Try this:

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

Deflocculate answered 2/5, 2011 at 3:9 Comment(0)
E
0

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.

Eirena answered 2/5, 2011 at 3:7 Comment(0)
W
0

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
Weisshorn answered 19/11, 2013 at 10:50 Comment(1)
please edit your post and format a bit to make it readable (tried but got lost ;-)Cassell

© 2022 - 2024 — McMap. All rights reserved.