Syntax Analysis

Question 1

How is a CFG defined?

Answer 1

N: a set of non-terminals
T: a set of terminals
P: a set of production rules
S: a start non-terminal

Question 2

Why are ambiguous grammars problematic?

Answer 2

Different parse trees may have different meaning - may not know which one to select.

Question 3

What are PDAs?

Answer 3

Pushdown automata.
A word is accepted once it is read and the stack is empty.

An instance description/ID is a triple (q, w, a) where:
q = current state
w = word to read
a = current stack.

Question 4

What are the two different kinds of parsers?

Answer 4

Top-Down (Recursive Descent): Construct parse tree from root - LEFTMOST.

Bottom-Up: Construct parse tree from leaves - RIGHTMOST.

Question 5

What are some issues with LL(k) parsers?

Answer 5

Must choose a derivation rule based on k tokens only.
Requires eliminating left recursions.
Some grammars are not LL(1) - 1 symbol being enough to decide which rule to apply.

Question 6

How do LR(k) parsers work?

Answer 6

Initially:
- input string to parse: w$
- stack: $ (start symbol)

Algorithm:
- shift input symbols to stack
- reduce a string B of grammar symbols on top of the stack to the head of the appropriate production rule.
- repeat until stack has start symbol + input is empty, or error