缂栬瘧鍘熺悊涔犻瑙ｇ瓟
椤?/p>
1/1
绗簲绔?/p>
鑷《鍚戜笅璇硶鍒嗘瀽鏂规硶
1
锛庡鏂囨硶
G[S]
S
飪?/p>
a|
鈭?/p>
|(T)
T
飪?/p>
T,S|S
(1)
缁欏嚭
(a,(a,a))
鍜?/p>
(((a,a),
鈭?/p>
,(a)),a)
鐨勬渶宸︽帹瀵笺�?/p>
(2)
瀵规枃娉?/p>
G
锛岃繘琛屾敼鍐欙紝鐒跺悗瀵规瘡涓潪缁堢粨绗﹀啓鍑轰笉甯﹀洖婧殑閫掑綊瀛愮▼搴忋�?/p>
(3)
缁忔敼鍐欏悗鐨勬枃娉曟槸鍚︽槸
LL(1)
鐨勶紵缁欏嚭瀹冪殑棰勬祴鍒嗘瀽琛ㄣ�?/p>
(4)
缁欏嚭杈撳叆涓?/p>
(a,a)#
鐨勫垎鏋愯繃绋嬶紝骞惰鏄庤涓叉槸鍚︿负
G
鐨勫彞瀛愩�?/p>
瑙ｏ細
(1) (a,(a,a))
鐨勬渶宸︽帹瀵间负
S
飪?/p>
(T)
飪?/p>
(T,S)
飪?/p>
(S,S)
飪?/p>
(a,(T))
飪?/p>
(a,(T,S))
飪?/p>
(a,(S,a))
飪?/p>
(a,(a,a))
(((a,a),
鈭?/p>
,(a)),a)
鐨勬渶宸︽帹瀵间负
S
飪?/p>
(T)
飪?/p>
(T,S)
飪?/p>
(S,a)
飪?/p>
((T),a)
飪?/p>
((T,S),a)
飪?/p>
((T,S,S),a)
飪?/p>
((S,
鈭?/p>
,(T)),a)
飪?/p>
(((T),
鈭?/p>
,(S)),a)
飪?/p>
(((T,S),
鈭?/p>
,(a)),a)
飪?/p>
(((S,a),
鈭?/p>
,(a)),a)
飪?/p>
(((a,a),
鈭?/p>
,(a)),a)
(2)
鐢变簬鏈?/p>
T
飪?/p>
T,S
鐨勪骇鐢熷紡锛屾墍浠ユ秷闄よ浜х敓寮忕殑宸﹂�掑綊锛屽涓竴涓潪缁堢粨绗?/p>
U
鏈夋柊鐨勬枃娉?/p>
G
/
[S]:
S
飪?/p>
a|
鈭?/p>
|(T)
T
飪?/p>
SU
U
飪?/p>
锛?/p>
SU|
蔚
鍒嗘瀽瀛愮▼搴忕殑鏋勯�犳柟娉?/p>
瀵规弧瓒虫潯浠剁殑鏂囨硶鎸夊涓嬫柟娉曟瀯閫犵浉搴旂殑璇硶鍒嗘瀽瀛愮▼搴忋�?/p>
(1)
瀵逛簬姣忎釜闈炵粓缁撳彿
U
锛岀紪鍐欎竴涓浉搴旂殑瀛愮▼搴?/p>
P(U)
锛?/p>
(2)
瀵逛簬瑙勫垯
U::=x1|x2|..|xn,
鏈変竴涓叧浜?/p>
U
鐨勫瓙绋嬪簭
P(U),P(U)
鎸夊涓嬫柟娉曟瀯閫狅細
IF CH IN FIRST(x1) THEN P(x1)
ELSE IF CH IN FIRST(x2) THEN P(x2)
ELSE ...
.
.
.
IF CH IN FIRST(xn) THEN P(xn)
ELSE ERROR
鍏朵腑锛?/p>
CH
瀛樻斁褰撳墠鐨勮緭鍏ョ鍙凤紝鏄竴涓叏绋嬪彉閲忥紱
ERROR
鏄竴娈靛鐞嗗嚭閿欎俊鎭殑绋嬪簭锛?/p>
P(xj)
涓虹浉搴旂殑瀛愮▼搴忋�?/p>
(3)
瀵逛簬绗﹀彿涓?/p>
x=y1y2...yn;p(x)
鐨勫惈涔変负锛?/p>
BEGIN
P(y1);
P(y2);
...
P(yn);
END
濡傛灉
yi
鏄潪缁堢粨绗︼紝鍒?/p>
P(yi)
浠ｈ〃璋冪敤澶勭悊
yi
鐨勫瓙绋嬪簭锛?/p>
濡傛灉
yi
鏄粓缁撶锛屽垯
P(yi)
涓哄舰濡備笅杩拌鍙ョ殑涓�娈靛瓙绋嬪簭
IF CH=yi THEN READ(CH) ELSE ERROR
鍗冲鏋滃綋鍓嶆枃娉曚腑鐨勭鍙蜂笌杈撳叆绗﹀彿鍖归厤锛屽垯缁х画璇诲叆涓嬩竴涓緟杈撳叆绗﹀彿鍒?/p>
CH
涓紝
鍚﹀垯琛ㄦ槑鍑洪敊銆?/p>
(4)
濡傛灉鏂囨硶涓湁绌鸿鍒?/p>
U::=EPSILON,
鍒欑畻娉曚腑鐨勮鍙?/p>
IF CH IN FIRST(xn) THEN P(xn)