, :
a) A a, a Î (VT È VN)* ;
b) A a1a1 | a2a2 |... | anan, ai Î VT i = 1,2,...,n; ai ¹ aj i ¹ j; ai Î (VT È VN)*, . . , , .
, , .
, : , -, ? , , , .. .
, . :
(1) , , - - (, , ..).
:
L a | a,L ( L a {,a})
, .. .
, a,a,a,a,a L a, a,a, a,a,a,a,a. , , L. , ( ), .
L :
void L()
{ if (c!= 'a') ERROR();
while ((c = fgetc(fp)) == ',')
if ((c = fgetc(fp))!= 'a') ERROR();
}
, , , L, ( - ), L , L. , B - L ,
S LB^
L a {, a}
B ,b
, -, ,,,b , .
, , , .
(2) , , .. , .
|
|
a) , , ..
A Aa1 |... | Aan | b1 |... | bm,
ai Î (VT È VN)+, bj Î (VT È VN)*, i = 1, 2,..., n; j =1, 2,..., m, - .
:
A b1A |... | bmA
A a1A |... | anA | e
, , .. A - bj {ai}, i = 1,2,...,n; j = 1,2,...,m.
b) , , ..
A aa1 | aa2 |... | aan | b1 |... |bm,
a Î VT; ai, bj Î (VT È VN)*, - . , :
A aA | b1 |... | bm
A a1 | a2 |... | an
, .
c) , , , , ..
A B1a1 |... | Bnan | a1b1 |... | ambm
B1 g11 |... | g1k
...
Bn gn1 |... | gnp,
Bi Î VN; aj Î VT; ai, bj, gij Î (VT È VN)*, Bi , A :
A g11a1 |... | g1ka1 |... | gn1an |... | gnpan | a1b1 |... | ambm
d) , ..
A a1a1 |... | anan | e,
( , ).
, G = ({a,b}, {S,A}, P, S),
P: S bAa
A aA | e
-, , :
void S(void)
{if (c == b) {c = fgetc(fp); A();
if (c!= a) ERROR();}
else ERROR();
}
void A(void)
{if (c == a) {c = fgetc(fp); A();}
}
baaa A() ; , - , S. , baaa , , .
, , , A, , , .
G = ({a,b,}, {S,A}, P, S),
P: S bA
A aA | e
.
, e- -.
: FIRST(A) - , ,
G = (VT, VN, P, S), .. FIRST(A) = { a Î VT | A Þ aa, A Î VN, a Î (VT È VN)*}.
: FOLLOW(A) - , ,
G = (VT, VN, P, S), .. FOLLOW(A) = { a Î VT | S Þ aAb, b Þ ag, A Î VN, a, b, g Î (VT È VN)*}.
|
|
, FIRST(A) Ç FOLLOW(A) ¹ Æ, .
A a1A |... | anA | b1 |... | bm| e
B aAb
FIRST(A) Ç FOLLOW(A) ¹ Æ (- ), :
B aA
A a1A |... | anA | b1b |... |bmb| b
A a1A |... | anA | b1 |... |bm| e
, .. B - a {ai} bj b a {ai} b.
A , , , , .
-. -, , , , , - , n cn. LL(k)-, LR(k)-, (., , [2], [3]).