Posted Friday, September 2, 2022 Due Friday, September 16, 2022
Note: Lecture 2 covers material for problems 1-3. Lectures 3 and 4 cover problems 4-5.
Problem 1 (10pts). Describe in English the languages denoted by the following regular expres- sions.
(a) (2pts) a(a|b)∗a (b) (2pts) (b*(ε|a))*
Copyright By PowCoder代写 加微信 powcoder
(c) (2pts) (a|b)∗a(a|b)(a|b) (d) (2pts) a*ba*ba*ba*
(e) (2pts) (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*
Note: Your description should be the most general high-level characterization. For example, (ba*ba*)* should be described as “All strings of a’s and b’s, beginning with b and having even number of b’s.” not as, for example, “The string of b followed by any number of a’s followed by a b followed by any number of a’s, repeated any number of times.”.
Problem 2 (10pts). The following grammar generates numbers in binary notation. C is the start symbol.
(1) C → C 0 | A 1 | 0 (2) A → B 0 | C 1 | 1 (3) B → A 0 | B 1
(a)(2pts) Construct a derivation that generates the binary notation of 21. (b)(4pts) Prove that the generated numbers are multiples of 3.
(c)(4pts) Prove that all such numbers are generated by the grammar.
Note: To receive full credit your answer must set up a proof and clearly state the key steps/arguments. Be concise and use mathematical notation instead of prose as much as possible. Overly verbose answers may incur a penalty.
Problem 3 (10pts). The following is an ambiguous expression grammar with one unary operator ∗ and n binary infix operators, θ1, θ2, …, θn, at n different levels of precedence:
expr → expr θ1 expr | expr θ2 expr | … | expr θn expr | expr∗ | (expr) | id
(a) (2pts) Show that the grammar is ambiguous.
(b) (8pts) Construct an equivalent unambiguous grammar such that binary operators θ1, θ2, …, θn
are all left-associative. Unary operator ∗ has the highest precedence. θn has precedence over θn−1, θn−1 has precedence over θn−2 and so on, and θ1 has the lowest precedence.
Problem 4 (10pts). Consider the following LL(1) grammar for a simplified subset of Lisp:
E → atom E→’E
E → (EEs) Es → EEs
atom, ’, (, ), and $$ are the terminals (tokens), and P, E and Es are the nonterminals.
(a) (3pts) (b) (3pts)
(c) (4pts)
What is FOLLOW(Es)? FOLLOW(E)? PREDICT(Es → ε)?
Give a parse tree for the string (cdr ’(a b c)) $$. Note: keyword cdr and identifiers a, b, and c are atoms.
Consider a recursive descent parser running on the same input. At the point where the quote token (’) is matched, which recursive descent routines will be active (i.e., what routines will have a frame on the run-time stack)?
Problem 5 (10pts). For each grammar below, determine if it is LL(1) or not and if it is ambiguous or not. You do not need to justify your answer, just write YES or NO. As an example of the format for answers we are looking for: (x) LL(1): YES, Ambiguous: YES.
(a)(2pts) A→0A1|01 (b)(2pts) A→+AA| ∗ AA|a
(c)(2pts) A→A(A)A|ε
(d) (2pts) A → B a | b B c | d c | b d c B → d
(e)(2pts) S→CaCb|DbDa C→ε D→ε
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com