Շարահյուսական վերլուծություն (ինֆորմատիկա)
| Այս հոդվածն աղբյուրների կարիք ունի։ Դուք կարող եք բարելավել հոդվածը՝ գտնելով բերված տեղեկությունների հաստատումը վստահելի աղբյուրներում և ավելացնելով դրանց հղումները հոդվածին։ Անհիմն հղումները ենթակա են հեռացման։ |
Շարահյուսական (անգլ.՝ Parsing, syntactic analysis), վերլուծությունը լեզվաբանությունում և ինֆորմատիկայում լեքսեմների գծային հաջորդականության համապատասխանեցման գործընթացն է, բնական կամ ֆորմալ լեզվում իր ֆորմալ քերականությանը։ Արդյունքը հիմանականում հանդիասնում է քերականական ծառ (կամ աբստրակտ քերականական ծառերի)։ Սովորաբանր օգտագործվում է լեքսիկական (բառային) վերլուծության հետ միասին։
Վերլուծություն (անգլ.՝ Parsing) տերմինը լեզվաբանությունում և ինֆորմատիկայում տարբեր իմաստներ ունի։ Տրադիցիոն նախադասության վերլուծությունը հաճախ իրականցվում է հասկանալու համար նախադասության ճշգրիտ իմաստը, երբեմն նախադասության սխեմաներով։ Դա որպես կանոն ընդգծում է քերականական մասերը, ինչպես օրինակ ենթական և ստորոգյլաը։
Ինֆորմատիկայում այդ տերմինն օգտագործում են ծրագրավորման լեզուների վերլուծություններում, թեթևացնում է կոմպիլյատորների և ինտերպրետատորների գրելը։
Շարահյուսական անալիզատոր(parser)
խմբագրելՇարահյուսական անալիզատորը (անգլ.՝ parser) ծրագիր է կամ ծրագրի մի մաս, որը կատարում է շարահյուսական վերլուծություն։ Շարահյուսական անալիզատորը(անգլ.՝ parser) օգտագործում է լեքսիկական վերլուծությունից ստացված առաջին թոքենների բաղադրիչները, ծառանման միջանկյալ ներկայացման ստեղծման համար, որը նկարագրում է թոքենների հոսքի քերականական կառուցվածքը։ Տիպիկ ներկայացում է համարվում շարահյուսական ծառը( parse tree, abstract syntax tree ), որում յուրաքանչյուր հանգույց ներկայացնում է գործողություն, իսկ երեխա հանգուցները՝ այդ գործողությունների արգումենտներ։ Ծրագրավորման լեզվի շարահյուսական կառուցվածքը կարող է նկարագրվել կոնտեքստային ազատ քերականության(անգլ.՝ context-free grammars) օգնությամբ։
Քերականությունը ծրագրավորման լեզվուները մշակողներին և կոմպիլյատոր սեղծողներին ապահովում է զգալի առավելություններ․
- Քերականությունը ծրագրավորման լեզվի համար տալիս է ճշգրիտ, միևնույն ժամանակ հասկանալու համար պարզ շարահյուսական հստակեցում։
- Քերականության որոշ դասերի համար հնարավոր է ավտոմատ կերպով կառուցել արդյունավետ շարահյուսական անալիզատոր, որը սահմանում է սկզբնական ծրագրի շարահյուսական կառուցվածքը։
- Անալիզատորի ավտոմատ ստեղծման լրացուցիչ առավելություն է հանդիսանում շարահյուսական անմիարժեքության և այլ բարդությունների հայտաբերելու հնարավորությունը, որոնք լեզուն և իր կոմպիլյատորի ստեղծման սկզբանական փուլում ի սկզբանե կարող են մնալ անտեսանելի։
- Քերականության ճշգրիտ կառուցումը ծրագրավորման լեզվին ��ալիս է այնպիսի կառուցվածք, որը նպաստում է սկզբանական ծրագրի տրանսլյացիայի թեթևացման և բացահայտում է սխալները։
- Քերականությունը թույլ է տալիս լեզվին իտերատիվ զարգանա՝ հարստանալով նոր կառուցվաածքներով նոր խնդիրներ լուծման համար։ Լեզվում նոր կառուցվածքները ավելացումը ավելի հեշտ խնդիր է դառնում, եթե լեզվի ներկայիս իրականցումը հիմնված է իր քերականական նկարագրության վրա։
Գործընթացի ակնարկ
խմբագրել
Դիտարկված օրինակը ցույց է տալիս ընդհանուր դեպք ծրագրավորման լեզվի վերլուծություն քերականության երկու փուլերով՝ լեքսիկական և շարահյուսական։
Առաջին էտապը թոքենների գեներացիան է, կամ լեքսիկական անալիզն է, որով կանոնավոր արտահայտությունների քերականությունով մուտքային տառերի հոսքը բաժանվում է իմաստալից սիմվոլների։ Օրինակ հաշվիչի ծրագիրի մուտքը պետք է ունենա "12*(3+4)^2" տեքը և բաժանվի թոքենների՝ 12, *, (, 3, +, 4, ), ^, 2, որոնցից յուրաքանչյուրը իմաստալից սիմվոլ է թվաբանություն արտահայտությունների կոնտեքստում։ Լեքսերը պահպանում է կանոններ որպեսզի նշի սրանք սիմվոլներ են *, +, ^, ( և ) նշի նոր թոքենի սկսվելը, այնպես որ անիմաստ թոքեննեը, ինչպիսին են "12*" or "(3" չեն գեներացվում։
Հաջորդ էտապը շարահյուսական վերլուծությունն է, որը ստուգում է, որ թոքենները ձևավորեն թույլատրելի արտահայտություններ։ Դա հիմանականում հղվում է context-free քերականություն, որը ռեկուրսիվ սահմանում է բաղադրիչները, որը կարող է կազմել արտահայտություններ և հերթականություն, որտեղ դրանք պետք է գտնվեն։
Վերջնական էտապը սեմանտիկ իմաստային վերլուծությունն է։ Հաշվիչի դեպքում կամ ինտերպրետատորի, գործողությունը գնահատում է արտահայտություն կամ ծրագիր, կոմպիլյատորը այլ տեսանկյունից կգեներացնի ինչ որ կոդ։
Շարահյուսական անալիզատորի տիպերը
խմբագրել
Վերլուծչի հիմանական խնդիրն է որոշել ինչպես կարող է մուտքը ստացվել քերականական սկզբանական սիմվոլներից։ Վերլուծության հայտնի մեթոդների մեծ մասը պատկանում են երկեւ դասերից մեկին՝ 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
Այստեղ Е-ն ներկայացնում է բոլոր տիպերի արտահայտությունները։ Սրա քերականությունը թույլատրում է ավելին քան մեկ վերլուծության ծառ а + Ъ* с -ի նման արտահայտությունների համար։