Csc 4330/6330, Programming Language Concepts (Summer 2020)

Homework 3a (Due: 30 June (Tuesday); Late Submission by July 3 (Friday))

Handin under Assignment 3a
sudo handin4330 3a TokenTypes.py Token.py Lexer.py LexerTest.py Parser.py

Consider the simplified LISP Grammar (from Project 1) shown below:

        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

PART I: Lexical Analyzer

Write a Lexer program in Python without using the PLY 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 the test program (LexerTest.py):

import sys
from Lexer import *
from TokenTypes import *

def main():
  input = sys.argv[1]
  lexer = Lexer(input)
  print("Tokenizing ",end="")
  print(input)
  while True:
    t = lexer.lex()
    if t.get_token().value == TokenTypes.EOF.value:
      break

main()

and a sample run:

macbook-pro:hw3a raj$ python3 LexerTest.py "(+ (car (1 2 3 4)) 20)"
Tokenizing (+ (car (1 2 3 4)) 20)
Next Token is: TokenTypes.LPAREN, Next lexeme is (
Next Token is: TokenTypes.ADD, Next lexeme is +
Next Token is: TokenTypes.LPAREN, Next lexeme is (
Next Token is: TokenTypes.CAR, Next lexeme is CAR
Next Token is: TokenTypes.LPAREN, Next lexeme is (
Next Token is: TokenTypes.INT, Next lexeme is 1
Next Token is: TokenTypes.INT, Next lexeme is 2
Next Token is: TokenTypes.INT, Next lexeme is 3
Next Token is: TokenTypes.INT, Next lexeme is 4
Next Token is: TokenTypes.RPAREN, Next lexeme is )
Next Token is: TokenTypes.RPAREN, Next lexeme is )
Next Token is: TokenTypes.INT, Next lexeme is 20
Next Token is: TokenTypes.RPAREN, Next lexeme is )
Next Token is: TokenTypes.EOF, Next lexeme is -1

PART II: Recursive Descent Parser

Write a Recursive Descent Parser in Python (Parser.py). Here are couple of sample runs:

macbook-pro:hw3a raj$ python3 Parser.py "(+ (car (1 2 3 4)) 20)"
Next Token is: TokenTypes.LPAREN, Next lexeme is (
Enter lisp
Next Token is: TokenTypes.ADD, Next lexeme is +
Next Token is: TokenTypes.LPAREN, Next lexeme is (
Enter lisp
Next Token is: TokenTypes.CAR, Next lexeme is CAR
Next Token is: TokenTypes.LPAREN, Next lexeme is (
Enter list
Next Token is: TokenTypes.INT, Next lexeme is 1
Enter seq
Enter lisp
Next Token is: TokenTypes.INT, Next lexeme is 2
Exit lisp
Enter lisp
Next Token is: TokenTypes.INT, Next lexeme is 3
Exit lisp
Enter lisp
Next Token is: TokenTypes.INT, Next lexeme is 4
Exit lisp
Enter lisp
Next Token is: TokenTypes.RPAREN, Next lexeme is )
Exit lisp
Exit seq
Next Token is: TokenTypes.RPAREN, Next lexeme is )
Exit list
Next Token is: TokenTypes.INT, Next lexeme is 20
Exit lisp
Enter lisp
Next Token is: TokenTypes.RPAREN, Next lexeme is )
Exit lisp
Next Token is: TokenTypes.EOF, Next lexeme is -1
Exit lisp
PARSE SUCCEEDED

macbook-pro:hw3a raj$ python3 Parser.py "(+ (car (1 2 3 4)) )"
Next Token is: TokenTypes.LPAREN, Next lexeme is (
Enter lisp
Next Token is: TokenTypes.ADD, Next lexeme is +
Next Token is: TokenTypes.LPAREN, Next lexeme is (
Enter lisp
Next Token is: TokenTypes.CAR, Next lexeme is CAR
Next Token is: TokenTypes.LPAREN, Next lexeme is (
Enter list
Next Token is: TokenTypes.INT, Next lexeme is 1
Enter seq
Enter lisp
Next Token is: TokenTypes.INT, Next lexeme is 2
Exit lisp
Enter lisp
Next Token is: TokenTypes.INT, Next lexeme is 3
Exit lisp
Enter lisp
Next Token is: TokenTypes.INT, Next lexeme is 4
Exit lisp
Enter lisp
Next Token is: TokenTypes.RPAREN, Next lexeme is )
Exit lisp
Exit seq
Next Token is: TokenTypes.RPAREN, Next lexeme is )
Exit list
Next Token is: TokenTypes.RPAREN, Next lexeme is )
Exit lisp
Enter lisp
SYNTAX ERROR: Expecting LPAREN