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

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

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

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

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

**Շարահյուսական անալիզատորը** () ծրագիր է կամ ծրագրի մի մաս, որը կատարում է շարահյուսական վերլուծություն։
Շարահյուսական անալիզատորը() օգտագործում է լեքսիկական վերլուծությունից ստացված առաջին թոքենների բաղադրիչները, ծառանման միջանկյալ ներկայացման ստեղծման համար, որը նկարագրում է թոքենների հոսքի քերականական կառուցվածքը։ Տիպիկ ներկայացում է համարվում շարահյուսական ծառը( parse tree, abstract syntax tree ), որում յուրաքանչյուր հանգույց ներկայացնում է գործողություն, իսկ երեխա հանգուցները՝ այդ գործողությունների արգումենտներ։ Ծրագրավորման լեզվի շարահյուսական կառուցվածքը կարող է նկարագրվել կոնտեքստային ազատ քերականության() օգնությամբ։
|thumb|left|289px|արտահայտության վերլուծության ծառի օրինակ
Քերականությունը ծրագրավորման լեզվուները մշակողներին և կոմպիլյատոր սեղծողներին ապահովում է զգալի առավելություններ․
* Քերականությունը ծրագրավորման լեզվի համար տալիս է ճշգրիտ, միևնույն ժամանակ հասկանալու համար պարզ շարահյուսական հստակեցում։
* Քերականության որոշ դասերի համար հնարավոր է ավտոմատ կերպով կառուցել արդյունավետ շարահյուսական անալիզատոր, որը սահմանում է սկզբնական ծրագրի շարահյուսական կառուցվածքը։
* Անալիզատորի ավտոմատ ստեղծման լրացուցիչ առավելություն է հանդիսանում շարահյուսական անմիարժեքության և այլ բարդությունների հայտաբերելու հնարավորությունը, որոնք լեզուն և իր կոմպիլյատորի ստեղծման սկզբանական փուլում ի սկզբանե կարող են մնալ անտեսանելի։
* Քերականության ճշգրիտ կառուցումը ծրագրավորման լեզվին տալիս է այնպիսի կառուցվածք, որը նպաստում է սկզբանական ծրագրի տրանսլյացիայի թեթևացման և բացահայտում է սխալները։
* Քերականությունը թույլ է տալիս լեզվին իտերատիվ զարգանա՝ հարստանալով նոր կառուցվաածքներով նոր խնդիրներ լուծման համար։ Լեզվում նոր կառուցվածքները ավելացումը ավելի հեշտ խնդիր է դառնում, եթե լեզվի ներկայիս իրականցումը հիմնված է իր քերականական նկարագրության վրա։

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

right

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

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

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

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

## Շարահյուսական անալիզատորի տիպերը
thumb|x200px|right|Bottom-up շարահյուսության վերլուծության տառի կառուցումը՝ համրակալված քայլերով

Վերլուծչի հիմանական խնդիրն է որոշել ինչպես կարող է մուտքը ստացվել քերականական սկզբանական սիմվոլներից։ Վերլուծության հայտնի մեթոդների մեծ մասը պատկանում են երկեւ դասերից մեկին՝ *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

Կատեգորիա:Համակարգիչ