Tuesday, March 08, 2005

I lost a bit of time this morning when I received a phone call from Luc's daycare to tell me he'd had an accident. So I went back to see Luc and make sure he was all right. When I finally got back to UQ there was no parking available, so I had to go home to work.

I had a few things to carry today, so I needed the car. However, I have to ask if it is worth it, given that I spent 2 hours and 20 minutes traveling traveling back and forth over a distance that I can cycle in under 10 minutes. Even if I want to use the bike there is a problem, as the cycle lockup in this building is full, and the rate of bicycle theft around here is too high to leave it chained up outside.

In the end I had to make up the time at night, which cut into my time for doing my confirmation writing. All in all, a frustrating experience.

The majority of my coding was spent on the grammar for SableCC.

I now realise that the various definition levels create the levels of associativity. Hence, the following extract from the definition makes the AND operation more strongly associative than OR:

  constraint_expression =
{term} constraint_term |
{or} constraint_expression or constraint_term ;

constraint_term =
{factor} constraint_factor |
{and} constraint_term and constraint_factor ;
The names "constraint_expression" and "constraint_term" are rather arbitrary. However, you can see that an AND-term is built from either a "factor" (constraint_factor) or an AND-term with a factor. Similarly, an OR-expression is built from either an AND-term or an OR-expression with an AND-term.

Going bottom up, this means that the factors will get found first, followed by the AND-terms, followed by the OR-expressions. This gives AND greater precedence than OR, as desired.

I decided to put MINUS below AND, not for any good reason, but because the WHERE clause evaluation could remain unchanged at the top level. I also have a idea that MINUS should be evaluated first, and that any complex statements for either the minuend or the subtrahend should be enclosed in brackets.

(I knew there were terms like "minuend" and "subtrahend", but I couldn't remember them and had to look them up. They may seem pretentious, but I thought they were better than LHS and RHS).

Consequently I created a new level between constraint_term and constraint_factor. Without any inventive ideas, I decided that this must be a "difference" term, so I called it constraint_dterm. After seeing the Java code for this I'm a little less sure of myself, as it is not so easy to see the difference in names when looking at constraint_term vs. constraint_dterm.

My first attempt tried to use a constraint_expression on either side of the MINUS keyword. This failed (and I see why now), with the following error from SableCC:
shift/reduce conflict in state [stack: PSelectClause TWhere PConstraintTerm *] on TAnd in {
[ PConstraintExpression = PConstraintTerm * ] followed by TAnd (reduce),
[ PConstraintTerm = PConstraintTerm * TAnd PConstraintDterm ] (shift)
I saw Simon online, and along with a little bit of help from the SableCC author, I was able to see where the ambiguity was coming from.

I expected that if SableCC saw an expression such as:
A - B - C
Then it would evaluate from left to right. ie.:
(A - B) - C
However, the compiler sees this as an ambiguity between both possible evaluations:
(A - B) - C
A - (B - C)
If you want left-to-right evaluation then you have to explicitly declare it. This makes sense, as a compiler should have the right to define this.

Anyway, after a couple of attempts I finally got it right. I also have all of the parser code implemented, so now I'm working on the actual difference code.

No comments: