<p>This language is implemented in Rust using a lot of enums for things like expressions. Some of the planned validation rules involve checking how parenthesis are used -- where they're needed and are not, for example. This is currently done with an <code>Expr::Parenthesized</code> node. However, I want to be able to <code>match</code> over an Expr type, only allowing the values producible at that level in the grammar. For example, with this simple grammar:</p>
<pre><code>expr = multiplicative;
multiplicative = additive | multiplicative &quot;*&quot; additive;
additive = primary | additive &quot;+&quot; primary;
primary = NUMBER | &quot;(&quot; expr &quot;)&quot;;
</code></pre>
<p>With the following AST:</p>
<pre><code>enum Expr {
    Mul(Box&lt;Expr&gt;, Box&lt;Expr&gt;),
    Add(Box&lt;Expr&gt;, Box&lt;Expr&gt;),
    Paren(Box&lt;Expr&gt;),
    Number(i32),
}
</code></pre>
<p>Let's say I <code>match</code> over something of type <code>Expr</code>:</p>
<pre><code>match my_expr {
    Expr::Add(lhs, rhs) =&gt; {
        // lhs and rhs are of type 'Expr'
        // however, Expr::Mul is not possible for either side without being
        // ...wrapped in Expr::Paren. Meaning, if we wanted to match over this,
        // ...we'd have an extra unreachable case:
        match lhs {
            Expr::Mul(_, _) =&gt; unreachable!(),
            _ =&gt; todo!(),
        }
        // This is not very intuitive and will not cause compiler errors if you add
        // more new operators.
    },
}
</code></pre>
<p>The current solution I'm using is the <a href="https://crates.io/crates/subenum" rel="nofollow noreferrer"><code>subenum</code> crate</a>. This results in an <code>Expr</code> enum looking like the following, with a sub-enum for every variant:</p>
<pre><code>#[subenum(Multiplicative, Additive, Primary)]
enum Expr {
    #[subenum(Multiplicative)]
    Mul(Box&lt;Multiplicative&gt;, Box&lt;Additive&gt;),
    #[subenum(Multiplicative, Additive)] // all possible rules that can produce Add
    Add(Box&lt;Additive&gt;, Box&lt;Primary&gt;),
    #[subenum(Multiplicative, Additive, Primary)]
    Paren(Box&lt;Expr&gt;), // lifts back to Expr
    #[subenum(Multiplicative, Additive, Primary)]
    Number(i32),
}
</code></pre>
<p>Is there some other way to represent an AST that avoids this chaos (additionally, many <code>.into()</code> and <code>.try_into()</code> calls exist to promote between types and it's very cluttered)</p>
<p>My compiler is still WIP and is just a parser at this time, but you can <a href="https://github.com/zirco-lang/zrc/blob/main/compiler/zrc_parser/src/parse_tree/expr.rs#L12-L293" rel="nofollow noreferrer">see the real chaos in the zrc_parser <code>Expr</code> enum...</a></p>

<implementation><parsing><abstract-syntax-tree>
Representing parenthesis in an AST
CC BY-SA 4.0
2023-05-17T19:05:55.967Z
This looks like a possible [XY problem](https://en.wikipedia.org/wiki/XY_problem) to me. Why is it desirable to encode this information in the type system in the first place?
James Martin
CC BY-SA 4.0
2023-05-17T19:12:11.367Z
You might also be interested in [trees that grow](https://www.jucs.org/jucs_23_1/trees_that_grow/jucs_23_01_0042_0062_najd.pdf), which was invented to deal with the many intermediate variants of AST. However, that's just another approach compared to `subenum`; it doesn't eliminate the complexity of having many, many AST variants.
James Martin
CC BY-SA 4.0
2023-05-17T19:23:32.393Z
@JamesMartin One of the validations in my compiler is planned to be for logical expressions containing multiple different operator types with no parenthesis, e.g. `a && b || c`. Unlike C, the grammar places && and || on the same precedence, and using a mix of them w/o parens is an error.
0xLogN
<p>If possible, I'd recommend validating the presence of required paretheses within the grammar definition, and storing the parenthesized expression in the AST without a specific wrapper. The key benefit of AST over CST is being able to abstract away grammatic details in favor of better generalization.</p>
<p>If what you meant was that in some cases parenthesized expressions are to be treated differently from their contents, create AST-level wrapper for those specific cases. Otherwise, if having parentheses or not generally make no difference except for some specific occasional checks, you could just store a flag <code>is_parenthesized</code> within the <code>Expr</code>. (This would require making <code>Expr</code> a struct, consisting of an enum which has previously been <code>Expr</code> and the common attributes)</p>

CC BY-SA 4.0
2023-05-17T18:50:59.180Z
2023-05-17T18:50:59.180Z
abel1502
CC BY-SA 4.0
2023-05-17T19:21:00.237Z
To be specific, the validation is that the compiler should fail on "a && b || c" without explicit parenthesis. My language requires them there instead of binding the && and || operators on different levels.
0xLogN
CC BY-SA 4.0
2023-05-17T19:31:38.470Z
@0xLogN I actually have the same thing in my language too. (I believe it's called 'operator precedence partial ordering'). And [here](https://github.com/abel1502/bondrewd/blob/master/grammar/bondrewd.gram#L211-L222)'s the grammar behind it, no further checks needed. (The spec format is pegen-based, feel free to ask if something is unclear). The corresponding generated PEG parser can be found [here](https://github.com/abel1502/bondrewd/blob/master/src/parse/parser.gen.cpp)
abel1502
CC BY-SA 4.0
2023-05-17T19:55:52.507Z
I'll look into it, would just storing like the depth of parenthesis as a usize (C equiv is size_t) or something within an Expr struct work?
0xLogN
CC BY-SA 4.0
2023-05-17T20:00:57.997Z
@0xLogN for the case in question even that is unnecessary (as I've said, it can be done just through the structure of the grammar). Otherwise, it depends on what else you want to use it for. In general, this would work, but most often you could get away with just a boolean flag, even
abel1502
CC BY-SA 4.0
2023-05-17T20:05:57.857Z
I understand it's possible in the grammar, but doing it in a separate validation phase allows me to provide a better error report than what LALRPOP can do for me, no?
0xLogN
CC BY-SA 4.0
2023-05-17T20:11:31.830Z
@0xLogN Oh, I haven't considered this. I myself use a cusom PEG parser generator, and have little experience with any LR-based ones. So then a flag is probably your best bet
abel1502
<p>Your grammar and AST look fine, so the trouble is with your matching logic. If you are visiting an addition expression, then just recursively visit both the operands.</p>
<p>To explain: your addition visitor should not, itself, look into the contents of the operands. Instead, the next recursive step is what investigates each operand independently. In pseudocode:</p>
<pre><code>visitAddition:
  left = visit(lhs)
  right = visit(rhs)
  # return something that contains/uses left and right
</code></pre>

CC BY-SA 4.0
2023-05-17T18:41:55.703Z
2023-05-17T18:41:55.703Z
chrisaycock
CC BY-SA 4.0
2023-05-17T19:19:51.573Z
I'm aware the visitor shouldn't look into the contents, but the validator needs to.
0xLogN
<p>One solution is to simply have two types: one with parens and one without, and then add a method to convert one to the other. I’ll write this in Swift rather than Rust as that’s what I’m familiar with, but the concept should be the same.</p>
<pre><code>indirect enum UnparenthesizedExpr {
  case add(UnparenthesizedExpr, UnparenthesizedExpr)
  case multiply(UnparenthesizedExpr, UnparenthesizedExpr)
  case number(Int)
}

indirect enum Expression {
  case add(Expression, Expression)
  case multiply(Expression, Expression)
  case parenthesized(Expression)
  case number(Int)

  func withoutParens() -&gt; UnparenthesizedExpr {
    switch self {
    case .add(let left, let right):
      return .add(left.withoutParens(), right.withoutParens())
    case .multiply(let left, let right):
      return .multiply(left.withoutParens(), right.withoutParens())
    case .parenthesized(let inner):
      return inner.withoutParens()
    case .number(let value):
      return .number(value)
    }
  }
}
</code></pre>
<p>In fact, once this exists, I wouldn’t pass around <code>Expression</code> at all, just <code>UnparenthesizedExpr</code>. <code>Expression</code> might need to exist for some intermediate stage, but I would try to eliminate it as much as possible.</p>

CC BY-SA 4.0
2023-05-17T18:47:21.157Z
2023-05-17T18:47:21.157Z
Bbrk24
CC BY-SA 4.0
2023-05-17T19:19:17.527Z
This doesn't actually resolve the issue of having the node in the AST in that manner.
0xLogN
# Representing parenthesis in an AST
Posted by: username_0 on 2023-05-17
This language is implemented in Rust using a lot of enums for things like expressions. Some of the planned validation rules involve checking how parenthesis are used -- where they're needed and are not, for example. This is currently done with an Expr::Parenthesized node. However, I want to be able to match over an Expr type, only allowing the values producible at that level in the grammar. For example, with this simple grammar:
expr = multiplicative;
multiplicative = additive | multiplicative "*" additive;
additive = primary | additive "+" primary;
primary = NUMBER | "(" expr ")";

With the following AST:
enum Expr {
    Mul(Box, Box),
    Add(Box, Box),
    Paren(Box),
    Number(i32),
}

Let's say I match over something of type Expr:
match my_expr {
    Expr::Add(lhs, rhs) => {
        // lhs and rhs are of type 'Expr'
        // however, Expr::Mul is not possible for either side without being
        // ...wrapped in Expr::Paren. Meaning, if we wanted to match over this,
        // ...we'd have an extra unreachable case:
        match lhs {
            Expr::Mul(_, _) => unreachable!(),
            _ => todo!(),
        }
        // This is not very intuitive and will not cause compiler errors if you add
        // more new operators.
    },
}

The current solution I'm using is the subenum crate. This results in an Expr enum looking like the following, with a sub-enum for every variant:
#[subenum(Multiplicative, Additive, Primary)]
enum Expr {
    #[subenum(Multiplicative)]
    Mul(Box, Box),
    #[subenum(Multiplicative, Additive)] // all possible rules that can produce Add
    Add(Box, Box),
    #[subenum(Multiplicative, Additive, Primary)]
    Paren(Box), // lifts back to Expr
    #[subenum(Multiplicative, Additive, Primary)]
    Number(i32),
}

Is there some other way to represent an AST that avoids this chaos (additionally, many .into() and .try_into() calls exist to promote between types and it's very cluttered)
My compiler is still WIP and is just a parser at this time, but you can see the real chaos in the zrc_parser Expr enum...
**Tags:** implementation parsing abstract-syntax-tree
> **Comments:**
> **username_1**: This looks like a possible [XY problem](https://en.wikipedia.org/wiki/XY_problem) to me. Why is it desirable to encode this information in the type system in the first place?  
> **username_1**: You might also be interested in [trees that grow](https://www.jucs.org/jucs_23_1/trees_that_grow/jucs_23_01_0042_0062_najd.pdf), which was invented to deal with the many intermediate variants of AST. However, that's just another approach compared to `subenum`; it doesn't eliminate the complexity of having many, many AST variants.  
> **username_0**: @JamesMartin One of the validations in my compiler is planned to be for logical expressions containing multiple different operator types with no parenthesis, e.g. `a && b || c`. Unlike C, the grammar places && and || on the same precedence, and using a mix of them w/o parens is an error.  
---
## 3 answers
### Answer by username_2 on 2023-05-17. Score: 6
If possible, I'd recommend validating the presence of required paretheses within the grammar definition, and storing the parenthesized expression in the AST without a specific wrapper. The key benefit of AST over CST is being able to abstract away grammatic details in favor of better generalization.

If what you meant was that in some cases parenthesized expressions are to be treated differently from their contents, create AST-level wrapper for those specific cases. Otherwise, if having parentheses or not generally make no difference except for some specific occasional checks, you could just store a flag `is_parenthesized` within the `Expr`. (This would require making `Expr` a struct, consisting of an enum which has previously been `Expr` and the common attributes)
> **Comments:**
> **username_0** (2023-05-17): To be specific, the validation is that the compiler should fail on "a && b || c" without explicit parenthesis. My language requires them there instead of binding the && and || operators on different levels.  
> **username_2** (2023-05-17): @0xLogN I actually have the same thing in my language too. (I believe it's called 'operator precedence partial ordering'). And [here](https://github.com/abel1502/bondrewd/blob/master/grammar/bondrewd.gram#L211-L222)'s the grammar behind it, no further checks needed. (The spec format is pegen-based, feel free to ask if something is unclear). The corresponding generated PEG parser can be found [here](https://github.com/abel1502/bondrewd/blob/master/src/parse/parser.gen.cpp)  
> **username_0** (2023-05-17): I'll look into it, would just storing like the depth of parenthesis as a usize (C equiv is size_t) or something within an Expr struct work?  
> **username_2** (2023-05-17): @0xLogN for the case in question even that is unnecessary (as I've said, it can be done just through the structure of the grammar). Otherwise, it depends on what else you want to use it for. In general, this would work, but most often you could get away with just a boolean flag, even  
> **username_0** (2023-05-17): I understand it's possible in the grammar, but doing it in a separate validation phase allows me to provide a better error report than what LALRPOP can do for me, no?  
> **username_2** (2023-05-17): @0xLogN Oh, I haven't considered this. I myself use a cusom PEG parser generator, and have little experience with any LR-based ones. So then a flag is probably your best bet  
---
### Answer by username_3 on 2023-05-17. Score: 2
Your grammar and AST look fine, so the trouble is with your matching logic. If you are visiting an addition expression, then just recursively visit both the operands.
To explain: your addition visitor should not, itself, look into the contents of the operands. Instead, the next recursive step is what investigates each operand independently. In pseudocode:
visitAddition:
  left = visit(lhs)
  right = visit(rhs)
  # return something that contains/uses left and right
> **Comments:**
> **username_0** (2023-05-17): I'm aware the visitor shouldn't look into the contents, but the validator needs to.  
---
### Answer by username_4 on 2023-05-17. Score: -1
One solution is to simply have two types: one with parens and one without, and then add a method to convert one to the other. I’ll write this in Swift rather than Rust as that’s what I’m familiar with, but the concept should be the same.
indirect enum UnparenthesizedExpr {
  case add(UnparenthesizedExpr, UnparenthesizedExpr)
  case multiply(UnparenthesizedExpr, UnparenthesizedExpr)
  case number(Int)
}

indirect enum Expression {
  case add(Expression, Expression)
  case multiply(Expression, Expression)
  case parenthesized(Expression)
  case number(Int)

  func withoutParens() -> UnparenthesizedExpr {
    switch self {
    case .add(let left, let right):
      return .add(left.withoutParens(), right.withoutParens())
    case .multiply(let left, let right):
      return .multiply(left.withoutParens(), right.withoutParens())
    case .parenthesized(let inner):
      return inner.withoutParens()
    case .number(let value):
      return .number(value)
    }
  }
}

In fact, once this exists, I wouldn’t pass around Expression at all, just UnparenthesizedExpr. Expression might need to exist for some intermediate stage, but I would try to eliminate it as much as possible.
> **Comments:**
> **username_0** (2023-05-17): This doesn't actually resolve the issue of having the node in the AST in that manner.  
---
