Brainscape's Knowledge GenomeTM

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


See full index

CS3342 > Scanning, LL Parsing, LR Parsing > Flashcards

Scanning, LL Parsing, LR Parsing Flashcards

1
Q

What do the following mean with regards to regular expressions:

  • Token
  • Alphabet
  • Epsilon
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

The arrow in regular expressions means?

A

Can be

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

What is the precedence order for the following in regular expressions:

|

.

*

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

What is a CFG?

A

A CFG is a Context Free Grammar

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

What is a CFG derivation?

A

A production from a CFG, what can be replaced in the LHS of a sentence (non-terminals) with RHS non-terminals and terminals as productions.

Note in the following example how expr is replaced

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

What does a parse tree do?

A

Represents a derivation graphically

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

What is the difference between right-most derivation and left-most derivation?

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

When a grammar can have two parse trees for the same sentence, what is it called?

A

Ambiguous grammar

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

What is an ambiguous grammar?

A

When there can be two difference parse trees for the same grammar

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

What is lexical analysis

A

Scanning:

Tokenizing the source code

Removing comments

Saving text of identifiers, numbers, strings

Saving source locations

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

What is ad-hoc

A

Ad-hoc simply means it was created by a human for the specific purpose of what it is being used for

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

What is a DFA? What does it mean? What do they look like?

A

A DFA is a deterministic finite automaton which means each state goes to one other state based on its current state and input.

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

What is a NFA? What do they look like?

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

How do you construct DFA from regular expressions?

A

Build NFA from regular expressions

Convert to DFA

Minimize DFA

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

Examine this NFA example:

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

Examine the following example for minimizing an NFA to DFA, dont move on until you understand

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

What is the “longest-possible token” rule?

A

Return only when the next character cannot continue the current token

18
Q

What is look-ahead?

A

How many characters you need to look forward to deterine the production being used

19
Q

Examine the following table-driven scanner:

A
20
Q

What is parsing?

A
21
Q

What is the difference between LL and LR parsing?

A
22
Q

Is LL parsing top-down or bottom-up?

A

Top-down

23
Q

Is LR parsing top-down or bottom-up

A

Bottom-up

24
Q

Top-down parsers are also called ____, the employ _____

A

Top-down parsers are also called LL parsers, the employ recursive descent

25
Q

LL / top-down parsers are ____ ____

A

Table driven

26
Q

A prediction in L parsing is based on

A

The current state and the input token

27
Q

With a current state and a given input token, a LL parser can take the following actions:

A
  1. match a terminal
  2. predict a production
  3. Announce a syntax error
28
Q

Examine the following LL(1) parse table and understand what it means FULLY

A
29
Q

Review the following LL(1) parse stack and how it works

A
30
Q

How do you construct First(a) and Follow(A)?

A
31
Q

What are some common problems with making a grammar LL(1)? What are their fixes?

A
32
Q

Is there a LL(1) grammar for the dangling-else problem?

A

NO

33
Q

What is the premise of an LR parser?

A

Read from input until you find a RHS, continue until you have fully reduced

34
Q

Examine how the dot productions work with LR parsing:

A
35
Q

Examine the following LR parse table:

A
36
Q

Examine the following parse table:

A
37
Q

Examine the following LR parse stack

A
38
Q

What is a shift/reduce conflict?

A
39
Q

What are two SLR conflicts?

A
40
Q

Examine the following for LL Left-recursion elimination:

A

CS3342 (10 decks)

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