CS 3723
 Programming Languages 
   Rec 4 Answers  

Answers to Recitation 4:

  1. Translation to RPN: See To_RPN for a complete solution.

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

    • Each time a letter is read by the scanner, output the letter.
    • Each time an operator is read by the scanner, 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. R-D- Parser for a Simplified Python Dictionary: Intuitively, the syntax of these simplified dictionaries, consist of a sequence of items, each separated from the next by a comma, enclosed in curly brackets. An item is a digit, followed by a colon, followed by a letter.

    Dict.java GetChar and Output
    /* Dict.java:
  D --> '{' L '}'
  L --> I { ',' I }
  I --> digit ':' letter
 */
class Dict {
   GetChar getChar = new GetChar();
   char next;

   void D() {
      scan();
      if (next == '{') {
         scan();
         L();
      }
      else error(1);
      if (next == '}')
         System.out.println("\nSuccess\n");
      else error(2);
   }

   void L() {
      I();
      while (next == ',') {
         scan();
         I();
      }
   }

   void I() {
      if (Character.isDigit(next)) {
         scan();
      }
      else error(3);
      if (next != ':') error(4);
      scan();
      if (Character.isLetter(next)) {
         scan();
      }
      else error(4);
   }

   private void scan() {
      while (Character.isWhitespace(next =
            getChar.getNextChar()))
         ;
      System.out.print(next);
   } 
      
   private void error(int n) {
      System.out.println("\nERR #: " + n +
         ", next:" + next);
      System.exit(1);
   }

   public static void main(String[] args) {
      Dict dict = new Dict();
      dict.D();
   }
}

    // GetChar: fetch next char 
import java.io.*;
public class GetChar { 
   private Reader in; // file name for input
  
   // GetChar: constructor  
   public GetChar () { 
      in = new InputStreamReader(System.in);
   }

   // getNextChar: fetches next char
   public char getNextChar() {
      char ch = ' '; // = ' ' for compiler
      try {
         ch = (char)in.read();
      } catch (IOException e) {
         System.out.println("Exception");
      }
      return ch;
   }
}

    
{ 3:a }
{3:a}
Success

{ 2:b , 4:d }
{2:b,4:d}
Success

{ 2:b , 4:d , 3 : e }
{2:b,4:d,3:e}
Success

{1:a,2:b,3:c,4:c}
{1:a,2:b,3:c,4:c}
Success

[ 2:a]
[
ERR #: 1, next:[

{ 2:a ]
{2:a]
ERR #: 2, next:]

{ 3:a. 2:b}
{3:a.
ERR #: 2, next:.

{ 2:a, b:3 }
{2:a,b
ERR #: 3, next:b

{2:a,3:4}
{2:a,3:4
ERR #: 4, next:4

  3. R-D- Parser for the Weird Grammar: 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("\nSuccess!\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()))
      ;
   printf("%c", next);
}

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

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

bab$ 
bab$
Success!

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

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

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

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

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


    baba$
baba
ERR #: 0, next: a

a ( a ) b $
a
ERR #: 1, next: a

aba$
a
ERR #: 1, next: a

baab$
baa
ERR #: 2, next: a

b ( ( a a ) a ) a ) b $
b((aa)a)a
ERR #: 2, next: a

b ( b a ) b $
b(b
ERR #: 3, next: b

b ( ( a a a ) a ) $
b((aaa
ERR #: 4, next: a

b ( a ) b $
b(a)
ERR #: 5, next: )

b ( ( a b ) a ) $ 
b((ab
ERR #: 5, next: b

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