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

Теорема 6.1. LL(1)-грамматикасының қажетті және жеткілікті шарттары

жүктеу 14,81 Mb.

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

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

Алгоритм 6.1. FIRST (1

Теорема 6.1. LL(1)-грамматикасының қажетті және жеткілікті шарттары.

G(V_N, V_T, P, S) грамматикасы LL(1)-грамматикасының қажетті және жеткілікті болу үшін, әрбір АV_N, у символ үшін, А→α 1 |α₂ |…| α_n ережесі түріндеграмматикаға бөлу үшін, мына шарттар орындалу керек:

FIRST(1, α_iFOLLOW(1,A)) ∩ FIRST(1, α_jFOLLOW(1, A)) = ∅, V i≠j,

Бұл дегеніміз А символы үшін А→ε, түрінде ереже болса, онда барлық жиын FIRST(1, α1), FIRST(1, α₂),…, FIRST(1, α_n) олар жұппен қиылысуы керек, егер А→ε, ереже бойынша қатысса, онда олар сонымен қатар FOLLOW(1, A) жиынымен қиылысу керек.

LL(1)-грамматикасын құру үшін FIRST(1, x) және FOLLOW(1, A). жиынын құру керек. Егер х жолы а символының терминалынан басталса, онда FIRST(1, x)=a, және егер ол А, терминал емес символдан басталса, онда FIRST(1, x)=FIRST(1, A). Бұл дегеніміз, FIRST(1, A) және FOLLOW(1, A) жиынының алгоритмнің құрылуын қарастыру үшін, әрбіреуіне А терминалды емес символы қажет.

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

Алгоритмді орындау үшін G шығу грамматикасын G^′, грамматикасына аудару керек, FIRST(1, A) жиынының құрылу алгоритмі G^′ грамматикасын қолданады.

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

2 қадам. Барлығы үшін АV_N орналастыру:

FIRST_i+1(1, A) = FIRSTi(1, A) FIRST_i(1, B), V В(FIRST(1, A)∩V_N).

3қадам. Егер А V_n, болса, онда FIRST_i+1(1, A) ≠ FIRST_i(1, A), онда оны орнатып i=i+1 2 – ші қадамға қайту, немесе 4 – ші қадамға өту.

4қадам. Құрылған жиыннан барлық терминал емес символдарды шығару, бұл дегеніміз

V A V_N FIRST(1, A) = FIRSTi(1, A) _{\ N}.

жүктеу 14,81 Mb.

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

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