Hi,
On Fri, 17 Dec 1999, Lars Skovlund wrote:
[...]
> Hope this helps. I know it's messy - not really easy to understand without a
> set of diagrams to refer to either.
I still don't have a good feeling about it. If you don't mind, I'd like to
iterate over the whole thing step by step, and break it down into little
pieces. This is going to be painful, though.
-- part 1
Let's start with a few definitions.
We take four sets (or data types, I don't know what the correct english
expression is): Trees (T), Natural numbers (N), Word groups (W), and
Said trees (S).
---
----------
/ \
0x141 tree node
/ \
/ \
0x13F (t)
is defined as TOP(t), the top tree. A vaild Said tree is a valid TOP
tree. It's signature (type of the return value) is S.
We define # to be an element of T; it's the "empty" tree.
The smallest valid Said tree is TOP(#), consisting of two tree nodes and
two leaf nodes.
---
The second function
(parent node in main tree)
/ \
/ \
0 tree node
/ \
/ \
tree node (t2)
/ \
/ \
(n1) (beginning of subtree)
/ \
/ \
(n2) (t1)
is defined as AUG(n1, n2, t1, t2), an augmentation tree. It's signature
is T.
---
-----
/ \
0x141 / \
/ \
/ \
/ \
0x153 (w)
is defined as WGROUP(w), signature is T.
---
According to your last mail, we also need an operation that takes an
existing tree
(parent node in main tree)
/ \
/ \
0 tree node
/ \
/ \
tree node (t2)
/ \
/ \
(n1) (beginning of subtree)
/ \
/ \
(n2) (t1)
and returns that tree with t2 replaced by t3. We call this function
ATT2(t, t2new).
Summary:
Our algebra SAID uses the sets {T, N, W, S}, and defines the following
functions:
TOP: T -> S
AUG: N x N x T x T -> T
WGROUP: W -> T
ATT2: T x T -> T
(I know that this is excessively formalistic, but I fear that we don't
have much of an alternative).
SAID doesn't define any axioms.
-- part 2
Now let's get more practical. I'll be using your yacc-style language
definition, and assign the semantic value of each expression to $$.
Parameters will be represented by $1 .. $5 (counting operators).
The signature of all evaluated expressions will be T, except for
said_spec, which returns S.
(All operators are part of the set {',', '&', '/', '(', ')', '[', ']',
'#', '<', '>', END}. The emty tree # is probably not related to the '#'
operator (which isn't used anyway.))
Subexpression : Expression
{ $$ = $1 }
| Expression < Subexpression
{ $$ = AUG(0x141, 0x144, $1, $3) }
| Expression < Subexpression < Subexpression
{ $$ = AUG(0x144, 0x14f, $1, AUG(0x141, 0x144, $3, $5)) }
| Expression [ < Subexpression ]
{ $$ = AUG(0x152, 0x144, $1, $3) }
|
{ $$ = # }
;
Expression : MainExp
{ $$ = $1 }
| MainExp , Expression
{ $$ = ATT2($1, $3) }
;
MainExp : [ Subexpression ]
{ $$ = AUG(0x152, 0x14c, $2, #) }
| ( Subexpression )
{ $$ = AUG(0x141, 0x14c, $2, #) }
| Wordgroup
{ $$ = WGROUP($1) }
;
BeforeExp : / Subexpression
{ $$ = $2 }
|
{ $$ = # }
;
NestedBeforeA : BeforeExp
{ $$ = AUG(0x142, 0x14a, BeforeExp, #) }
| [ BeforeExp ]
{ $$ = AUG(0x152, 0x142, BeforeExp, #) }
;
NestedBeforeB : BeforeExp
{ $$ = AUG(0x143, 0x14a, BeforeExp, #) }
| [ BeforeExp ]
{ $$ = AUG(0x152, 0x143, BeforeExp, #) }
;
MoreAfter : >
{ $$ = AUG(0x14b, 0xf900, #, #) }
|
{ $$ = # }
;
said_spec : Subexpression NestedBeforeA MoreAfter
{ $$ = TOP(ATT2($1, ATT2($2, $3)) }
| Subexpression NestedBeforeA NestedBeforeB MoreAfter
{ $$ = TOP(ATT2($1, ATT2($2, ATT2($3, $4))) }
;
I hope that I got it now (I'm not sure whether I got the operator
precedence of (Expression < Subexpression < Subexpression) vs. (Expression
< Subexpression) correctly, though).
Any subtle bug in the Said() implementation will be extremely hard to
find.
llap,
Christoph
