Csc 4330/6330, Programming Language Concepts (Spring 2018)

Homework 3b (Due: 25 February (Sunday))

LISP Grammar:

        lisp : 
            INT 
          | LPAREN ADD lisp lisp RPAREN
          | LPAREN SUB lisp lisp RPAREN
          | LPAREN MUL lisp lisp RPAREN
          | LPAREN DIV lisp lisp RPAREN
          | LPAREN CAR list RPAREN

        list :
            LPAREN CDR list RPAREN
          | LPAREN seq RPAREN

        seq :
            lisp
          | lisp seq

1. Write a Lexer program in Java (LISPLexer.java) without using the Antlr4 system to generate the tokens for the LISP language. Write it as a class with a constructor and a lex() method so that the Parser program can use it. Here is a test program and a sample run:

   public  class TestLexer {
     public static void main(String args[]) {
       Lexer l = new Lexer(args[0]);
       Token t = l.lex();
       while (t.getTokenID() != TokenTypes.EOF)
         t = l.lex();
     }
   }
   
   mirage:3b raj$ java TestLexer "(+ (car (1 2 3 4)))"
   Next lexeme is LPAREN
   Next lexeme is ADD_OP
   Next lexeme is LPAREN
   Next lexeme is CAR
   Next lexeme is LPAREN
   Next lexeme is INT_LIT<1>
   Next lexeme is INT_LIT<2>
   Next lexeme is INT_LIT<3>
   Next lexeme is INT_LIT<4>
   Next lexeme is RPAREN
   Next lexeme is RPAREN
   Next lexeme is RPAREN
   Next lexeme is EOF
   

2. Write a Recursive Descent Parser in Java (LISPParser.java). Here are couple of sample runs:

   mirage:3b raj$ java LISPParser "(+ (car (1 2 3 4)) 20)"
   Next lexeme is LPAREN
   Enter <lisp>
   Next lexeme is ADD_OP
   Next lexeme is LPAREN
   Enter <lisp>
   Next lexeme is CAR
   Next lexeme is LPAREN
   Enter <list>
   Next lexeme is INT_LIT<1>
   Enter <seq>
   Enter <lisp>
   Next lexeme is INT_LIT<2>
   Exit <lisp>
   Enter <lisp>
   Next lexeme is INT_LIT<3>
   Exit <lisp>
   Enter <lisp>
   Next lexeme is INT_LIT<4>
   Exit <lisp>
   Enter <lisp>
   Next lexeme is RPAREN
   Exit <lisp>
   Exit <seq>
   Next lexeme is RPAREN
   Exit <list>
   Next lexeme is INT_LIT<20>
   Exit <lisp>
   Enter <lisp>
   Next lexeme is RPAREN
   Exit <lisp>
   Next lexeme is EOF
   Exit <lisp>
   
   mirage:3b raj$ java LISPParser "(+ (car (1 2 3 4)))"
   Next lexeme is LPAREN
   Enter <lisp>
   Next lexeme is ADD_OP
   Next lexeme is LPAREN
   Enter <lisp>
   Next lexeme is CAR
   Next lexeme is LPAREN
   Enter <list>
   Next lexeme is INT_LIT<1>
   Enter <seq>
   Enter <lisp>
   Next lexeme is INT_LIT<2>
   Exit <lisp>
   Enter <lisp>
   Next lexeme is INT_LIT<3>
   Exit <lisp>
   Enter <lisp>
   Next lexeme is INT_LIT<4>
   Exit <lisp>
   Enter <lisp>
   Next lexeme is RPAREN
   Exit <lisp>
   Exit <seq>
   Next lexeme is RPAREN
   Exit <list>
   Next lexeme is RPAREN
   Exit <lisp>
   Enter <lisp>
   SYNTAX ERROR: Expecting LPAREN