COMS W4115
Programming Languages and Translators
Homework Assignment #1
Submit solutions in pdf format on
     Courseworks/COMSW4115/Assignments
     by 2:40pm, March 4, 2015

Instructions

• Your answers must be your own words and your own code.
• Problems 1-5 are each worth 20 points.
• Solutions to these problems will be posted on Courseworks on March 9, 2015.
• This assignment may submitted on Courseworks by 2:40pm, March 9, 2015 for 50% credit.
• Be sure to put your name and uni on your answers.

Problems

1. Briefly explain the difference between
1. A compiler and an interpreter.
2. A statically typed language and a dynamically typed language.
3. A just-in-time compiler and an interpreter.
4. Top-down parsing and bottom-up parsing.
5. A functional language and an object-oriented language.


2. Let L be the language { abxba | x is any string of a's, b's and c's not containing the substring ba }.
1. Construct a minimum-state deterministic finite automaton for L.
2. Show how your DFA processes the input string abbcabcba.
3. Show how your DFA processes the input string abbcababa.
4. Construct a regular expression for L.
5. Show how your regular expression generates the input string abbcabcba.


3. Let L be the set of all strings of a's and b's with the same number of a's as b's.
1. Construct an LL(1) grammar that generates L.
2. Explain how your grammar generates L.
3. Prove that your grammar is LL(1).
4. Construct a predictive parsing table for your grammar.
5. Show how your predictive parser processes the input string abbbaa.


4. Interactive desk calculator for prefix expressions.
1. Using Lex and Yacc or their equivalents, implement an interpreter that evaluates newline-terminated input lines of prefix arithmetic expressions. The expressions may contain integers and operators for addition, subtraction, multiplication, division, and negation. The answers are to be integers. Show the Lex-Yacc code for your calculator.
2. Show the output generated by your calculator for
1. + 1 - 2 3
2. + 1 - 2


5. Let L be the language generated by the grammar S → a S b S | ε.
1. Describe L in English. E.g., L is the set of all strings of a's and b's such that . . . Using induction twice prove that your answer is correct.
2. Using the pumping lemma for regular languages prove that L cannot be specified by a regular expression.