Logical Or

For supporting a logical Or we have to go through the same steps as for the logical not:

• We have to update the grammar (and based on that the parser) and

• define an enum contant for a corresponding expression kind in expr.h

• Support constant folding. In this case by adapting constFoldBinary() in expr.c.

• Adapt functions loadExpr() and condJmpExpr() in expr.c

• Adapt function printExprNode() in expr.c

Compared to before only a few lines of code will be involved. Having restructured now pays off.

Grammar and Parser Update

Like in C the logical Or will be a left associative binary operator. In grammar the production rule for an assigment expression now reads as follows:

That means it is the first left associative binary operator that now occurs in the sequence of production rules for left associative binary operators:

Hence, of all left associative binary operators it has the lowest precedence. And like in C (See Session 8, Page 4) we give it the precedence level 4. So this is the current state of our supported associative binary operators and their precedence levels:

Updating Expression Kinds

In expr.h we define the enum constant EK_LOGICAL_OR with the group of binary operators:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

enum ExprKind
{
    EK_BINARY,
    // binary expression
    // ...
    EK_LOGICAL_OR,
    // ...
    EK_BINARY_END,

    /* ... as before ... */
};

Updating the Parser

In tokenkind.txt change the line with VBAR2 to

1

VBAR2           ||      4       EK_LOGICAL_OR

That's it!

Constant Folding

In expr.c function constFoldBinary() now also has to handle the case that both child node are constant:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

static const struct Expr *
constFoldBinary(const struct Expr *expr)
{
    /* ... as before ...*/

    // handle cases where node can be completely folded
    // NOTE: here we exploit that in our case constants are always unsigned
    uint64_t leftVal = left->primary.literal.uint;
    uint64_t rightVal = right->primary.literal.uint;
    switch (expr->kind) {
        /* ... as before ...*/
        case EK_LOGICAL_OR:
            return newUnsignedLiteralExpr(leftVal || rightVal);
        /* ... as before ...*/
    }
  

That's it!

Adapting loadExpr()

Expression nodes of kind EK_LOGICAL_OR can be handled like any other kind of logical expression node (i.e. EK_LOGICAL_NOT, EK_GREATER, etc.). Hence, the code block in the switch statement just gets another case:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

void
loadExpr(const struct Expr *expr, GenReg dest)
{
    /* ... as before ... */

    switch (expr->kind) {
        /* ... as before ... */

        case EK_LOGICAL_OR:
        case EK_LOGICAL_NOT:
        case EK_GREATER:
        case EK_GREATER_EQUAL:
        case EK_LESS:
        case EK_LESS_EQUAL:
        case EK_EQUAL:
        case EK_NOT_EQUAL:
            {
                /* handle logical expression nodes */
            }
            return;

        /* ... as before ... */
    }
    /* ... as before ... */
}

That's it!

Adapting condJmpExpr()

This is actually the place were some careful thought is required. Like in C the right expression in an Or conjunction should only be evaluated if the left expression was false (Short-circuit evaluation). But it is actually kind of simple. We just have to consider two examples and make sure it works for them:

• One example where the jump should take place if the condition is true, and

• one example where the jump should take place if the condition is false.

From this examples we can derive an implementation by considering flow charts.

Jump if Condition is True

In this case we have to generate for both child nodes a condition jump that takes place if their condition is true. Both condition jumps for the child nodes inherit the “true label” from the parent node:

Jump if Condition is False

Here we have to generate a new “true label”. This “true label” marks the end of the generated code block. If the left child evaluates to true the Or conjunction is false. Hence, for the left child node a conditional jump gets generated that jumps in this case to the end of the generated code block, i.e. it jumps to the generated “true label” if its condition is true. The right child node inherits the “false label” and jumps if its condition is false:

If the jump should take place when the condition is true the “true label” is used for the recursive call of condJmpExpr() for the child nodes. But if the jump should happen if the condition is false we need to generate a new label. This label is used for the left child node as “true label”:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

void
condJmpExpr(const struct Expr *expr, GenReg dest, const char *trueLabel,
            const char *falseLabel)
{
    /* ... as before ... */

    switch (expr->kind) {
        /* ... as before ... */
        case EK_LOGICAL_OR:
            {
                const struct Expr *left = expr->binary.left;
                const struct Expr *right = expr->binary.right;
                if (trueLabel) {
                    condJmpExpr(left, dest, trueLabel, 0);
                    condJmpExpr(right, dest, trueLabel, 0);
                } else {
                    trueLabel = genGetLabel();
                    condJmpExpr(left, dest, trueLabel, 0);
                    condJmpExpr(right, dest, 0, falseLabel);
                    genLabelDef(trueLabel);
                }
            }
            return;
        /* ... as before ... */
    }
}

But that's it! And a logical AND can be supported in the same fashion.

Adapting printExprNode()

Here we have to handle the new expression kind. The hardest part is two choose a good name for nodes representing a logical Or. Here the symbol \(\lor\) is used:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

static void
printExprNode(const struct Expr *expr, size_t indent, FILE *out)
{
    /* ... as before ... */

    if (expr->kind >= EK_BINARY && expr->kind < EK_UNARY_END) {
        switch (expr->kind) {
            /* ... as before ... */
            case EK_LOGICAL_OR:
                fprintf(out, "[ $\\lor$ \n");
                return;
            default:;
        }
    } else if (expr->kind == EK_UNSIGNED_LITERAL) {
        /* ... as before ... */
    } else if (expr->kind == EK_IDENTIFIER) {
        /* ... as before ... */
    }
    /* ... as before ... */
}

Tests

In the test we should check whether the new expression kind can be used in control statements (for testing condJmpExpr() directly) but also in assignments (for testing if loadExpr() makes proper use of condJmpExpr()). And we also should test constant folding. So a simple test would be:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

x = 0 || 1;
$< x;

x = 1 || 0;
$< x;

x = 0 || 0;
$< x;

$> x;
$> y;

z = x || y;
$< z;
z = !(x || y);
$< z;
if (x < y || x > y) {
    $< 42;
} else {
    $< 13;
}

Here the generated logical-or-simple.pdf for the expression trees in the program. And here a test run:

theon$ make logical_or_simple
../xtest_abc logical_or_simple.s < logical_or_simple.abc
../../../ulm-generator/1_ulm_build/stack/ulmas logical_or_simple.s getuint64.s printuint64.s
(echo "#! ../../../ulm-generator/1_ulm_build/stack/ulm"; cat a.out) > logical_or_simple
rm -f a.out
chmod +x logical_or_simple
rm logical_or_simple.s
theon$ echo "0 5" | ./logical_or_simple
1
1
0
1
0
42
theon$ echo "5 5" | ./logical_or_simple
1
1
0
1
0
13
theon$ echo "5 0" | ./logical_or_simple
1
1
0
1
0
42
theon$ echo "0 0" | ./logical_or_simple
1
1
0
0
1
13
theon$ 

Here another test with multiple logical Or conjunctions:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

$> a;
$> b;
$> c;
$> d;

x = a || b || c || d;
$< x;
x = !(a || b || c || d);
$< x;
x = !a || !b || !c || !d;
$< x;

Here the generated logical-or.pdf for the expression trees in the program. And here a test run:

And here a test run:

theon$ make logical_or
../xtest_abc logical_or.s < logical_or.abc
../../../ulm-generator/1_ulm_build/stack/ulmas logical_or.s getuint64.s printuint64.s
(echo "#! ../../../ulm-generator/1_ulm_build/stack/ulm"; cat a.out) > logical_or
rm -f a.out
chmod +x logical_or
theon$ echo "1 2 3 4" | ./logical_or
1
0
0
theon$ echo "0 2 3 4" | ./logical_or
1
0
1
theon$ echo "0 0 3 4" | ./logical_or
1
0
1
theon$ echo "0 0 0 4" | ./logical_or
1
0
1
theon$ echo "0 0 0 0" | ./logical_or
0
1
1
theon$ 

Here some test for short-circuit evaluation for the logical Or:

1
2
3
4
5

$> a;

x = a || (a = a + 1);
$< x;
$< a;

Only when a is zero it gets incremented:

theon$ make logical_or_sce
../xtest_abc logical_or_sce.s < logical_or_sce.abc
../../../ulm-generator/1_ulm_build/stack/ulmas logical_or_sce.s getuint64.s printuint64.s
(echo "#! ../../../ulm-generator/1_ulm_build/stack/ulm"; cat a.out) > logical_or_sce
rm -f a.out
chmod +x logical_or_sce
rm logical_or_sce.s
theon$ echo "1" | ./logical_or_sce
1
1
theon$ echo "0" | ./logical_or_sce
1
1
theon$ 

Here the generated logical-or-sce.pdf for the expression trees in the program.