QxRed » 日志 » LR(1)分析器
LR(1)分析器
风暴红QxRed 发表于 2008-02-20 08:34:13
Build FIRST:
for each X \in N, FIRST(X)=NULL;
for each x \in T, FIRST(x)={x};
do
OLD_FIRST=FIRST;
for each generation X-> alpha_1 alpha_2 ... alpha_k
if alpha_1 alpha_2 ... alpha_k == e
FIRST(X)+={e};
else
add_e=true;
for i=1 to k and add_e
FIRST(X) += FIRST(alpha_i)-{e};
if e \not\in FIRST(alpha_i)
add_e=false;
if add_e
FIRST(X) += {e};
while OLD_FIRST!=FIRST;
output FIRST;
Build FOLLOW:
for start state S, FOLLOW(S) = #;
for each X \in N, FOLLOW(X)=NULL;
for each x \in T, FOLLOW(x)=NULL;
do
OLD_FOLLOW=FOLLOW;
for each generation X-> alpha_1 alpha_2 ... alpha_k
FOLLOW(alpha_k)+=FOLLOW(X);
FOLLOW_X=FOLLOW(X);
for i=k to 2
if e \not\in FIRST(alpha_i)
FOLLOW_X=NULL;
FOLLOW(alpha_{i-1})+=FIRST(alpha_i)-{e} + FOLLOW_X;
while OLD_FIRST!=FIRST;
output FIRST;
build CLOSURE:
for each iterm set I
CLOSURE(I)=I;
OLD_CLOSURE(I)=CLOSURE(I);
do
for each [X->alpha_1 . Y alpha_2 ,a] in I,
for each b \in FIRST(alpha_2 a), each generator Y->.gama
CLOSURE(I)+={[Y->.gama, b]}
while OLD_CLOSURE(I)!=CLOSURE(I);
build GO:
for iterm set I,
GO(I,zeta)=CLOSURE({ [X->alpha zeta . beta, a]|[X->alpha . zeta beta, a] \in I})
build GO_SET C:
build FIRST;
build FOLLOW;
I_1=CLOSURE({S'->[.S,#]})
C={I_1}
s=1;
do
OLD_C=C;
for each item [X->alpha .zeta beta, a] in I_i
I=GO(I_i,zeta);
j=index of I \in C;
if I \not\in C
C+=I;
j=|C|;
I_j=I;
I_j=GO(I_i,a);
while OLD_C!=C;
build ACTION, GOTO table:
build GO_SET C;
for i=1 to n
for each item [X-> ... , b] in I_i
if item has form [X-> alpha . a beta, b]
I_j=GO(I_i,a);
ACTION(i,a)=sj;
else if item has form [X-> alpha a. , b]
j=index of generator X-> alpha a;
ACTION(i,b)=rj;
else if iterm is [S'->S. , #]
ACTION(i,#)=acc;
for each X
GOTO(i,X)=GO(i,X);
recognition:
state_stack={1};
symbol_stack=NULL;
add "#" to the end of input_string queue s=a_1 a_2 ... a_n
while true
action=ACTION(state_stack.top(),s.head())
if action==sj
state_stack.push(j);
symbol_stack.push(s.head())
s.pop();
else if action==rj
get j th generator X-> alpha_1,...,alpha_k
state_stack.pop(k);
symbol_stack.pop(k);
symbol_stack.push(X);
state_stack.push(GOTO(state_stack.top(),X))
else if action==acc
return success;
else
return error;
example:
S->BB
B->aB
B->b
reform the grammar:
1) S'->S
2) S->BB
3) B->aB
4) B->b
build FIRST_SET and FOLLOW_SET:
|
|
FIRST
|
FOLLOW
|
|
S'
|
a,b
|
#
|
|
S
|
a,b
|
#
|
|
B
|
a,b
|
a,b,#
|
|
a
|
a
|
a,b
|
|
b
|
b
|
b
|
build GO_SET:
(here the index start with 0)
start with [S'->.S,#]
I_0=CLOSURE({[S'->.S,#]})
=
[S'->.S,#]
[S->.BB,#]
[B->.aB,a/b]
[B->.b,a/b]
Here a/b comes from FIRST(B #)={a,b}
Build other SETS in the same way
Build ACTION and GOTO table:
Recognition example:
abab#
|
state_stack
|
symbol_stack
|
string_queue
|
action
|
|
0
|
|
abab#
|
s3
|
|
03
|
a
|
bab#
|
s4
|
|
034
|
ab
|
ab#
|
r3
|
|
038
|
aB
|
ab#
|
r2
|
|
02
|
B
|
ab#
|
s6
|
|
026
|
Ba
|
b#
|
s7
|
|
0267
|
Bab
|
#
|
r3
|
|
0269
|
BaB
|
#
|
r2
|
|
025
|
BB
|
#
|
r1
|
|
01
|
S
|
#
|
acc
|
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾
