الگوریتم سثی-اولمن

الگوریتم Sethi–Ullman درعلوم رایانه الگوریتم Sethi–Ullman به خاطر مخترعین آن Ravi Sethi و Jeffrey D. Ullman به این نام، نامگذاری شده‌است. این الگوریتم درخت نحوی محض را با استفاده از کمترین دستورالعمل ممکن به زبان ماشین ترجمه می‌کند.

دید کلی

هنگام تولید کد برای عبارتهای حسابی، مترجم باید تصمیم بگیرد که بهترین راه برای ترجمه عبارت با توجه به تعداد دستورالعمل‌های استفاده شده و همچنین تعداد ثبات‌های لازم برای ازریابی یک زیر درخت معین، کدام است. به خصوص در صورتی که تعداد ثبات‌های آزاد اندک باشند، ترتیب ارزیابی نسبت به طول کد تولید شده می‌تواند مهم باشد، زیرا ترتیب‌های مختلف شاید باعث جابجا شدن تعداد زیاد یا اندکی از کدمیانی از حافظه و بازگرداندن به آن می‌شود. الگوریتم Sethi–Ullman (که با نام Sethi–Ullman numbering نیز شناخته می‌شود) ویژگی تولید کدی که نیاز به کمترین تعداد دستورالعمل ممکن، همچنین کمترین حداقل تعداد رجوع به حافظه را دارد، را برآورده می‌کند. (با این فرض که خاصیت جابجایی و انجمنی در بیش تر موارد براساس عملگر اعمال می‌شود ولی خاصیت توزیع پذیری مانند a * b + a * c = a * (b + c) برقرار نیست. ) لطفاً توجه داشته باشید که الگوریتم زمانی به درستی اجرا می‌شود که هیچ‌کدام از خاصیت جابجایی و خاصیت انجمنی برای عبارت مورد استفاده برقرار نباشد و همچنین تغییر شکل محاسباتی قابل انجام نباشد.

الگوریتم Sethi–Ullman ساده

الگوریتم Sethi–Ullman ساده به صورت زیر کار می‌کند (برای معماری load-store):

1. درخت نحوی محض را به صورت پیمایش پیش یا پس ترتیب بنویسید
   1. به هر گره برگ غیر ثابت، یک "1" تخصیص دهید. (برای مثال 1 ثبات برای نگهداری متغیر/میدان/غیره لازم است.) و به هر گره برگ ثابت (سمت راست عملگر، لیترال، مقادیر) "0" تخصیص دهید.
   2. به هر گره غیربرگ n، عدد تعداد ثبات‌های لازم برای ارزیابی زیردرخت مربوطه را تخصیص دهید. اگر تعداد ثبات‌ها لازم برای زیردرخت چپ (l) با تعداد ثبات‌ها لازم برای زیردرخت راست (r) برار نبود، تعداد ثبات‌های لازم برای گرهٔ n بیشینه l و r می‌شود. حال اگر l و r برابر بودند، تعداد ثبات‌های لازم برای گره l+1 خواهد شد.
2. نشر کد
   1. اگر تعداد ثبات‌های لازم برای محاسبه زیردرخت چپ گره n بزرگتر از تعداد ثبات‌های لازم برای محاسبه زیردرخت راست بود، آنگاه زیردرخت چپ اول مورد ارزیابی قرار می‌گیرد (از آنجا که ممکن است که به یک ثبات بیش تر برای زیردرخت راست نیاز باشد، برای ذخیره نتیجه زیردرخت چپ را به حافظه منتقل می‌کنیم). اگر زیر درخت راست تعداد بیش تری ثبات نسبت به زیردرخت چپ نیاز داشت، بر این اساس زیردرخت راست چپ اول مورد ارزیابی قرار می‌گیرد. اگر هر دو زیردرخت تعداد یکسانی ثبات نیاز داشتند، آنگاه ترتیب ارزیابی فرقی ندارد.

مثال

برای عبارت حسابی (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

حال ما شروع به تبدیل درخت به پیمایش پیش ترتیب می‌کنیم، برای ارزیابی هر زیر درخت تعداد ثبات‌های لازم را تخصیص می‌دهیم. (دقت کنید که آخرین عملوند جمع در عبارت (b + c + f * g) * (d + 3) یک ثابت است. )

               *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 ثبات باقی‌مانده امکان‌پذیر است.

الگوریتم Sethi–Ullman پیشرفته

در نسخه پیشرفته الگوریتم Sethi–Ullman، عبارات محاسباتی ابتدا با استفاده از خواص جبری عملگرهای استفاده شده، تبدیل می‌شوند.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Sethi-Ullman-algorithm». در دانشنامهٔ ویکی‌پدیای انگلیسی.