Շարահյուսական վերլուծություն (ինֆորմատիկա)

Վիքիպեդիայից՝ ազատ հանրագիտարանից

Շարահյուսական (անգլ.՝ Parsing, syntactic analysis), վերլուծությունը լեզվաբանությունում և ինֆորմատիկայում լեքսեմների գծային հաջորդականության համապատասխանեցման գործընթացն է, բնական կամ ֆորմալ լեզվում իր ֆորմալ քերականությանը։ Արդյունքը հիմանականում հանդիասնում է քերականական ծառ (կամ աբստրակտ քերականական ծառերի)։ Սովորաբանր օգտագործվում է լեքսիկական (բառային) վերլուծության հետ միասին։

Վերլուծություն (անգլ.՝ Parsing) տերմինը լեզվաբանությունում և ինֆորմատիկայում տարբեր իմաստներ ունի։ Տրադիցիոն նախադասության վերլուծությունը հաճախ իրականցվում է հասկանալու համար նախադասության ճշգրիտ իմաստը, երբեմն նախադասության սխեմաներով։ Դա որպես կանոն ընդգծում է քերականական մասերը, ինչպես օրինակ ենթական և ստորոգյլաը։

Ինֆորմատիկայում այդ տերմինն օգտաագործում են ծրագրավորման լեզուների վերլուծություններում, թեթևացնում է կոմպիլյատորների և ինտերպրետատորների գրելը։

Շարահյուսական անալիզատոր(parser)[խմբագրել | խմբագրել կոդը]

Շարահյուսական անալիզատորը (անգլ.՝ parser) ծրագիր է կամ ծրագրի մի մաս, որը կատարում է շարահյուսական վերլուծություն։ Շարահյուսական անալիզատորը(անգլ.՝ parser) օգտագործում է լեքսիկական վերլուծությունից ստացված առաջին թոքենների բաղադրիչները, ծառանման միջանկյալ ներկայացման ստեղծման համար, որը նկարագրում է թոքենների հոսքի քերականական կառուցվածքը։ Տիպիկ ներկայացում է համարվում շարահյուսական ծառը( parse tree, abstract syntax tree ), որում յուրաքանչյուր հանգույց ներկայացնում է գործողություն, իսկ երեխա հանգուցները՝ այդ գործողությունների արգումենտներ։ Ծրագրավորման լեզվի շարահյուսական կառուցվածքը կարող է նկարագրվել կոնտեքստային ազատ քերականության(անգլ.՝ context-free grammars) օգնությամբ։

արտահայտության վերլուծության ծառի օրինակ

Քերականությունը ծրագրավորման լեզվուները մշակողներին և կոմպիլյատոր սեղծողներին ապահովում է զգալի առավելություններ․

  • Քերականությունը ծրագրավորման լեզվի համար տալիս է ճշգրիտ, միևնույն ժամանակ հասկանալու համար պարզ շարահյուսական հստակեցում։
  • Քերականության որոշ դասերի համար հնարավոր է ավտոմատ կերպով կառուցել արդյունավետ շարահյուսական անալիզատոր, որը սահմանում է սկզբնական ծրագրի շարահյուսական կառուցվածքը։
  • Անալիզատորի ավտոմատ ստեղծման լրացուցիչ առավելություն է հանդիսանում շարահյուսական անմիարժեքության և այլ բարդությունների հայտաբերելու հնարավորությունը, որոնք լեզուն և իր կոմպիլյատորի ստեղծման սկզբանական փուլում ի սկզբանե կարող են մնալ անտեսանելի։
  • Քերականության ճշգրիտ կառուցումը ծրագրավորման լեզվին տալիս է այնպիսի կառուցվածք, որը նպաստում է սկզբանական ծրագրի տրանսլյացիայի թեթևացման և բացահայտում է սխալները։
  • Քերականությունը թույլ է տալիս լեզվին իտերատիվ զարգանա՝ հարստանալով նոր կառուցվաածքներով նոր խնդիրներ լուծման համար։ Լեզվում նոր կառուցվածքները ավելացումը ավելի հեշտ խնդիր է դառնում, եթե լեզվի ներկայիս իրականցումը հիմնված է իր քերականական նկարագրության վրա։

Գործընթացի ակնարկ[խմբագրել | խմբագրել կոդը]

Parser Flowո.gif

Դիտարկված օրինակը ցույց է տալիս ընդհանուր դեպք ծրագրավորման լեզվի վերլուծություն քերականության երկու փուլերով՝ լեքսիկական և շարահյուսական։

Առաջին էտապը թոքենների գեներացիան է, կամ լեքսիկական անալիզն է, որով կանոնավոր արտահայտությունների քերականությունով մուտքային տառերի հոսքը բաժանվում է իմաստալից սիմվոլների։ Օրինակ հաշվիչի ծրագիրի մուտքը պետք է ունենա "12*(3+4)^2" տեքը և բաժանվի թոքենների՝ 12, *, (, 3, +, 4, ), ^, 2, որոնցից յուրաքանչյուրը իմաստալից սիմվոլ է թվաբանություն արտահայտությունների կոնտեքստում։ Լեքսերը պահպանում է կանոններ որպեսզի նշի սրանք սիմվոլներ են *, +, ^, ( և ) նշի նոր թոքենի սկսվելը, այնպես որ անիմաստ թոքեննեը, ինչպիսին են "12*" or "(3" չեն գեներացվում։

Հաջորդ էտապը շարահյուսական վերլուծությունն է, որը ստուգում է, որ թոքենները ձևավորեն թույլատրելի արտահայտություններ։ Դա հիմանականում հղվում է context-free քերականություն, որը ռեկուրսիվ սահմանում է բաղադրիչները, որը կարող է կազմել արտահայտություններ և հերթականություն, որտեղ դրանք պետք է գտնվեն։

Վերջնական էտապը սեմանտիկ իմաստային վերլուծությունն է։ Հաշվիչի դեպքում կամ ինտերպրետատորի, գործողությունը գնահատում է արտահայտություն կամ ծրագիր, կոմպիլյատորը այլ տեսանկյունից կգեներացնի ինչ որ կոդ։

Շարահյուսական անալիզատորի տիպերը[խմբագրել | խմբագրել կոդը]

Bottom-up շարահյուսության վերլուծության տառի կառուցումը՝ համրակալված քայլերով

Վերլուծչի հիմանական խնդիրն է որոշել ինչպես կարող է մուտքը ստացվել քերականական սկզբանական սիմվոլներից։ Վերլուծության հայտնի մեթոդների մեծ մասը պատկանում են երկեւ դասերից մեկին՝ top-down կամ bottom-up ալգորիթմներ։ Դրանց անվանումները կապված են այն բանի հետ, թե ինչպես է շարահյուսական ծառի հանգույցները կառուցվում՝ կամ արմատից դեպի տերևներ կամ տերևներից դեպի արմատ։

  • Top-down parsing — շարահյուսական անալիզատորը վերլուծության ծառը կառուցում է վերևից(արմատից) ներքև(տերևներ) ։
  • Bottom-up parsing — շարահյուսական անալիզատորը վերլուծության ծառը կառուցում է ներքևից(տերևներից) վերև(արմատ)։

Քերականության նմուշներ[խմբագրել | խմբագրել կոդը]

Е-ն ներկայացնում է արտահայտություն, որը բաղկացած է գումարելիներից՝ բաժանված + նշաններով, T-ն ներկայացնում է գումարելիներ, որոնք բաղկացած են բազմապատկիչներից, բաժանված * նշաններով, իսկ F-ը ներկայացնում է բազմապատկիչներ, որոնք կարող են լինել կամ փակագծերում արտահայտություններ, կամ իդենտիֆիկատորներ՝

E -> E + T\ T 
T -> T*F|F 
F → (E)|id

Այս արտահայտության քերականությունը պատկանում է LR քերականությանը, որը համապատասխանում է Bottom-up շարահյուսական վերլուծությանը։ Աըս քերականությունը կարող է համատեղ աշխատել լրացուցիչ օպերատորների և առաջնահերթությունների մակարդակների հետ։ Այն չի կարող օգտագործել Top-down շարահյուսական վերլուծությունը իր ձախ ռեկուրսիայի հիման վրա։

Top-down շարահյուսական վերլուծությունը կարող է օգտագործել հետևյալ քերականության տարբերակը, որում հեռացված է ձախ ռեկուրսիան՝

E → ТЕ'   
Е'→ +T*Е'|ε
T -» FT'
T → *FT'|ε
F → (E)\ id

Ստորև բերված քերականությունը դիտարկում է * և + որպես միանման արտահայտություններ, այնպես որ այն օգտակար է շարահյուսական վերլուծության ժամանակ անմիարժեքությունների մշակման մեթոդների նկարագրման համար՝

Е -► Е + Е | Е * Е | (Е) | id

Այստեղ Е-ն ներկայացնում է բոլոր տիպերի արտահայտությունները։ Սրա քերականությունը թույլատրում է ավելին քան մեկ վերլուծության ծառ а + Ъ* с -ի նման արտահայտությունների համար։

Հղումներ[խմբագրել | խմբագրել կոդը]