7 Jun 2002 23:40:06 -0400

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) |

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.