یک ساختار درختی یا ترسیم درختی یا درخت تجزیه درختی است که نشان دهندهٔ ساختار دستوری ( نحوی ) یک رشته است. معمولاً این نمایش با توجه به دستور زبان های رسمی است. دریک درخت تجزیه گره های داخلی، نقش های دستوری و برگ ها یا همان گره های خارجی کلمات مربوط به آن نقش هستند.
فرض کنید ( G= ( V, T, P, S یک گرامر مستقل از متن باشد، یک درخت مرتب یک درخت تجزیه برای گرامر G است اگر خصوصیات زیر را داشته باشد:
• ۱ - ریشه درخت دارای برچسب S است.
• ۲ - هر برگ دارای برچسبی از{T∪{ε است.
• ۳ - هر گره میانی دارای برچسبی از V است.
• ۴ - اگر یک گره درونی برچسب A∈V داشته باشد و فرزندانش از چپ به راست دارای برچسب های X1 X2 . . . . Xi باشند، A ⟶ X1 X2 . . . Xi یکی از قوانین تولید باشد.
• ۵ - گره ای که دارای برچسب ε است، دارای هیچ همزادی نمی باشد.
یکی از نیازمندیهای اساسی که در تولید برنامه ها نیاز است، این است که بایستی از لحاظ دستوری، درستی برنامه های نوشته شده تائید گردند. اغلب غیرممکن است که یک برنامهٔ نوشته شده با زبان های کامپیوتری را به شکل اولیه نوشته شده توسط برنامه نویس؛ اجرا کنیم، زیرا اولاً برنامه نوشته شده به احتمال زیاد با خطاهای دستوری کاربر همراه است و ثانیاً اینکه فرم اولیه برنامه ها سطح بالا بوده و قابل تبدیل به کد، در همان شکل اولیه اش نیست؛ بنابراین برنامه بایستی در ابتدا به یک شکل بهتری تبدیل شود؛ بنابراین کامپایلرها سعی می کنند که برنامه نوشته شده را به یک فرم یکنوا و ساده تر که درخت تجزیه نام دارند، تبدیل کنند. درخت تجزیه با بحث کامپایلرها ( همگردان ) مرتبط است. برنامه ای که این چنین درخت هایی را تولید می کنند؛ تجزیه کننده ( Parser ) نامیده می شوند. درخت های تجزیه ممکن است برای جملات و عبارات زبان های روزمره مورد استفاده قرار بگیرند یا در پردازش زبان های کامپیوتری ( زبان های برنامه نویسی ) مثل: C، جاوا، دلفی و . . . بکار گرفته شوند. کارکرد این درخت بدین صورت است که با یک درخت تجزیه مثل دیگر درخت ها از یال و گره تشکیل شده است.
در زیر مثال هایی از این نوع درخت را می بینید. البته شکل ۱، یک حالت از درخت تجزیهٔ این جمله است، که البته حالت های دیگری را نیز می توان متصور بود. درخت تجزیه یک ساختار کامل است که با جمله شروع می شود و به نقش های دستوری در برگ های انتهایی، پایان می یابد. البته این در صورتی درست است که که عبارتی مورد بررسی یک عبارت یا جمله از جملات روزمره باشد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلففرض کنید ( G= ( V, T, P, S یک گرامر مستقل از متن باشد، یک درخت مرتب یک درخت تجزیه برای گرامر G است اگر خصوصیات زیر را داشته باشد:
• ۱ - ریشه درخت دارای برچسب S است.
• ۲ - هر برگ دارای برچسبی از{T∪{ε است.
• ۳ - هر گره میانی دارای برچسبی از V است.
• ۴ - اگر یک گره درونی برچسب A∈V داشته باشد و فرزندانش از چپ به راست دارای برچسب های X1 X2 . . . . Xi باشند، A ⟶ X1 X2 . . . Xi یکی از قوانین تولید باشد.
• ۵ - گره ای که دارای برچسب ε است، دارای هیچ همزادی نمی باشد.
یکی از نیازمندیهای اساسی که در تولید برنامه ها نیاز است، این است که بایستی از لحاظ دستوری، درستی برنامه های نوشته شده تائید گردند. اغلب غیرممکن است که یک برنامهٔ نوشته شده با زبان های کامپیوتری را به شکل اولیه نوشته شده توسط برنامه نویس؛ اجرا کنیم، زیرا اولاً برنامه نوشته شده به احتمال زیاد با خطاهای دستوری کاربر همراه است و ثانیاً اینکه فرم اولیه برنامه ها سطح بالا بوده و قابل تبدیل به کد، در همان شکل اولیه اش نیست؛ بنابراین برنامه بایستی در ابتدا به یک شکل بهتری تبدیل شود؛ بنابراین کامپایلرها سعی می کنند که برنامه نوشته شده را به یک فرم یکنوا و ساده تر که درخت تجزیه نام دارند، تبدیل کنند. درخت تجزیه با بحث کامپایلرها ( همگردان ) مرتبط است. برنامه ای که این چنین درخت هایی را تولید می کنند؛ تجزیه کننده ( Parser ) نامیده می شوند. درخت های تجزیه ممکن است برای جملات و عبارات زبان های روزمره مورد استفاده قرار بگیرند یا در پردازش زبان های کامپیوتری ( زبان های برنامه نویسی ) مثل: C، جاوا، دلفی و . . . بکار گرفته شوند. کارکرد این درخت بدین صورت است که با یک درخت تجزیه مثل دیگر درخت ها از یال و گره تشکیل شده است.
در زیر مثال هایی از این نوع درخت را می بینید. البته شکل ۱، یک حالت از درخت تجزیهٔ این جمله است، که البته حالت های دیگری را نیز می توان متصور بود. درخت تجزیه یک ساختار کامل است که با جمله شروع می شود و به نقش های دستوری در برگ های انتهایی، پایان می یابد. البته این در صورتی درست است که که عبارتی مورد بررسی یک عبارت یا جمله از جملات روزمره باشد.
wiki: ساختار درختی