CS152 EXAM 2

What does the regex [a-z]+ read as?

If input is one or more lower case characters

Executable machine code is

Machine Specific

“Compile once, run everywhere” can be achieved when the target language is

Bytecode

What are the tokens from the following: Falseif ~> scanner ~>

Identifier Falseif

What are the tokens from the following: ** ~> scanner ~>

Exp

What are the tokens from the following: * * ~> scanner ~>

Times, Times

What expression do we need for lower case identifiers?

first = 5

second = 6

total = first + second

[a-z]+

What expression do we need for the ‘+’ identifier?

first = 5

second = 6

total = first + second

\+

We are implementing a scanner for a language where the string "or" denotes a logical operator. To match  the string "or" corresponding to the OR token, which of the following regular expressions do we need?

or

For the regex 10*1, which strings of the following match?

11, 101, 1001, 10, 100, 1000001

11, 101, 1001, 1000001

Write a regex that matches both grey and gray.

gr[ae]y OR grey | gray

Write a regex for exactly 3 digits.

[0-9]{3}

Write a regex for exactly 5 lowercase letters.

[a-z]{5}

What does the expression 5 + 8.3 × 12 evaluate to according to the parse tree?

104.6

What does the expression 5 + 8.3 × 12 evaluate to according to the parse tree?

159.6

Is the following grammar ambiguous?

<expr> → <expr> PLUS <expr> | <term>
<term> → <term> TIMES <term> | <number>

<number> → INT | FLOAT

Yes, it is cascading, but doesn’t specify associativity

Is the following grammar ambiguous?

<expr> → <expr> PLUS <term> | <expr> MINUS <term> | <term>
<term> → <term> TIMES <term> | <number>

<number> → INT | FLOAT

Yes, there’s no associativity for multiplication

Based on the following grammar, what does 12 - 5 + 3 evaluate to?

<expr> → <expr> PLUS <term> | <expr> MINUS <term> | <term>
<term> → <term> TIMES <number> | <number>

<number> → INT | FLOAT

10; Evaluate the leftmost expression first (12-5), then evaluate the resulting expression ((12-5)+3)

Consider the following grammer and identify the start symbol, all nonterminals, all terminals, and the # of possible requests.

<request> → <action><target>
<action> → SEND | SAVE
<target> → FILE | MESSAGE

start symbol: <request>

requests: 2 × 2 = 4

nonterminals: <action>, <target>, <request>

terminals: SEND, SAVE, FILE, MESSAGE

Create a BNF grammar that generates one or more mneu items separated by commas. For example, this is allowed:

PIZZA PIZZA COMMA SALAD PIZZA COMMA SALAD COMMA SOUP

But this should not be allowed:

COMMA PIZZA

PIZZA COMMA

<list> → <list> COMMA <item> | <item>
<item> → PIZZA

Rewrite the following grammar so that SHIFT has higher precedence than MERGE using the separate nonterminal <term>.

<expr> → <expr> MERGE <expr> | <expr> SHIFT <expr> | ATOM

<expr> → <expr> MERGE <term> | <term>

<term> → <term> SHIFT <atom> | <atom>

<atom → ATOM

** if a term has higher precedence, it goes deeper into the recursion

Design a BNF grammar for a simple search language with AND, OR, and parenthesis such that the following combinations can be made:

TERM AND TERM

TERM OR TERM

TERM OR TERM AND TERM

LPAREN TERM OR TERM RPAREN AND TERM

<expr> → <expr> OR <term> | <term>

<term> → <term> AND <factor> | <factor>

<factor> → TERM | LPAREN <expr> RPAREN

What is the correct EBNF for the following term?

<expr> → <expr> ADD_OP <term> | <term>

<expr> → <term> {ADD_OP <term>}

What is the correct EBNF for the following term?

<term> → <term> TIMES <number> | <number>

<term> → <number> {TIMES <number>}

Which diagram is valid in the attached image?

B

Convert the following BNF into EBNF:

<playlist> → <playlist> NEXT <song> | <song>

<playlist> → <song> {NEXT <song>}

Convert the following BNF into EBNF:

<command> → RUN <program> | RUN <program> WITH <options>

<command> → RUN <program> [WITH <options>]

Convert the following BNF to EBNF:

<expr> → <value> | <expr> JOIN <value>
<value> → ITEM

<expr> → <value> {JOIN <value>}
<value> → ITEM

Does the following satisfy the condition that parsers must be able to distinguish between choices in a rule?

<factor> → LPAREN <expr> RPAREN | POSNUM

Yes, LPAREN and POSNUM are distinct

Does the following satisfy the condition that parsers cannot have a token beginning the optional part also come after the optional part?

<special> → NUMBER [<special>] NUMBER | NUMBER

No,

In the following, which tokens belong to First(<expr>)?

<expr> -> OPENPAREN OPERATOR <operands> CLOSEPAREN | POSNUM

First(<expr>) = {OPENPAREN, POSNUM}

In the following, which tokens belong to Follow(<operands>)?

<expr> -> OPENPAREN OPERATOR <operands> CLOSEPAREN | POSNUM

Follow(<operands>) = {CLOSEPAREN}

For the following, find FIRST(<expr>).

<expr> → <application> | POSNUM
<application> → OPENPAREN OPERATOR <operands> CLOSEPAREN
<operands> → <expr> [<operands>]

FIRST(<expr>) = {OPENPAREN, POSNUM}

For the following, find FIRST(<operands>).

<expr> → <application> | POSNUM
<application> → OPENPAREN OPERATOR <operands> CLOSEPAREN
<operands> → <expr> [<operands>]

FIRST(<operands>) = FIRST(<expr>) = {FIRST(<application>), POSNUM} = {OPENPAREN, POSNUM}

For the following, find FOLLOW(<operands>).

<expr> → <application> | POSNUM
<application> → OPENPAREN OPERATOR <operands> CLOSEPAREN
<operands> → <expr> [<operands>]

FOLLOW(<operands>) = {CLOSEPAREN}

The list [1,2,3] can be written as which of the following?

1:2:3:[]

What list does [5,8…20] evaluate to?

[5, 8, 11, 14, 17, 20]

What is z in the following pattern matched list?

xs = [1,2,3,4]
x:y:z = xs

[3,4]

For the following swap function, what does swap Hello evaluate to?

swap :: [a] → [a]
swap [] = []

swap [x] = [x]

swap(first:second:rest) = second:first:rest

eHllo

Given the following function, what is the result of testLazy (length [1…]) 90?

testLazy :: a → a → a

testLazy _ x = x

90

Given the following function, what is the result of testLazy (infinite 1) 5?

testLazy :: a → a → a

testLazy _ x = x

infinite x = infinite (x+1)

5

What gets printed after the following runs?

def test(first, second):

return second

def infinite(x):

return infinite(x+1)

result = test(infinite(1), 5)

print (result)

An error occurs

There are 3 implementations of a function: using pattern matching, guards, and an if/then/else clause. Which is most idiomatic?

Pattern matching

Consider the following Haskell function:

mystery []  = Nothing
mystery [x] = Nothing
mystery (_:x:_) = Just x

What does the following expression evaluate to?

mystery [9..19]

Just 10

Consider the following Haskell function definition:

mystery x y = if x then [y] else []

What is the inferred type declaration of the function mystery?

mystery :: Bool -> a -> [a]

Determine the type of the following: [1,2,3]

Num a => [a]

Determine the type of the following: \x → x * x

Num a => a → a

What is the value of map (*3) [1, 3…6]?

[3, 9, 15]

What is the value of map (>10) [5, 20, 4, 5, 23]?

[False, True, False, False, True]

What is the value of filter (> 5) [6, 1, 2, 3, 9]

[6, 9]

What is the length of the list resulting from zipWith (\x y → x*x + y*y) [1, 2] [4..200]

2

What is the resulting list from zipWith (\x y → x*x + y*y) [1, 2] [4..200]

[17, 29]

What is foldl (-) 10 [1,2,3]?

4

What is foldr (-) 10 [1,2,3]?

-8

What is foldl1 (-) [4, 3, 2, 1]?

-2

Given the following function, what is the result of ‘1 + (‘S’ “Go Spartans!”)’?

index :: Eq a => a -> [a] -> Maybe Int

index _ [] = Nothing

index y (x:xs)

| y == x = Just 0

| otherwise = let indexRest = index y xs

in case indexRest of

Nothing -> Nothing

Just i -> Just (1 + i)

An error

Evaluate the following: foldr (-) 10 [1, 2, 3]

(1 - (2 - (3 - 10))) = -8

What is the general type of addOne x = x + 1?

Num a => a → a

What is the general type of applyIncrement f x = f (x + 1)?

Num a => (a → b) → a → b

What is the general type of same (x, y) = x == y?

Eq a => (a, a) → Bool

What is the general type of twice f x = f (f x)?

(a → a) → a → a

What is the general type of pairWithList x = (x, [x])?

a → (a, [a])