Compiler Design Laboratory

3. MiniJava Expressions

In this lab we will design the expressions of MiniJava together with the apropriate operators.

You may design your own expressions as far as you implement the logical expressions, relational expressions and arithmetical expressions.

3.1 Logical expressions

The logical expressions are organized around the following logical operators: not !, and &&, or ||.

You may look in the Java language specification for the associativity and distributivity of these operators if you are not already aware of them. The not "!" unary operator has higher priority then the and "&&" operator. The and "&&" operator has higher priority then the or "||" operator. The subexpression operator, expressed by parantheses "()", has higher priority then the not operator. For this reason we need to design four levels of grammar rules modelling the four priorities when processing such a logical expression.

To model the logical expressions we propose the following rules:

Exp ::= Condition

Condition ::= LogExp | "!" LogExp

LogExp ::= LogExpTerm ("||" LogExpTerm)*

LogExpTerm ::= LogExpFactor ("&&" LogExpFactor)*

LogExpFactor ::= "(" LogExp ")" | RelExp | "true" | "false"

The proposed rules are organized on four levels:

• not !
• and &&
• or ||
• subexpression ()

The first rule has the lowest priority, while the last rule has the highest priority when evaluating or generating code. This will be shown in the example section.

The first Exp rule states that an expression in general can be a Condition. This is a natural choice.

The second Condition rule states that a logical expression can be negated or not using the not ("!") logical operator.

The LogExp rule was designed to model in general the logical expressions being in charge with all the "or" logical operations. If no "or" logical operations are present then it can be reduced to the LogExpTerm rule. We remind that the star * metasymbol represents repetition zero or more times.

The LogExpTerm rule was designed to model all the and ("&&") logical operations after the processing of logical subexpressions or relational expressions. If no and logical operations are present then it can be reduced to the LogExpFactor rule.

The LogExpFactor rule may hold a subexpression of another logical expression LogExp or may hold a relative expression RelExp.

Example 1:

Example 2:

a && (c || e) && !f && g

For this example draw on a paper the corresponding tree.

3.2 Relational expressions

Relational expressions are usually part of the logical expressions.

They are organized around the following relational operators: "<" , ">" , "<=" , ">=" , "==" , "!=".

In C programming language, these operators may have multiple operands while in Java they are binary operators. For example, you cannot compare a boolean with an int. We keep the same philosophy in MiniJava.

To model the relational expressions we consider the following rules:

RelExp := ArExp RelOp ArExp | ArExp

RelOp ::= "<" | ">" | "<=" | ">=" | "==" | "!="

The first rule RelExp models all the comparisons. The first rule also allows a relational expression to be an arithmetical expression.
The second rule RelOp enumerates all the possible comparison operators.
In these rules there are no priority levels like in the previous ones, all operators are binary and are not associative.

3.3 Arithmetical expressions

Arithmetical expressions may be used in relational expressions, but not necessarily. We defined an expression as condition. The condition can be a relational expression. The relational expression can be an arithmetical expression. Thus, we created a hierarchy for all the operators of the whole language alltogether.

Arithmetical expressions may be used also in assignments, in array indexes, in call arguments etc.

ArExp :: = Term (AdOp Term)*

AdOp ::= "+" | "-"

Term ::= Factor (MulOp Factor)*

MulOp ::= "*" | "/"

Factor ::= "(" ArExp ")" | ID | INT

The first rule ArExp models the sum/subtraction of terms.
The second rule Term models the product/division of factors.
The third rule Factor models subexpressions, IDs and integer constants.

Example 1:

3.4 Assignments

1. Study the expressions from the examples located in the JavaCC.zip.

2. Design the expression rules for the grammar given in file MiniJava.txt

3. Check the correctness of the operators precedence in the expression tree. Test on several examples.

Assignments time: week 4