Python

1

The George Washington University School of Engineering and Applied Science

Department of Computer Science CSci 4223 – Principles of Programming Languages – Spring 2016

Programming Assignment #2: A Simple lexical analyzer Due Date: March 6, 2016 -- Midnight

Instructor: A. Bellaachia

The following represents the EBNF grammar for a very simple language, called C--:

program ----> {stmt} stmt ----> var_dec ";" | assign ";" | read_stat ";" | write_stat ";" | if_stmt ";" | while_stmt ";" var_dec ----> type var assign ----> var "=" expr expr ----> add_expr add_expr ----> mul_expr {("+"|"-") mul_expr} mul_expr ----> simple_expr {("*"|"/"|"%") simple_expr } simple_expr ----> id | var | "(" expr ")" read_stat ----> "READ" "(" expr ")" write_stat ----> "PRINT" "(" expr ")" type ----> "int" | "float" | "boolean" id ----> intnumber | floatnumber

intnumber ----> Digit | Digit intnumber floatnumber: ----> intnumber "." intnumber

Digit ----> [0-9]+ boolean ----> "0" | "1"; var ----> [A-Z, a-z]+ block ----> program [ block ] if_stmt ----> "if" bool_stmt ":" [block] [ "else:" [block] ] "end if" while_stmt ----> "while" bool_stmt "do" [block] "end while" bool_stmt ----> and_stmt | rel_stmt |boolean and_stmt ----> bool_stmt {("and"|"or") bool_stmt} rel_stmt ----> simple_expr (">"|"<"|">="|"==") simple_expr

x Please note the following about C--: o C-- variables are not case sensitive: Var and var refer to the same variable.

All variables are declared at the beginning of your program.

2

x Sample input data:

{ Int x ; Int y ; Int z ; X = 10 ; Y = 20 ; print (x); print (x+y); read(z) z = z + x + y; print (z);

} {

if 5 > 1: {

if (4>3) and (2 <5) : {

print 1; print 2;

} else:

{ print 3; print (3+1)

} end if;

} end if;

}

In this first project, we would like to develop a lexical analyzer for C—using Python. The lexical analyzer (sometimes referred as or recognizer or simply as tokenizer) reads a string of characters and checks if a valid token in the grammar. Lexical Analysis terminology:

- Token: o Terminal symbol in a grammar o Classes of sequences of characters with a collective meaning, e.g., IDENT o Constants, Operators, Punctuation, Reserved words (keywords)

3

- Lexeme : o character sequence matched by an instance of the token, e.g. “sqrt”

Given the following expression: total = subtotal1 * 12;

- Lexical Analyzer step 1: group a stream of characters into lexemes:

t o t a l = s u b T o t a l 1 * 1 2 ;

- Lexical Analyzer step 2: Convert lexemes into tokens

The lexical analyzer should return the following:

Token (Also known as Lexeme) Token Type Total VAR_CODE (identifier) = ASSIGN_OP Subtotal1 VAR_CODE * MULTIPLY_OP 12 DIGIT_CODE (integer literal) ; SEMICOLON

□ Your lexical analyzer should include the following:

x Extract tokens from a given input string and generate the type of the token.

x Skip comments and blanks x You may need a lookup table that stores all the reserved

words of your grammar. This will be used to check whether a token is a reserved word.

x Insert user-defined tokens into a symbol table, which will be used by other components.

x Detect syntactic errors in tokens and report such errors. x Your lexical analyzer will always put the code of the next

token in a variable called nextToken. For example, if the token is an integer, nextToken will be equal to DIGIT_CODE.

Develop you lexical analyzer is Python

total = subtotal1 * 12 ;