Chapter 1
Short answer
- What three components allow us to fully specify a language? How do Tucker & Noonan end up with four principles? (which 'component' do they divide into two 'principles'?) Why?
- Name and describe the four programming paradigms. Give an example of a language particularly well-suited to each. If you choose a language that is designed to support more than one paradigm, specify what would constitute a program that follows the paradigm in question.
- Other than simplicity and readability, what are some outcomes & goals that are desirable in programming language design?
- Beyond internal theoretical issues (e.g., correctness, ease of expression), what are some external constraints that impact language design?
Chapter 2
- Be prepared to use the formalisms of (E)BNF grammars to specify the syntax of a language described in prose. For example
- L = the set of non-negative integers, including 0 but without leading zeros. Use your grammar to give parse trees for 0, 10, and 135
- L = the set of all integers, including leading '-' and optional leading '+' signs. Give parse trees for 0, 64, -128, and 256
- L = the set of strings beginning with an upper-case letter, followed by any number of lower-case letters or digits. Give parse trees for Boo, D8, and MoOo
- L = the set of strings of letters, digits, underscores and dashes, provided that (1) the first character in the string is an upper-case letter, and (2) the final character is neither an underscore or a dash. Give parse trees for B4-8, L_L, and La-Ti-Do
- L = the set of even negative integers (-2, -4, -6, ...). Give parse trees for -16, and -378.
- L = the set of odd positive integers that have an even digit as their first character (21, 23, ... 41, 43, ...). Give parse trees for 21 and 235794
- L = the set of strings axbx -- any number of a's followed by an equal number of b's. Give parse trees for "" (the empty string), aabb
- L = the set of sequences of syllables CVN, where C stands for exactly one consonant from the set {k,s,t,n,h,m,y,r,w}, V stands for exactly one of {a,i,u,e,o} and N is optional {n} (each syllable either ends with either V or Vn). give trees for watasi, wa, nihon, jin, desu
- L = the set of strings C0-3V1-2C0-2 : that is, sequences of 0-3 consonants, followed by 1-2 vowels, followed by 0-2 consonants (use {a,e,i,o,u} for vowels and all other English letters as consonants). Give parse trees for fled, bring, sprains
- Determine whether two grammars are equivalent and defend your answer.
Chapter 3
- Chomsky hierarchy, generative grammar
- Why is a right-regular grammar (or a left-regular grammar) preferable to a grammar which is neither?
- review exercises like those we did in 3.1 - 3.5.
- give a grammar for numbers in accounting format. These have the form $X,XXX,XXX.XX: leading '$', no leading zeros; commas in groups of three.
- should generate $0.99 $9.99 $999.99 $9,999.99
- should avoid generating $.99 (missing int part) $09.99 (leading zero) $,999.99 (leading comma) $0,999.99 (leading zero comma)
- Ex. 3.10: "For floating point numbers in scientific notation, give: (a) a right regular grammar; (b) a regular expression; and (c) a DFSA
Chapter 4
Define the following terms and discuss their significance to programming languages
- binding (static & dynamic)
- reserved words & predefined identifiers
- l-value & r-value
- scope, visibility, overloading
Short answer
- What are the four basic bindings for a variable?
- Given a program segment, show how static v. dynamic scoping will result in different run-time behavior (see 4.5-4.6)