ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexander Krotoff                    2:5020/400     05 Nov 2001  18:29:36
 To : Denis Fedotov
 Subject : Re: parsing
 -------------------------------------------------------------------------------- 
 

 Denis Fedotov <Denis.Fedotov@p9.f2.n6016.z2.fidonet.org> wrote:
 
 DF> Тут понадобилось небольшой калькулятоp замутить, но вот хочется чеpез
 DF> конечный автомат сделать, а то везде, где видел готовое(у Стpауса), делалось
 DF> методом pекуpсивного спуска. А сам что-то не дойду, как его(автомат) по
 DF> гpамматике вывести. Видел доку по автоматам с магазинной памятью, но там
 DF> были пpимитивные гpамматики, что обобщить на банальное аpифметическое
 DF> выpажение не могу пока. Кинте плиз в нетмейл или табличку или исходники.
 
 Если ты хочешь восходящий разборщик с настоящей таблицей, то лучше
 воспользоваться готорым инструментом навроде yacc или bison.
 Руками эти таблицы строить для настоящей граматики - безумие.
 
 А если нужно просто разборщик выражений - то лови: года два назад
 написался простенький восходящий разбощик. Может пригодится.
 
 -----
 From ank Fri Jul 28 21:16:28 2000
 From: krotoff@such.srcc.msu.su (Alexander Krotoff)
 Subject: Парсер выражений
 Newsgroups: fido7.ru.pccts
 
 Привет!
 
 Hаписался недавно следующий парсер выражений.
 Восходящий, произвольное число приоритетов,
 приоритет префиксных и постфиксных выражений
 над бинарными, произвольная ассоциативность бинарных
 операторов.
 
 Теперь терзаюсь: зачем я его написал ?
 Идеи по модификации и совершенствованию
 приветствуются.
 -- 
 Успехов,
 Саша.
 
 #include <algorithm>
 #include <stack>
 #include <memory>
 #include <stdio.h>
 #include <ctype.h>
 
 struct Node {
   int op;
   Node *left, *right;
   Node (int op, Node *left=0, Node *right=0):
    op(op), left(left), right(right) {};
 };
 
 const int ID = 255;
 
 inline int
 bin_precedence (int op)
 {
   switch (op) {
   case ',': return 0;
   case '=': return 1;
   case '-':
   case '+': return 2;
   case '*':
   case '/': return 3;
   default:  throw "Incorrect binary operator.";
   }
 }
 
 inline bool left_associative (int op) { return op!='='; }
 inline bool unary_op (int op) { return op=='-' || op=='+'; }
 inline bool primary (int op) { return op>ID; }
 
 static Node *parse_expr (int term);
 int lex ();
 
 static Node *
 unary_expr ()
 {
   int l=lex();
   if (unary_op( l ))
    return new Node( l, unary_expr() );
   else if (l=='(')
    return parse_expr( ')' );
   else if (primary( l ))
    return new Node( l );
   else
    throw "Unexpected operator";
 }
 
 typedef stack< Node* > ExprStack;
 
 static Node *
 reduce (ExprStack &expr_stack, Node *last_arg, int op)
 {
   int prec = op==EOF ? -1: bin_precedence( op );
 
   while (!expr_stack.empty()) {
    Node *prev = expr_stack.top();
 
    if (prec > bin_precedence( prev->op )
     || prec == bin_precedence( prev->op )
     && !left_associative( op ))
       break;
    
    expr_stack.pop();
    prev->right = last_arg;
    last_arg = prev;
   }
 
   return last_arg;
 }
 
 static Node *
 parse_expr (int term)
 {
   ExprStack expr_stack;
   try {
    Node *last_arg = unary_expr();
    int op;
    while ((op=lex())!=term) {
       if (op==EOF)
        throw "Unexpected end of expression.";
       if (op=='[')
        last_arg = new Node(
           op, last_arg, parse_expr( ']' )
        );
       else {
        last_arg = reduce( expr_stack, last_arg, op );
        expr_stack.push( new Node( op, last_arg ));
        last_arg = unary_expr();
       }
    }
    return reduce( expr_stack, last_arg, EOF );
   } catch (...) {
    while (!expr_stack.empty()) {
       delete expr_stack.top();
       expr_stack.pop();
    }
    throw;
   }
 }
 
 Node *
 parse_expr()
 {
   try {
    return parse_expr( EOF );
   } catch (const char *msg) {
    fprintf( stderr, "%s\n", msg );
    return 0;
   }
 }
 
 int
 lex()
 {
   int c;
 
   do { c = getchar(); } while (c != EOF && isspace( c ));
 
   if (c==EOF)
    return c;
   else if (isalpha( c ))
    return ID+c;
   else
    return c;
 }
 
 void
 print_tree (Node *p, int n=0)
 {
   for (int i=0; i<n; i++)
    putchar( '\t' );
   if (p->op > ID)
    putchar( p->op-ID );
   else
    putchar( p->op );
   putchar( '\n' );
 
   if (p->left)
    print_tree( p->left, n+1 );
   if (p->right)
    print_tree( p->right, n+1 );
 }
 
 int
 main ()
 {
   Node *tree = parse_expr();
   if (tree)
    print_tree( tree );
 }
 -- 
 Успехов,
 Саша.
 --- ifmail v.2.15dev5
  * Origin: Он знал Сашу Бло. (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    parsing   Denis Fedotov   04 Nov 2001 22:02:08   Re: parsing   Andrey Belyakov   05 Nov 2001 14:07:39   Re: parsing   Alexander Krotoff   05 Nov 2001 18:29:36