Re: New package dependency field format

[Goswin von Brederlow <brederlo@informatik.uni-tuebingen.de>]

Hi,

two things mentioned on irc you told me to mail:

Your grammar read:
==================================================
/* Whitespace is insignificate between tokens */

<expression>:
	'(' <expression> ')' |
	'!' <expression> |
	<predicate> (<operator> <predicate>)*;
<operator>:
	',' | '|';
<predicate>:
	<arch> |
	<feature> |
	<package>;
==================================================

That should be:

<expression>:
    <and-expression>                            $$ = $1

<and-expression>:
    <or-expression>                             $$ = $1
  | <and-expression> ',' <or-expression>        $$ = and_node($1, $3)

<or-expression>:
    <not-expression>                            $$ = $1
  | <or-expression> '|' <not-expression>        $$ = or_node($1, $3)

<not-expression>:
    <primary-expression>                        $$ = $1
  | '!' <primary-expression>                    $$ = not_node($2)

<primary-expression>:
    '(' <expression> ')'                        $$ = $2
  | <predicate>                                 $$ = $1

Tabified is the annotation to build a parse tree for the grammar,
which is the second thing I mentioned. Building a parse tree is dead
simple. Rules with only one element usually just get passed on as they
are, unless you need to change them in some way to make the type fit.
More complex rules create a node containing the operator/type as key
and the arguments as children.

Lets have a look at your examples:

> <arch>:
> 	'[' '!'? <arch-name> (',' <arch-name>)* ']';

[alpha, sparce]
[!i386, hurd-i386]

arch_node(2, "alpha", "sparc")
arch_node(2, not_node("i386"), "hurd-i386")

> <feature>:
> 	'{' <arch-feature> (';' <arch-feature>)* '};

{i386: mmx, sse}
{i386: mmx, !sse; sparc: 64-bit-kernel}

feature_node(1, arch_feature_node("i386", 2, "mmx", "sse"))
feature_node(2, arch_feature_node("i386", 2, "mmx", not_node("sse")),
                arch_feature_node("sparc", 1, "64-bit-kernel"))

> <version>:
> 	'(' <verop> <version-string> (',' <verop> <version-string>)* ')';

(= 1.2.3)
(>= 1.2.0, <= 1.2.3)
(>= 1.2, <= 1.5, != 1.3.7)

version_node(1, eq_node("1.2.3"))
version_node(2, ge_node("1.2.0), le_node("1.2.3"))
version_node(3, ge_node("1.2"), le_node("1.5"), not_node(eq_node("1.3.7")))


The above examples would be with tress with varibale number of
children to represent the "*" in your grammar.My sniplet didn't have
any of those having deeper trees but allways one or to children.

Lets add some full examples showing the "!", "|" and ",":
(First infix, then rpn than tree)

------------------------------------------------------------
A, B

A B ,

  ,
 / \
A   B
------------------------------------------------------------
A | B

A B |

  |
 / \
A   B
------------------------------------------------------------
! A

A !

  !
  |
  A
------------------------------------------------------------
A , B | C, !D, !(E, F | !G | ( H, !I))

A B C | , D ! , E F G ! | H I ! , | , ! ,

              ,
             / \
            /   !
           /     \
          ,       ,
         / \     / \
        ,   !   E   |
       / \   \     / \
      A   |   D   F   |
         / \         / \
        B   C       /   ,
                   /   / \
                  !   H   !
                   \       \
                    G       I
------------------------------------------------------------
Last example but with * rules: (token rows and structure rows alternate)
,
+-+---+-+
A |   ! !
  +-+ | |
  B C D ,
        +-+
        D |
          +-+-+
          G ! ,
            | +-+
            G H !
                |
                I
------------------------------------------------------------

To convert the tree to infix you do in-order traversal:
1. if parent has higher priority ('ident' > '!' > ',' > '|') print "("
2. print left child
3. print yourself
4. print right child
5. if parent has higher priority ('ident' > '!' > ',' > '|') print ")"

Steps 2 and 4 are skiped if child not present.
Instead of checking the parent in 1/5 the children can be checkd and
enclosed in () instead. Depends on the representation of the tree.

To convert to rpn you do post-order traversal:
1. print left child
2. print right child
3. print yourself


As a sidenote, rpn and tree can be given at the same time if the
operator in the rp form carry 1/2 pointers to what they refer to:

A , B | C

  ,
 / \
A   |
   / \
  B   C

A B C | ,
  ^ ^ | |
  |_|_| |
^     ^ |
|_____|_|



And last, to evaluate a tree:
- Any leaf is true or false.
- An inner node is true if the childrens bools combined with the
  operator ('!', '|' or ',') is true.

You can go bottom-up or top-down. The later has the advantage that you
can do lazy evaluation of '|' and ',' for the cost of recursion.

MfG
        Goswin