Как мне написать парсер в C или Objective-C без генератора парсера? - PullRequest
Новая
       60

Как мне написать парсер в C или Objective-C без генератора парсера?

8 голосов
/ 02 мая 2011

Я пытаюсь создать калькулятор на языке C или Objective-C, который принимает строку вдоль строк 

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

и возвращает ответ 2920. Я бы предпочел не использовать генератор, такой как Lex илиЯк, так что я хочу закодировать это с нуля.Как мне это сделать?Кроме книги Дракона, есть ли какие-либо рекомендуемые тексты, которые охватывают эту тему?

Ответы [ 7 ]

4 голосов
/ 02 мая 2011

Класс Дейва Делонга DDMathParser может сэкономить вам много времени и хлопот.

2 голосов
/ 02 мая 2011

Алгоритм маневрового двора уже упоминался.Другой классический - простой рекурсивный спуск.Вот довольно короткий, который я написал много лет назад: 

#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.Если вместо этого вы хотите интерпретировать результат, вы заменили бы распечатку каждого операнда / оператора фактической оценкой результата этой части выражения.

2 голосов
/ 02 мая 2011

Если я правильно помню, вы можете решить эту проблему с помощью двух стеков, один для операторов, другой для операндов. 

// 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);
   }
1 голос
/ 02 мая 2011
1 голос
/ 02 мая 2011

Я думаю, это близко к тому, что вы хотите: http://www.codeproject.com/KB/recipes/alxparser.aspx

0 голосов
/ 19 ноября 2013

с использованием Objective-C NSLinguisticTagger может быть хорошим решением 

- (void)enumerateTagsInRange:(NSRange)range 
                      scheme:(NSString *)tagScheme
                     options:(NSLinguisticTaggerOptions)opts 
                  usingBlock:(void (^)(NSString *tag, NSRange tokenRange, NSRange sentenceRange, BOOL *stop))block
0 голосов
/ 02 мая 2011

Я сделал это в CSE340: Введение в программирование языков на моем младшем курсе CS в колледже.Так что, если вы действительно хотите закодировать парсер с нуля, будьте готовы, что это может быть "проект продолжительностью в семестр".

Вам понадобится токенизировать, разобрать, построить дерево абстрактных выражений, оценить и т. Д.

Мы использовали Языки программирования Лоудена: принципы и практика .Мне понравилось.Хотя это и не помогло провести вас через процесс реализации.

Конечно, это было бы больше, чем "программирование с нуля".Вам нужно будет создать грамматику, а затем создать синтаксический анализатор для обработки правил ... кроме учебного процесса, я не уверен, почему вы хотите это сделать.

...