موضوع مقاله: الگوریتم سثی-اولمن | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم سثی-اولمن | مقدمه: این الگوریتم درخت نحوی محض را با استفاده از کمترین دستورالعمل ممکن به زبان ماشین ترجمه می‌کند. | ## بخش 1: الگوریتم سثی-اولمن | دید کلی هنگام تولید کد برای عبارتهای حسابی، مترجم باید تصمیم بگیرد که بهترین راه برای ترجمه عبارت با توجه به تعداد دستورالعمل‌های استفاده شده و همچنین تعداد ثبات‌های لازم برای ارزیابی یک زیر درخت معین، کدام است. به خصوص در صورتی که تعداد ثبات‌های آزاد اندک باشند، ترتیب ارزیابی نسبت به طول کد تولید شده می‌تواند مهم باشد، زیرا ترتیب‌های مختلف شاید باعث جابجا شدن تعداد زیاد یا اندکی از کدمیانی از حافظه و بازگرداندن به آن می‌شود. (با این فرض که خاصیت جابجایی و انجمنی در بیش تر موارد براساس عملگر اعمال می‌شود ولی خاصیت توزیع پذیری مانند a * b + a * c = a * (b + c) برقرار نیست. ) لطفاً توجه داشته باشید که الگوریتم زمانی به درستی اجرا می‌شود که هیچ‌کدام از خاصیت جابجایی و خاصیت انجمنی برای عبارت مورد استفاده برقرار نباشد و همچنین تغییر شکل محاسباتی قابل انجام نباشد. (برای مثال 1 ثبات برای نگهداری متغیر/میدان/غیره لازم است.) و به هر گره برگ ثابت (سمت راست عملگر، لیترال، مقادیر) "0" تخصیص دهید. | ## بخش 2: الگوریتم سثی-اولمن | به هر گره غیربرگ n، عدد تعداد ثبات‌های لازم برای ارزیابی زیردرخت مربوطه را تخصیص دهید. اگر تعداد ثبات‌ها لازم برای زیردرخت چپ (l) با تعداد ثبات‌ها لازم برای زیردرخت راست (r) برار نبود، تعداد ثبات‌های لازم برای گرهٔ n بیشینه l و r می‌شود. نشر کد اگر تعداد ثبات‌های لازم برای محاسبه زیردرخت چپ گره n بزرگتر از تعداد ثبات‌های لازم برای محاسبه زیردرخت راست بود، آنگاه زیردرخت چپ اول مورد ارزیابی قرار می‌گیرد (از آنجا که ممکن است که به یک ثبات بیش تر برای زیردرخت راست نیاز باشد، برای ذخیره نتیجه زیردرخت چپ را به حافظه منتقل می‌کنیم). اگر زیر درخت راست تعداد بیش تری ثبات نسبت به زیردرخت چپ نیاز داشت، بر این اساس زیردرخت راست چپ اول مورد ارزیابی قرار می‌گیرد. اگر هر دو زیردرخت تعداد یکسانی ثبات نیاز داشتند، آنگاه ترتیب ارزیابی فرقی ندارد. | ## بخش 3: الگوریتم سثی-اولمن | مثال برای عبارت حسابی (a = (b + c+ f * g) * (d + 3 درخت نحوی محض به این شکل خواهد بود: = / \ a * / \ / \ + + / \ / \ / \ d 3 + * / \ / \ b c f g برای اجرای ادامه الگوریتم، ما فقط نیاز داریم عبارت (b + c + f * g) * (d + 3) را امتحان کنیم، به عنوان مثال ما فقط باید به زیردرخت راست علامت "=" نگاه کنیم: * / \ / \ + + / \ / \ / \ d 3 + * / \ / \ b c f g حال ما شروع به تبدیل درخت به پیمایش پیش ترتیب می‌کنیم، برای ارزیابی هر زیر درخت تعداد ثبات‌های لازم را تخصیص می‌دهیم. ) *2 / \ / \ +2 +1 / \ / \ / \ d1 30 +1 *1 / \ / \ b1 c0f1 g0 از این درخت می‌توان دید که ما به 2 ثبات برای محاسبه زیردرخت چپ "*" نیاز داریم، ولی فقز 1 ثبات برای محاسبه زیردرخت راست. گره‌های "c" و "g" به دلایل زیر به ثبات نیاز ندارند: اگر T یک برگ درخت باشد، آنگاه تعداد ثباتهای لازم برای ارزیابی براساس اینکه T زیردرخت راست یا چپ باشد، 0 یا 1 می‌شود.(از آنجایی که عملیاتی مانند جمع کردن A و R1 می‌تواند به صورت مستقیم و بدون ذخیره‌سازی مؤلفه سمت راست در ثبات انجام گیرد). بنابراین ما اول باید شروع به نشر کد زیردرخت چپ کنیم، چرا که ممکن است ما به موقعیتی برسیم که فقط 2 ثبات برای انجام کلیه محاسبات باقی‌مانده باشد. اگر ما حالا زیردرخت سمت راست را محاسبه کنیم (که فقط 1 ثبات نیاز دارد)، پس از آن ما نیاز به 1 ثبات برای نگهداری نتیجه زیردرخت سمت راست داریم، در زمانی که در حال محاسبه زیردرخت چپ هستیم (که به 2 ثبات نیاز خواهد داشت)، در نتیجه به صورت همزمان به 3 ثبات نیاز خواهیم داشت. | ## جمع‌بندی | محاسبه زیردرخت چپ به 2 ثبات نیاز دارد ولی نتیجهٔ آن را می‌توان در 1 ثبات ذخیره کرد، و از آنجا که زیردرخت راست فقط به 1 ثبات نیاز دارد، ارزیابی عبارت را با 2 ثبات باقی‌مانده امکان‌پذیر است.