- G = (N, T, P, S). ( -) G.
- , . . 4.1.
|
. , S. S X1X2..., S. , X1, .., , , , Y a.... .
. 4.2 , . .
|
- , (), , () .
, $ - . .
- M[A, a], A - , a - $. M[A, a] .
$ . $ .
. , S$, w$ (w - ), . X - a - . . .
1. X = a = $, , .
2. X = a $, X .
3. X - , X a, , .
4. X - , M[X, a]. :
- M[X, a] X. X , . .
- M[X, a] . , .
:
|
|
do {X= ; if (X - || X=="$") if (X==InSym) { X ; InSym= ; } else error(); else /*X - */ if (M[X,InSym]=="X->Y1Y2...Yk") { X ; Yk,Yk-1,...Y1 (Y1 ); X->Y1Y2...Yk; } else error(); /* M */ } while (X!=$) /* */ |
4.3. G = ({E, E', T, T', F}, {id, +, *, (,)}, P, E) :
E TE' | T' *FT' | ||
E' +TE' | T' e | ||
E' e | F (E) | ||
T FT' | F id | ||
. 4.3. .
|
id + id * id$ , . 4.4. , . , . . 4.5.
| ||
|
FIRST FOLLOW
- FIRST FOLLOW.
G = (N, T, P, S) - -. - , , FIRST() , , . *e, e FIRST().
FOLLOW(A) A a, A , .. a , S * Aa , (N T)*. , A a , e. A , $ FOLLOW(A).
FIRST.
4.3. FIRST .
. - G = (N, T, P, S).
. FIRST(X) X (N T).
. 1-3:
- X - , FIRST(X) = {X}; X - , FIRST(X) = .
- P X e, e FIRST(X).
- FIRST(X) , :
X - X Y 1Y 2...Y k, a FIRST(X), a FIRST(Y i) i, 1 i k, e FIRST(Y 1),..., FIRST(Y i-1), Y 1...Y i-1 *e. e FIRST(Y j) j = 1, 2,..., k, e FIRST(X).
4.4. FIRST .
. - G = (N, T, P, S).
. FIRST(X1X2...Xn), Xi (N T).
. 1-3:
- FIRST(X) X (N T).
- FIRST(X1X2...Xn) = .
- FIRST(X1X2...Xn) e- FIRST(X1). e- FIRST(X2), e FIRST(X1), e- FIRST(X3), e FIRST(X1), FIRST(X2), .. , e FIRST(X1X2...Xn), e FIRST(Xi) i.
|
|
FOLLOW.
4.5. FOLLOW .
. - G = (N, T, P, S).
. FOLLOW(X) X N.
. 1-4:
- FOLLOW(X) = X N.
- $ FOLLOW(S).
- P e A B , , (N T)* FIRST(), e, FOLLOW(B).
- FOLLOW(X), :
P A B A B , , (N T)*, FIRST() e (.. *e), FOLLOW(A) FOLLOW(B).
4.4. 4.3.
FIRST(E) = FIRST(T) = FIRST(F) = {(, id} | |
FIRST(E') = {+, e} | |
FIRST(T') = {*, e} | |
FOLLOW(E) = FOLLOW(E') = {), $} | |
FOLLOW(T) = FOLLOW(T') = {+,), $} | |
FOLLOW(F) = {+, *,), $} | |
, id FIRST(F) 3 i = 1, FIRST(id) = {id} FIRST(() = {(} 1. 3 i = 1, T FT' FIRST(T) id . 2 FIRST(E') e.
FOLLOW 2 FOLLOW(E) $. 3, F (E), FOLLOW(E) . 4, E TE', FOLLOW(E') $ . E' *e, FOLLOW(T). E TE', 3 FOLLOW(T) FIRST(E'), e.