LR Parser

Question 1

LR Parser

Answer 1

input is scanned left-to-right and a rightmost derivation is constructed

Question 2

SLR

Answer 2

simple LR

Question 3

LALR

Answer 3

look ahead LR

Question 4

What is the most general grammar?

Answer 4

LR

Question 5

What is the most specific grammar?

Answer 5

SLR

Question 6

LR parsers to time and space __________ in the size of input

Answer 6

linear

Question 7

Which is more powerful, LR or LL?

Answer 7

LR

Question 8

Which is more natural, LR or LL?

Answer 8

LR

Question 9

Disadvantages of LR grammar?

Answer 9

harder to write parser, larger table size, more difficult error repair

Question 10

What does the stack represent in a bottom up parser?

Answer 10

summary of input already seen

Question 11

shift operation

Answer 11

shif the next input token from the input to the top of the stack

Question 12

reduce operation

Answer 12

pop N symbols on stack that match a RHS of production and push non-term

Question 13

What type of derivation is constructed for LR?

Answer 13

reverse rightmost derivation

Question 14

reduction

Answer 14

each step of building the parse tree (add a new nonterm as parent of subtree)

Question 15

What actions can an LR parser perform?

Answer 15

shift, reduce, accept, reject

Question 16

What are symbols pushed onto LR parser’s stack?

Answer 16

states

Question 17

2 tables of LR parsers:

Answer 17

action table

goto table

Question 18

action table

Answer 18

indexed by the top-of-stack symbol and current token, tells which action to perform

Question 19

What is different for different LR parsers?

Answer 19

definition of an item
number of states in underlying state machine
amount of information in a state

Question 20

item

Answer 20

production with a dot somewhere on the rhs

Question 21

for an item to the right of a dot

Answer 21

look for productions with a LHS of that symbol, then add to the closure

Question 22

Closure(I) tells you what?

Goto(I,X) tells you what?

Answer 22

where we might be in the parse

where we might be after parsing X

Question 23

When is a grammar not in SLR(1)

Answer 23

When there is a conflict in the SLR Action Table

Question 24

2 types of conflicts for

Answer 24

shift/reduce

reduce/reduce

Question 25

shift/reduce

Answer 25

it is not possible to determine based on the top-of-stack state symbol and current token to shift or reduce

Question 26

reduce/reduce

Answer 26

not possible to determine which grammar rule to reduce by