
Re: Is this an exceptionally hard set of questions to answer?
Posted:
Nov 3, 2002 10:09 AM


David B. Redmond <redmonds@sprynet.com> said:
>No, the issue here is expanding the expression by use of the >distributive property and there is no intuition involved.
I'm going to follow this up again. No, the issue is not to expand the expression by use of the distributive property, that's an awfully clunky way of doing it. What we want is a contentfree way of parsing expressions, that is, a syntaxonly way, that works irrespective of semantics.
It is much more effective to use the notions of operator associativity and precedence, which are defined at syntactical level and do not need any knowledge of the semantics of the operations. The rules in this particular case can be pretty simple:
1. Count the level of parenthesis and do operations deeper inside first, 2. Once you got rid of parenthesis, do exponentiations first, followed by multiplications, followed by additions.
This can be encoded in a simple parsing scheme:
1. addition and subtraction have base precedence 1; 2. multiplication and division have base precedence 2; 3. exponentiation has base precedence 3; 4. for every level of parenthesis, add a bias > 4 to the operator's precedence.
What you're left with is the sequence in which you must compute your operations. So, for example,
(3+4)*(5*(6+7))
( sets bias=10 + has precedence 1+10 = 11 ) sets bias=0 * has precedence 2 ( sets bias=10 * has precedence 10+2 = 12 ( sets bias =20 + has precedence 20+2=22 ) sets bias=10 ) sets bias=0
So, what we have to do is to compute in precedence order,
6+7=13 because the rightmost + has precedence 22 5*13=65 because the rightmost * has precedence 12 3+4=7 because the leftmost + has precedence 11 7 * 65 = 455 because the leftmost * has precedence 2.
The point that these rules of precedence get operations do behave as if a distributive law holds is of second importance here, parsing the expression using the distributive property is a waste of time for both men and machines.
By the way, this is called "Klammergebirge", the mountains of parentheses, by its creators Grau, Hill and Langmaak in their vintage 60's Algol compilation book. And notice I'm glossing over issues with unary operators and with operator left or right associativity.
Now, change the precedences, and guess what ? The meaning of the expression may change. That's why something like
a + b*c + d
is ambiguous, notationwise, unless we apply operator precedence rules to it. These precedence rules can be contrived to satisfy the arithmetic distributive property; or they can be changed to mimc whatever semantics we might want to, and they can be made semantics free. We can change the precedence rules if what we want is to do a+b and c+d before we multiply: it basically has to do with what we want our notation to express. And in modern computing, we are entitled to overload the meanings of scribbles such as "+" and "*" to mean things other than numeric addition and multiplication, so in a way the traditional math track is a bit stifling here, we need to have rules to parse expressions that work at syntatic level only and pay no attention to the semantics of the underlying operations. I said it before, the advent of computers has put a different spice into this brew.
Alberto.

