如果没有解析器生成器，如何用 C 或 Objective-C 编写解析器？

Question

我正在尝试用 C 或 Objective-C 制作一个计算器，它接受 2920 的字符串

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

并返回答案 2920。我不想使用像 Lex 或 Yacc 这样的生成器，所以我想从头开始编码。我该怎么做呢？除了《龙》这本书之外，还有其他涉及此主题的推荐文本吗？

Answer 1

Dave DeLong 的 DDMathParser 类可能会为您节省大量时间和麻烦。

Answer 2

如果我没记错的话，你可以用两个堆栈来解决这个问题，一个用于运算符，另一个用于操作数。

// 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);
   }

Answer 3

调车场算法已经提到过。另一种经典的方法是简单的递归下降。这是我多年前写的一篇相当短的文章：

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

请注意，这个特定的文章只是解析输入，并将其转换为 RPN 形式。如果您想解释结果，则可以用实际评估表达式该部分的结果来代替打印每个操作数/运算符。

Answer 4

试试这个：

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

Answer 5

我认为这接近你想要的：
http://www.codeproject.com/KB/recipes/alxparser.aspx

Answer 6

我在大学计算机科学专业三年级时在《CSE340：编程语言简介》中做到了这一点。因此，如果您真的想要从头开始编写解析器，请做好准备，这可能是“一个学期的项目”。

您需要标记、解析、构建抽象表达式树、评估等。

我们使用 劳登的编程语言：原理与实践。我喜欢它。尽管它并没有很好地引导您完成实施过程。

当然，这不仅仅是“从头开始编码”。您需要制定语法，然后构建一个解析器来处理规则......除了学习活动之外，我不确定您为什么要这样做。

Answer 7

使用 Objective-C NSLinguisticTagger 可能是一个很好的解决方案

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