8 Mar 2007 19:53:16 -0500

Related articles |
---|

expressions -- functions within function mr.waverlye@verizon.net (Mr.E) (2007-03-08) |

Re: expressions -- functions within function ajo@alumni.cmu.edu (Arthur J. O'Dwyer) (2007-03-08) |

Re: expressions -- functions within function mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2007-03-10) |

From: | "Arthur J. O'Dwyer" <ajo@alumni.cmu.edu> |

Newsgroups: | comp.compilers |

Date: | 8 Mar 2007 19:53:16 -0500 |

Organization: | Carnegie Mellon, Pittsburgh, PA |

References: | 07-03-027 |

Keywords: | parse |

Posted-Date: | 08 Mar 2007 19:53:16 EST |

On Thu, 8 Mar 2007, Mr.E wrote:

*>*

*> How would you insert a generic function into the precedence parser?*

*> Actually more specifically, is it possible to insert a representation*

*> of a generic function that has parameters that allows functions with*

*> formal parameters as arguments?*

*>*

*> As I thought about the use of an operator precedence parser I*

*> concluded that if I were to encounter an expression that contained a*

*> parameterized function, there would not be a way for me to deal with a*

*> new expression until the original was complete unless I instantiated*

*> another stack to represent the new expression. Example:*

*>*

*> a = FN thisFunction( b ,FN thatFunction( c + 1, FN*

*> anotherFunction))*

*>*

*> When I start to deal with FN thatFunction which has parameters and*

*> expressions of its own, I would need to start a brand new stack. That*

*> doesn't seem like a good idea. If this were a recursive descent*

*> evaluation just recursively calling the procedure expr0 (the*

*> expression entry point) would be the thing to do. I'm at a loss as to*

*> how I would deal with parameterized functions that have parameterized*

*> functions as expressions.*

*>*

*> Would someone mind presenting some ideas that would assist me in*

*> dealing with this problem?*

Well, your first idea sounds good to me: just recursively invoke expr0()

to deal with each of the parameter-expressions. As you say, that would

be like recursive descent parsing.

If you really want everything to use the same stack-based method, you

could try the following approach:

First, as an exercise, implement implicit multiplication. That is,

modify your parser so that if it sees two expressions butting up against

one another, as in "2 x" or "(x+y)(x-y)", it will push a multiplication

operator automatically onto the operator stack. Make the "implicit

multiplication" operator distinct from the "explicit multiplication"

operator, so that you can change its precedence later on.

Then, consider that the expression "f(x)" is not all that different

from "(x+y)(x-y)". Modify the implicit-multiplication parser so that

the "implicit multiplication" operator has very high precedence, and

only gets pushed if the second expression starts with a left parenthesis.

Change its name to "function-call operator". Now you should be able to

correctly parse functions of one argument, such as "sin(x)"; however,

you will treat "(x+y)(z)" as an application of the function "(x+y)" to z,

which is probably not what you want; and you won't parse "pow(e,x)".

Next, add the "comma" operator with very low precedence, and make

"x,y" evaluate to a list containing both x and y. Now you can parse

and evaluate "pow(e,x)" --- it's the application of "pow" to the list

containing both e and x.

Finally, if you like, you can disallow "(x+y)(z,w)" by only inserting

the implicit function-call operator if it comes before a left-parenthesis

*and* after an identifier. Or you can make your language more ML-like

by removing the left-parenthesis requirement, and letting the user type

things like "f x" as a synonym for "f(x)".

The "implicit function-call operator" idea is used in plenty of

real-world languages, from C to Lisp. It might seem a weirder approach

than just adding a special case using recursive descent... and I think

it is! But it can be done.

HTH,

-Arthur

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.