Parsing flat infix operators?

[oconnor0]

I have a grammar like the following:

expr =
   number : literal
 .operators infix left
   '*' : times
 .operators infix flat
   comparator : relation

comparator =
 '<'  : less
 '<=' : lessequals

I am attempting to codegen the relation with a loop like the following:

struct owl_ref r = ...
struct parsed_expr expr = parsed_expr_get(r);
struct owl_ref left = expr.operand;
struct owl_ref comparator = expr.comparator;
assert(!comparator.empty); // This assertion fails. 
struct owl_ref right = owl_next(expr.operand);
bool first = true;
for (; !right.empty; right = owl_next(left)) {
    if (!first) {
        printf(" && ");
    } else {
        first = false;
    }

    printf("(");
    codegen_expr(left, false);
    const char *operator = "<"; // codegen_comparator(comparator);
    printf(" %s ", operator);
    codegen_expr(right, false);
    printf(")");

    left = right;
    // comparator = owl_next(comparator);
}

My goal is to turn something like: 1 <= 2 < 3 into (1 <= 2) && (2 < 3) but expr.comparator is empty. Is this a limitation in Owl or a misunderstanding on my part?

I can provide a more involved example if you need something to debug, but figured I'd ask first.

[ianh]

I believe these lost slots are the last_operator slots this FIXME comment refers to:

owl/src/x-construct-parse-tree.h

Lines 218 to 224 in ae33e64

	struct construct_node *next_op = last_operator->next;
	// FIXME: Combine last_operator slots together instead of just
	// throwing them away. To do this, we either need a way to link
	// finished nodes together or a way of storing unfinished nodes in
	// slots.
	construct_node_free(s, last_operator);
	last_operator = next_op;

It does seem like this should be implemented properly. I don't have time to dig into it too deeply at the moment, but I can give it a look tomorrow.

[ianh]

BTW, if you want a workaround, you could try making the comparators left-associative (at the cost of potentially doing some extra work when going through the tree). Left-associative operator slots do make their way to the parse tree successfully—it's just the flat associativity that has this bug.

[ianh]

I looked at it today and have a vague plan: normally, separate nodes are created for each occurrence of an operator and for the operands between them. These nodes are then associated into the final tree structure using a precedence parser. For infix flat operators, this means taking the existing nodes and trying to combine them together, which isn't too hard for the operand nodes, but is challenging for the operator nodes. Instead, it seems like it would make more sense to reuse the same operator node, adding to its slots as the parser goes.

[oconnor0]

Sounds good. I ended up hacking a right-associative version of this together just a little bit ago and got it to produce what I want.