Re: expressions -- functions within function

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

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