Cast/Paren precedence/assoc shift-reduce conflict

[JohanVonElectrum]

I think I have found something weird with precedence.
Following the table C operator precedence I built the expr production rule (and a few other things), but I'm running into a problem with the cast.

.\src\grammar.lalrpop:251:5: 251:14: Local ambiguity detected

The problem arises after having observed the following symbols in the input:
  "(" Identifier
At that point, if the next token is a `")"`, then the parser can proceed in
two different ways.

First, the parser could execute the production at
.\src\grammar.lalrpop:251:5: 251:14, which would consume the top 1 token(s)
from the stack and produce a `Atom`. This might then yield a parse tree like
  "(" Identifier ")"
  │   ├─Atom───┤   │
  │   ├─Term───┤   │
  │   ├─Expr0──┤   │
  │   ├─Expr1──┤   │
  │   ├─Expr2──┤   │
  │   ├─Expr3──┤   │
  │   ├─Expr4──┤   │
  │   ├─Expr5──┤   │
  │   ├─Expr6──┤   │
  │   ├─Expr7──┤   │
  │   ├─Expr8──┤   │
  │   ├─Expr9──┤   │
  │   ├─Expr10─┤   │
  │   ├─Expr11─┤   │
  │   ├─Expr12─┤   │
  │   ├─Expr13─┤   │
  │   ├─Expr14─┤   │
  │   └─Expr───┘   │
  └─Expr───────────┘

Alternatively, the parser could execute the production at
.\src\grammar.lalrpop:158:5: 158:14, which would consume the top 1 token(s)
from the stack and produce a `Type`. This might then yield a parse tree like
  "(" Identifier ")" Expr2
  │   └─Type───┘         │
  └─Expr2────────────────┘

See the LALRPOP manual for advice on making your grammar LR(1).

I understand that there is a shift-reduce conflict going on here because of the “(” Type . “)” Expr and “(” Expr . “)” states can shift to form a cast or reduce to form a paren, because Type and Expr can be Identifier, so the following case occurs:

“(” Identifier . ”)” Expr
“(” Identifier . ”)”

where . marks the current position of the parser.
What happens is that if I understand correctly, assigning higher precedence to the cast than to the paren and making the cast right-associative and the paren left-associative should solve the conflict.
The attached grammar should accomplish that, but the parser fails to generate due to the conflict. The line marked for deletion is the cast line, which when commented out causes everything to compile, and the one marked for addition is the paren line.

use crate::token::{Token, TokenKind, LexicalError};
use crate::ast::AST;

use lalrpop_util::ErrorRecovery;

grammar<'err>(errors: &'err mut Vec<ErrorRecovery<usize, TokenKind, LexicalError>>);

extern {
    type Location = usize;
    type Error = LexicalError;

    enum TokenKind {
        "error" => TokenKind::Error(_),
        // ========
        // Keywords
        // ========
        // Modifiers
        "const" => TokenKind::Const,
        "static" => TokenKind::Static,
        // Types
        "never" => TokenKind::Never,
        "void" => TokenKind::Void,
        "u8" => TokenKind::U8,
        "u16" => TokenKind::U16,
        "u32" => TokenKind::U32,
        "u64" => TokenKind::U64,
        "u128" => TokenKind::U128,
        "i8" => TokenKind::I8,
        "i16" => TokenKind::I16,
        "i32" => TokenKind::I32,
        "i64" => TokenKind::I64,
        "i128" => TokenKind::I128,
        "f32" => TokenKind::F32,
        "f64" => TokenKind::F64,
        // =========
        // Operators
        // =========
        // Assignment
        "=" => TokenKind::Assign,
        "~=" => TokenKind::TildeAssign,
        "+=" => TokenKind::PlusAssign,
        "-=" => TokenKind::MinusAssign,
        "*=" => TokenKind::StarAssign,
        "/=" => TokenKind::SlashAssign,
        "%=" => TokenKind::PercentAssign,
        "^=" => TokenKind::CaretAssign,
        "&=" => TokenKind::BitAndAssign,
        "|=" => TokenKind::BitOrAssign,
        "<<=" => TokenKind::ShlAssign,
        ">>=" => TokenKind::ShrAssign,
        "&&=" => TokenKind::AndAssign,
        "||=" => TokenKind::OrAssign,
        // Prefix
        "~" => TokenKind::Tilde,
        // Arithmetic
        "+" => TokenKind::Plus,
        "-" => TokenKind::Minus,
        "*" => TokenKind::Star,
        "/" => TokenKind::Slash,
        "%" => TokenKind::Percent,
        // Bitwise
        "&" => TokenKind::BitAnd,
        "^" => TokenKind::Caret,
        "|" => TokenKind::BitOr,
        "<<" => TokenKind::Shl,
        ">>" => TokenKind::Shr,
        // Logical
        "&&" => TokenKind::And,
        "||" => TokenKind::Or,
        // Comparison
        "==" => TokenKind::Eq,
        "!=" => TokenKind::Ne,
        "<" => TokenKind::Lt,
        "<=" => TokenKind::Le,
        ">" => TokenKind::Gt,
        ">=" => TokenKind::Ge,
        // Increment/Decrement
        "++" => TokenKind::Increment,
        "--" => TokenKind::Decrement,
        // =====
        // Atoms
        // =====
        // Identifiers
        "ident" => TokenKind::Identifier,
        // Integers
        "rawint" => TokenKind::RawInt,
        "decint" => TokenKind::DecInt,
        "binint" => TokenKind::BinInt,
        "octint" => TokenKind::OctInt,
        "hexint" => TokenKind::HexInt,
        // Floats
        "float" => TokenKind::Float,
        "intfloat" => TokenKind::IntFloat,
        "floatexp" => TokenKind::FloatExp,
        "intexp" => TokenKind::IntExp,
        // Strings
        "str" => TokenKind::String,
        "rstr" => TokenKind::RawString,
        // =======
        // Symbols
        // =======
        // Enclosures
        "(" => TokenKind::LParen,
        ")" => TokenKind::RParen,
        "{" => TokenKind::LBrace,
        "}" => TokenKind::RBrace,
        "[" => TokenKind::LBracket,
        "]" => TokenKind::RBracket,
        // Punctuation
        "." => TokenKind::Dot,
        "," => TokenKind::Comma,
        ":" => TokenKind::Colon,
        ";" => TokenKind::Semicolon,
        "!" => TokenKind::Bang,
        "?" => TokenKind::Question,
        "->" => TokenKind::Arrow,
    }
}

pub Source: AST = {
    TopLevel* => AST::Source(<>),
}

// ======
// Macros
// ======

Comma<T>: Vec<T> = {
    <mut v:(<T> ",")*> <e:T?> => match e {
        None => v,
        Some(e) => {
            v.push(e);
            v
        }
    }
};

// ==========
// Statements
// ==========

TopLevel: AST = {
    FuncDecl,
}

FuncDecl: AST = {
    <ty:Type> <name:Token<"ident">>
    "(" <args:Comma<FuncDeclArg>> ")"
    <body:Expr> => AST::FunctionDeclaration(name, Box::new(ty), args, Box::new(body)),
    ! => { errors.push(<>); AST::Error },
}

FuncDeclArg: (Token, AST) = {
    <ty:Type> <name:Token<"ident">> => (name, ty),
}

Type: AST = {
    Identifier,
    IntType,
    FloatType,
}

Block: AST = {
    "{" <Stmt*> "}" => AST::Block(<>),
}

Stmt: AST = {
    <Expr> ";",
    ! => { errors.push(<>); AST::Error },
}

// ===========
// Expressions
// ===========

FuncCall: AST = {
    <ident:Identifier> "(" <args:Comma<Expr>> ")" => AST::FunctionCall(Box::new(ident), args),
}

Expr: AST = {
    #[precedence(level="0")]
    Term,
    #[precedence(level="1")] #[assoc(side="left")]
    <lhs:Identifier> <op:Token<"++">> => AST::PostfixOp(Box::new(lhs), op),
    <lhs:Identifier> <op:Token<"--">> => AST::PostfixOp(Box::new(lhs), op),
    FuncCall,
    <expr:Expr> "[" <index:Expr> "]" => AST::Index(Box::new(expr), Box::new(index)),
    //member access
    #[precedence(level="2")] #[assoc(side="right")]
    <op:Token<"++">> <rhs:Expr> => AST::PrefixOp(op, Box::new(rhs)),
    <op:Token<"--">> <rhs:Expr> => AST::PrefixOp(op, Box::new(rhs)),
    <op:Token<"+">> <rhs:Expr> => AST::PrefixOp(op, Box::new(rhs)),
    <op:Token<"-">> <rhs:Expr> => AST::PrefixOp(op, Box::new(rhs)),
    <op:Token<"!">> <rhs:Expr> => AST::PrefixOp(op, Box::new(rhs)),
    <op:Token<"~">> <rhs:Expr> => AST::PrefixOp(op, Box::new(rhs)),
-   "(" <ty:Type> ")" <expr:Expr> => AST::Cast(Box::new(ty), Box::new(expr)),
    "*" <rhs:Expr> => AST::Deref(Box::new(rhs)),
    "&" <rhs:Expr> => AST::Ref(Box::new(rhs)),
    #[precedence(level="3")] #[assoc(side="left")]
    <lhs:Expr> <op:Token<"*">> <rhs:Expr> => AST::BinaryOp(Box::new(lhs), op, Box::new(rhs)),
    <lhs:Expr> <op:Token<"/">> <rhs:Expr> => AST::BinaryOp(Box::new(lhs), op, Box::new(rhs)),
    <lhs:Expr> <op:Token<"%">> <rhs:Expr> => AST::BinaryOp(Box::new(lhs), op, Box::new(rhs)),
    #[precedence(level="4")] #[assoc(side="left")]
    <lhs:Expr> <op:Token<"+">> <rhs:Expr> => AST::BinaryOp(Box::new(lhs), op, Box::new(rhs)),
    <lhs:Expr> <op:Token<"-">> <rhs:Expr> => AST::BinaryOp(Box::new(lhs), op, Box::new(rhs)),
    #[precedence(level="5")] #[assoc(side="left")]
    <lhs:Expr> <op:Token<"<<">> <rhs:Expr> => AST::BinaryOp(Box::new(lhs), op, Box::new(rhs)),
    <lhs:Expr> <op:Token<">>">> <rhs:Expr> => AST::BinaryOp(Box::new(lhs), op, Box::new(rhs)),
    #[precedence(level="6")] #[assoc(side="left")]
    <lhs:Expr> <op:Token<"<">> <rhs:Expr> => AST::BinaryOp(Box::new(lhs), op, Box::new(rhs)),
    <lhs:Expr> <op:Token<"<=">> <rhs:Expr> => AST::BinaryOp(Box::new(lhs), op, Box::new(rhs)),
    <lhs:Expr> <op:Token<">">> <rhs:Expr> => AST::BinaryOp(Box::new(lhs), op, Box::new(rhs)),
    <lhs:Expr> <op:Token<">=">> <rhs:Expr> => AST::BinaryOp(Box::new(lhs), op, Box::new(rhs)),
    #[precedence(level="7")] #[assoc(side="left")]
    <lhs:Expr> <op:Token<"==">> <rhs:Expr> => AST::BinaryOp(Box::new(lhs), op, Box::new(rhs)),
    <lhs:Expr> <op:Token<"!=">> <rhs:Expr> => AST::BinaryOp(Box::new(lhs), op, Box::new(rhs)),
    #[precedence(level="8")] #[assoc(side="left")]
    <lhs:Expr> <op:Token<"&">> <rhs:Expr> => AST::BinaryOp(Box::new(lhs), op, Box::new(rhs)),
    #[precedence(level="9")] #[assoc(side="left")]
    <lhs:Expr> <op:Token<"^">> <rhs:Expr> => AST::BinaryOp(Box::new(lhs), op, Box::new(rhs)),
    #[precedence(level="10")] #[assoc(side="left")]
    <lhs:Expr> <op:Token<"|">> <rhs:Expr> => AST::BinaryOp(Box::new(lhs), op, Box::new(rhs)),
    #[precedence(level="11")] #[assoc(side="left")]
    <lhs:Expr> <op:Token<"&&">> <rhs:Expr> => AST::BinaryOp(Box::new(lhs), op, Box::new(rhs)),
    #[precedence(level="12")] #[assoc(side="left")]
    <lhs:Expr> <op:Token<"||">> <rhs:Expr> => AST::BinaryOp(Box::new(lhs), op, Box::new(rhs)),
    #[precedence(level="13")] #[assoc(side="right")]
    <cond:Expr> "?" <then:Expr> ":" <r#else:Expr> => AST::TernaryOp(Box::new(cond), Box::new(then), Box::new(r#else)),
    #[precedence(level="14")] #[assoc(side="right")]
    <lhs:Expr> <op:Token<"=">> <rhs:Expr> => AST::Assignment(Box::new(lhs), op, Box::new(rhs)),
    <lhs:Expr> <op:Token<"+=">> <rhs:Expr> => AST::Assignment(Box::new(lhs), op, Box::new(rhs)),
    <lhs:Expr> <op:Token<"-=">> <rhs:Expr> => AST::Assignment(Box::new(lhs), op, Box::new(rhs)),
    <lhs:Expr> <op:Token<"*=">> <rhs:Expr> => AST::Assignment(Box::new(lhs), op, Box::new(rhs)),
    <lhs:Expr> <op:Token<"/=">> <rhs:Expr> => AST::Assignment(Box::new(lhs), op, Box::new(rhs)),
    <lhs:Expr> <op:Token<"%=">> <rhs:Expr> => AST::Assignment(Box::new(lhs), op, Box::new(rhs)),
    <lhs:Expr> <op:Token<"&=">> <rhs:Expr> => AST::Assignment(Box::new(lhs), op, Box::new(rhs)),
    <lhs:Expr> <op:Token<"^=">> <rhs:Expr> => AST::Assignment(Box::new(lhs), op, Box::new(rhs)),
    <lhs:Expr> <op:Token<"|=">> <rhs:Expr> => AST::Assignment(Box::new(lhs), op, Box::new(rhs)),
    <lhs:Expr> <op:Token<"<<=">> <rhs:Expr> => AST::Assignment(Box::new(lhs), op, Box::new(rhs)),
    <lhs:Expr> <op:Token<">>=">> <rhs:Expr> => AST::Assignment(Box::new(lhs), op, Box::new(rhs)),
}

Term: AST = {
    Atom,
    Block,
+   "(" <Expr> ")",
}

Atom: AST = {
    Identifier,
    Int,
    Float,
    String,
}

// ================
// Token definition
// ================

Token<Kind>: Token = <start: @L> <kind: Kind> <end: @R> => Token::new(kind, start..end);

Identifier: AST = {
    Token<"ident"> => AST::Identifier(<>),
}

Int: AST = {
    Token<"decint"> => AST::Integer(<>),
    Token<"binint"> => AST::Integer(<>),
    Token<"octint"> => AST::Integer(<>),
    Token<"hexint"> => AST::Integer(<>),
}

Float: AST = {
    Token<"float"> => AST::Float(<>),
    Token<"intfloat"> => AST::Float(<>),
    Token<"floatexp"> => AST::Float(<>),
    Token<"intexp"> => AST::Float(<>),
}

String: AST = {
    Token<"str"> => AST::String(<>),
    Token<"rstr"> => AST::String(<>),
}

IntType: AST = {
    Token<"u8"> => AST::IntType(<>),
    Token<"u16"> => AST::IntType(<>),
    Token<"u32"> => AST::IntType(<>),
    Token<"u64"> => AST::IntType(<>),
    Token<"u128"> => AST::IntType(<>),
    Token<"i8"> => AST::IntType(<>),
    Token<"i16"> => AST::IntType(<>),
    Token<"i32"> => AST::IntType(<>),
    Token<"i64"> => AST::IntType(<>),
    Token<"i128"> => AST::IntType(<>),
}

FloatType: AST = {
    Token<"f32"> => AST::FloatType(<>),
    Token<"f64"> => AST::FloatType(<>),
}

[yannham]

I haven't read and understood everything yet, but note that making something right-associative or left-associative when there's only one recurrence of Expr in the expression doesn't have any effect. That is, in

  "(" <ty:Type> ")" <expr:Expr> => AST::Cast(Box::new(ty), Box::new(expr)),

There's only one recursive occurrence of Expr, which is expr. Thus, it will always be replaced by the previous level, and associativity has no effect, whether it's left, right, or no associativity.

Associativity only has effect when there are at least two recursive occurrences of the current rule Expr. There, which one will be substituted for the current level or for the previous level is determined by associativity.

[JohanVonElectrum]

It makes sense, but I think the problem is more related to precedence than to associativity. It was there in the grammar just to clarify that it is right-associative (even if it is implicitly right-associative by the very definition of the production rule) and because I was blindly copying the Cpp operator precedence table.
Anyway, I tried to remove the #[assoc(side=“right”)] part and it still doesn't compile the grammar due to the same problem, so as expected associativity does nothing in this case.

[JohanVonElectrum]

I'm starting to think this is something weird with precedence.
Am I doing something wrong or should I open an issue?

[yannham]

Sorry, I still haven't had the time to look into more closely, but I'm not sure there's a problem with precedence. Precedence in LARLPOP isn't as powerful as precedence annotation in more conventional lexer: it doesn't really enable to prefer shift over reduce in general. Instead, it's a generic rewriting technique that creates one level for each precedence, and substitute the recursive occurrences of each rule Expr with the appropriate level Expr2 or Expr4 for example.

I think here, if you expand the precedence to what you expect it to be with explicit levels, I suspect you'll still have the ambiguity because there's basically two possible "paths" in the parser to reach ( Identifier ), as the error explains: through Atom -> Term -> Expr -> "(" Exp ")" and through "(" Identifier ")" Expr, as a prefix. So the answer is probably that precedence works as expected here, but it is not enough to disambiguate the grammar.

Though I haven't looked in detail, so I might be wrong.

[JohanVonElectrum]

So it is not currently possible to tell the parser generator to prefer to shift rather than reduce for a given production? This is the expected behavior when I think of precedence in parser generators like Bison. Our grammar is almost LR(1), but we need precedence to disambiguate some cases, and this is one of them. Do we have any way to do that with the current state of LALRPOP?

• If yes, how?
• If not, is it planned to support it?

[chanbengz]

AFAIK, the conflict is that at this point

“(” Identifier . ”)”

parser don't know where to reduce for Identifier, Type or Term. And the case

“(” Identifier . ”)” Expr

is not possible because parser needs to look ahead two symbols. Assuming we have a Bison-like reduce/reduce solution:

1. if you prefer shift over reduce, you don't have a rule for "(" Identifier ")"
2. let's assume you have it, you will need to reduce on "(" Identifier ")" Expr rather than "(" Type ")" Expr
3. so, how about just create a new production for CastExpr?

Found some "elegant" solution in C's <cast-expression>

https://cs.wmich.edu/~gupta/teaching/cs4850/sumII06/The%20syntax%20of%20C%20in%20Backus-Naur%20form.htm

[JohanVonElectrum]

It looks like C's "elegant" solution is not a good fit for the definition of "solution".
If LALRPOP does not have reduction/reduction handling, do we have another solution or do we have to switch to another tool?

  ./src\grammar.lalrpop:260:5: 260:14: Local ambiguity detected
    The problem arises after having observed the following symbols in the input:
      "(" Identifier
    At that point, if the next token is a `")"`, then the parser can proceed in
    two different ways.
    First, the parser could execute the production at
    ./src\grammar.lalrpop:260:5: 260:14, which would consume the top 1 token(s)
    from the stack and produce a `PrimaryExpr`. This might then yield a parse tree
    like
      "(" Identifier           ╷ ")"
      │   ├─PrimaryExpr────────┤   │
      │   ├─PostfixExpr────────┤   │
      │   ├─UnaryExpr──────────┤   │
      │   ├─CastExpr───────────┤   │
      │   ├─MultiplicativeExpr─┤   │
      │   ├─AdditiveExpr───────┤   │
      │   ├─ShiftExpr──────────┤   │
      │   ├─RelationalExpr─────┤   │
      │   ├─EqualityExpr───────┤   │
      │   ├─BitwiseAndExpr─────┤   │
      │   ├─BitwiseXorExpr─────┤   │
      │   ├─BitwiseOrExpr──────┤   │
      │   ├─LogicalAndExpr─────┤   │
      │   ├─LogicalOrExpr──────┤   │
      │   ├─ConditionalExpr────┤   │
      │   ├─AssignmentExpr─────┤   │
      │   └─Expr───────────────┘   │
      └─PrimaryExpr────────────────┘
    Alternatively, the parser could execute the production at
    ./src\grammar.lalrpop:158:5: 158:14, which would consume the top 1 token(s)
    from the stack and produce a `Type`. This might then yield a parse tree like
      "(" Identifier ")" CastExpr
      │   └─Type───┘            │
      └─CastExpr────────────────┘
    See the LALRPOP manual for advice on making your grammar LR(1).

[chanbengz]

do we have to switch to another tool?

Perhaps you can try pest but I'm not familiar with it. RustPython is implemented in LALRPOP and why can't C be?

Sorry that I can't help much.

[yannham]

The usual work-around for those cases it to make sure that only one derivation can ever produce ( Identifier ), and use that derivation in the appropriate places. In practice, that is a rule ParenthesizedIdentifier.

This incurs quite a bit of boilerplate then because you need to have:

• two variants of Type, one that include Identifier and the other that doesn't
• two versions of Atom, one with and one without Identifier
• two versions of Expr, where the corresponding Atom rule is used. However, the recursive occurrences of expressions should use the rule that allow Identifier
• Use the identifier-free Expr rule for parenthesis: "(" ExprNoIdent ")"
• Artificially include the parenthesized identifier rule as well in Atom: ParenthsizedIdentifier
• For the type cast rule, duplicate it into two different rules, one that use the identifier-free type, and one that artificially use the ParenthesizedIdentifier

It's a bit blunt as a description, but the idea is that when the parser sees "(" Identifier ")", there's actually one unique rule that can be applied. Then this rule can be re-used in other rules, but first it needs to produce a parenthesized identifier.

It is annoying to do because you then have some kind of "dangling-else" problem: you need two variants of many rules, to make sure to exclude the other ways of deriving "(" Identifier ")". Usually LALRPOP macros can make that nicer, and it's not too bad. But in your case precedence annotations won't work so well with the two variants of Expr, as you'll need somehow two mutually recursive definitions for Expr and ExprNoIdent.

So all in all I believe it's possible (in a quite generic way), but:

• you'll need to butcher your grammar a bit by duplicating rules. You can avoid duplicating the actual content of rules by using LALRPOP macros
• you'll need to carefully re-introduce parenthesized identifier in an ad-hoc way where they can be used: as parenthesized expressions or as type casts.
• I fear you'll have to abandon the usage of precedence annotations in Expr, because it won't be powerful enough to handle the Expr and ExprNoIdent intricacies, which means being back to writing explicit levels like you did with @chanbengz's suggestions above.

[chanbengz]

It's a very detailed explanation. I think we're all clear now.

But I'm kinda worried that how to interpret "(" Identifier ")" in AST as it's Term in Expr while it's Type in CastExpr.

[yannham]

In this example everything is an AST, if I'm not mistaken, so ParenthesizedIdentifier would be as well. In any case it's no different than the Identifier rule itself. So it should have the same return type and be used the same way (whether you need to wrap it as a Term::Identifier or Type::Identifier for example when including Identifier in Type or Expr.