Print-expr
Print an expression.
- Signature
(print-expr expr expected-prio pstate) → new-pstate
- Arguments
- expr — Guard (exprp expr).
- expected-prio — Guard (expr-priorityp expected-prio).
- pstate — Guard (pristatep pstate).
- Returns
- new-pstate — Type (pristatep new-pstate).
The tree structure of the abstract syntax of C expressions
describes the grouping of nested subexpressions.
For instance, the tree
(expr-binary (binop-mul)
(expr-binary (binop-add)
(expr-ident (ident "x") ...)
(expr-ident (ident "y") ...))
(expr-ident (ident "z") ...))(where ... is the additional information, irrelevant here)
represents the expression (x + y) * z.
When this expression is written in concrete syntax as just done,
parentheses must be added,
because * binds tighter (i.e. has a higher priority) than +.
The relative priorities of C operators are implicitly defined
by the grammar rules for expressions,
which also define the left vs. right associativity
of binary operators.
For instance, the rules in [C:6.5.5] and [C:6.5.6] tell us that
(i) + binds tighter than * and
(ii) + is left-associative:
- Consider an expression x + y * z.
In order to parse this as a multiplicative-expression,
x + y would have to be a multiplicative-expression),
which is not.
Thus, the expression can only be parsed
as an additive-expression.
- Consider an expression x * y + z.
In order to parse this as a multiplicative-expression,
y + z would have to be a cast-expression,
which is not.
Thus, the expression can only be parsed
as an additive-expression.
- Consider an expression x + y + z.
In order to right-associate it (i.e. x + (y + z)),
y + z would have to be a multiplicative-expression,
which is not.
Thus, the expression can only be left-associated
(i.e. (x + y) + z).
Our printer adds parentheses
based on the relative priorities of the C operators
and the left or right associativity of the C binary operators,
following the grammar.
The function expr-priority classifies expressions
according to certain nonterminals of the C grammar.
For instance, the priority of additive expressions
corresponds to the nonterminal additive-expression.
The function expr->priority defines a mapping
from the expressions of our abstract syntax to their priorities,
e.g. (expr-binary (binop-add) ... ...)
and (expr-binary (binop-sub) ... ...)
are mapped to expr-priority-add,
the priority of additive expressions.
The function expr-priority-<= defines
a total order on expression priorities:
see that function's documentation for details of
how that total order is defined in relation to the grammar.
Besides the abstract syntactic expression to print,
this printer function for expression has an argument
that is the priority of the expression that must be printed
at that point.
At the top level, this second argument is
the priority of top-level expressions,
i.e. the priority that corresponds to
the nonterminal expression [C:6.5.17].
As we descend into subexpressions,
the second argument of this function is changed according to
the grammar rule corresponding to the super-expression.
For instance, when printing the left and right subexpressions
of a super-expression (expr-binary (binop-add) left right),
we recursively call the printer twice,
once on left and once on right.
Because of the grammar rule
additive-expression:
additive-expression + multiplicative-expression
that corresponds to the super-expression,
the recursive call on left will have as second argument
the priority of additive-expression,
while the recursive call on right will have as second argument
the priority of multiplicative-expression.
The second argument of the printer is used as follows:
the printer compares the second argument
(i.e. the expected priority of the expression)
with the priority of the expression passed as first argument
(i.e. the actual priority of the expression),
according to the total order on expression priorities;
if the actual priority is greater than or equal to the expected priority,
the expression is printed without parentheses,
otherwise parentheses are added.
The reason why no parentheses are needed in the first case is that
the nonterminal for the expected priority can be expanded,
possibly in multiple steps,
into the nonterminal for the actual priority:
or conversely, the actual expression can be parsed
into an expression of the expected priority.
The expansion is based on the grammar (sub)rules
discussed in expr-priority-<=.
On the other hand,
if the actual priority is less than the expected priority,
there is no such possibility;
by adding parentheses, we change the priority of the actual expression
into the one at the top of the total order,
i.e. the priority corresponding to primary-expression,
which again lets the parenthesized expression be parsed
into an expression of the expected priority.
For instance, consider the abstract syntax tree for (x + y) * z,
shown earlier as motivating example.
Assume that it is printed as a top-level expression,
i.e. that the second argument is the priority of expression
(the expected priority).
Since the actual priority of the expression is
the one for multiplicative-expression,
which is greater than or equal to the one for expression
(via
assignment-expression,
conditional-expression,
logical-OR-expression,
logical-AND-expression,
inclusive-OR-expression,
exclusive-OR-expression,
AND-expression,
equality-expression,
relational-expression,
shift-expression, and
additive-expression),
no parentheses are printed at the top level.
When printing the left subexpression x + y,
the expected priority is multiplicative-expression:
since the actual priority of x + y is additive-expression,
which is less than the expected priority,
parentheses must be added,
as mentioned when the example was first presented.
On the other hand, when printing the right subexpression z,
the expected priority is cast-expression:
since the actual priority of z is primary-expression,
which is less than the expected priority,
no parentheses are printed.
The total order on expression priority only considers,
as explained in expr-priority-<=,
(sub)rules of the form nonterm1: nonterm2
where nonterm2 is a single nonterminal.
Rule definientia that are not single terminals
are captured as tree structures in our abstract syntax,
and thus have their own explicit priority.
On the other hand, single-nonterminal definientia
do not correspond to any tree structure,
but rather allow the same expression to have, in effect,
different priorities (a form of subtyping).
We treat the printing of conditional expressions
slightly differently based on the printer option
about parenthesizing nested conditional expressions.
The difference is in the expected priority
used for the `then' and `else' subexpressions.
If that flag is not set,
we print things with minimal parentheses,
and therefore we use
the lowest expression priority
for `then' and the conditional grade for `else',
consistently with the grammar rule for conditional expressions.
This means that if the `then' and/or `else' is a conditional expression,
it is not parenthesized.
If instead the flag is set,
then we use a higher-priority for both `then' and `else',
precisely the priority just one higher than conditional expressions,
namely the priority of logical disjunction.
This means that if the `then' and/or `else' is a conditional expression,
it is parenthesized, in order to raise its priority.
