Re: simple syntax analysis

"Walter Misar" <misar@rbg.informatik.tu-darmstadt.de>
7 Jun 2002 23:40:06 -0400

          From comp.compilers

Related articles
simple syntax analysis julia.donawald@gmx.de (Julia Donawald) (2002-05-27)
Re: simple syntax analysis joachim_d@gmx.de (Joachim Durchholz) (2002-05-27)
Re: simple syntax analysis andreas.gieriet@externsoft.ch (Andreas Gieriet) (2002-05-31)
Re: simple syntax analysis misar@rbg.informatik.tu-darmstadt.de (Walter Misar) (2002-06-07)
| List of all articles for this month |

From: "Walter Misar" <misar@rbg.informatik.tu-darmstadt.de>
Newsgroups: comp.compilers
Date: 7 Jun 2002 23:40:06 -0400
Organization: Technische Universitaet Darmstadt
References: 02-05-140
Keywords: syntax
Posted-Date: 07 Jun 2002 23:40:06 EDT

Julia Donawald <julia.donawald@gmx.de> wrote:
> I have written the following pseudo-code to built up a parse tree of the
> following sequence: [A] [OR] [B] [AND] [C]. I read in some books about that
> theme and create the following grammar:
> expr := factor | factor OR expr | factor AND expr
> factor:= letter | (expr)


> So I want that first the both left letters are considered and after the
> result of these both in connection with the next is calculated and so on...
> so maybe I want something like: more left, first considered.
> Maybe my grammar is wrong ( I dont need any priority of the operators ), or
> the code I wrote from it. But really dont know what I have done wrong.


You probably want the operators to be left associative. This can be
done by stating the grammar as:


expr := factor | expr OR factor | expr AND factor
factor := letter | (expr)


But from this grammar one can't directly build a recursive descent
parser. One can get rid of the left recursions via well known
transformations [1]. This will lead to something like:


expr := factor expr2
expr2 := | OR factor expr2 | AND factor expr2
factor := letter | (expr)


The recursive descent parser would look like:


expr() { return expr2(factor()); }
expr2(left_tree)
{ if (next_char == OR)
        return expr2(CreateOperatorOr(left_tree, factor()));
    else if (next_char == AND)
        return expr2(CreateOperatorAnd(left_tree, factor()));
    else
        return left_tree;
}


Of course it isn't necessary to use two rules and recursion, instead
something like the follwing will work too:


expr()
{ left_tree = factor();
    while (next_char == OR || next_char == AND)
        left_tree = CreateOperator(next_char, left_tree, factor());
    return left_tree;
}


[1] for example see http://ironbark.bendigo.latrobe.edu.au/subjects/bitsys/clect/Lect07.html


--
Walter Misar misar@rbg.informatik.tu-darmstadt.de


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.