Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CPE Exam Module 1 > Module 2: Syntax Analysis and Parsing > Flashcards

Module 2: Syntax Analysis and Parsing Flashcards

1
Q

What is the goal of syntax analysis?

a. Transform the sequence of tokens from a lexer into something useful.
b. Make sure that each of the words in a string is real words.

A

a. Transform the sequence of tokens from a lexer into something useful.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

True or False: Regular expressions are sufficient to capture all programming constructs?

a. True
b. False

A

b. False

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is each row in context-free grammars called?

a. row
b. production
c. column
d. element

A

b. production

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the correct syntactical order for context-free grammars?

a. Right arrow
b. Non-terminals
c. Non-terminals and terminals

A

b. Non-terminals on the left
a. Right arrow
c. Non-terminals and terminals on the right

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

How can you tell the difference between terminals and non-terminals?

a. Terminals are longer names
b. Terminals start with an upper case and non-terminals will be lowercase and are tokens
c. Terminals will be all lowercase and are tokens and non-terminals will start with an upper case.
d. You can’t tell the difference without any context

A

c. Terminals will be all lowercase and are tokens and non-terminals will start with an upper case.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What letter is used for the start of a non-terminal?

a. A
b. S
c. T
d. N

A

b. S

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What production is equivalent to:
S -> ɛ
S -> (S)

a. S -> (S)
b. S -> (ɛ)S
c. S -> (S)ɛ
d. S -> (S) | ɛ

A

d. S -> (S) | ɛ

Two rules can be combined using the bar symbol.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the derivations of the CFG for:

S -> (S) | ɛ

A

S => ɛ
S => (S) => (ɛ) => ()
S => (S) => ((S)) => ((ɛ)) => (())

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the derivations of the CFG for:
Exp -> Exp + Exp
Exp -> Exp * Exp
Exp -> NUM

A

Exp => Exp * Exp => Exp * 3 => Exp + Exp * 3 => Exp + 2 * 3 => 1 + 2 * 3

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are the two different ways of deriving CFG?

a. Leftmost
b. Center Out
c. Rightmost
d. Full stack

A

a. Leftmost

c. Rightmost

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is a parse tree?

a. Creating a tree from the leftmost or rightmost derveriations of CFG.
b. A tree that shows how to parse a parser
c. A flat file showing a CFG

A

a. Creating a tree from the leftmost or rightmost derveriations of CFG.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What are the major problems in parsing?

a. Ambiguous grammars
b. Parsing is super efficient
c. Parsing can be inefficient
d. There is never more than one way to parse data.

A

a. Ambiguous grammars

c. Parsing can be inefficient

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Can parsing imply operator precedence rules?

a. True
b. False

A

a. True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

When is a grammar considered to be ambiguous?

a. When there is two different leftmost derivations
b. When there is two different rightmost derivations
c. When there is two different parse trees for any string in the grammar
d. All of the above

A

d. All of the above

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What are the different types of turning trees into parse trees?

a. Bottom up
b. Top down
c. Left to right
d. Right to left

A

a. Bottom up

b. Top down

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How does Top-Down parsing work?

A

Top down parsing works like a if-elif-else statement.

17
Q

Is a predictive recurisve descent parser:

a. Bottom up
b. Top down

A

a. Top down

18
Q

What can a predictive recursive descent parser be used for?

a. Ambiguous grammar
b. Non-ambiguous grammar
c. Left to right parsing
d. None of the above

A

b. Non-ambiguous grammar

19
Q

What does FIRST(α) return?

a. The set of terminals that begin strings derived from α
b. The set of terminals that begin strings derived from ɛ
c. The set of terminals and ɛ that begin strings derived from ɛ
d. The set of terminals and ɛ that begin strings derived from α

A

d. The set of terminals and ɛ that begin strings derived from α

20
Q

What is the FIRST Set of:

S -> ABCD
A -> CD | aA
B -> b
C -> cC | ɛ
D -> dD | ɛ
A 
FIRST(S) = {a,c,d,b}
FIRST(A) = {a,c,d,ɛ}
FIRST(B) = {b}
FIRST(C) = {ɛ,c}
FIRST(D) = {ɛ,d}
21
Q

What is the FOLLOW of the following:

S -> A | B | C
A -> a
B -> Bb | b
C -> Cc | ɛ

A 
FOLLOW(S) = {$}
FOLLOW(A) = {$}
FOLLOW(B) = {$,b}
FOLLOW(C) = {$,c}
22
Q

What are the steps to calculate FOLLOW sets?

A
  1. First calculate FIRST sets
  2. Initialize FOLLOW sets to initialize empty
  3. Finally apply the following rules until FOLLOW does not change
    1. If S is the starting symbol of the grammar, then add $ to FOLLOW(S)
    2. If B -> αA, then add FOLLOW(B) to FOLLOW(A)
    3. If B -> αAC0,C1,C2…Ck and ɛ IN FIRST(C1) and ɛ in FIRST(C2)…and ɛ in FIRST(Ck) then add FOLLOW(B) to FOLLOW(A)
    4. If B -> αAC0,C1,C2…Ck, then add FIRST(C0) - {ɛ} to FOLLOW(A)
    5. If B -> αAC0,C1,C2…Ci,Ci+1…Ck, and ɛ in FIRST(C0) and ɛ in FIRST(C1) and ɛ in FIRST(C2) and …. ɛ in FIRST(Ci), then add FIRST(Ci+1) - {ɛ} to FOLLOW(A)
23
Q

What is the FOLLOW set of:

S -> ABCD
A -> CD | aA
B -> b
C -> cC | ɛ
D -> dD | ɛ
A

The first sets will be:

FIRST(S) = {a,c,d,b}
FIRST(A) = {a,c,d, ɛ}
FIRST(B) = {b}
FIRST(C) = {c, ɛ}
FIRST(D) = {d, ɛ}

So using that we can find the FOLLOW sets which are:

FOLLOW(S) = {$}
FOLLOW(A) = {b}
FOLLOW(B) = {$,c,d}
FOLLOW(C) = {$,b,d}
FOLLOW(D) = {$,b}
24
Q

What are the conditions that should be meet for a predictive parser?

a. If A -> α and A -> β, then FIRST(α) INTERSECT FIRST(β) = Null
b. If A -> α and A -> β, then FIRST(α) INTERSECT FIRST(β) = 0
c. If ɛ in FIRST(A), then FIRST(A) INTERSECT FOLLOW(A) = 0
d. If ɛ in FIRST(A), then FIRST(A) INTERSECT FOLLOW(A) = Null

A

a. If A -> α and A -> β, then FIRST(α) INTERSECT FIRST(β) = Null
d. If ɛ in FIRST(A), then FIRST(A) INTERSECT FOLLOW(A) = Null

25
Q

What are the steps to follow to write a predictive recursive descent parser for a Grammar G?

A
  1. Given a problem, create a context-free grammar (CFG) (if not given already)
  2. Calculate the FIRST and the FOLLOW sets.
  3. Check if a predictive recursive descent parser exists for the given grammar using the FIRST and the FOLLOW sets.
  4. Write the predictive recursive descent parser using the FIRST and the FOLLOW sets.

CPE Exam Module 1 (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions