ساختار درختی

یکساختار درختییاترسیم درختییادرخت تجزیهدرختیاست که نشان دهندهٔ ساختار دستوری (نحوی) یک رشته است. معمولاً این نمایش با توجه به دستور زبانهای رسمی است. دریک درخت تجزیه گرههای داخلی، نقشهای دستوری و برگها یا همان گرههای خارجی کلمات مربوط به آن نقش هستند.

خصوصیات درخت تجزیه[ویرایش]

فرض کنید (G=(V,T,P,S یکگرامر مستقل از متنباشد، یک درخت مرتب یک درخت تجزیه برای گرامر G است اگر خصوصیات زیر را داشته باشد:

۱- ریشه درخت دارای برچسب S است.
۲- هر برگ دارای برچسبی از{T∪{ε است.
۳- هر گره میانی دارای برچسبی از V است.
۴- اگر یک گره درونی برچسب A∈V داشته باشد و فرزندانش از چپ به راست دارای برچسبهای X1 X2....Xi باشند،A ⟶ X1 X2...Xi یکی از قوانین تولید باشد.
۵- گرهای که دارای برچسب ε است، دارای هیچ همزادی نمیباشد.

کاربردها و مثالها[ویرایش]

شکل ۱. یک درخت تجزیهٔ ساده برای جملات روزمره

یکی از نیازمندیهای اساسی که در تولید برنامه ها نیاز است، این است که بایستی از لحاظ دستوری، درستی برنامه های نوشته شده تائید گردند. اغلب غیرممکن است که یک برنامهٔ نوشته شده با زبانهای کامپیوتری را به شکل اولیه نوشته شده توسط برنامه نویس؛ اجرا کنیم، زیرا اولاً برنامه نوشته شده به احتمال زیاد با خطاهای دستوری کاربر همراه است و ثانیاً اینکه فرم اولیه برنامهها سطح بالا بوده و قابل تبدیل به کد، در همان شکل اولیه اش نیست؛ بنابراین برنامه بایستی در ابتدا به یک شکل بهتری تبدیل شود؛ بنابراین کامپایلرها سعی میکنند که برنامه نوشته شده را به یک فرم یکنوا و سادهتر که درخت تجزیه نام دارند، تبدیل کنند. درخت تجزیه با بحثکامپایلرها (همگردان)مرتبط است. برنامهای که این چنین درختهایی را تولید میکنند؛تجزیهکننده(Parser) نامیده میشوند. درختهای تجزیه ممکن است برای جملات و عبارات زبانهای روزمره مورد استفاده قرار بگیرند یا در پردازش زبانهای کامپیوتری (زبانهای برنامه نویسی) مثل:C،جاوا،دلفیو... بکار گرفته شوند. کارکرد این درخت بدین صورت است که با یک درخت تجزیه مثل دیگردرختهااز یال و گره تشکیل شدهاست.

در زیر مثالهایی از این نوع درخت را میبینید. البته شکل ۱، یک حالت از درخت تجزیهٔ این جمله است، که البته حالتهای دیگری را نیز میتوان متصور بود. درخت تجزیه یک ساختار کامل است که با جمله شروع میشود و به نقشهای دستوری در برگهای انتهایی، پایان مییابد. البته این در صورتی درست است که که عبارتی مورد بررسی یک عبارت یا جمله از جملات روزمره باشد.

در مورد زبانهای کامپیوتری شکل شمارهٔ ۲ مثال خوبی است. در این مثال یکی از حالتهای تجزیهٔ عبارت(x/y+(10+32))-(3*(Pow(x,y)))را میبینید. البته در اینجا هم همان قواعد به گونهای دیگر صادق است. با توجه به قواعد توافقی و همچنین نیاز میتوان حالتهای دیگری از تجزیه را به دست آورد. با شروع از پایین به بالا و قرار دادن پدر هر یک از گرهها به عنوان عملوند ان دو گره؛ عبارت مورد نظر به دست میآید.

همانطور که در شکل فوق نیز میبینید، تمام عملگرها و توابعی که پارامتر به عنوان ورودی دریافت میکنند در ریشه زیردرختها قرار میگیرند و متغیرها، ثابتها، و توابعی که پارامتر به عنوان ورودی دریافت نمیکنند، در برگها قرار داده میشوند. گرههای ریشه که به هیچ چیز دیگری بستگی ندارند و فرزند نیز ندارند، اصطلاحاً پایانه(Terminals) نامیده میشوند.