Աբստրակտ շարահյուսական ծառ

Էվկլիդյան ալգորիթմի համար վերացական շարահյուսական ծառ. while b ≠ 0 if a > b a := a − b elseb := b − a return a

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

Շարահյուսական ծառերը օգտագործվում են վերլուծիչներում՝ ծրագրի միջանկյալ ներկայացում ապահովելու վերլուծական ծառի (որոշակի շարահյուսություն ունեցող ծառի) և տվյալների կառուցվածքի միջև, որն այնուհետև օգտագործվում է որպես ներքին ներկայացում կոմպիլյատորում կամ ծրագրի ինտերպրետատորում՝ օպտիմալացման և կոդի ստեղծման համար։ Նման կառույցների հնարավոր տարբերակները նկարագրված են վերացական շարահյուսությամբ։

Վերացական շարահյուսական ծառը տարբերվում է վերլուծական ծառից նրանով, որ այն չունի հանգույցներ և եզրեր այն շարահյուսական կանոնների համար, որոնք չեն ազդում ծրագրի իմաստաբանության վրա։ Խմբավորման փակագծերը այս բացակայության դասական օրինակ են, քանի որ վերացական շարահյուսական ծառի մեջ օպերանդների խմբավորումը հստակորեն նշված է ծառի կառուցվածքով։

Լեզվի համար, որը նկարագրվում է առանց համատեքստի քերականությամբ (գրեթե բոլոր ծրագրավորման լեզուներն են), վերլուծիչում ծառ ստեղծելը պարզ խնդիր է։ Քերականության կանոնների մեծ մասը ստեղծում է նոր գագաթ, և կանոնի նիշերը դառնում են եզրեր։ Կանոնները, որոնք ոչնչով չեն նպաստում ծառին (օրինակ՝ խմբավորման կանոնները), պարզապես վերևում փոխարինվում են իրենց նշաններից մեկով։ Բացի այդ, վերլուծիչը կարող է ստեղծել ամբողջական վերլուծական ծառ և այնուհետև անցնել այն՝ հեռացնելով աբստրակտ շարահյուսության մեջ չօգտագործվող հանգույցներն ու եզրերը՝ ստանալով վերացական շարահյուսական ծառ։

Գրականություն

• Iulian Neamtiu, Jeffrey S. Foster, Michael Hicks Understanding source code evolution using abstract syntax tree matching(անգլ.) // Proceedings of the 2005 international workshop on Mining software repositories (MSR ’05). — 2005. —
• Beat Fluri, Michael Würsch, Martin Pinzger, Harald C. Gall Change Distilling: Tree Differencing for Fine-Grained Source Code Change Extraction(անգլ.) // IEEE Transactions on Software Engineering. — 2007. — Т. 33. — № 11. — С. 725—743.
• Jean-Rémy Falleri, Floréal Morandat, Xavier Blanc, Matias Martinez, Martin Monperrus Fine-grained and Accurate Source Code Differencing(անգլ.) // Proceedings of the International Conference on Automated Software Engineering. — 2014. — С. 313—324. —

Արտաքին հղումներ

• AST View — плагин для Eclipse показывает абстрактное синтаксическое дерево программ на языке Java
• Полезная информация о представлении абстрактного синтаксического дерева в Eclipse и манипулировании исходным кодом Java
• Представление CAST
• Abstract Syntax Tree Unparsing (չաշխատող հղում — պատմություն)