=========================================
Parsing Left Associative Binary Operators				[TOC]
=========================================

We will further extend our grammar (See __Session 24, Page 3__). Before that
we will simplify its implementation in _parse.c_. You certainly have noticed
for the production rules 

---- LATEX ---------------------------------------------------------------------
\begin{array}{rcl}
\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}
    \}
    \\
\end{array}
--------------------------------------------------------------------------------

the implementation of the corresponding parse functions have the same pattern.
These rules have in common that they are production rules for left associative
binary operators. We will exploit this an will replace _parseEqualExpr()_,
_parseRelExpr()_, _parseAdditiveExpr()_ and _parseMultiplicativeExpr()_ with
a single function _parseLeftAssocBinaryExpr()_.

Precedence Levels for Left Associative Operators
================================================
The grammar specifies the different precedences of the operators. Operators
that occur first in a production rule have the lowest precedence. Below the
precedence levels are noted in table form analogously to the corresponding
precedence levels in C (See __Session 8, Page 4__).

+---------------+---------------------------------------+---------------+
| Precedence	|	Operators			| Meaning	|
+---------------+---------------------------------------+---------------+
| 13		|	`*` (multiply)			|Multiplicative |
|		|					|		|
|		|	`/` (divide)			|		|
|		|					|		|
|		|	`%` (modulo)			|	        |
+---------------+---------------------------------------+---------------+
| 12		|	`+` (add)			|   Additive    |
|		|					|	        |
|		|	`-` (subtract)			|		|
+---------------+---------------------------------------+---------------+
| 10		|	`<`  (less)			|   Relation    |
|		|					|		|
|		|	`>`  (greater)	     		|		|
|		|					|		|
|		|	`<=` (less equal)		|		|
|		|					|		|
|		|	`>=` (greater equal)		|		|
+---------------+---------------------------------------+---------------+
| 9		|	`==`				| Equality	|
|		|					|		|
|  		|	`!=`				| Inequality	|
+---------------+---------------------------------------+---------------+

For the implementation of a common parse function it is convenient to implement
two auxiliary functions. Function _tokenKindPrec()_ will be used to obtain the
precedence form a given token kind, and function _makeBinaryExprKind()_ will be
used to translate the token kind into a corresponding expression kind. Both
functions later can be generated from a textual description.

Obtain Precedence from Token Kinds
----------------------------------
If a token kind represents one of the operators in the above table function
_tokenKindPrec()_ returns its precedence which will always be a positive value.
Otherwise it returns zero:

---- CODE (type=c) -------------------------------------------------------------
static int
tokenKindPrec(enum TokenKind kind)
{
    switch (kind) {
        case ASTERISK:
        case SLASH:
        case PERCENT:
            return 13;
        case PLUS:
        case MINUS:
            return 12;
	/*
	    TODO:
	    handle all other cases of left associative binary operators
	*/
        default:
            return 0;
    }
}
--------------------------------------------------------------------------------

Complete the implementation by handling in the switch statement all other token
kinds that represent a left associative binary operator.

Translating Token Kinds into Expression Kinds
---------------------------------------------
For creating binary expressions the token kind needs to be translated into an
expression kind. This is implemented in _makeBinaryExprKind()_ and it is an
internal error if it received a parameter that can not be translated:

---- CODE (type=c) -------------------------------------------------------------
static enum ExprKind
makeBinaryExprKind(enum TokenKind kind)
{
    switch (kind) {
        case ASTERISK:
            return EK_MUL;
        case SLASH:
            return EK_DIV;
        case PERCENT:
            return EK_MOD;
        case PLUS:
            return EK_ADD;
        case MINUS:
            return EK_SUB;
	/*
	    TODO:
	    handle all other cases of left associative binary operators
	*/
        default:
            fprintf(stderr, "makeBinaryExprKind: token kind %s (%d) not "
		    "handled\n", strTokenKind(kind), kind);
            assert(0);
            return 0;
    }
}
--------------------------------------------------------------------------------

Complete the implementation by handling all relevant token kinds, i.e. all
token kinds where _tokenKindPrec()_ returns a positive value.

Parse Function for Left Associative Binary Operators
----------------------------------------------------
Now consider the following implementation of _parseLeftAssocBinaryExpr()_:

---- CODE (type=c) -------------------------------------------------------------
static const struct Expr *
parseLeftAssocBinaryExpr(int prec)
{
    if (prec > 13) {
        return parseUnaryExpr();
    } else {
        const struct Expr *expr = parseBinaryExpr(prec + 1);
        while (tokenKindPrec(token.kind) == prec) {
            enum ExprKind op = makeBinaryExprKind(token.kind);
            getToken();
            expr = newBinaryExpr(op, expr, parseLeftAssocBinaryExpr(prec + 1));
        }
        return expr;
    }
}
--------------------------------------------------------------------------------

Convince yourself that for example _parseLeftAssocBinaryExpr(9)_ is equivalent
to  _parseEqualExpr()_

---- CODE (type=c) -------------------------------------------------------------
static const struct Expr *
parseEqualExpr(void)
{
    const struct Expr *expr = parseRelExpr();
    while (token.kind == EQUAL2 || token.kind == NOT_EQUAL) {
        enum TokenKind op = token.kind;
        getToken();
        const struct Expr *exprRight = parseRelExpr();
        if (op == EQUAL2) {
            expr = newBinaryExpr(EK_EQUAL, expr, exprRight);
        } else if (op == NOT_EQUAL) {
            expr = newBinaryExpr(EK_NOT_EQUAL, expr, exprRight);
        }
    }
    return expr;
}
--------------------------------------------------------------------------------

and calling _parseLeftAssocBinaryExpr(14)_ is equivalent to calling
_parseUnaryExpr()_. It is also no problem that we have "gaps" in the precedence
levels, e.g. we have no operator with a precedence level of 10.

Examples
--------
For illustrating how _parseLeftAssocBinaryExpr()_ works the implementation was
modified so that we can see its call stack:

---- CODE (type=c) -------------------------------------------------------------
static const struct Expr *
parseLeftAssocBinaryExpr(int prec)
{
    printf("%*sparseBinaryExpr(%d)\n", prec, "", prec);
    if (prec > 13) {
	printf("%*s->parseUnaryExpr()\n", prec, "");
        return parseUnaryExpr();
    } else {
        const struct Expr *expr = parseLeftAssocBinaryExpr(prec + 1);
        while (tokenKindPrec(token.kind) == prec) {
            enum TokenKind opTokenKind = token.kind;
            enum ExprKind op = makeBinaryExprKind(token.kind);
            getToken();

	    printf("%*s->newBinaryExpr(...) for operator %s\n", prec, "",
		   strTokenKind(opTokenKind));
            expr = newBinaryExpr(op, expr, parseLeftAssocBinaryExpr(prec + 1));
        }
        return expr;
    }
}
--------------------------------------------------------------------------------

---- SHELL (path=session25/git/abc_step0,hide) ---------------------------------
make
--------------------------------------------------------------------------------

_a + b * (c + d)_
~~~~~~~~~~~~~~~~~
Here the call stack when the expression _a + b * (c + d)_ gets parsed:

---- SHELL (path=session25/git/abc_step0) --------------------------------------
echo "a + b * (c + d);" | ./xtest_abc foo.s foo.tex
--------------------------------------------------------------------------------


_z == x * ( y + z) / a + 5 + (x == y)_
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Here the call stack when the expression _z == x * ( y + z) / a + 5 + (x == y)_
gets parsed:

---- SHELL (path=session25/git/abc_step0) --------------------------------------
echo "z == x * ( y + z) / a + 5 + (x == y);" | ./xtest_abc foo.s foo.tex
--------------------------------------------------------------------------------

Optimization of ``parseLeftAssocBinaryExpr``
============================================

---- CODE (type=c) -------------------------------------------------------------
static const struct Expr *
parseLeftAssocBinaryExpr(int prec)
{
    const struct Expr *expr = parseUnaryExpr();
    for (int p = tokenKindPrec(token.kind); p >= prec; --p) {
        while (tokenKindPrec(token.kind) == p) {
            enum ExprKind op = makeBinaryExprKind(token.kind);
            getToken();
            expr = newBinaryExpr(op, expr, parseLeftAssocBinaryExpr(p + 1));
        }
    }
    return expr;
}
--------------------------------------------------------------------------------

For visualizing  the call stack it was modified to:

---- CODE (type=c) -------------------------------------------------------------
static const struct Expr *
parseLeftAssocBinaryExpr(int prec)
{
    printf("%*sparseBinaryExpr(%d)\n", prec, "", prec);
    const struct Expr *expr = parseUnaryExpr();
    printf("%*s->parseUnaryExpr()\n", prec, "");
    for (int p = tokenKindPrec(token.kind); p >= prec; --p) {
        while (tokenKindPrec(token.kind) == p) {
            enum TokenKind opTokenKind = token.kind;
            enum ExprKind op = makeBinaryExprKind(token.kind);
            getToken();
	    printf("%*s->newBinaryExpr(...) for operator %s\n", prec, "",
		   strTokenKind(opTokenKind));
            expr = newBinaryExpr(op, expr, parseLeftAssocBinaryExpr(p + 1));
        }
    }
    return expr;
}
--------------------------------------------------------------------------------

---- SHELL (path=session25/git/abc_step1,hide) ---------------------------------
make
--------------------------------------------------------------------------------

_a + b * (c + d)_
~~~~~~~~~~~~~~~~~
Here the call stack when the expression _a + b * (c + d)_ gets parsed:

---- SHELL (path=session25/git/abc_step1) --------------------------------------
echo "a + b * (c + d);" | ./xtest_abc foo.s foo.tex
--------------------------------------------------------------------------------


_z == x * ( y + z) / a + 5 + (x == y)_
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Here the call stack when the expression _z == x * ( y + z) / a + 5 + (x == y)_
gets parsed:

---- SHELL (path=session25/git/abc_step1) --------------------------------------
echo "z == x * ( y + z) / a + 5 + (x == y);" | ./xtest_abc foo.s foo.tex
--------------------------------------------------------------------------------

Exercise
========
Implement ``parseLeftAssocBinaryExpr()`` and the auxiliary functions as
described above. Do not forget to remove the forward declarations of the
obsolete parse functions. In ``parseAssignmentExpr()`` call
``parseLeftAssocBinaryExpr(1)`` instead of ``parseLeftAssocBinaryExpr(9)``. Then
nothing needs to be changed in this place when new left associative binary
operators will be added.

Write a test program for the ABC compiler. For example (but feel free to make
it more extensive):

---- CODE (file=session25/git/abc_step1/test.abc) ------------------------------
a + b * (c + d);
x + 1 == y;
x + 1 != y * z;
x + 1 <= y * z;
x + 1 >= y * z;
x + 1 < y * z;
x + 1 > y * z;
--------------------------------------------------------------------------------

and check the expression trees in the generated Latex. In this case

---- SHELL (path=session25/git/abc_step1/) -------------------------------------
./xtest_abc test.s test.tex < test.abc
lualatex test.tex > /dev/null
--------------------------------------------------------------------------------

---- SHELL (path=session25/git/abc_step1/, hide) -------------------------------
cp test.pdf /home/www/htdocs/numerik/hpc/ss22/hpc0/session25/
--------------------------------------------------------------------------------

you should get this __pdf__.


:links: Session 24, Page 3 -> doc:session24/page03
	Session 8, Page 4 -> doc:session08/page04
	pdf -> https://www.mathematik.uni-ulm.de/numerik/hpc/ss22/hpc0/session25/test.pdf