Thu, 28 Feb 2008 19:03:26 -0600

Related articles |
---|

Noob parser question imissfloppydisks@gmail.com (2008-02-27) |

Re: Noob parser question DrDiettrich1@aol.com (Hans-Peter Diettrich) (2008-02-28) |

Re: Noob parser question max@gustavus.edu (Max Hailperin) (2008-02-28) |

Re: Noob parser question gene.ressler@gmail.com (Gene) (2008-02-28) |

Re: Noob parser question imissfloppydisks@gmail.com (2008-02-28) |

From: | Max Hailperin <max@gustavus.edu> |

Newsgroups: | comp.compilers |

Date: | Thu, 28 Feb 2008 19:03:26 -0600 |

Organization: | Compilers Central |

References: | 08-02-094 |

Keywords: | parse |

Posted-Date: | 29 Feb 2008 01:21:26 EST |

imissfloppydisks@gmail.com writes:

*> This is a CFG listed in the Aho (dragon) compiler text:*

*>*

*> expr -> expr + term | expr - term | term*

*> term -> term * factor | term / factor | factor*

*> factor -> digit | (expr)*

*> digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9*

*>*

*> It is intended to parse simple arithmetic expressions taking into*

*> account the precedence of operators. What I don't understand is why*

*> you parse the operators with lower precedence first. I have worked*

*> through several examples by hand and it works but I don't understand*

*> why it works. Perhaps I should be content with that but I am a*

*> perfectionist.*

I think the following might help you think about it. Let's start by

defining the word "bare" to mean "not enclosed in parentheses." Now,

by looking at the grammar, you ought to be able to convince yourself

of the following facts:

(1) A factor does not include any bare operators.

(2) A term does not include any bare + or - operators.

Most of my students when they think about the grammar and these facts

find them relatively convincing, though to actually prove fact (2)

would require the principle of mathematical induction. That's because

in a production like

term -> term * factor

you can't tell that the term on the left of the arrow doesn't include

a bare + or - without somehow knowing (inductively assuming) that the

term on the right of the arrow doesn't include a bare + or -. I think

what happens is that students are essentially implying the induction

principle at an intuitive level.

Anyhow, once you've got those two facts, then the precedence and

associativity follows. For example, returning to

term -> term * factor

we can see that neither the left nor the right operand of the * can

contain a bare + or -, which tells us that * binds more tightly than +

or - does. And, because the right operand cannot contain even a bare

* or /, we know that these operations are left-associative.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.