Section 6.2 The Abstract Syntax of C0
C0 consists of programs that contain statements which in turn can contain expressions. We will first consider programs and statements and then introduce expressions separately later. Note that C0 does not have functions. It is however not too hard to add them and it is a good exercise to work on that after having studied this chapter.
Statements can form lists which we then call programs. A program can be put into a block which then itself is a statement. This allows us to use lists of statements wherever a statement is required, for example in the consequence and alternative of an if-then-else. In the following, we will be exclusively interested in C0 programs in their abstract syntax. We will nevertheless use some elements' concrete syntax (parentheses, braces, etc.) to make it easier to read them for us humans.
Definition 6.2.1 defines the abstract syntax of C0 statements and programs.
Definition 6.2.1. C0 Statement Language.
\begin{equation*}
\begin{array}{rclll}
\text{Category} \amp \amp \text{Abstract Syntax} \amp \text{Concrete Syntax} \amp \text{Description} \\
\hline
\mathit{Prg} \ni p \amp \syndef \amp \ASeq sp \amp \CSeq sp \amp \text{Sequence} \\
\amp | \amp \ATerm \amp \CTerm \amp \text{Empty Program} \\
\amp | \amp \ACrash \amp \amp \text{Crash} \\
\mathit{Stmt} \ni s \amp \syndef \amp \AAssign{l}{e} \amp \CAssign le \amp \text{Assignment} \\
\amp | \amp \ABlock{}p \amp \CBlock p \amp \text{Block} \\
\amp | \amp \AIf{e}{s_1}{s_2} \amp \CIf e{s_1}{s_2} \amp \text{If} \\
\amp | \amp \AWhile{e}{s} \amp \CWhile es \amp \text{Loop} \\
\amp | \amp \AAbort \amp \CAbort \amp \text{Abort} \\
\end{array}
\end{equation*}
Note that the empty program is denoted by the empty string \(\varepsilon\text{.}\) In most of the examples, we do not write down \(\varepsilon\) explicitly. Only in cases where we want to make explicit that we are talking about the empty program, we use \(\varepsilon\text{.}\) For example, we write the program \(\CSeq{\CAssign{\CVar x}{\CConst 2}}{\CTerm}\) as \(\CAssign{\CVar x}{\CConst 2}\text{.}\) Some statements, like the if statement, contain expressions, which we introduce in the following:
Definition 6.2.2. C0 Expression Language.
\begin{equation*}
\begin{array}{rclll}
\text{Category} \amp \amp \text{Abstract Syntax} \amp \text{Concrete Syntax} \amp \text{Description} \\
\hline
\mathit{LExpr} \ni l \amp \syndef \amp \AVar x \amp x \amp \text{Variable} \\
\mathit{Expr} \ni e \amp \syndef \amp l \amp \amp \text{L-Value} \\
\amp | \amp \AConst c \amp c \amp \text{Constant} \\
\amp | \amp \ABinary{o}{e_1}{e_2}\amp e_1\mathop{o} e_2 \amp \text{Binary Expr.} \\
\mathit{Op} \ni o \amp \syndef \amp r \mid m \amp \amp \text{Operators} \\
\mathit{AOp} \ni r \amp \syndef \amp \amp \mathtt+ \mid \mathtt- \mid \cdots \amp \text{Arithmetic Op.} \\
\mathit{COp} \ni m \amp \syndef \amp \amp \mathtt{==} \mid \mathtt{!\!\!=} \mid \mathtt{\lt} \mid \cdots \amp \text{Comparison Op.} \\
\end{array}
\end{equation*}
Example 6.2.3.
The following example shows a small C0 program with its concrete and abstract syntax and the corresponding abstract syntax tree.
q = 0;
r = x;
while (y <= r) {
r = r - y;
q = q + 1;
}
Run
