Compiler Paper

Instructions: 1. PLEASE ANSWER ALL QUESTIONS. 2. PLEASE WRITE THE QUESTION NUMBER AND ITEM NEXT TO EACH OF YOUR ANSWERS (Examples: Question 2.a., Question 3.c., Question 4.g. etc.) 3. WRITE YOUR ANSWERS ON CLEAN SHEETS. 4. WRITE BRIEFLY AND NEATLY. 5. PLEASE SCAN YOUR ANSWER SHEET THEN UPLOAD IT INTO BLACKBOARD. YOU ARE ONLY ALLOWED ONE ATTEMPT. NO EMAIL SUBMISSION WILL BE ACCEPTED 6. PLEASE WRITE YOUR FIRST NAME, LAST NAME, AND NUMBER. 7. PLEASE TURN IN YOUR GENUINE ANSWERS. DON’T SHARE YOUR ANSWERS WITH ANYONE. ANY VIOLATION FOUND WILL RESULT IN FAILING THE COURSE AND BEING REPORTED TO THE DEPARTMENT. 8. IN ANY GIVEN GRAMMAR, SYMBOLS IN BOLD ARE TERMINALS WHILE SYMBOLS IN ITALIC ARE NONTERMINALS. 9. IF YOU HAVE NO ACCESS TO A SCANNER, YOU CAN USE A PHONE APP TO SCAN YOUR ANSWER SHEETS. ALL OF YOUR ANSWERS MUST BE SUBMITTED IN ONE PDF FILE ON BLACKBOARD. 10. GOOD LUCK! Q.1. Write a Lex input file that will produce a scanner that capitalizes all comments in a C program. Moreover after replicating its input program in the terminal (or in a file), the scanner should append the total number of comments to its output. Your scanner should be able to accept optional command line arguments to indicate the input and output filenames. Please consider using toupper(char c) from <ctype.h> to convert to uppercase. Q.2. Write a rule in Lex to print integer numbers that are multiple of five. The numbers are allowed to have an optional sign (+/-). You are not neither allowed to convert the matched strings into integers, nor to use the modulus operator (%) in your rule. Q.3. Give only the rule section of a Lex input file for a scanner that prints only all the letters in its input on screen, and ignores everything else. Q.4. Answer the following: a) Write down an unambiguous grammar that generates the set of strings { s; , s;s; , s;s;s; , … }. The semicolon should be right associative. b) Give a leftmost and a rightmost derivation for the string s;s; using your grammar. Q.5. Given the grammar exp → exp + term | exp − term | term term → term * factor | factor factor → ( exp ) | number a) Write down a parse tree and abstract syntax tree for the expressions 3+4*5-6. b) On the parse tree, number the nodes to represent a rightmost derivation. Q.6. Consider the following grammar representing simplified LISP-like expressions lexp → atom | list atom → number | identifier list → ( seq ) seq → seq lexp | lexp a) Draw a parse tree for the LISP expression (a 23 (m x y)). Number the nodes in the tree to represent a leftmost derivation. There are one number and 4 identifiers in the given expression besides the parentheses. b) Translate the given grammar into EBNF. c) Draw syntax diagrams for the EBNF from part (b). Q.7. Give a grammar that generates the following set of strings a) { aⁿ bⁿ⁺¹ | n ≥ 0 }. b) { aⁿ⁺¹cbⁿ | n ≥ 0 }. Q.8. Given the following grammar statement → if-stmt | other | ε if-stmt → if ( exp ) statement else-part else-part → else statement | ε exp → 0 | 1 a) Is the grammar ambiguous? Justify your answer (with examples if applicable) b) Draw a parse tree for the string if(0) if(1) other else else other c) What is the purpose of the two else’s in the given string?