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

жүктеу 14,81 Mb.

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

1 ... 119 120 121 122 123 124 125 126 127

Теория негізі Анықтама7.1.

Зертханалық жұмыс № 7

Төмен түсу әдісі бойынша КТ-тілдердің синтаксистік талдау
Мазмұны: Жоғарыдан төмен синтаксистік талдауды автоматы жүзеге асыру, қарапайым көрсетілімді грамматика үшін анықтауыштың функционалдау моделін құру. L(A) және R(A) жиындарын құру, грамматика белгілерінің матрицаларын төмен түсу әдісі бойынша құру.
Мақсаты - «Қарапайым қатынас граматикасы» мағынасын толықтыру-көпмүшенің құрылымын талдай білу.L(A) және R(A), матрицаның грамматикалық символдарының қатысы және қарапайым «сдвиг-свертка» үлгісімен табу грамматикасы.

Теория негізі

Анықтама7.1. Келтірілген КС-грамматика G (V_N, V_T, P, S) қарапайым келтіру грамматикасы деп аталады егер келесі шарттар орындалса.

1) Әрбір реттелген терминальды және терминальданбаған жұбтар үшін қатынастың біреуі ғана орындалады.

а) B_i = Bj (V B_i, Bj V), егер тек қана мына шарттар орындалса A→xBiBjyP, мұндағы x,y V*;

б) B_i < Bj (V B_h Bj V), егер текқана мына шарт орындалса A→xBiDyP және шығуD*BjZ, осыA, D V_N, x,y,z V*

в)B_i > Bj (V B_i, Bj V егер тек осы шарт орындалса A→xCBjy және шығу C*zB_{ егер шарт бар болсаA→xCDyР шығу C^>*zB_t и D^*BjW, meA,C,D V_N, x, y,z,w V.

2) Грамматикада түрлі ережелер әртүлі дұрыс бөлімдерден тұрады.

жүктеу 14,81 Mb.

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

1 ... 119 120 121 122 123 124 125 126 127