CS 3723
 Programming Languages 
   Rec 5 Answers  

Answers to Recitation 5:

  1. All you need to do is add a few output statements to the bare parser:

    • Each time a letter is read, output the letter.
    • Each time an operator is read, output the operator after calling the second operand.
    • Ignore parentheses.
    • Put a '$' at the end if you like.

    Basically, the parser takes care of everything, the precedence and associativity of operators, and the effects of the parentheses.

  2. Here is a description of all strings generated by this grammar, or recognized by the parser:

      b [ ( ] n a [ a )] n b, for n >= 0

    Above, all terminals are bold red, and [ ]n means "n repetitions of what is inside [ ]." This language cannot be recognized by any finite-state automaton, since "finite automata can't count", meaning that no finite-state machine can make sure there are the same number of items before and after the central "a".

    /* ablm.c: parser based on
 *     S --->  b M b
 *     M --->  ( L  |  a
 *     L --->  M a )
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
void S (void);
void M (void);
void L (void);
void scan(void);
void error(int n);
int next;

int main() {
   scan();
   S();
   if (next == '$') printf("Success!\n");
   else error(0);
}

void S (void) {
   if (next != 'b') error(1);
   scan();
   M();
   if (next != 'b') error(2);
   scan();
}

void M (void) {
   if (next == '(') { scan(); L(); return;}
   else if (next == 'a') { scan(); return;}
   else error(3);
}

void L (void) {
   M();
   if (next == 'a') {
      scan();
      if (next == ')') { scan(); return;}
      else error(4);
   }
   else error(5);
}
   
void scan(void) {
   while (isspace(next = getchar()))
      ;
}

void error(int n) {
   printf("ERROR: %i, next: %c\n", n, next);
   exit(n);
}

    /*

% cc -o ablm -Wall ablm.c
% ./ablm

bab$ 
Success!

b ( a a ) b $ 
Success!

b ( ( a a ) a ) b $ 
Success!

b ( ( ( a a ) a ) a ) b $ 
Success!

b ( ( ( ( a a ) a ) a ) a ) b $ 
Success!

b ( ( ( ( ( ( ( ( ( a a ) a ) a )
 a ) a ) a ) a ) a ) a ) b $
Success!


    
baba$ 
ERROR: 0, next: a

a ( a ) b $ 
ERROR: 1, next: a

aba$
ERROR: 1, next: a

baab$
ERROR: 2, next: a

b ( ( a a ) a ) a ) b $ 
ERROR: 2, next: a

b ( b a ) b $ 
ERROR: 3, next: b

b ( ( a a a ) a ) $ 
ERROR: 4, next: a

b ( a ) b $ 
ERROR: 5, next: )

b ( ( a b ) a ) $ 
ERROR: 5, next: b

 */

  3. Where the multipy occurs (at the instruction mul.d $f6, $f2, $f4) patch in an extra instruction mul.d $f6, $f6, $f6. This will square what is in $f6. Since n^2 was there, after the additional instruction, it will be n^4.