disambiguation_by_associativity.md

Disambiguation By Associativity

For the previous grammar:

S: S Plus S
  | A;

terminals

Plus: '+';
A: /a/;

We got an error when running rcomp with the grammar. rcomp does not know how to parse a string by the grammar. For example, consider a string a + a + a, it is not known that it should be parsed as (a + a) + a or a + (a + a).

We can use left or right at a grammar rule to indicate our preference. Here is an example of using left:

S: S Plus S {left}
  | A;

terminals

Plus: '+';
A: /a/;

By passing a + a + a to the parser generated by this grammar, we get the following tree-like output:

Accept
Ok(
  C1(
    SC1 {
      s_1: C1(
        SC1 {
          s_1: A(
            "a",
          ),
          s_3: A(
            "a",
          ),
        },
      ),
      s_3: A(
        "a",
      ),
    },
  ),
)

We can see that the first two a's are closer than the third a, which means the string is parsed as (a + a) + a.

To make a + a + a to be parsed as a + (a + a), we can use right.

S: S Plus S {right}
  | A;

terminals

Plus: '+';
A: /a/;

The output looks like this:

Accept
Ok(
  C1(
    SC1 {
      s_1: A(
        "a",
      ),
      s_3: C1(
        SC1 {
          s_1: A(
            "a",
          ),
          s_3: A(
            "a",
          ),
        },
      ),
    },
  ),
)

➡️ Next: Disambiguation By Priority

📘 Back: Table of contents