ساختار درختی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

فرض کنید (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) نامیده می شوند.

پیوندهای درونی[ویرایش]

پیوند به بیرون[ویرایش]

منابع[ویرایش]