Pprint-expressions
Pretty-printing of expressions.
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 (make-ident :name "x"))
(expr-ident (make-ident :name "y")))
(expr-ident (make-ident :name "z")))represents the expression (x + y) * z.
Note that, 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 +
in C.
The relative priorities of C operators are implicitly defined
by the C grammar of expressions,
which also defines 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 original 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 original 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 original expression can only be left-associated
(i.e. (x + y) + z).
Our pretty-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 approach is explained in the following paragraphs.
We define `grades' of expressions
that correspond to certain nonterminals of the C grammar,
such as a grade of additive expressions
corresponding to the nonterminal additive-expression.
We define a mapping from the expressions of our abstract syntax
to their grades,
e.g. (expr-binary (binop-add) ... ...)
and (expr-binary (binop-sub) ... ...)
are mapped to the grade of additive expressions.
We define a total order on expression grades that is
the reflexive and transitive closure of the binary relation
that consists of the pairs grade1 < grade2 such that
there is a grammar (sub)rule nonterm2: nonterm1
saying that the nonterminal nonterm2 corresponding to grade2
may expand to the nonterminal nonterm1 corresponding to grade1.
For instance, grade1 is the grade of multiplicative expressions
and grade2 is the grade of additive expressions,
because there is a (sub)rule
additive-expression: multiplicative-expression in the grammar.
(Here by `subrule' we mean a rule not necessarily in the grammar
but obtainable by selecting just some of the alternatives in the definiens
that are on different lines in [C].)
The nonterminal additive-expression also has other alternatives,
but those are not single nonterminals;
here we are only concerned with single nonterminals as rule definientia.
The reason is explained below.
Besides the abstract syntactic expression to pretty-print,
the pretty-printer for expression has an argument
that is the grade of expression that must be pretty-printed
at that point.
At the top level, this second argument is
the grade of top-level expressions,
i.e. the grade that corresponds to
the nonterminal expression [C:6.5.17].
As the pretty-printer descends into subexpressions,
the second argument is changed according to
the grammar rule corresponding to the super-expressions.
For instance, when pretty-printing the left and right subexpressions
of a super-expression (expr-binary (binop-add) left right),
we recursively call the pretty-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 grade of additive-expression,
while the recursive call on right will have as second argument
the grade of multiplicative-expression.
The second argument of the pretty-printer is used as follows:
the pretty-printer compares the second argument
(i.e. the expected grade of expression)
with the grade of the expression passed as first argument
(i.e. the actual grade of expression),
according to the total order on expression grades described above;
if the actual grade is less than or equal to the expected grade,
the expression is pretty-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 grade can be expanded,
possibly in multiple steps,
into the nonterminal for the actual grade:
or conversely, the actual expression can be parsed
into an expression of the expected grade.
On the other hand, if the actual grade is greater than the expected grade,
there is no such possibility;
by adding parentheses, we change the grade of the actual expression
into the one at the bottom of the total order,
i.e. the grade corresponding to primary-expression,
which again lets the parenthesized expression be parsed
into an expression of the expected grade.
For instance, consider the abstract syntax tree for (x + y) * z,
shown earlier as motivating example.
Assume that it is pretty-printed as a top-level expression,
i.e. that the second argument is the grade of expression
(the expected grade).
Since the actual grade of the expression is
the one for multiplicative-expression,
which is less 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 pretty-printing the left subexpression x + y,
the expected grade is multiplicative-expression:
since the actual grade of x + y is additive-expression,
which is greater than the expected grade,
parentheses must be added,
as mentioned when the example was first presented.
On the other hand, when pretty-printing the right subexpression z,
the expected grade is cast-expression:
since the actual grade of z is primary-expression,
which is less than the expected grade,
no parentheses are printed.
The total order on expression grades only considers, as mentioned,
(sub)rules of the form nonterm2: nonterm1
where nonterm1 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 grade.
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 grades (a form of subtyping).
