CS 3723  Programming Languages
Tiny® Extensions

M  −−−>  { ( S  |  D ) }  '$'
S  −−−>  I  |  W  |  A  |  P  |  C  |  G
D  −−−>  '(' id '(' [ id { ',' id } ] ')'  S { S } E ')'
I  −−−>  '[' E '?' S { S } ':' S { S } ']'  |  '[' E '?' S { S } ']'
W  −−−>  '{' E '?' S { S } '}'
A  −−−>  lower-case '=' E ';'
P  −−−>  '<'  E  ';'
G  −−−>  '>'  id ';'
C  −−−>  '<' ( 'B'  | 'T' | 'N' ) ';'
E  −−−>  Q [ ('&' | '|') Q ]
Q  −−−>  R [ ('<' | '>' | '<=' | '>=' | '==' | '!=' ) R ]
R  −−−>  T { ('+' | '-') T }
T  −−−>  U { ('*' | '/' | '%' | '@') U }
U  −−−>  F '^' U | F
F  −−−>  '(' E ')' | ('+' | '-' | '!') F  |  id  |  double  |
           id '(' [ E { ',' E } ] ')' )
id −−−>  letter  { letter | digit }
double −−−> (standard double syntax)

Just to help with understanding, here is the intuitive meaning of each of the above non-terminals:

The grammar above has added:

• identifiers and constant doubles.
• relational operators: '<', '>', '<=', '>=', '==', '!='
• logical operators, '&', '|', '!', and
• functions with parameters: here is an example of a defined function and its use:

  Function Example
  # definition (a (x, y) x = x/2; y = 2*y+1; x+y) # x and y above are formal parameters # use: u = 9; z = a(u+1, 4); # u+1 and 4 above are actual parameters # z has value (((9+1)/2)+(2*4+1) = 14

The grammar gives the CF-syntax, but one also has to worry about:

• The semantics of any proposed extensions, and
• How such extensions might be implemented.

Implementation is surprisingly simple. First keep the convention that a zero double is false and all non-zero doubles are true. Add to this the idea that the result of any of the new operators will be either 0.0 or 1.0. This means that the old if-then and while constructs will work as before. The blue code below implements <=. The other relations and logical operators are similar.

# implement relational op <=
main:   addu    $s7, $ra, $zero
        la      $s1, M
# start of <= test: c = (a <= b)
# Read 'a' as double
        li      $v0, 7
        syscall
        s.d     $f0, 80($s1)
# Read 'b' as double
        li      $v0, 7
        syscall
        s.d     $f0, 88($s1)
# want to do c = (a <= b)
        l.d     $f2, 80($s1)  # a
        l.d     $f4, 88($s1)  # b
        l.d     $f6, 8($s1)   # res = 1.0
        c.le.d  $f2, $f4      # a <= b ?
        bc1t    Rel01
        l.d     $f6, 0($s1)   # res = 0.0
Rel01:
        s.d     $f6, 96($s1)  # res in c
# Print 'c'
        li      $v0, 3
        l.d     $f12, 96($s1)
        syscall
# Print NewL as ASCII char
        li      $v0, 4
        la      $a0, NewL
        syscall
# end of <= test
        addu    $ra, $s7, $zero
        jr      $ra
        .data
        .align  3
M:      .double 0.,1.,2.,3.,4.,5.,6.
        .double 7.,8.,9. # constants
        .space  208  # variables a to z
        .space  1000 # 125 temporaries
NewL:   .asciiz "\n"
# end of program

% spim ble.s
1
2
1
% spim ble.s
2
2
1
% spim ble.s
2
1
0
% spim ble.s
0
0
1
% spim ble.s
-4
-1
1
% spim ble.s
-2
5
1
% spim ble.s
-3
-7
0
% spim ble.s
7
-2
0

Semantic Problems and Questions:

• Let's assume we stick with only doubles and have no declarations.
• Should allow arbitrary expression for the actual parameter, which is passed by value to the formal parameter.
• I would propose having the formal parameters and any variables appearing in the function body to be "local variables", whose scope is limited to the function body.
• This language is so simple, it's probably reasonable to allow the function definition anywhere, and not restricted to before the use, but one could do that if it made the implementation easier.
• Recursion will come for free with the implementation strategy proposed below.
• In the grammar, there is a required final expression, and that will be returned.

Implementation: The page Activation Records illustrates the implementation of a recursive functions in MIPS, using a special stack and "activation records" on the stack for function calls. In addition to other problems, all the data except for addresses would have to adapted to doubles, but still it would be complex but not hard.

(Revision date: 2014-11-03. Please use ISO 8601, the International Standard.)