# 語法理論

Syntactic structure (Chromsky)

LR parser

# 遞迴下降剖析法

Recursive Decendent
First(x) = { a <in> Vt | a => *aB} <U> { if a =>* r then {r} else <NIL>
Follow(A) = { a <in> Vt | S =>+ … Aa … } <U> {if S=>+ aA then {r} else <NIL> }
LL(1) Grammer
Predict ( A —> X1…Xm ) =
if r <in> First(X1,…,Xm)
(First(X1,…,Xm) - r) <U> Follow(A)
else
First(X1,…,Xm)
Grammer G is LL(1) <=> Predict(A -> a) <I> Predict(A -> b) = <NIL>
LL(1) Parser
puch(s)
while (! stack_empty())
if ( is_nonterminal(stack_top) and T[stack_top][token] = X -> Y1,…,Ym )
pop(1)
push Ym,Ym-1,…, Y1 onto stack
else if is_terminal(stack_top) and stack_top = token
pop(1)
get_next_token
else
error
LL(1) 的困難有 1. common prefix 2. left recursion

# Shift-Reduce 剖析法

Shift - Reduce Parser
s0 s1 … sm | a1 a2 … ai … \$
driver ——> output
action table | goto table
Shift-Reduce Driver()
push s0
while true
switch (action[s][T]
case shift :
push(go_to[s][T]
get_next_token(T)
case reduce : (Assume i th production is X->Y1,…,Ym)
pop(m)
push(go_to[s][x])