Ўзбекистон республикаси алоқА, ахборотлаштириш ва телекоммуникация технологиялари давлат қЎмитаси тошкент ахборот технологиялари университети

Назорат саволлари

1. 
   Хомский иерархияси неча тур грамматикани уз ичига олган? Уларнинг турларини айтинг.
   
2. 
   Регуляр грамматиканинг ютук ва камчиликлари нималардан иборат?
   

3. Контекст-озод грамматикага таъриф беринг.
4.Хомскийнинг нормал формаси нима?
5..Грейбахнинг нормал формаси нима?
Фойдаланилган адабиётлар

1. 
   Молчанов А.Ю. Системное программное обеспечение: Учебник для вузов. –СПб: Питер, 2003.-396 с.
   
2. 
   Афанасьев А.Н. Формальные языки и грамматики: Учебная школа: УлГТУ, 1997. – 84 с
   
3. 
   Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции -: Мир, 1979.-487с.
   
4. 
   Компаниец Р.И. Системное программирование. Основы построения трансляторов. СПб.:Корна принт., 2000. -256 стр.
   
5. 
   Дьяконов В.Ю. Системное программирование. Высш.шк.. 1990. -221 с.
   
6. 
   WWW.codecrojekt.ru
   
7. 
   WWW. master.ru
   
8. 
   WWW.bdn_borland.com
   
9. 
   http://microsofft.com
   

Маъруза № 7.
Мавзу: Разбор муаммоси.
Режа:
1. Разбор муаммоси.
2. Разбор дарахти.
3. Бир хил кийматга эга булмаган грамматикалар.
Калит сузлар.

• 
  Бошланғич белги
  
• 
  Туғилувчи қоидалар
  
• 
  Чап томонли чиқиш
  
• 
  Ўнг томонли чиқиш
  
• 
  Разбор дарахти
  

1. Разбор муаммоси.

Кандайдир тилнинг мавжуд грамматикаси асосида ушбу тилнинг англовчисини куришни англатади.

Разбор масаласи барча тиллар учун ечилмайди.
Разбор масаласи куйидаги масалалар учун ечилади:
- кирувчи белгилар занжирининг маъновий юкланишини аниклаш;
- занжирни куришда фойдаланилган коидаларни аниклаш;
- хатоликларни мавжудлиги фактини аниклаш, хатоликлар урни ва тури.
Компилятор белгилар каторини текшириш муаммосини, ушбу катор шу тилга тегишли ёки йуклигини аниклаш учун ва тегишли булса, у холда тугилувчи грамматика коидалари терминларида каторни структурасини англашни хал килиши керак. Ушбу муаммо разбор муаммоси сифатида машхур. Тугилувчи коидалар билан ишловчи грммматикани текширамиз.
(Е-бошлангич белги).
1. Е à E+T 5. Fà (E)
2. Eà- T 6. F à x
3. T à T*F 7. F à y
4. Tà F

Куриниб турибдики, (х+у)*х катор ушбу тилга тегишли. Хусусий холда, буни куйидагича келтириб чикариш мумкин (хар бир келтириб чикариш кадами учун кулланилаётган коида раками курсатилган):

2) E à T 4) à (F+T)*F
3) à T*F 6) à (x+T)*F
4) à F*F 4) à (x+F)*F
5) à (E)*F 7) à (x+y)*F
1) à (E+T)*F 6) à (x+y)*x
2) à (T+T)*F
Ёки куйидагича келтириб чикариш мумкин:
2) E à T 4) à (E+F)*x
3) à T*F 7) à (E+y)*x
6) à T*x 2) à (T+y)*x
4) à F*x 4) à (F+y)*x
5) à (E)*x 6) à (x+y)*x
1) à (E+T)*x
Биринчи чикишнинг хар бир боскичида сентенциал форманинг энг чап нотерминали грамматиканинг бирон бир тугилувчи коидаси ёрдамида алмаштирилди. Шу сабабли ушбу чикиш чап томонли чикиш дейилади. Хар бир боскичида энг унг нотерминал алмаштирилган иккинчи чикиш эса унг томонли чикиш деб аталади.
Шу каби бошка чикишлар хам мавжудки, улар чап томонли хам, унг томонли хам хисобланмайдилар, лекин трансляторларни куришда улардан фойдаланилмайди. Гапни чап томонли разбори чап томонли чикишни кулланилган холда гапни генерация килиш учун тугилувчи коидаларнинг кетма-кетлиги сифатида аникланади. Ушбу холда чап томонли разборни куйидагича ёзиш мумкин:
2,3,4,5,1,2,4,6,4,7,6.
Гапни унг томонли разбори унг томонли чикишни кулланилган холда гапни генерация килиш учун тугилувчи коидаларнинг тугилувчи коидаларнинг тескари кетма кетлиги хисобланади; масалан, юкорида келтирилган холда унг томонли разбор куйидагича ёзилади:
6,4,2,7,4,1,5,4,6,3,2.
Тугилувчи коидалар кетма-кетлигининг тескари тартиби шу билан богликки, унг томонли разбор гапни бошлангич белгига келтириш сифатида каралади, гапни бошлангич белгидан бошлаб генерация килиш эмас (пастдан юкорига караб разбор). Шуни таъкидлаш керакки, хар бир тугилувчи коидадан иккала чикишда хам бир хил сон марта фойдаланилади (разборларда).