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

2.Разбор дарахти. Чикиш яна синтаксис дарахт (разбор дарахти) номи билан машхур дарахтни куриш терминларида хам ифодаланиши мумкин. (х+у)*х катор холида синтаксис дарахт куйидаги куринишда булади:

Расм 1. Разбор дарахти.

Разбор муаммисини куйидаги масалаларга келтириш мумкин.

1. 
   чап томонли разборни топиш
   
2. 
   унг томонли разборни топиш
   
3. 
   синтаксис дарахтни куриш.
   

3.Бир хил кийматга эга булмаган грамматикалар.
Купгина холларда чап томонли ва унг томонли разборлар ва синтаксис дарахт уникал хисобланади. Лекин, куйидаги тугилувчи коидали грамматика учун
S à S+S| x х+х+х гап иккита синтаксис дарахтга, иккита чап (унг) томонли разборга эга.

Расм 2. Разбор вариантлари.

S  S+S S  S+S

 S +S+S  x+S
 x+S+S  x+S+S
 x+x+S  x+x+S
 x+x+x  x+x+x

Агар грамматикада генерация килинган кандайдир гап, биттадан ортик разбор дарахтига эга булса, бундай грамматика хакида у бир кийматли эмас дейилади. Эквивалент шарт шунда куринадики, гап биттадан ортик чап ёки унг томонли разборга эга булиши керак. Грамматиканинг бир кийматли эмаслигини урнатиш масаласи умумий холда ечими йук масаладир, яъни киришда ихтиёрий грамматикани кабул киладиган ва уни бир кийматлими ёки йуклигини аниклайдиган универсал алгоритм мавжуд эмас. Баъзи бир бир кийматли булмаган грамматикаларни уша тилни генерация киладиган бир кийматлига айлантириш мумкин. Масалан, куйидаги тугилувчи коидаларга эга грамматика

S x S +x бир кийматли булиб, у уша тилни худди аввалги бир кийматли булмаган грамматика каби генерациялайди.
Разбор усуллари купинча пастдан юрувчидир, яъни бошлангич белгидан бошлаб гапга караб юрилади ёки юкоридан юрувчи булиб, гапдан бошлаб бошлангич белгига караб юрилади.
Разборда ечимни рад этиш (отказ) кайтиш (возврат) деб аталади. Разбор усуллари кайтиш бор ёки йуклигига караб детерминирован ва нодетерминирован булиши мумкин. Нодетерминирован усуллар хотира ва вакт нуктаи назаридан киммат булиб, компиляция вактида бажарилувчи натижалари кейинчалик йук килиниши керак булган харакатларни синтаксис анализаторга кушишни кийинлаштиради (масалан, белгилар жадвалини куриш ва х.к.). Бундан сунг биз факат разборнинг детерминирован усуллари хакида суз юритамиз.