Learning Objectives

With this assignment you will demonstrate:

• An understanding of formal language theory and its importance within computer science
• The ability to write grammars for both simple formal languages and for simple programming languages
• The ability to write abstract syntax specifications
• The ability to construct abstract syntax trees

Readings and Videos

Please:

• Read the Chapter 3 of Programming Language Concepts and Implementation (you will find this in BrightSpace).
• Review the course notes for Language Theory, Syntax, The Language Astro and watch all of the embedded videos in the course notes listed above. Also, follow a few of the links on the page that interest you.
• Read the Introduction and Chapter 1 of the Schmidt book. (There is information here about abstract syntax.)
• Read Chapter 1 of the Slonneger and Kurtz book.

Submission Instructions

You may work alone or in groups of at most 3 students. If you choose to pair or triple up, DO NOT “partition” the work. Letting a team member do some problems while you do others cheapens your educational experience and leaves you behind. It is best for each student to do all of the problems, then meet as a group to (1) select the “best” answer for submission when more than one exist, and (2) teach each other: that is, if one group member is unable to do one of the problems, another group member can teach that student how it do it. Everyone is responsible for understanding the entire homework submission, so everyone should contribute to the entire assignment.

Submit your work in a single beautiful PDF uploaded to BrightSpace. Please do not submit photos of handwritten answers; you need to take pride in your work.

On the PDF, include each student’s name along with the list of which of the assigned readings were done. For each reading, mark it skimmed, read, or did-not-do. Then include answers to the following:

1. Give grammars for the following mini-languages:
   1. Odd-length Palindromes of strings made from Unicode letters only
   2. All strings over the alphabet ${a, b, c, d, e}$ where the symbols are in decreasing alphabetic order
   3. $\{ 0^i1^j2^k \mid i=j \vee j=k \}$
   4. $\{ w \in \{0,1\}^* \mid w \textrm{ does not contain the substring 000} \}$
   5. $\{ w \in \{a,b\}^* \mid w \textrm{ has twice as many $a$'s as $b$'s} \}$
   6. (EXTRA CREDIT) $\{ a^nb^na^nb^n \mid n \geq 0 \}$
2. Give a programming language grammar, using the notation from class, for the programming language described as follows. Programs are made up of a possibly empty sequence of function declarations, followed by a single expression. Each function declaration is of the form $f = (p_1, \ldots, p_m) \Rightarrow e$ where $f$ is the function name (an identifier), each $p_i$ is a parameter (also identifiers) and the result (the “body”) is an expression. Expressions can be numeric literals, string literals, identifiers, function calls, or can be made up of other expressions with the usual binary arithmetic operators (plus, minus, times, divide, remainder) and a unary prefix negation and a unary postfix factorial (!). There’s a conditional expression with the syntax x ? y : z. Parentheses are used, as in most other languages, to group subexpressions. Numeric literals are non-empty sequences of decimal digits with an optional fractional part and an optional exponent part. String literals delimited with double quotes with the escape sequences \', \", \n, \\, and \u{$hhhhhh$} where $hhhhhh$ is a sequence of one-to-six hexadecimal digits. Identifiers are non-empty sequences of letters, decimal digits, underscores, and dollar signs, beginning with a letter or dollar sign. Function calls are formed with an identifier followed by a parenthesized, comma-separated list of expressions.
3. For the language in the previous problem, write an abstract syntax specification.
4. For the language in the previous problem, give an abstract syntax tree for the program:

   gcd = (x, y) => y ? gcd(y, x % y) : x
   cube = (x) => x * x * x
   "The answer is" + cube(gcd(30, 4!)) + "😦😦"
   

5. For the following complete JavaScript program, draw the AST, using the level of detail we used during class. You can use Esprima to guide you and check your work, but remember, the drawing you need to produce for full credit will be far less verbose than the Esprima output.

   import x from "x"
   console.log(93.8 * {x} << x.r[z])