«Соңғы автоматтар және формальдік тілдер теориясы»

жүктеу 14,81 Mb.

бет	120/127
Дата	21.05.2018
өлшемі	14,81 Mb.
	#15467

1 ... 116 117 118 119 120 121 122 123 ... 127

Алгоритм 6.2. FOLLOW(1,A) жиынының құрылуы

Алгоритм G грамматикасының ережесін қолдану негізінде құрылған.

1қадам. Алдымен терминал емес А символының әрбіреуіне келесі жиын символдарын енгізу, олар шығару ережесінің оң жақ бөлімінде А символымен сәйкестеледі. Бұл дегеніміз

2 Қадам. Жиынға бос жол енгізу FOLLOW(1, S), бұл дегеніміз FOLLOW(1, S) = FOLLOW(1, S){ε}.

3Қадам. Барлығы үшін АV_N есептеу:

4Қадам. Барлығы үшін АV_N қою:

FOLLOW″i(1, A)=FOLLOW′i(1, A) FOLLOW′i(1, B), MB (FOLLOW ′i(1, A)∩V_N), егер З ережеде B→ε.

5Қадам. Барлығы үшін АV_N анықтау:

FOLLOW_i+1(1, A) = FOLLOW″i(1, A)∪FOLLOW″i(1, B),

Барлық терминал емес символдар үшін B ∈V_N, ереженің түріндей

6 Қадам. Егер A V_N болса, онда FOLLOW_i+1(1,A)≠FOLLOW i(1,A), онда оны қойып i:=i+1 және 3 – ші қадамға қайту, немесе 7 – ші қадамға өту.

7Қадам. Құрылған жиыннан терминал емес барлық символдарды шығару, бұл дегеніміз V A V_nFOLLOW(1, A) = FOLLOW_i(1, A)\_N.

жүктеу 14,81 Mb.

Достарыңызбен бөлісу:

1 ... 116 117 118 119 120 121 122 123 ... 127