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

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

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

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

Շարահյուսական անալիզատոր(parser) 

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

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

Գործընթացի ակնարկ 

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

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

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

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

Շարահյուսական անալիզատորի տիպերը 

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

Քերականության նմուշներ 
Е-ն ներկայացնում է արտահայտություն, որը բաղկացած է գումարելիներից՝ բաժանված + նշաններով, 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

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

Հղումներ 
 The Lemon LALR Parser Generator
 Stanford Parser
 Turin University Parser
 Short history of parser construction

Համակարգիչ