Scripting Languages CS5142, Fall 2013 hw09

hw08_2 Comprehensions, Generators

(10 points) Write 4 versions of a Python subroutine cubes(n) that computes the cubes of the first n non-negative numbers (0^3,...,n^3). The four versions are:
1a.
(2 points) Using standard control-flow structures (no comprehensions of generators), returning the list of values.
1b.
(2 points) As a list comprehension, returning the list of values.
1c.
(2 points) As a generator using the yield keyword, returning a generator object such that i-th call to next() on the generator object return the i-th value.
1d.
(2 points) As a generator expression that creates a the generator object, such that i-th call to next() on the generator object return the i-th value.
1e.
(2 points) Compare and contrast the different implementations. What are the advantages (or disadvantages) of each? Your comparison should be technical in nature, so "comprehensions are cool" is not a valid answer.
Be sure to include driver code for each version demonstrating that it works to the TAs who are grading the assignment.

hw08_2 Context-Free Grammars

(20 points) Build a recursive-descent parser.
Consider the following grammar, which is written in Backus-Naur Form, uses double quotes to denote terminals, and has S as its start symbol: 

S ::= A B C
A ::= V*
B ::= W B X
    | W B Y
    |
C ::= (Z Z Z)?
V ::= "pro"
W ::= "gram"
X ::= "mar"
Y ::= "ming"
Z ::= "la"
2a.
(5 points) Show a parse tree for the string "programming". Use Nonterminal(Child, ...) notation.
2b.
(15 points) Write a Python program testgrammar.py that uses a recursive-descent parser to test whether the content of a text file is a string generated by the above grammar. Your parser should directly reflect the above context-free grammar, i.e., use one function for each nonterminal. You must not use a parser generator or library. Likewise, you must not use a regular expression library. Again, like a lot of Unix command line tools, the program accepts one or more file names as command line arguments and prints basic usage information when provided with no arguments. Here is an example of testgrammar.py in action: 

> ./testgrammar.py
Usage: testgrammar.py file ...

> ./testgrammar.py foo bar
foo: matches grammar
bar: does not match grammar
>
http://www.cs.cornell.edu/Courses/cs5142/2013fa/hw09.html