برداشت کلی شما از مقاله‌ی داده‌شده چیست؟

مقاله: هنگام تولید کد برای عبارتهای حسابی، مترجم باید تصمیم بگیرد که بهترین راه برای ترجمه عبارت با توجه به تعداد دستورالعمل‌های استفاده‌شده و همچنین تعداد ثبات‌های لازم برای ازریابی یک زیر درخت معین، کدام است. به خصوص در صورتی که تعداد ثبات‌های آزاد اندک باشند، ترتیب ارزیابی نسبت به طول کد تولید شده می‌تواند مهم باشد، زیرا ترتیب‌های مختلف شاید باعث جابجا شدن تعداد زیاد یا اندکی از کدمیانی از حافظه و بازگرداندن به آن می‌شود. الگوریتم sethi–ullman (که با نام sethi–ullman numbering نیز شناخته می‌شود) ویژگی تولید کدی که نیاز به کمترین تعداد دستورالعمل ممکن، همچنین کمترین حداقل تعداد رجوع به حافظه را دارد، را برآورده می‌کند. (با این فرض که خاصیت جابجایی و انجمنی در بیش‌تر موارد براساس عملگر اعمال می‌شود ولی خاصیت توزیع پذیری مانند a * b + a * c = a * (b + c) برقرار نیست.) لطفا توجه داشته باشید که الگوریتم زمانی به درستی اجرا می‌شود که هیچ‌کدام از خاصیت جابجایی و خاصیت انجمنی برای عبارت مورد استفاده برقرار نباشد و همچنین تغییر شکل محاسباتی قابل انجام نباشد. الگوریتم sethi–ullman ساده به صورت زیر کار می‌کند (برای معماری load-store): درخت نحوی محض را به صورت پیمایش پیش یا پس ترتیب بنویسید به هر گره برگ غیر ثابت، یک «۱» تخصیص دهید. (برای مثال ۱ ثبات برای نگهداری متغیر / میدان / غیره لازم است.) و به هر گره برگ ثابت (سمت راست عملگر، لیترال، مقادیر) «۰» تخصیص دهید. به هر گره غیربرگ n، عدد تعداد ثبات‌های لازم برای ارزیابی زیردرخت مربوطه را تخصیص دهید. اگر تعداد ثبات‌ها لازم برای زیردرخت چپ (l) با تعداد ثبات‌ها لازم برای زیردرخت راست (r) برار نبود، تعداد ثبات‌های لازم برای گره n بیشینه l و r می‌شود. حال اگر l و r برابر بودند، تعداد ثبات‌های لازم برای گره l+ ۱ خواهد شد. نشر کد اگر تعداد ثبات‌های لازم برای محاسبه زیردرخت چپ گره n بزرگتر از تعداد ثبات‌های لازم برای محاسبه زیردرخت راست بود، آنگاه زیردرخت چپ اول مورد ارزیابی قرار می‌گیرد (از آنجا که ممکن است که به یک ثبات بیش‌تر برای زیردرخت راست نیاز باشد، برای ذخیره نتیجه زیردرخت چپ را به حافظه منتقل می‌کنیم). اگر زیر درخت راست تعداد بیش‌تری ثبات نسبت به زیردرخت چپ نیاز داشت، بر این اساس زیردرخت راست چپ اول مورد ارزیابی قرار می‌گیرد. اگر هر دو …
برداشت:
الگوریتم sethi–ullman درعلوم رایانه الگوریتم sethi–ullman به خاطر مخترعین آن ravi sethi و jeffrey d.ullman به این نام ، نامگذاری شده‌است . این الگوریتم درخت نحوی محض را با استفاده از کمترین دستورالعمل ممکن به زبان ماشین ترجمه می‌کند .