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

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

دید کلی

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

مثال

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

  
               *₂
              / \
             /   \
            +₂    +₁
           / \   / \
          /   \ d₁  3₀
         +₁   *₁
        / \   / \
       b₁  c₀f₁  g₀
  
از این درخت می‌توان دید که ما به 2 ثبات برای محاسبه زیردرخت چپ "*" نیاز داریم، ولی فقز 1 ثبات برای محاسبه زیردرخت راست. گره‌های "c" و "g" به دلایل زیر به ثبات نیاز ندارند: اگر T یک برگ درخت باشد، آنگاه تعداد ثباتهای لازم برای ارزیابی براساس اینکه T زیردرخت راست یا چپ باشد، 0 یا 1 می‌شود.(از آنجایی که عملیاتی مانند جمع کردن A و R1 می‌تواند به صورت مستقیم و بدون ذخیره‌سازی مؤلفه سمت راست در ثبات انجام گیرد). بنابراین ما اول باید شروع به نشر کد زیردرخت چپ کنیم، چرا که ممکن است ما به موقعیتی برسیم که فقط 2 ثبات برای انجام کلیه محاسبات باقی‌مانده باشد. اگر ما حالا زیردرخت سمت راست را محاسبه کنیم (که فقط 1 ثبات نیاز دارد)، پس از آن ما نیاز به 1 ثبات برای نگهداری نتیجه زیردرخت سمت راست داریم، در زمانی که در حال محاسبه زیردرخت چپ هستیم (که به 2 ثبات نیاز خواهد داشت)، در نتیجه به صورت همزمان به 3 ثبات نیاز خواهیم داشت. محاسبه زیردرخت چپ به 2 ثبات نیاز دارد ولی نتیجهٔ آن را می‌توان در 1 ثبات ذخیره کرد، و از آنجا که زیردرخت راست فقط به 1 ثبات نیاز دارد، ارزیابی عبارت را با 2 ثبات باقی‌مانده امکان‌پذیر است.

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

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