Scanning, LL Parsing, LR Parsing

Question 1

What do the following mean with regards to regular expressions:

• Token
• Alphabet
• Epsilon

Answer 1

Question 2

The arrow in regular expressions means?

Answer 2

Can be

Question 3

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

|

.

*

Answer 3

Question 4

What is a CFG?

Answer 4

A CFG is a Context Free Grammar

Question 5

What is a CFG derivation?

Answer 5

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

Question 6

What does a parse tree do?

Answer 6

Represents a derivation graphically

Question 7

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

Answer 7

Question 8

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

Answer 8

Ambiguous grammar

Question 9

What is an ambiguous grammar?

Answer 9

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

Question 10

What is lexical analysis

Answer 10

Scanning:

Tokenizing the source code

Removing comments

Saving text of identifiers, numbers, strings

Saving source locations

Question 11

What is ad-hoc

Answer 11

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

Question 12

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

Answer 12

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

Question 13

What is a NFA? What do they look like?

Answer 13

Question 14

How do you construct DFA from regular expressions?

Answer 14

Build NFA from regular expressions

Convert to DFA

Minimize DFA

Question 15

Examine this NFA example:

Answer 15

Question 16

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

Answer 16

Question 17

What is the “longest-possible token” rule?

Answer 17

Return only when the next character cannot continue the current token

Question 18

What is look-ahead?

Answer 18

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

Question 19

Examine the following table-driven scanner:

Answer 19

Question 20

What is parsing?

Answer 20

Question 21

What is the difference between LL and LR parsing?

Answer 21

Question 22

Is LL parsing top-down or bottom-up?

Answer 22

Top-down

Question 23

Is LR parsing top-down or bottom-up

Answer 23

Bottom-up

Question 24

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

Answer 24

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

Question 25

LL / top-down parsers are ____ \_\_\_\_

Answer 25

Table driven

Question 26

A prediction in L parsing is based on

Answer 26

The current state and the input token

Question 27

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

Answer 27

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

Question 28

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

Answer 28

Question 29

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

Answer 29

Question 30

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

Answer 30

Question 31

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

Answer 31

Question 32

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

Answer 32

NO

Question 33

What is the premise of an LR parser?

Answer 33

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

Question 34

Examine how the dot productions work with LR parsing:

Answer 34

Question 35

Examine the following LR parse table:

Answer 35

Question 36

Examine the following parse table:

Answer 36

Question 37

Examine the following LR parse stack

Answer 37

Question 38

What is a shift/reduce conflict?

Answer 38

Question 39

What are two SLR conflicts?

Answer 39

Question 40

Examine the following for LL Left-recursion elimination:

Answer 40