Homework 5
Last updated: Sat, 22 Oct 2022 12:37:33 -0400
Out: Mon Oct 17, 00:00 EST Due: Sun Oct 23, 23:59 EST
This assignment explores context-free languages.
Homework Problems
Context-Free Grammars and String Derivations (9 points)
Design a CFG, Including Whitespace? (10 points)
Design a PDA, Including Whitespace? (10 points)
README (1 point)
Total: 30 points
Submitting
Submit your solution to this assignment in Gradescope hw5. Please assign each page to the correct problem and make sure your solutions are legible.
A submission must also include a README containing the required information.
1 Context-Free Grammars and String Derivations
Here’s a CFG, called PY, representing a small Python-like language:
Updated 2022-10-22: semicolons inserted between STMT
\left\langle STMTS\right\rangle | \rightarrow | \left\langle STMT\right\rangle; \left\langle STMTS\right\rangle \mid \left\langle STMT\right\rangle |
\left\langle STMT\right\rangle | \rightarrow | \left\langle ID\right\rangle \texttt{=} \left\langle EXPR\right\rangle \mid \texttt{if} \left\langle EXPR\right\rangle\texttt{:} \left\langle STMT\right\rangle \texttt{else:} \left\langle STMT\right\rangle |
\mid \texttt{print(} \left\langle EXPR\right\rangle \texttt{)} \mid \left\langle EXPR\right\rangle | ||
\left\langle EXPRS\right\rangle | \rightarrow | \left\langle EXPR\right\rangle, \left\langle EXPRS\right\rangle \mid \left\langle EXPR\right\rangle \mid \varepsilon |
\left\langle EXPR\right\rangle | \rightarrow | \left\langle ID\right\rangle \mid \left\langle NUM\right\rangle \mid \left\langle EXPR\right\rangle \texttt{==} \left\langle EXPR\right\rangle \mid \left\langle EXPR\right\rangle \texttt{+} \left\langle EXPR\right\rangle |
\mid \left\langle TUP\right\rangle \mid \texttt{lambda (} \left\langle IDS\right\rangle \texttt{) :} \left\langle EXPR\right\rangle \mid \left\langle ID\right\rangle\texttt{(} \left\langle EXPRS\right\rangle \texttt{)} | ||
\left\langle TUP\right\rangle | \rightarrow | \mid \texttt{(} \left\langle EXPRS\right\rangle \texttt{)} |
\left\langle NUM\right\rangle | \rightarrow | 0\mid 1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9 |
\left\langle IDS\right\rangle | \rightarrow | \left\langle ID\right\rangle \texttt{,} \left\langle IDS\right\rangle \mid \left\langle ID\right\rangle \mid \varepsilon |
\left\langle ID\right\rangle | \rightarrow | \texttt{a}\mid\texttt{b}\mid\texttt{c}\mid\cdots\mid\texttt{x}\mid\texttt{y}\mid\texttt{z} |
(Yes, real-world languages are much more complicated than textbook examples.)
The variables of the CFG are all the names enclosed in angle brackets, e.g., \left\langle EXPR\right\rangle is a variable name. All other symbols used in the rules are terminals.
Note, however, that unlike Python, this grammar ignores whitespace (so your answers to this problem do not need to explicitly deal with whitespace).
Give two strings in PY’s language by showing their derivation steps. Each given string must have at least five derivation steps (and cannot be the strings in part 3).
Give a formal description of the grammar PY. You may assume that the given rules are in a set called \textit{RULES}.
- Give parse trees for the following strings in the language of PY:
Updated 2022-10-22: newlines in 3b replaced with semicolons
\texttt{if x == 9: print((a,b,c)) else: print(0)}
\texttt{a = 1; f = lambda(x): x + a; f(5)}
2 Design a CFG, Including Whitespace?
The first problem, Context-Free Grammars and String Derivations, ignored whitespace. This problem will try to see if a CFG can enforce at least some whitespace constraints.
Prove that the following language B, which contains a subset of Python if statements, is a CFL. Do this by designing a CFG that describes B.
Specifically, B is a language over alphabet \Sigma = \left\{\texttt{a},\ldots,\texttt{z},0,1\ldots,9,\texttt{\_},\texttt{=},\texttt{:}\right\} (the \texttt{\_} char represents a space) that contains strings of the following form:
2022-10-18: Added clarification: give subscripts to num
var\in\left\{\texttt{a},\ldots,\texttt{z}\right\}
num,num_1,num_2\in\left\{0,1,\ldots,9\right\}
indent_1,indent_2\in\texttt{\_\_}^*
|indent_1|=|indent_2|
3 Design a PDA, Including Whitespace?
Create a PDA that recognizes the B language from problem Design a CFG, Including Whitespace?.
Drawing the state diagram is sufficient. You may also use the shorthands discussed in class and the Textbook, for example, having one transition read multiple input characters, or push multiple input characters onto the stack.