程序代写代做代考 Haskell C Java Name:

Name:
Instructions
Midterm Review
CSCE 322
Please solve the problems presented below. Show your work to receive full credit; just an answer is not enough. No Approximations.
1

Question 1 (12 points)
(a) DescribeinEnglishthelanguagedefinedbytheregularexpression^([1-9][0-9]*)?[13579]$. (b) Write an unambiguous context-free grammar that generates the same language.
(c) Using your grammar from part (b), give a derivation of the string 20140213.
Page 2

Question 2 (10 points)
Consider this top-down grammar for if statements:
S → if (expression) S
S → if (expression) S else S S → other
Give two parse trees for the expression if ( expr1 ) if( expr2 ) f(); else g(); that prove this grammar is ambiguous.
Page 3

Question 3 (18 points)
Consider the following CFG for octal numbers.
O→NO O→ε
N → 0|1|2|3|4|5|6|7
Augment this grammar with attribute rules that will accumulate the value of the number into
a val attribute of the root of the parse tree.
Page 4

Question 4 (24 points)
For the regular expression ^(-)?[^0][0-9]*(‘.'[0-9]+)?$, determine which of the following inputs will match
(a) 3.14159
(b) -2
(c) F.75
(d) 0.7071
(e) .5
(f)
(g) ->
(h) F80000
Page 5

Question 5 (24 points)
Consider this top-down grammar
S →aS
S →aSbS S→ε
(a) Provide the parse tree for the input aab
(b) Is this language ambiguous? If so, provide an alternate parse tree for aab to prove it. If not, why not?
Page 6

Question 6 (26 points)
Consider the following CFG for binary numbers.
B→Z
◃ B.twice = false
B→NM Z→0
N→1
M →ZM M→NM M→ε
(a) Augment this grammar with attribute rules that will accumulate true into a twice at- tribute of the root of the parse tree if the string contains at least twice as many 1s as 0s, and false otherwise.
(b) Is your attribute grammar S-attributed?
Page 7

Question 7 (15 points)
(a) What is the input to a scanner?
(b) What is the input to a parser?
(c) What is the input to a semantic analyzer?
Page 8

Question 8 (18 points)
Consider the following CFG for hexidecimal numbers
H →NNS NS →NNS NS →ε
N→0
◃ N.value = 0
N→1
◃ N.value = 1
N→2
◃ N.value = 2
N→3
◃ N.value = 3
N→4
◃ N.value = 4
N→5
◃ N.value = 5
N→6
◃ N.value = 6
N→7
◃ N.value = 7
N→8
◃ N.value = 8
N→9
◃ N.value = 9
N→a
◃ N.value = 10
N→b
◃ N.value = 11
N→c
◃ N.value = 12
N→d
◃ N.value = 13
N→e
◃ N.value = 14
N→f
◃ N.value = 15
Augment this grammar with attribute rules that will accumulate the Decimal representation dec into the root of the parse tree.
Page 9

Question 9 (12 points)
For the regular expression ^/’*'[^*/]*’*’/$, determine which of the following inputs will match
(a) /* This is a Java comment */
(b) // This is also a Java comment
(c) — This is a Haskell comment
(d) % This is a Prolog comment
(e) /* Is *this* a Java comment? */
(f)
(g) /* What is the value of array[0]? */
(h) /* Is this a /* comment */ within a comment? */
(i) /* What is the value of x^2? */
(j) /* How much is $Texas ? */
Page 10

Question 10 (12 points) Consider this grammar
A →I=E
I →a|b|c
E →E+E E →E*E E →(E) E→I
(a) Providetheparsetreefortheinputa = b + c * a
(b) Is this language ambiguous? If so, provide an alternate parse tree for a = b + c * a to prove it. If not, why not?
Page 11

Question 11 (12 points)
Consider the following CFG for a list of numerals.
L→ε
◃ L.avg = 0
L→NL N→0
◃ N.value N→1
◃ N.value N→2
◃ N.value N→3
◃ N.value N→4
◃ N.value N→5
◃ N.value N→6
◃ N.value N→7
◃ N.value N→8
◃ N.value N→9
◃ N.value
= 0
= 1
= 2
= 3
= 4
= 5
= 6
= 7
= 8
= 9
Page 12

(a) Augment this grammar with attribute rules that will accumulate the average of the list into an avg attribute at the root of the parse tree. Hint: The first number in a list of five numbers contributes 20% of its value to the average; the average of the last four numbers accounts for the other 80% of the overall average.
(b) Is your attribute grammar S-attributed?
Page 13

Question 12 (12 points)
Create the scanner table for this finite state automata that describes optionally signed integers,
digit
digit
−
1 + 2 digit 3
Page 14

Question 13 (12 points)
(a) Provide two examples of imperative languages (b) Provide two examples of functional languages (c) Provide one example of logic languages
Page 15

Question 14 (12 points) Consider this grammar
A →I=E|I=E+E I →a|b|c
E →E*E E →(E) E→I
(a) Providetheparsetreefortheinputa = b + c * a
(b) Is this language ambiguous? If so, provide an alternate parse tree for a = b + c * a to prove it. If not, why not?
Page 16

Question 15 (12 points)
Consider the following CFG for a list of numerals.
L →NLT LT →ε
LT →,NLT
N→0
◃ N.value = 0
N→1
◃ N.value = 1
N→2
◃ N.value = 2
N→3
◃ N.value = 3
N→4
◃ N.value = 4
N→5
◃ N.value = 5
N→6
◃ N.value = 6
N→7
◃ N.value = 7
N→8
◃ N.value = 8
N→9
◃ N.value = 9
Page 17

(a) Augment this grammar with attribute rules that will accumulate the maximum of the list into a max attribute at the root of the parse tree.
(b) Is your attribute grammar S-attributed?
Page 18

Question 16 (20 points)
For the regular expression ^(<[^>]*>[A-Za-z0-9+=/]*]*>)+$, determine which of the following inputs will match
(a) HELLO
(b)

HELLO
(c) 5>4
(d) 1+1=2
(e) 5-2=3
(f)
(g) 1

OK