CPW Part 16 (A): Equality and Relational Expressions in the Grammar

The new operators "==“, ”!=“, ”>“, ”>=“, ”<“ and ”<=" should habe the same meaning, associativity and precedence as in C (See Session 8, Page 4). Below the corresponding grammar. Note that some of the production rules were simply renamed (e.g. expr into additive-expr and term into multiplicative-expr). But essentially just two new production rules, i.e. equality-expr and relational-expr, were added.

\[\begin{array}{rcl}\text{input-sequence} & = & \{\; $> \; \text{assignment-expr}\; \texttt{;}\; |\; $< \; \text{assignment-expr}\; \texttt{;}\; |\; \text{expr-statement}\; \}\; \\\text{expr-statement} & = & \text{assignment-expr}\; \texttt{;}\; \\\text{assignment-expr} & = & \text{equality-expr}\; [\; \texttt{=}\; \text{assignment-expr}\; ]\; \\\text{equality-expr} & = & \text{relational-expr}\; \{\; (\; \texttt{"=="}\; |\; \texttt{"!="}\; )\; \text{relational-expr} \} \\\text{relational-expr} & = & \text{additive-expr}\; \{\; (\; \texttt{">"}\; |\; \texttt{"<"}\; |\; \texttt{">="}\; |\; \texttt{"<="}\; )\; \text{additive-expr} \} \\\text{additive-expr} & = & \text{multiplicative-expr}\; \{\; (\; \texttt{"+"}\; |\; \texttt{"-"}\; )\; \text{multiplicative-expr} \} \\\text{multiplicative-expr} & = & \text{unary-expr}\; \{\; (\; \texttt{"*"}\; |\; \texttt{"/"}\; |\; \texttt{"%"} )\; \text{unary-expr} \} \\\text{unary-expr} & = & \text{primary-expr}\; |\; (\; \texttt{"+"}\; |\; \texttt{"-"}\;)\; \text{unary-expr} \\\text{primary-expr} & = & \text{identifier}\; \\ & | & \text{dec-literal}\; \\ & | & \text{hex-literal}\; \\ & | & \text{oct-literal}\; \\ & | & \texttt{"("}\; \text{assignment-expr}\; \texttt{")"}\; \\\end{array}\]

Exercise

In enum ExprKind add constants for the new binary operators:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
enum ExprKind
{
    EK_BINARY,
    // binary expression
    EK_ADD = EK_BINARY,
    EK_ASSIGN,
    EK_EQUAL,
    EK_NOT_EQUAL,
    EK_GREATER,
    EK_GREATER_EQUAL,
    EK_LESS,
    EK_LESS_EQUAL,
    EK_SUB,
    EK_MUL,
    EK_DIV,
    EK_MOD,
    EK_BINARY_END,

    // ...
};

Update the parser for the new grammar:

  • Rename parse functions to reflect the naming used in the grammar. E.g rename parseExpr() into parseAdditiveExpr(), etc. This is annoying but when a project grows such modifications are part of the game.

  • Add parse the functions parseEqualityExpr() and parseRelationalExpr() for the corresponding production rules.

What Should Work Now

After this update make sure that you can build xtest_abc:

theon$ make
gcc -o xgen_tokenkind xgen_tokenkind.c -lm
./xgen_tokenkind tokenkind.txt gen_tokenkind.h gen_strtokenkind.c
gcc -c -Wall -Wcast-qual  -MT xtest_abc.o -MMD -MP -MF xtest_abc.c.d xtest_abc.c
gcc -c -Wall -Wcast-qual  -MT expr.o -MMD -MP -MF expr.c.d expr.c
gcc -c -Wall -Wcast-qual  -MT finalize.o -MMD -MP -MF finalize.c.d finalize.c
gcc -c -Wall -Wcast-qual  -MT gen.o -MMD -MP -MF gen.c.d gen.c
gcc -c -Wall -Wcast-qual  -MT lexer.o -MMD -MP -MF lexer.c.d lexer.c
gcc -c -Wall -Wcast-qual  -MT memregion.o -MMD -MP -MF memregion.c.d memregion.c
gcc -c -Wall -Wcast-qual  -MT parser.o -MMD -MP -MF parser.c.d parser.c
gcc -c -Wall -Wcast-qual  -MT str.o -MMD -MP -MF str.c.d str.c
gcc -c -Wall -Wcast-qual  -MT sym.o -MMD -MP -MF sym.c.d sym.c
gcc -c -Wall -Wcast-qual  -MT tokenkind.o -MMD -MP -MF tokenkind.c.d tokenkind.c
gcc -c -Wall -Wcast-qual  -MT ustr.o -MMD -MP -MF ustr.c.d ustr.c
gcc -o xtest_abc xtest_abc.o expr.o finalize.o gen.o lexer.o memregion.o parser.o str.o sym.o tokenkind.o ustr.o -lm
gcc -c -Wall -Wcast-qual  -MT xtest_cond.o -MMD -MP -MF xtest_cond.c.d xtest_cond.c
gcc -o xtest_cond xtest_cond.o expr.o finalize.o gen.o lexer.o memregion.o parser.o str.o sym.o tokenkind.o ustr.o -lm
gcc -c -Wall -Wcast-qual  -MT xtest_expr.o -MMD -MP -MF xtest_expr.c.d xtest_expr.c
gcc -o xtest_expr xtest_expr.o expr.o finalize.o gen.o lexer.o memregion.o parser.o str.o sym.o tokenkind.o ustr.o -lm
gcc -c -Wall -Wcast-qual  -MT xtest_finalize.o -MMD -MP -MF xtest_finalize.c.d xtest_finalize.c
gcc -o xtest_finalize xtest_finalize.o expr.o finalize.o gen.o lexer.o memregion.o parser.o str.o sym.o tokenkind.o ustr.o -lm
gcc -c -Wall -Wcast-qual  -MT xtest_gen.o -MMD -MP -MF xtest_gen.c.d xtest_gen.c
gcc -o xtest_gen xtest_gen.o expr.o finalize.o gen.o lexer.o memregion.o parser.o str.o sym.o tokenkind.o ustr.o -lm
gcc -c -Wall -Wcast-qual  -MT xtest_lexer_sanity.o -MMD -MP -MF xtest_lexer_sanity.c.d xtest_lexer_sanity.c
gcc -o xtest_lexer_sanity xtest_lexer_sanity.o expr.o finalize.o gen.o lexer.o memregion.o parser.o str.o sym.o tokenkind.o ustr.o -lm
gcc -c -Wall -Wcast-qual  -MT xtest_lexer.o -MMD -MP -MF xtest_lexer.c.d xtest_lexer.c
gcc -o xtest_lexer xtest_lexer.o expr.o finalize.o gen.o lexer.o memregion.o parser.o str.o sym.o tokenkind.o ustr.o -lm
gcc -c -Wall -Wcast-qual  -MT xtest_memregion.o -MMD -MP -MF xtest_memregion.c.d xtest_memregion.c
gcc -o xtest_memregion xtest_memregion.o expr.o finalize.o gen.o lexer.o memregion.o parser.o str.o sym.o tokenkind.o ustr.o -lm
gcc -c -Wall -Wcast-qual  -MT xtest_sym.o -MMD -MP -MF xtest_sym.c.d xtest_sym.c
gcc -o xtest_sym xtest_sym.o expr.o finalize.o gen.o lexer.o memregion.o parser.o str.o sym.o tokenkind.o ustr.o -lm
gcc -c -Wall -Wcast-qual  -MT xtest_ustr.o -MMD -MP -MF xtest_ustr.c.d xtest_ustr.c
gcc -o xtest_ustr xtest_ustr.o expr.o finalize.o gen.o lexer.o memregion.o parser.o str.o sym.o tokenkind.o ustr.o -lm
gcc -c -Wall -Wcast-qual  -MT xgen_tokenkind.o -MMD -MP -MF xgen_tokenkind.c.d xgen_tokenkind.c
theon$ 

Test the compiler with expressions like in this example (of course you can extend this):

session24/git1/abc/test.abc 
1
2
3
4
5
6
x == y;
x != y;
x <= y;
x >= y;
x < y;
x > y;

If you also want to update const folding use

session24/git1/abc/test_cf.abc 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
x == y;
x != y;
x <= y;
x >= y;
x < y;
x > y;
3 == 4;
3 != 4;
3 <= 4;
3 >= 4;
3 < 4;
3 > 4;

Expected Error

You will get an assertion failure from the code generator (i.e. in loadExpr()) but you should not get a syntax error:

theon$ ./xtest_abc < test.abc
loadExpr: internal error. kind = 2
warning: register 6 not released
        ldzwq 0x0, %2
theon$ 

So in the next step you should

  • adapt the implementation of loadExpr().

  • handle in printExprNode() the new expression kinds.

  • handle in constFoldBinary() the new expression kinds (optional).