parser: Associativity and precedence of binary operations

[mewmew]

From LR1_conflicts.txt generated by Gocc:

    S105
        symbol: *
            Reduce(39:Expr : Expr BinaryOp Expr <<  >>)
            Shift(70)
        symbol: /
            Reduce(39:Expr : Expr BinaryOp Expr <<  >>)
            Shift(71)
        symbol: !=
            Reduce(39:Expr : Expr BinaryOp Expr <<  >>)
            Shift(76)
        symbol: &&
            Reduce(39:Expr : Expr BinaryOp Expr <<  >>)
            Shift(78)
        symbol: =
            Reduce(39:Expr : Expr BinaryOp Expr <<  >>)
            Shift(79)
        symbol: ==
            Reduce(39:Expr : Expr BinaryOp Expr <<  >>)
            Shift(77)
        symbol: -
            Reduce(39:Expr : Expr BinaryOp Expr <<  >>)
            Shift(68)
        symbol: +
            Reduce(39:Expr : Expr BinaryOp Expr <<  >>)
            Shift(69)
        symbol: <
            Shift(72)
            Reduce(39:Expr : Expr BinaryOp Expr <<  >>)
        symbol: >
            Reduce(39:Expr : Expr BinaryOp Expr <<  >>)
            Shift(73)
        symbol: <=
            Shift(74)
            Reduce(39:Expr : Expr BinaryOp Expr <<  >>)
        symbol: >=
            Reduce(39:Expr : Expr BinaryOp Expr <<  >>)
            Shift(75)

Relevant production rules from the BNF grammar:

Expr
    : int_lit
    | ident
    | ident "[" Expr "]"
    | UnaryOp Expr
    | Expr BinaryOp Expr
    | ident "(" Actuals ")"
    | "(" Expr ")"
;

BinaryOp
    : "+"
    | "-"
    | "*"
    | "/"
    | "<"
    | ">"
    | "<="
    | ">="
    | "!="
    | "=="
    | "&&"
    | "="
;

Example which fails to parse using uparse on input testdata/quiet/parser/p04.c:

u@x1 ~/D/g/s/g/m/uc> uparse testdata/quiet/parser/p04.c 
Parsing "testdata/quiet/parser/p04.c"

…

pos: 49
typ: 4
lit: x

S39 ident(4,x) reduce:21(Locals : empty <<  >>)
S55 ident(4,x) reduce:22(Locals : VarDecl ";" Locals    <<  >>)
S55 ident(4,x) reduce:22(Locals : VarDecl ";" Locals    <<  >>)
S55 ident(4,x) reduce:22(Locals : VarDecl ";" Locals    <<  >>)
S38 ident(4,x) shift:42
pos: 50
typ: 20
lit: -

S42 -(20,-) reduce:36(Expr : ident  <<  >>)
S48 -(20,-) shift:68
pos: 51
typ: 4
lit: y

S68 ident(4,y) reduce:45(BinaryOp : "-" <<  >>)
S67 ident(4,y) shift:42
pos: 52
typ: 20
lit: -

S42 -(20,-) reduce:36(Expr : ident  <<  >>)
S105 -(20,-) shift:68
pos: 53
typ: 4
lit: z

S68 ident(4,z) reduce:45(BinaryOp : "-" <<  >>)
S67 ident(4,z) shift:42
pos: 54
typ: 20
lit: -

S42 -(20,-) reduce:36(Expr : ident  <<  >>)
S105 -(20,-) shift:68
pos: 55
typ: 8
lit: 42

S68 int_lit(8,42) reduce:45(BinaryOp : "-"  <<  >>)
S67 int_lit(8,42) shift:44
pos: 57
typ: 3
lit: ;

S44 ;(3,;) reduce:35(Expr : int_lit <<  >>)
S105 ;(3,;) reduce:39(Expr : Expr BinaryOp Expr <<  >>)
S105 ;(3,;) reduce:39(Expr : Expr BinaryOp Expr <<  >>)
S105 ;(3,;) reduce:39(Expr : Expr BinaryOp Expr <<  >>)
S48 ;(3,;) shift:66
pos: 71
typ: 33
lit: // associativity

2016/03/31 12:08:42 main.parseFile (uparse.go:71): error: Error in S66: comment(33,// associativity
), Pos(offset=71, line=11, column=2), expected one of: ; ident ( int_lit { } return while if - ! 

Still looking for a good solution to this issue.

[mewmew]

Updated by commit 072e46b3b99e8c481a102f9eb8c03195757b1150.

This issue is not yet resolved, however, as is made apparent when trying to parse quiet/lexer/l05.c.

u@x1 ~/D/g/s/g/m/uc> uparse testdata/quiet/lexer/l05.c 
Parsing "testdata/quiet/lexer/l05.c"

…

S26 {(13,{) shift:32
pos: 19
typ: 11
lit: int

S32 int(11,int) shift:9
pos: 23
typ: 4
lit: i

S9 ident(4,i) reduce:11(TypeName : "int"    <<  >>)
S37 ident(4,i) shift:40
pos: 24
typ: 3
lit: ;

S40 ;(3,;) reduce:8(ScalarDecl : TypeName ident <<  >>)
S6 ;(3,;) reduce:6(VarDecl : ScalarDecl <<  >>)
S36 ;(3,;) shift:39
pos: 28
typ: 8
lit: 1

S39 int_lit(8,1) reduce:21(Locals : empty   <<  >>)
S62 int_lit(8,1) reduce:22(Locals : VarDecl ";" Locals  <<  >>)
S38 int_lit(8,1) shift:44
pos: 29
typ: 30
lit: !=

S44 !=(30,!=) reduce:57(Expr1 : int_lit <<  >>)
S61 !=(30,!=) reduce:55(Expr2R : Expr1  <<  >>)
S60 !=(30,!=) reduce:53(Expr5L : Expr2R <<  >>)
S59 !=(30,!=) reduce:50(Expr9L : Expr5L <<  >>)
S58 !=(30,!=) shift:99
pos: 31
typ: 21
lit: !

2016/04/04 17:16:28 main.parseFile (uparse.go:71): error: Error in S99: !(21,!), Pos(offset=31, line=5, column=10), expected one of: ident ( int_lit 

[mewmew]

As of commit 1727d79 the precedence order has been corrected. However, we still need to find a solution for handling left- and right-associativity. The uC language has a single expression which requires right-associativity, namely the assignment expression. For now, finding a solution to this remains an open topic for discussion.

[mewmew]

Below follows an example which demonstrates the current (incorrect) behaviour of parsing assignment expressions, which should be right-associative, but are treated as left-associative like all the other expressions.

Relevant sections of the input file testdata/quiet/parser/p01.c and the output of the uparse command have been included below.

Line 5 of testdata/quiet/parser/p01.c:

x=y=4711;

u@x1 ~/D/g/s/g/m/uc> uparse testdata/quiet/parser/p01.c 
Parsing "testdata/quiet/parser/p01.c"

…

            &ast.ExprStmt{
                X:  &ast.BinaryExpr{
                    X:  &ast.BinaryExpr{
                        X:  &ast.Ident{Name:"x"},
                        Op: 0xd,
                        Y:  &ast.Ident{Name:"y"},
                    },
                    Op: 0xd,
                    Y:  &ast.BasicLit{Kind:0x5, Val:"4711"},
                },
            },

[mewmew]

The parse tree before and after applying commit 2cba9fc, which fixes the right-associativity of assignment expressions.

Before:

u@x1 ~/D/g/s/g/m/uc> uparse testdata/quiet/parser/p01.c 
Parsing "testdata/quiet/parser/p01.c"
=== [ Top-level declaration ] ===

decl type: *ast.FuncDecl

decl: &{0xc8200aa750 0xc8200126c0 0xc82000a560}

&ast.FuncDecl{
    Name: &ast.Ident{Name:"main"},
    Type: &types.Func{
        Params: nil,
        Result: &types.Basic{Kind:2},
    },
    Body: &ast.BlockStmt{
        Stmts: {
            &ast.DeclStmt{
                Decl: &ast.VarDecl{
                    Type: &types.Basic{Kind:2},
                    Name: &ast.Ident{Name:"x"},
                    Val:  nil,
                },
            },
            &ast.DeclStmt{
                Decl: &ast.VarDecl{
                    Type: &types.Basic{Kind:2},
                    Name: &ast.Ident{Name:"y"},
                    Val:  nil,
                },
            },
            &ast.ExprStmt{
                X:  &ast.BinaryExpr{
                    X:  &ast.Ident{Name:"x"},
                    Op: 0xd,
                    Y:  &ast.BasicLit{Kind:0x5, Val:"42"},
                },
            },
            &ast.ExprStmt{
                X:  &ast.BinaryExpr{
                    X:  &ast.BinaryExpr{
                        X:  &ast.Ident{Name:"x"},
                        Op: 0xd,
                        Y:  &ast.Ident{Name:"y"},
                    },
                    Op: 0xd,
                    Y:  &ast.BasicLit{Kind:0x5, Val:"4711"},
                },
            },
        },
    },
}
<*>{<*>{main} <*>{<nil> <*>{Int}} <*>{[<*>{<*>{<*>{Int} <*>{x} <nil>}} <*>{<*>{<*>{Int} <*>{y} <nil>}} <*>{<*>{<*>{x} Assign <*>{IntLit 42}}} <*>{<*>{<*>{<*>{x} Assign <*>{y}} Assign <*>{IntLit 4711}}}]}}

After:

u@x1 ~/D/g/s/g/m/uc> uparse testdata/quiet/parser/p01.c 
Parsing "testdata/quiet/parser/p01.c"
=== [ Top-level declaration ] ===

decl type: *ast.FuncDecl

decl: &{0xc8200a2110 0xc8200a8180 0xc820098120}

&ast.FuncDecl{
    Name: &ast.Ident{Name:"main"},
    Type: &types.Func{
        Params: nil,
        Result: &types.Basic{Kind:2},
    },
    Body: &ast.BlockStmt{
        Stmts: {
            &ast.DeclStmt{
                Decl: &ast.VarDecl{
                    Type: &types.Basic{Kind:2},
                    Name: &ast.Ident{Name:"x"},
                    Val:  nil,
                },
            },
            &ast.DeclStmt{
                Decl: &ast.VarDecl{
                    Type: &types.Basic{Kind:2},
                    Name: &ast.Ident{Name:"y"},
                    Val:  nil,
                },
            },
            &ast.ExprStmt{
                X:  &ast.BinaryExpr{
                    X:  &ast.Ident{Name:"x"},
                    Op: 0xd,
                    Y:  &ast.BasicLit{Kind:0x5, Val:"42"},
                },
            },
            &ast.ExprStmt{
                X:  &ast.BinaryExpr{
                    X:  &ast.Ident{Name:"x"},
                    Op: 0xd,
                    Y:  &ast.BinaryExpr{
                        X:  &ast.Ident{Name:"y"},
                        Op: 0xd,
                        Y:  &ast.BasicLit{Kind:0x5, Val:"4711"},
                    },
                },
            },
        },
    },
}
<*>{<*>{main} <*>{<nil> <*>{Int}} <*>{[<*>{<*>{<*>{Int} <*>{x} <nil>}} <*>{<*>{<*>{Int} <*>{y} <nil>}} <*>{<*>{<*>{x} Assign <*>{IntLit 42}}} <*>{<*>{<*>{x} Assign <*>{<*>{y} Assign <*>{IntLit 4711}}}}]}}