مشاهده

Report
‫بسم هللا الرحمن‬
‫الرحیم‬
‫فصل‪8‬‬
‫کنترل ترتیب اجرا‬
‫رضاخرمی‪ ،‬علی رزمجویی‬
‫استاد مربوطه ‪ :‬استاد بیدکی‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪2‬‬
‫فهرست مطالب‬
‫‪-1‬مقدمه‬
‫‪ -2‬کنترل ترتیب ضمنی و صریح‬
‫‪-3‬ترتیب اجرا در عبارات محاسباتی‬
‫• نمایش درختی عبارات‬
‫• نمایش زمان اجرا‬
‫‪ -3‬کنترل ترتیب بین دستورات‬
‫• دستورات اصلی‬
‫• کنترل ترتیب ساخت یافته‬
‫• برنامه های بنیاد‬
‫‪-4‬ترتیب در عبارات غیر محاسباتی‬
‫• تطابق الگو‬
‫• اتحاد‬
‫• عقبگرد‬
‫• اصل راه حل‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪3‬‬
‫مقدمه‬
‫ساختارهای کنترلی در زبان برنامه نویسی‪ ،‬چارچوبی اند که عملیات و داده ها را‬
‫در برنامه ها و مجموعه ای از برنامه ها را با هم ترکیب میکند‪.‬‬
‫این کار دو جنبه دارد‪:‬‬
‫‪ ‬کنترل ترتیب اجرای عملیات است که آن را که کنترل ترتیب می نامند و در این فصل‬
‫بررسی می شود‪.‬‬
‫‪ ‬کنترل انتقال داده ها بین زیربرنامه ها و برنامه ها است که آن را کنترل داده ها می نامند‬
‫(در دو فصل بعد بررسی می شود)‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪4‬‬
‫کنترل ترتیب ضمنی و صریح‬
‫ساختارهای کنترل ترتیب به چهار دسته تقسیم می شوند‪:‬‬
‫‪ ‬ساختارهایی که در عبارات مورد استفاده قرار می گیرند‪ ،‬مثل قاعده تقدم عملگرها و پرانتزها‪.‬‬
‫‪ ‬ساختارهایی که بین دستورات یا گروهی از دستورات به کار می روند‪ ،‬مثل دستورات شرطی و‬
‫تکراری‪.‬‬
‫‪ ‬برنامه نویسی اعالنی‪ ،‬یک مدل اجرایی است که به دستورات بسنگی ندارد‪ ،‬اما موجب پیشروی‬
‫کنترل اجرا در برنامه می شود‪ .‬برنامه نویسی منطقی در پرولوگ نمونه ای از آن است‪.‬‬
‫‪ ‬کنترل ترتیب در زیر برنامه ها‪ ،‬مثل فراخوانی زیربرنامه ها و همروالها که مو جب انتقال کنترل از‬
‫نقطه ای به نقطه ی دیگری از برنامه می شود‪.‬‬
‫‪ ‬زبانهایی مثل لیسپ و ‪ APL‬فاقد کنترل ترتیب دستورات هستند‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪5‬‬
‫کنترل ترتیب ضمنی و صریح‬
‫(ادامه)‬
‫ساختارهای کنترل ترتیب ممکن است ضمنی یا صریح باشند‪:‬‬
‫‪ ‬ساختار های کنترل ضمنی ‪ ،‬اجراي دستورات به صورت پیش فرض توسط زبان برنامه نویسي‬
‫مشخص مي شود‪ .‬به عنوان مثال ترتیب اجرای عملیات ها در یک عبارت بدون پرانتز‬
‫‪ ‬ساختار کنترل ترتیب صریح‪ ،‬توسط برنامه نویس تعریف می شود‪.‬به عنوان مثال وارد کردن پرانتز‬
‫در عبارات ریاضی و استفاده از ‪goto‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪6‬‬
‫ترتیب اجرا در عبارات محاسباتی‬
‫عبارات وسیله ای قدرتمند و طبیعی برای نمایش دنباله از عملیات است‪.‬‬
‫اما برنامه نویس ترتیب اجرای آنها را چگونه درک میکند؟‬
‫‪ ‬مکانییزم های کنترل ترتیب که برای تعیین ترتیب عملیات در این عبارات به کار می روند‪ ،‬پیچیده‬
‫و ظریف اند‪.‬‬
‫‪ ‬مثال‪ :‬فرمول محاسبه ی ریشه های معادله ی درجه دوم را در نظر بگیرید؟‬
‫××‪−± 2 −4‬‬
‫= ‬
‫×‪2‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪7‬‬
‫نمایش درختی عبارات‬
‫‪‬با در نظر گرفتن عملیات در عبارات آرگومانهای عملیات را عملوند می نامیم‪.‬‬
‫‪‬مکانیزم کنترل ترتیب در عبارات ترکیب تابعی است یعنی عملیات و عملوندهایش مشخص می شود‪.‬‬
‫‪‬ترکیب تابعی ساختار درختی را به عبارات ِاعمال می کند‪.‬‬
‫‪ ‬نمایش رختی ساختار کنترلی عبارات را نشان می دهد ‪ .‬نتایج ارجاع به داده ها یا عملیات در در‬
‫سطوح پایین تر درخت‪ ،‬به عنوان عملوند های عملیات سطوح باالتر محسوب می شود‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪8‬‬
‫مثال‪:‬‬
‫عبارت مربوط به محاسبه ی معادله ی درجه ی دوم‪:‬‬
‫) ∗‪ = (− +   ∗∗ 2 − 4∗ ∗  )/(2‬‬
‫‪/‬‬
‫*‬
‫‪+‬‬
‫‪2‬‬
‫‪A‬‬
‫مشکالت‬
‫‪ -1‬آیا ‪ –B‬باید قبل یا بعد از ‪B**2‬‬
‫ارزیابی شود‪.‬‬
‫‪-2‬مشخص نیست که دو ارجاع به شناسه‬
‫ی ‪ B‬می تواند در یک ارجاع جا داده شود‬
‫یا خیر‪.‬‬
‫‪SQR‬‬
‫‪T‬‬
‫‬‫*‬
‫**‬
‫*‬
‫‪C‬‬
‫‪A‬‬
‫فصل هشتم‬
‫‪-‬‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪B‬‬
‫‪4‬‬
‫‪2‬‬
‫‪B‬‬
‫‪9‬‬
‫نحو عبارات‬
‫ترتیب اجرا در عبارات محاسباتی(ادامه)‬
‫اگر عبارات به صورت درختی نمایش داده شوند‪ ،‬در برنامه ها باید عبارات را به صورت یک دنباله ی خطی مشخص کرد‪:‬‬
‫‪ ‬نشانه گذاری ‪prefix‬‬
‫‪ ‬نشانه گذاری ‪postfix‬‬
‫‪ ‬نشانه گذاری ‪infix‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪10‬‬
‫نمایش درختی عبارات ‪-‬نحو عبارات‬
‫نشانه گذاری ‪: prefix‬‬
‫در این نوع نشانه گذاری داریم‪:‬‬
‫‪ ‬ابتدا نماد عملیات نوشته می شود‪ .‬و سپس عملوندها به ترتیب از چپ به راست نوشته خواهند شد‪.‬‬
‫‪ ‬اگرعملوند ی خودش یک عملیات باشد که این عملیات دارای عملوند های دیگری باشد‪ ،‬این قاعده‬
‫تکرار می شود‪.‬‬
‫‪ ‬در این نوع نشانه گذاری پرانتز وجود ندارد‪ ،‬که آن را عبارات ‪ polish‬نیز می نامند‪.‬‬
‫نکته‪:‬‬
‫شکلی از این نمایش در لیسپ مورد استفاده قرار می گیرد که ‪ Cambridge Polish‬نام دارد‪ .‬در این‬
‫روش نشانه گذاری عملیات و آرگومانهایش در داخل پرانتز قرار می گیرند‪ .‬بدین ترتیب عبارت مانند‬
‫لیسی تودرتو است که هر لیست با یک نماد عملگر شروع می شود و بعد از آن لیستی ازعملوند ها قرار‬
‫می گیرد‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪11‬‬
‫مثال‬
‫برای درخت زیر میخاهیم عبارات ‪polish‬و ‪ Cambridge polish‬را به دست بیاوریم‪.‬‬
‫×‬
‫‪(×(+ab)(-‬‬
‫‪Polish: ×+ab-ca‬‬
‫‪Cambridge polish:‬‬
‫))‪ca‬‬
‫‪-‬‬
‫‪a‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪+‬‬
‫‪c‬‬
‫‪b‬‬
‫‪a‬‬
‫‪12‬‬
‫نمایش درختی عبارات‪-‬نحو عبارات‬
‫نشانه گذاری ‪postfix‬‬
‫‪ ‬همانند نشانه گزاری ‪ prefix‬است با این تفاوت که عملگرها بعد از عملوندها می آیند‪.‬‬
‫* مثال‬
‫برای مثال قبل نشانه گذاری ‪ postfix‬آن را به دست بیاورد؟‬
‫×‪ab+ca-‬‬
‫نشانه گذاری ‪infix‬‬
‫‪ ‬برای عملیات دودویی بسیار مناسب است‪.‬‬
‫‪ ‬در این نوع نشانه گذاری عملگر بین عملوندها نوشته می شود‪.‬‬
‫‪ ‬در این نوع نشانه گذاری از پرانتز هم استفاده می شود‪.‬‬
‫‪ ‬برای عملیات محاسبه ای و منطقی و رابطه ای در ریاضیات به کار می رود‪.‬‬
‫‪ ‬برای عملگرهایی که بیش از دو عملوند دارند مناسب نیست‪.‬‬
‫مثال‬
‫فصل هشتم‬
‫برای مثال قبل داریم‪:‬‬
‫)‪Infix : (a+b)*(c-a‬‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪13‬‬
‫ارزیابی عبارات‬
‫ارزیابی عبارات ‪:prefix‬‬
‫‪ ‬با یک بار پیمایش عبارات می توانیم آن را ارزیابی کنیم‪ .‬باید تعداد آرگومانهای هرعملیات را بدانیم‪ ،‬به‬
‫همین دلیل نمادهای منحصر به فردی برای عملگرها در نظر گرفته می شود‪.‬‬
‫این نوع نشانه گذاری عالوه بر صرفه جویی در پرانتز‪ ،‬ارزشهای خاصی در زبان های برنامه سازی‬
‫دارند‪ ،‬که می توان موارد زیر را نام برد‪:‬‬
‫‪ ‬فراخوانی تابع به صورت نشانه گذاری ‪ prefix‬انجام می شود‪.‬‬
‫‪ ‬برای نمایش عملیاتی با هر تعدادی از عملوندها به کار گرفته می شود‪ .‬بنابراین یک شیوه ی کلی است‪.‬‬
‫‪ ‬نشانه گذاری ‪ prefix‬را به راحتی می توان رمز گشایی کرد و به همین دلیل‪ ،‬ترجمه ی عبارات‬
‫‪ prefix‬به دنباله ای از کدهای ساده‪ ،‬انجام پذیر است‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪14‬‬
‫الگوریتم رمز گشایی ‪prefix‬‬
‫رمزگشایی نشانه گذاری ‪:prefix‬‬
‫برای اینکار مراحل زیر را باید انجام دهیم(فرض کنید ‪ p‬یک عبارت ‪ prefix‬هست)‪.‬‬
‫‪ ‬اگر قلم بعدی در ‪ p‬یک عملگر است‪ ،‬آن را به باالی پشته اضاف کنید‪.‬‬
‫‪ ‬اگر قلم بعدی ‪ p‬یک عملوند باشد آن را در باالی پشته قرار دهید‪.‬‬
‫‪ ‬اگر عملوندهای مورد نیاز یک عملگر در باالی پشته قرار داشت‪ ،‬می توان عملگر را بر روی این‬
‫عملوندها عمل کنیم‪.‬‬
‫عیب این روش‬
‫پس از قرار دادن هر عملوند در باالی پشته باید چک کنیم ببینیم آیا تعداد‬
‫عملوندهای الزم برای عملگر فعلی باالی پشته‪ ،‬وجود دارد یا خیر‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪15‬‬
‫الگوریتم رمز گشایی ‪postfix‬‬
‫ارزیابی عبارات ‪:postfix‬‬
‫نکته‪:‬‬
‫در اینجا برخالف نشانه گذاری ‪ ،prefix‬چون عملگر موجود در نشانه گذاری ‪ postfix‬بعد از‬
‫عملوندهایش قرار دارد‪ ،‬وقتی عملگری پیمایش می شود‪ ،‬عملوندهایش قبال ارزیابی شده اند‪.‬‬
‫مراحل الگوریتم ‪ postfix‬به صورت زیر است‪:‬‬
‫‪ ‬اگر قلم بعدی در ‪ p‬یک عملوند باشد‪ ،‬آن را در باالی پشته قرار دهید‪.‬‬
‫‪ ‬اگر قلم بعدی در ‪ p‬یک عملگر ‪ n‬تایی است‪ ،‬و ‪ n‬آرگومان آن در باالی پشتته قرار دارد‪ ،‬به جای این‬
‫‪ n‬قلم‪ ،‬نتیجه ی اجرای عملگر بر روی آنها در پشته قرار دهید‪.‬‬
‫مزیت‪:‬‬
‫چون استراتژی ارزیابی و پیاده سازی آن ساده است‪ ،‬اساس کار بسیاری از مفسرها برای تولید کد‬
‫است‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪16‬‬
‫ارزیابی عبارات ‪infix‬‬
‫ارزیابی عبارات ‪:infix‬‬
‫گرچه نشانه گذاری ‪ infix‬متداول است‪ ،‬استفاده از آن در زبان برنامه سازی مشکالتی را به وجود می‬
‫آورد‪:‬‬
‫‪ ‬چون نشانه گذاری ‪ infix‬فقط برای عملگرهای دودویی مناسب است‪ ،‬زبان نمی تواند تنها از این نشانه‬
‫گذاری استفاده کند‪.‬بلکه باید نشانه گذاری ‪ infix‬را با ‪ postfix‬یا ‪ prefix‬ترکیب کند‪ .‬این ترکیب‬
‫ترجمه را دشوار میکند‪.‬‬
‫‪ ‬وقتی بیش از یک عملگر ‪ infix‬در عبارتی ظاهر شود‪ ،‬این نشانه گذاری مبهم است‪ ،‬مگر اینکه از‬
‫پرانتز استفاده گردد‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪17‬‬
‫مثال‬
‫عبارت روبه رو که به صورت ‪ infix‬هست رادر نظر بگیرید‪2*3+4:‬‬
‫‪+‬‬
‫*‬
‫‪2‬‬
‫‪+‬‬
‫‪4‬‬
‫‪4‬‬
‫‪3‬‬
‫‪3‬‬
‫‪2*(3+4)=14‬‬
‫فصل هشتم‬
‫*‬
‫‪2‬‬
‫‪(2*3)+4=10‬‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪18‬‬
‫قواعد ضمنی برای کاهش پرانتز‬
‫سلسله مراتب عملگرها(قواعد تقدم عملگرها)‪:‬‬
‫‪ ‬عملگرهایی که در عبارات ظاهر می شوند‪ ،‬به ترتیب سلسله مراتبی یا تقدم قرار می گیرند‪.‬‬
‫‪ ‬در عبارتی که شامل عملگرهایی از چند سطح سلسله مراتب باشد‪ ،‬قاعده ی ضمنی این است که‬
‫عملگرهایی با تقدم باالتر زودتر اجرا شود‪.‬‬
‫سطح تقدم‬
‫باالترین تقدم‬
‫سلسله مراتب در ادا‬
‫پایین ترین تقدم‬
‫فصل هشتم‬
‫عملگرها‬
‫‪** abs not‬‬
‫‪* / mod rem‬‬
‫‪+‬‬‫& _‪+‬‬
‫≥ > < ≤ =‬
‫‪And‬‬
‫‪or‬‬
‫‪xor‬‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫عملیات‬
‫توان‪ ،‬قدر مطلق‪ ،‬نقیض‬
‫ضرب‪ ،‬تقسیم‬
‫جمع‪ ،‬تفریق یکانی‬
‫جمع و تفریق دودویی‬
‫رابطه ا ی‬
‫عملیات بولین‬
‫‪19‬‬
‫قواعد ضمنی برای کاهش پرانتز‬
‫شرکت پذیری‪:‬‬
‫‪ ‬در عباراتی که شامل عملیاتی در یک سلسله مراتب هستند‪ ،‬قاعده ی ضمنی دیگری الزم است تا ترتیب‬
‫عملیات را کامال مشخص کند‪.‬‬
‫‪ ‬شرکت پذیری چپ به راست متداولترین قاعده ی ضمنی است‬
‫استثنا‪:‬‬
‫قواعد ریاضی طوری است که توان از چپ به راست انجام می شود‪.‬‬
‫‪ ‬تقدم عملگرها برای عبارات محاسباتی به خوبی عمل می کند‪ .‬زیرا اغلب برنامه نویسان مدل مربوط به‬
‫معنای عبارات را می شناسند‪.‬‬
‫‪ ‬اگر زبان حاوی عملگرهایی باشد‪ ،‬که در ریاضیات کالسیک موجود نباشند‪ ،‬تقدم ها با شکست مواجه‬
‫می شوند‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪20‬‬
‫نمونه هایی از زبانهایی دارای عملگر توسعه یافته‬
‫نمونه هایی از زبانهایی که عملگرهای توسعه یافته ای دارند‪:‬‬
‫زبان ‪C‬‬
‫این زبان از جدول تقدم پیشرفته ای استفاده می کند‪ .‬اغلب آنها‪ ،‬از قاعده ی شرکت پذیری چپ به راست‬
‫استفاده می کنند‪.‬‬
‫زبان ‪APL‬‬
‫زبانی است که عملیات اولیه آن برای کار کردن بر روی آرایه ها و بردارها طراحی شده است‪ .‬تقدم‬
‫برای عملگرهای آن مصنوعی است و تمام عبارات از راست به چپ ارزیابی می شوند‪ .‬مگر اینکه‬
‫بعضی از عبارات قابل فهم نباشند‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪21‬‬
‫نمونه هایی از زبانهایی دارای عملگر توسعه یافته‬
‫زبات اسمالتاک‬
‫هدف اسمالتاک ایجاد توابع(متدهایی) برای کارایی است‪ ،‬روشن نیست که تابع جدید چه تقدمی باید داشته‬
‫باشد‪ .‬بنابراین تقدم به طور کلی حذف می شود و عبارات از چپ به راست ارزیابی می شود‪.‬‬
‫زبان فورث‬
‫فورث زبانی است که ساختار زمان اجرای آن پشته بوده ‪ ،‬و نحو آن ‪ postfix‬محض بود‪ .‬در ‪postfix‬‬
‫محض تقدم به عنوان یک مشکل مطرح نیست‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪22‬‬
‫ترتیب اجرا در عبارات محاسباتی‪-‬نمایش زمان اجرا‬
‫اگر هر عبارت را به یکی از سه شکل ‪ postfix ,prefix‬و‪ infix‬تبدیل کنیم مترجم برای ارزیابی آن‬
‫عبارت گزینه هایی مختلفی دارد‪.‬‬
‫‪ ‬اولین مرحله در ترجمه‪ ،‬ایجاد ساختار کنترلی درختی برای عبارت است‪.‬‬
‫‪ ‬در مرحله ی اختیاری دوم تصمیمات مشروح در رابطه با ترتیب ارزیابی گرفته می شود‪.‬‬
‫‪ ‬چنانچه در مرحله ی اول عبارت شامل نشانه گذاری ‪ infix‬باشد‪ ،‬از قواعد تقدم و شرکت پذیری‬
‫ضمنی استفاده می شود‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪23‬‬
‫چندين آلترناتيو جهت ايجاد‬
‫فرم اجرايی يك عبارت‬
‫به دلیل مشکل بودن رمز گشایی عبارات به شکل ‪ ،infix‬مطلوب است به شکل اجرایی تبدیل شود که در‬
‫حین اجرا به راحتی رمز گشایی می شود‪ .‬برای اینکار سه روش مختلف داریم‪:‬‬
‫‪ ‬دنباله ای از کد ماشین‪ :‬اگر عبارات را به یک سری کد ماشین واقعی تبدیل کنیم‪ .‬ترتیب این دستورات‬
‫ترتیب عملیات را مشخص می کند‪.‬نمایش کد ماشین استفاده از مفسر سخت افزار را امکان پذیر می‬
‫سازد و موجب افزایش سرعت اجرا می شود‪.‬‬
‫‪ ‬ساختارهای درختی‪ :‬در این روش در مرحله ی اول عبارات به کمک مفسر نرم افزاری به شکل‬
‫درختی در می آیند‪ ،‬سپس در مرحله ی دوم یعنی اجرا‪ ،‬پیمایش درخت انجام می شود‪ .‬این تکنیک در‬
‫زبان لیسپ استفاده می شود ‪.‬‬
‫‪ ‬شکل ‪ prefix‬یا ‪ :postfix‬دو روش ‪ prefix‬یا ‪ postfix‬طبق الگوریتم های قبلی می توانند اجرا‬
‫شوند‪ .‬در برخی از کامپیوترهای واقعی که بر مبنای پشته کار می کنند کد واقعی ماشین به شکل‬
‫‪ postfix‬است‪ .‬اجرا از چپ به راست انجام می شود و هر عملیات مفسر خود را را به طور بازگشتی‬
‫فراخوانی می کند تا عملوندهایش را ارزیابی کند‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪24‬‬
‫نمایش زمان اجرا(ارزیابی نمایش درختی عبارات)‬
‫گرچه ترجمه ی عبارات برنامه به نمایش های درختی گاهی دشوار است‪ ،‬رویه ی اصلی ترجمه آسان است‪.‬‬
‫در مرحله ی دوم‪ ،‬که در آن درخت به دنباله ی اجرایی از عملیات اولیه تبدیل می شود‪ ،‬مسائلی در مورد‬
‫ترتیب ارزیابی مطرح می شود‪.‬‬
‫نکته ی خیلی مهم‬
‫در اینجا نمی خواهیم الگوریتم هایی را مطالعه کنیم که کدی را از نمایش درختی تولید کند‪ ،‬بلکه مسئله‬
‫های مربوط به ترتیب ارزیابی را در هنگام تولید کد‪ ،‬بررسی میکنیم‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪25‬‬
‫مسائلی در مورد ترتیب ارزیابی‬
‫مسئله ی ‪ :1‬قواعد ارزیابی یکنواخت‪:‬‬
‫در ارزیابی عبارات یا تولید کدی برای ارزیابی آن‪ ،‬باید این قاعده ارزیابی یکنواخت اعمال شود‪:‬‬
‫‪ ‬برای هر گره عملیاتی در درخت عبارت‪ ،‬ابتدا هر یک از عملوندهایش را ارزیابی کن ( یا کدی برای‬
‫ارزیابی آن تولید کن) و سپس عملیات را بر روی عملوندهای ارزیابی شده اجرا کن( یا کدی را برای‬
‫انجام عملیات تولید کن) این قاعده ی عملیاتی را عجول(‪ )aeger‬می نامیم‪.‬‬
‫‪ ‬ترتیب دقیق ارزیابی برخی از اعمال مهم نیست‪ ،‬ترتیب ارزیابی عملوندها یا عملیات مستقل به طوری‬
‫انتخاب می شود که از حافظه ی موقت یا سایر ویژگیهای ماشین به طور بهینه استفاده شود‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪26‬‬
‫مثال‪:‬‬
‫)‪(a+b)*(c-a‬‬
‫ترتیب ‪ :1‬ابتدا (‪ )a+b‬محاسبه شود‪.‬‬
‫‪1‬‬
‫‪ -1‬مقدار راست ‪ a‬را بگیر‪.‬‬
‫‪-2‬مقدار راست ‪ b‬را بگری‪.‬‬
‫‪ a-3‬و ‪ b‬را جمع و در ‪ d‬قرار بده‪.‬‬
‫‪-4‬مقدار راست ‪ c‬را بگیر‪.‬‬
‫‪ a-5‬را از ‪ c‬کم کن و در ‪ e‬قرار بده‪.‬‬
‫‪ d -6‬و ‪ e‬را ضرب کن و در ‪ f‬قرار بده‪.‬‬
‫فصل هشتم‬
‫ترتیب ‪ :2‬عملوندها قبل از عملگرها ارزیابی شوند‪.‬‬
‫‪1‬‬
‫‪ -1‬مقدار راست ‪ C‬را بگیر‪.‬‬
‫‪-2‬مقدار راست ‪ b‬را بگری‪.‬‬
‫‪-3‬مقدار راست ‪ a‬را بگیر‪.‬‬
‫‪ a-4‬را از ‪ c‬کم کن و در ‪ e‬قرار بده‪.‬‬
‫‪ a-5‬و ‪ b‬را جمع کن و در ‪ d‬قرار بده‪.‬‬
‫‪ d -6‬و ‪ e‬را ضرب کن و در ‪ f‬قرار بده‪.‬‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪27‬‬
‫مسائلی در مورد ترتیب ارزیابی‪ -‬ارزیابی‬
‫یکنواخت‬
‫‪ ‬این روش همیشه انجام پذیرنیست‪ .‬به عنوان مثال عبارت شرطی زیر را در نظر بگیرید‪.‬‬
‫مثال‬
‫عبارت روبه رو را در نظر بگیرید‪z+(Y=0 ? X : X/Y) .‬‬
‫در این عبارت مشکلی در در رابطه با قواعد ارزیابی یکنواخت وجود دارد‪ .‬اگر عملوندهای عملیات‬
‫شرطی را ارزیابی کنیم نتیجه ای به دست می آید که مورد قبول نیست‪ .‬یعنی اگر ‪ Y‬صفر باشد‪ X ،‬بر‬
‫‪ Y‬تقسیم می شود‪ .‬بدیهی است که در این حالت نمی خاهیم قبل از انجام عملیات‪ ،‬عملوندها ارزیابی‬
‫شوند‪.‬‬
‫‪ ‬مشکل مربوط به عملیات شرطی نشان می دهد که ممکن است قاعده ی ارزیابی یکنواخت دیگری به‬
‫نام قاعده ی ارزیابی تنبل (‪ )lazy‬بهتر باشد‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪28‬‬
‫مسائلی در مورد ارزیابی‪ -‬ارزیابی یکنواخت‬
‫‪ ‬قاعده ی ارزیابی تنبل‪ :‬عملوندها را قبل از اجرای عملیات ارزیابی نکنید‪ .‬بلکه عملوندها را ارزیابی‬
‫نشده ارسال کنید و اجازه دهید عملیات تصمیم بگیرد که ارزیابی الزم است یا خیر‪.‬‬
‫‪ ‬این قاعده ی ارزیابی در تمام موارد عمل میکند‪ .‬اما پیاده سازی آن دشوار است‪ .‬این کار مستلزم شبیه‬
‫سازی نرم افزاری زیادی است‪.‬‬
‫‪ ‬زبانهای محاورهای لیسپ و پرولوگ از این روش برای ارزیابی عبارات استفاده می کنند‪.‬‬
‫‪ ‬دو قاعده ی ارزیابی یکنواخت که مطرح شد‪ ،‬عجول وتنبل معادل ارسال پارامترها به زیر برنامه ها به‬
‫ترتیب انتقال پارامترها با مقدار و نام است‪.‬‬
‫‪ ‬قاعده ی ارزیابی یکنواخت ساده ای وجود ندارد‪ .‬در پیاده سازی های زبان معموال از ترکیبی از این‬
‫دو تکنیک استفاده می شود‪.‬‬
‫‪ ‬در اسنوبال ‪ ،4‬عملیات تعریف شده توسط برنامه نویس‪ ،‬همواره عملوندهای ارزیابی شده دریافت‬
‫میکنند و لی عملیات اولیه ای که توسط زبان تعریف شده اند‪ ،‬عملوند های ارزیابی نشده را دریافت می‬
‫کنند‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪29‬‬
‫مسائلی در مورد ارزیابی‪ -‬اثرات جانبی‬
‫مسئله ی ‪ :2‬اثرات جانبی‬
‫‪ ‬استفاده از عملیاتی که اثرات جانبی بر عبارت دارند‪.‬‬
‫‪ ‬ترتیب ارزیابی باید به طور کامل در این عبارتها مشخص باشد‪.‬‬
‫‪a*fun(x)+a‬‬
‫مثال‪:‬‬
‫فرض کنید مقدار اولیه ‪ a‬برابر با است‪ Fun ،‬مقدار سه را برگرداند‪ ،‬و ‪ a‬را به دو تغییر دهد‪.‬‬
‫داریم‪:‬‬
‫‪1*3+2=5‬‬
‫‪ -1‬هر ترم را به ترتیب ارزیابی کنید‪:‬‬
‫‪1*3+1=4‬‬
‫‪ a -2‬را یک بار ارزیابی کنید‪:‬‬
‫‪3*2+2=8‬‬
‫‪ -3‬تابع ‪ fun‬را قبل از ‪ a‬ارزیابی کنید‪:‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪30‬‬
‫مسائلی در مورد ارزیابی‪-‬اثرات جانبی‬
‫‪ ‬در استفاده از اثرات جانبی در عبارات دو دیدگاه مطرح است‪:‬‬
‫• دیدگاه اول این است که اثرات جانبی باید در عبارات ممنوع باشند که اینکار به دو صورت انجام می‬
‫شود‪:‬‬
‫‪-1‬توابع اجازه نداشته باشند اثرات جانبی به وجود آورند‪.‬‬
‫‪ -2‬مقدار هر عبارتی که اثرات جانبی در آن اثر داشته باشد‪ ،‬تعریف نشده معرفی گردد‪.‬‬
‫• دیدگاه دیگر این است که اثرات جانبی وجود داشته باشد و تعریف زبان دقیقا باید مشخص کند که ترتیب‬
‫ارزیابی عبارات چگونه است‪.‬‬
‫‪ ‬مشکل دیدگاه دوم این است که بسیاری از بهینه سازی ها را غیر ممکن می سازد‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪31‬‬
‫مسائلی در مورد ارزیابی‪ -‬اثرات جانبی‬
‫سؤال‬
‫آیا وابستگی های داخلی از طریق اثرات جانبی ‪ ،‬باید امکان پذیر باشد یا خیر؟‬
‫به این سؤال به دو طریق می توان جواب داد‪:‬‬
‫‪ ‬اگر امکان پذیر نباشد‪ ،‬باید ترتیب عبارات را فقط توسط نمایش درختی مشخص کنیم‪ ،‬که در این حالت ارزیابی عبارات‬
‫توسط برنامه نویس قابل درک است و مترجم می تواند بهینه سازی را انجام دهد‪.‬‬
‫‪ ‬اگر بهینه سازی مهم نباشد‪ ،‬می توان امکان اثرا جانبی را فراهم کرد که در این صورت باید ترتیب ارزیابی را به طور‬
‫کامل مشخص کرد‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪32‬‬
‫مسائلی در مورد ارزیابی‪ -‬شرایط خطا‬
‫مسئله ی ‪ :3‬شرایط خطا‬
‫‪ ‬نوع ویژه ای از اثر جانبی در عملیاتی وجود دارد که ممکن است با شکست مواجه شود و شرایط خطا‬
‫را فراهم کند‪.‬‬
‫‪ ‬شرایط خطا ممکن است در بسیاری از عملیات های اولیه به وجود آیند مانند سرریز وتقسیم بر صفر‪.‬‬
‫‪ ‬معنا و حتی وقوع شرایط خطا ممکن است به خاطر تفاوت در ترتیب ارزیابی اجزای عبارات تحت‬
‫تأثیر قرار بگیرد‪ ،‬در چنین شرایطی برنامه نویس ممکن است مجبور باشد ترتیب ارزیابی را دقیقا‬
‫کنترل کند‪.‬‬
‫‪ ‬راه حل عمومي براي حل اين مشكل وجود ندارد و از يك زبان‬
‫به زبان ديگر متفاوت است‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪33‬‬
‫ارزیابی نمایش درختی عبارات(عبارات بولین مدار کوتاه)‬
‫مسئله ی ‪ :4‬عبارات بولین مدار کوتاه‬
‫‪ ‬در برنامه نویسی از عملیات بولین ‪ and‬و ‪ or‬برای ترکیب عبارات رابطه ای استفاده می شود‪.‬‬
‫مثال‬
‫دستورات زیرا در نظر بگیرید‪:‬‬
‫}…{ ((‪if((A==0(||)B/A>C‬‬
‫&& )‪while ((I<= UB‬‬
‫}‪(v[I]>C)){...‬‬
‫دوم عملگر بولین ممکن است شرایط خطایی به وجود آورد‪ .‬لذا‬
‫‪ ‬در هر دو عبارت ‪ ،‬ارزیابی عملوند ِ‬
‫عملوند اول گنجانده شده تا تضمین کند که خطایی اتفاق نمی افتد‪.‬‬
‫‪ ‬اگر مقدار کل عبارت فقط با توجه به مقدار عملوند سمت چپ تعیین شود‪ ،‬این مقدار می تواند بقیه ی‬
‫عبارت را کوتاه کند‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪34‬‬
‫کنترل ترتیب بین دستورات‪ -‬دستورات اصلی‬
‫در این بخش می خواهیم مکانیزم های اصلی را برای کنترل ترتیب بین دستورات بررسی کنیم‪.‬‬
‫دستورات اصلی‪:‬‬
‫‪ ‬نتایج هر برنامه توسط دستورات اصلی آن تعیین می شود که عملیاتی را بر روی اشیای داده انجام‬
‫میدهد‪.‬‬
‫‪ ‬می توانیم دستورات اصلی را واحدی از برنامه در نظر بگیریم‪ ،‬که یک مرحله از محاسبات را به ما‬
‫نشان می دهد‪.‬‬
‫‪ ‬نمونه هایی از دستورات اصلی عبارتند از انتساب و دنباله ای از عملیات ها که با استفاده از عبارات‬
‫فراخوانی می شوند‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪35‬‬
‫دستورات اصلی‪-‬انتساب به اشیای داده‬
‫برنامه نویس می تواند از طریق انتساب مقادیر به اشیای داده حالت محاسبات را تغییر دهد‪ .‬انتسابها به‬
‫شیوه های گوناگونی انجام می شوند از جمله‪:‬‬
‫دستور انتساب‪:‬‬
‫‪ ‬هدف اولیه انتساب این است که مقدار راست عبارت ( یعنی مقدار اشیای داده) را به مقدار چپ آن‬
‫(یعنی محل حافظه آن) نسبت دهد‪.‬‬
‫مثال‬
‫در ‪ C‬انتساب یک عملگر است‪ ،‬عبارت روبه را در نظر بگیرید‪c=b=1 :‬‬
‫)‪c=(b=1‬‬
‫با توجه به تقدم عملگرها در ‪ ،C‬داریم ‪:‬‬
‫‪ -1‬مقدار یک به ‪ b‬نسبت داده می شود‪.‬‬
‫‪ -2‬عبارت ‪ b=1‬مقدار یک را برمی گرداند‪.‬‬
‫‪ -3‬مقدار یک در ‪ c‬قرار می گیرد‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪36‬‬
‫دستورات اصلی‪-‬انتساب به اشیای داده‪-‬دستورات اصلی‬
‫‪ ‬در برخی از زبانها‪ ،‬انتساب به عنوان یک دستور محسوب می شود‪ .‬مثال در زبان پاسکال‪ ،‬انتساب‬
‫مقدار صحیحی را برنمیگرداند‪.‬‬
‫‪ ‬اغلب زبانها فقط یک عملگر انتساب دارند‪ ،‬ولی ‪ C‬چند عملگر دارد‪)A++ ،++A ،+= ،=(.‬‬
‫‪ ‬انتساب قابلیت انعطاف را افزایش می دهد‪.‬‬
‫‪ ‬در ‪ ،C‬عملگره * یک عملگر ارجاع غیر مستقیم است‪ ،‬که با مقدار راست یک متغیر مثل مقدار چپ آن‬
‫رفتار می کند‪.‬‬
‫‪ ‬عملگر & یک عملگر آدرس هست‪ ،‬که مقدار چپ را به مقدار راست تبدیل میکند‪.‬‬
‫مثال‬
‫فصل هشتم‬
‫;‪int i,*p‬‬
‫;‪P=&I‬‬
‫;‪*P=7‬‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪37‬‬
‫دستورات اصلی‪-‬انتساب به اشیای داده‪ -‬دستورات ورودی‬
‫دستورات وردی‪:‬‬
‫‪ ‬اغلب زبانهای برنامه سازی دستوراتی برای خواندن داده ها از پایانه‪ ،‬فایل یا خطوط ارتباطی دارند‪ .‬این‬
‫دستورات مقادیر متغیرها را با انتساب وردی به متغیرها تغییر میدهند‪.‬‬
‫‪ ‬نحو این دستورات به صورت )‪ read(file,data‬است‪.‬‬
‫سایر عملیات انتساب‪:‬‬
‫‪ ‬انتقال پارامترها به عنوان انتساب مقدار آرگومان به پارامترهای مجازی محسوب می شود‪.‬‬
‫‪ ‬انتسابهای ضمنی نیز وجود دارد مثال در اسنوبال ‪ ،4‬ارجاع به ‪ input‬موجب می شود مقدار جدیدی به‬
‫آن نسبت داده شود‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪38‬‬
‫دستورات اصلی‪ -‬شکلهای مختلف کنترل ترتیب در سطح دستور‬
‫سه شکل مختلف برای کنترل ترتیب سطح دستور وجود دارد‪:‬‬
‫‪composition ‬‬
‫ممکن است دستورات در یک دنباله ی متنی قرار گیرند و هر وقت‬
‫که برنامه ی حاوی آن دنباله اجرا شود این دستورات نیز به‬
‫ترتیب اجرا شوند‪.‬‬
‫‪alternation ‬‬
‫دستوراتي كه دو یا چند آلترناتیو جهت اجرا وجود دارد‪ .‬مثال‬
‫دو دنباله از دستورات ممکن است طوری باشند که یکی از آنها‬
‫اجرا شود و دیگری اجرا نشود‪ .‬ولی هر دو دنباله نمی توانند‬
‫اجرا شوند‪.‬‬
‫‪iteration ‬‬
‫كنترل ترتیب در دستوراتي كه براي چندین بار باید تكرار‬
‫شود‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪39‬‬
‫دستورات اصلی‪-‬کنترل ترتیب ضمنی‬
‫زبانهای برنامه سازی اولیه از دستوراتی برای پیاده سازی کنترل ترتیب ضمنی استفاده می کردند که می‬
‫توان موارد زیر را نام برد‪:‬‬
‫‪ ‬دستور ‪goto‬‬
‫‪ ‬دستور ‪break‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪40‬‬
‫کنترل ترتیب ضمنی( دستور ‪)goto‬‬
‫معموال دو شکل از دستورات ‪ goto‬در بسیاری از زبانها وجود دارد‪:‬‬
‫‪ ‬پرش غیر شرطي ‪:‬‬
‫در این نوع دستور كنترل برنامه بدون شرط به محل دیگري از‬
‫برنامه داده مي شود ‪ .‬مثل ‪Goto NEXT :‬‬
‫‪ ‬پرش شرطي ‪:‬‬
‫در صورت برقراري یك شرط كنترل برنامه به محل دیگري انتقال‬
‫نکتهشود ‪ .‬مثل ‪:‬‬
‫داده مي‬
‫ساده‪then‬‬
‫‪GOTO‬‬
‫)‪(A=0‬به‪if‬دلیل اینکه برنامه را از حالت ساخت یافته خارج می کند‪ ،‬به‬
‫است‪ ،‬ولی‬
‫‪ next‬دستور‬
‫‪ end‬شکل‬
‫‪if‬گرچه‬
‫ندرت مورد استفاده قرار می گیرد‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪41‬‬
‫کنترل ترتیب ضمنی‪-‬دستور ‪break‬‬
‫دستور ‪break‬‬
‫‪ ‬این دستور کنترل اجرا را طرف پایین برنامه و در نقطه ی مشخصی خارج از ساختار‬
‫کنترلی است منتثل می کند‪.‬‬
‫‪ ‬این دستور یک ساختار کنترلی را ارائه می کند که یک نقطه ی ورود و یک نقطه ی‬
‫خروج دارد‪.‬‬
‫دستور ‪continue‬‬
‫‪ ‬در ‪ C‬دستوری به نام ‪ continue‬وجود دارد‪ .‬این دستور موجب می شود کنترل اجرا به‬
‫انتهای بدنه ی حلقه ی تکرار برود‪.‬‬
‫فصل هشتم‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪42‬‬
‫ساختار ‪break‬و ‪continue‬‬
‫{)(‪while‬‬
‫‪-----------‬‬‫‪----------‬‬‫‪----------‬‬‫;‪if () continue‬‬
‫‪-----------‬‬‫‪-----------‬‬‫‪------------‬‬‫}‬
‫فصل هشتم‬
‫در صورتی که شرط ‪if‬‬
‫درست باشد‪ ،‬دستورات‬
‫‪ break‬و ‪continue‬‬
‫اجرا می شود‪.‬‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫{)(‪While‬‬
‫‪----------‬‬‫‪--------‬‬‫‪---------‬‬‫;‪If () break‬‬
‫‪------------‬‬‫‪----------‬‬‫‪-----------‬‬‫}‬
‫‪43‬‬
‫کنترل ترتیب بین دستورات‬
‫دستورات اصلی‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪44‬‬
‫کنترل ترتیب بین دستورات‪ :‬دستورات اصلی‬
‫طراحی برنامه نویس ی ساخت یافته‬
‫• گرچه اغلب زبان ها برچسب ها و دستورات ‪ go to‬را تعریف می کنند‪ ،‬اما استفاده‬
‫از آنها از دهه ی ‪ 70‬محدود شده است‪.‬‬
‫• در بعض ی از زبان های جدید همانند ‪ ML‬دستور ‪ goto‬وجود ندارد‪.‬‬
‫‪:‬‬
‫‪goto‬‬
‫امتیاز‬
‫•‬
‫ً‬
‫• اگر برچسب ها از نظر نحوی ساده باشند مستقیما توسط سخت افزار پشتیبانی‬
‫میشود و کارایی آن باال است‬
‫• استفاده از آن در برنامه های کوچک ساده است‬
‫• برای برنامه نویسان اسمبلی و کسانی که با زبانهای قدیمی برنامه نویس ی می کنند آشنا‬
‫است‬
‫• هدف کلی برای نمایش (شبیه سازی) شکلهای دیگری از کنترل است‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪45‬‬
‫کنترل ترتیب بین دستورات‪ :‬دستورات اصلی‬
‫طراحی برنامه نویس ی ساخت‬
‫یافته‬
‫معایب ‪: goto‬‬
‫• عدم وجود ساختار سلسله مراتبی برنامه‪ :‬اجرای درست برنامه از اجرای کار آمد آن مهمتر‬
‫است‪ .‬طراحی زبان برنامه سازی ‪ ،‬باید این نیازمندی ها را برآورده کند‪.‬‬
‫•‬
‫•‬
‫•‬
‫•‬
‫فصل هشتم‬
‫مفهوم ساختار یک نقطه ورود‪ ،‬یک نقطه خروج‪ ،‬طراحی برنامه را قابل درک میکند‪.‬‬
‫برنامه ای که دستورات زیادی داشته باشد‪ ،‬وقتی قابلیت درک آن باالست که به صورت سلسله‬
‫مراتبی از گروهها سازماندهی شده باشد‪ ،‬به طوری که هر گروه یک واحد مفهومی از محاسبات‬
‫باشد‪.‬‬
‫این سازمان سلسله مراتبی به برنامه نویس اجازه می دهد تا درک کند که بخش های مختلف برنامه چگونه با‬
‫یکدیگر جور در می آیند‪.‬‬
‫اگر تمام دستورات برنامه ‪ ،‬به جای اینکه سازماندهی سلسله مراتبی داشته باشند‪ ،‬فقط در یک سطح ظاهر‬
‫شوند‪ ،‬می گوییم برنامه ساختار مسطح دارد‪.‬‬
‫طراحی و پیاده سازی زبان های برنامه نویسی‬
‫‪46‬‬
‫کنترل ترتیب بین دستورات‪ :‬دستورات اصلی ‪ :‬طراحی برنامه نویس ی ساخت یافته‬
‫معایب ‪: goto‬‬
‫• ترتیب دستورات در متن برنامه الزم نیست با ترتیب اجرا یکی باشد‪.‬‬
‫• با استفادهداز ‪ goto‬می توان برنامه هایی نوشت که کنترل اجرا به طور نامنظم بین‬
‫دنباله های مختلفی از دستورات منتقل شود‪.‬‬
‫• برای درک برنامه ‪ ،‬باید ترتیب اجرای دستورات را درک کنیم و درک برنامه وقتی ساده تر‬
‫است که ترتیب اجرای دستورات تقریبا همان ترتیب فیزیکی دستورات باشد‪.‬‬
‫• گروهی از دستورات ممکن است اهداف متعددی داشته باشد‪.‬‬
‫• اگر هر گروه از دستورات ‪ ،‬یک هدف را در ساختار کلی برنامه دنبال کند ‪ ،‬درک برنامه‬
‫آسان تر می شود‪.‬‬
‫• به طور مثال ممکن است دو گروه از دستورات ‪ ،‬دستورات مشابهی داشته باشند ‪ ،‬با استفاده از‬
‫‪ goto‬می توانیم این دو گروه را طوری ترکیب کنیم که دستورات مشابه ‪ ،‬فقط یکبار نوشته‬
‫شوند و در حین اجرای هر گروه ‪ ،‬کنترل به این دستورات مشترک منتقل شود‪ .‬به این ترتیب درک‬
‫این کد مشکل می شود‪.‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪47‬‬
‫کنترل ترتیب بین دستورات‪ :‬دستورات اصلی ‪ :‬طراحی برنامه نویس ی ساخت یافته‬
‫معایب ‪: goto‬‬
‫• برنامه نویس ی ساخت یافته‪ :‬این اصطالح برای طراحی هایی از برنامه به کار می‬
‫رود که ‪:‬‬
‫• بر طراحی سلسله مراتبی ساختار های برنامه با استفاده از شکل های کنترلی ساده‬
‫مثل ترکیب‪ ،‬انتخاب و تکرار تاکید دارد‪.‬‬
‫• بر نمایش طراحی سلسله مراتبی در متن برنامه ‪ ،‬با استفاده از دستورات کنترلی‬
‫«ساختاری» تاکید دارد‪.‬‬
‫• بر متنی از برنامه که ترتیب فیزیکی دستورات همان ترتیب اجرا باشد تاکید دارد‪.‬‬
‫• بر استفاده از گرو هایی از دستورات با یک هدف تاکید دارد ‪ ،‬حتی اگر مستلزم کپی‬
‫کردن دستورات باشد‪ .‬درک‪ ،‬اشکال زدایی‪ ،‬کنترل‪ ،‬تصحیح و نگهداری برنامه های‬
‫ساخت یافته آسان است‪.‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪48‬‬
‫کنترل ترتیب بین دستورات‬
‫کنترل ترتیب ساخت یافته‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪49‬‬
‫کنترل ترتیب بین دستورات‬
‫کنترل ترتیب ساخت یافته‬
‫• اغلب زبان ها مجموعه ای از دستورات کنترلی را برای بیان شکل های کنترلی اصلی ‪،‬یعنی ترکیب ‪،‬انتخاب و‬
‫تکرار فراهم می کنند‪.‬‬
‫• اگر یکی از دستورات کنترل ترتیب ساخت یافته به همراه دستورات دیگر به کار گرفته شود ‪ ،‬ترتیب اجرا از‬
‫دستور قبلی به دستوری که یک نقطه ی ورود و یک نقطه ی خروج دارد منتقل می شود و پس از اجرای آن‬
‫به دستور بعدی منتقل می شود‪.‬‬
‫• در خواندن برنامه هایی که فقط از دستوراتی با یک نقطه ی ورود و یک نقطه ی خروج استفاده می کنند‬
‫جریان اجرای برنامه باید با دنباله ای از دستورات موجود در متن برنامه مطابقت داشته باشد‪.‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪50‬‬
‫کنترل ترتیب بین دستورات‪:‬‬
‫•‬
‫•‬
‫•‬
‫•‬
‫•‬
‫کنترل ترتیب ساخت یافته‬
‫دستورات مرکب‬
‫دنباله ای از دستورات است که در ایجاد دستورات بزرگتر ‪،‬به عنوان یک دستور محسوب می شود‪.‬‬
‫معموال دستورات مرکب با یک نماد شروع و پایان نوشته می شوند‪.‬‬
‫در این دستور‪ ،‬دستورات به ترتیبی که باید اجرا شوند نوشته می شوند‪.‬‬
‫ممکن است سلسله مراتبی از دستورات مرکب ساخته شود‪.‬‬
‫برای پیاده سازی دستور مرکب در کامپیوتر ‪،‬بلوکی از کد اجرایی که هر دستور موجود در دنباله را نشان می‬
‫دهد در حافظه قرار می گیرد‪ .‬ترتیب وجود انها در حافظه ‪ ،‬ترتیب اجرا ی آنها را نشان می دهد‪.‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪51‬‬
‫کنترل ترتیب بین دستورات‪:‬‬
‫کنترل ترتیب ساخت یافته‬
‫دستورات شرطی‬
‫• انتخاب دو یا چند دستور یا اجرای اختیاری یک دستور را بیان می کند‪.‬‬
‫• گزینش مسیر های اجرا با تست شرطی انجام می شود‪.‬‬
‫• متداول ترین شکل های دستورات شرطی‪:‬‬
‫• ‪ :IF‬به صورت کلی این دستور به صورت زیر است‪:‬‬
‫اگر ]شرط[‬
‫برقرار بود {عمل دلخواه ‪ 1‬را انجام بده}‬
‫برقرار نبود{عمل دلخواه ‪ 2‬را انجام بده}‬
‫• ‪:case‬برای انتخاب یک یا چند دستور با استفاده از نتیجه ی یک عبارت استفاده می شود‪.‬‬
‫بر اساس ]عبارت[ انتخاب کن‬
‫{نتیجه اول} {عمل اول}‬
‫{نتیجه دوم}{عمل دوم}‬
‫‪...‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪52‬‬
‫کنترل ترتیب بین دستورات‪:‬‬
‫کنترل ترتیب ساخت یافته‬
‫دستورات شرطی‬
‫پیاده سازی‪:‬‬
‫• دستورات ‪ IF‬با دستورات پرش سخت افزاری پیاده سازی می شوند ‪.‬‬
‫• دستورات ‪ Case‬معموال با جدول پرش پیاده سازی میشوند تا از تست های‬
‫تکراری مقدار یک متغیر جلوگیری شود‪.‬‬
‫• جدول پرش برداری است که به طور ترتیبی در حافظه ذخیره شده است و هر یک از‬
‫عناصر آن یک دستور پرش غیر شرطی است‪.‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪53‬‬
‫دستور قبل از ‪Case‬‬
‫محاسبه ‪ t‬با استفاده‬
‫‪Jamp to L0+t‬‬
‫‪Jamp to L1‬‬
‫جدول برش‬
‫‪Jamp to L2‬‬
‫‪L0‬‬
‫‪:‬‬
‫‪Jamp to L3‬‬
‫‪Jamp to L4‬‬
‫‪Jamp to L4‬‬
‫‪Jamp to L4‬‬
‫ساختار بخش ‪0‬‬
‫‪L1‬‬
‫‪:‬‬
‫ساختار بخش ‪1‬‬
‫‪L2‬‬
‫‪:‬‬
‫‪Jamp to L5‬‬
‫‪Jamp to L5‬‬
‫انتخاب های دستور ‪case‬‬
‫ساختار بخش ‪2‬‬
‫‪L3‬‬
‫‪:‬‬
‫ساختار بخش ‪3‬‬
‫‪L4‬‬
‫‪:‬‬
‫‪L5‬‬
‫‪:‬‬
‫‪Jamp to L5‬‬
‫دستور بعد از ‪case‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪54‬‬
‫کنترل ترتیب بین دستورات‪:‬‬
‫کنترل ترتیب ساخت یافته‬
‫دستورات تکرار‬
‫• مکانیزمی را برای تکرار محاسبات در اغلب برنامه ها فراهم می کنند ‪ .‬ساختار اصلی دستور تکرار متشکل از‬
‫یک راس و یک بدنه است‪.‬‬
‫• راس تعداد دفعاتی که بدنه باید اجرا شود را مشخص می کند‪.‬‬
‫• بدنه شامل دستوراتی است که باید تکرار شود‪.‬‬
‫• بدنه ی دستورات تکرار‪ ،‬نامحدود است ولی ساختار راس محدود است‪:‬‬
‫•‬
‫•‬
‫•‬
‫•‬
‫•‬
‫تکرار ساده‪ :‬مشخص می کند که بدنه باید به تعداد معینی اجرا شود‪ .‬مثال ‪100 :‬بار تکرار کن‬
‫تکرار در صورتی که شرط برقرار باشد‪ :‬همانند دستور‪while‬‬
‫تکرار با افزایش یک شمارنده‪ :‬دستور ‪for‬‬
‫تکرار مبتنی بر داده ها‪ :‬همانند دستور ‪ foreach‬در ‪c#‬‬
‫تکرار نا متناهی‪ :‬همانند دستور ‪ while‬با شرط همیشه درست‪.‬‬
‫• برای پیاده سازی دستورات تکرار‪ ،‬از دستورات پرش‪/‬انشعاب سخت افزاری استفاده می شود‪.‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪55‬‬
‫کنترل ترتیب بین دستورات‪:‬‬
‫کنترل ترتیب ساخت یافته‬
‫مشکالت کنترل ترتیب ساخت یافته‬
‫• از نظر تئوری می توان هر ساختار کنترل ترتیب را با استفاده از دستورات ساخت‬
‫یافته بیان کرد ‪،‬ولی مواردی وجود دارد که استفاده از ‪ goto‬را ایجاب می کند‪:‬‬
‫• خروج چند گانه از حلقه‪ :‬اغلب برای خاتمه ی حلقه به چند شرط نیاز است‪ .‬که با دستور‬
‫‪ break‬بدون ‪goto‬ساخته می شود‪.‬‬
‫• ‪ :Do-while-do‬اغلب‪ ،‬مناسب ترین جا برای تست خروج از حلقه در وسط آن است‪.‬‬
‫تقریبا هیچ زبان متداولی این روش را پیاده سازی نمی کند‪.‬‬
‫• شرایط استثنایی‪ :‬برای کنترل استثنا ها در زبانهایی که پردازش استثنا ندارند استفاده از‬
‫‪ goto‬بهترین کار است‪.‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪56‬‬
‫کنترل ترتیب بین دستورات‬
‫برنامه های بنیادی‬
‫• فرض می کنیم که هر فلوچارت حاوی این سه دسته گره اصلی است‪:‬‬
‫• گره های تابع‪ :‬محاسبات موجود در برنامه را نمایش می دهد‪.‬با مربع نمایش داده می شود‪.‬‬
‫• گره های تصمیم گیری‪:‬با لوزی نمایش داده می شود‪.‬برای تصمیم گیری بین دوحالت استفاده می شود‪.‬‬
‫• گره های اتصال‪:‬با نقطه نمایش داده می شود ‪.‬برای اتصال چند کمان به کار می رود‪.‬‬
‫• برنامه محض‪ :‬برنامه ای به صورت فلوچارت است که مدل رسمی یک ساختار کنترلی است‬
‫و‪:‬‬
‫• فقط یک کمان ورودی دارد‪.‬‬
‫• فقط یک کمان خروجی دارد‪.‬‬
‫• مسیری از کمان ورودی به هر کمان و از هر کمان به کمان خروجی وجود دارد‪.‬‬
‫برنامهیافته است‪.‬‬
‫غیر ساخت‬
‫طراحی یو محض‬
‫هدف جداسازی برنامه های ساخت یافته‬
‫•‬
‫های های‬
‫برنامهزبان‬
‫پياده ازسازی‬
‫فصل هشتم‬
‫نويسی‬
‫‪57‬‬
‫کنترل ترتیب بین دستورات‬
‫برنامه های بنیادی‬
‫• برنامه بنیادی یک برنامه ی محض است که نمی تواند به برنامه های محض‬
‫کوچکتری تقسیم شود‪.‬‬
‫• برنامه ی محض ی که بنیادی نباشد مرکب است که با جایگزینی هر مؤلفه با یک‬
‫گره تابع می توان آن را بنیادی کرد‪.‬‬
‫• برنامه های بنیادی شمارش ی اند‪.‬‬
‫• همه ی برنامه های بنیادی کار آمد نیستند‪.‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪58‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪59‬‬
‫کنترل ترتیب بین دستورات‪:‬برنامه های بنیادی‬
‫قضیه ساخت یافته‬
‫• باهوم و جاکوبینی نشان دادند که هر برنامه ی بنیادی می تواندبه برنامه هایی تبدیل شود که فقط از‬
‫دستورات ‪while‬و ‪ if‬استفاده کند‪.‬‬
‫• اثبات قضیه ی ساخت یافته(هارالن میلز)‪:‬‬
‫•‬
‫•‬
‫•‬
‫•‬
‫گره های فلوچارت را با برچسب مشخص کنید ‪ .‬کمان خروجی را با عدد صفر مشخص کنید‪.‬‬
‫‪ I‬را به عنوان یک متغیر جدید برنامه تعریف کنید‪.‬‬
‫برای هر گره فلوچارت اگر به صورت برچسب خالیست یک گره تابع معرفی کنید‪.‬‬
‫برنامه را با شکلهای بدست آمده دوباره بسازید‪.‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪60‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪61‬‬
‫• اصالح شده‬
‫قضیه ساخت یافته‬
‫مثال‬
‫• حالت معمول‬
‫‪A=2‬‬
‫‪B=3‬‬
‫<‪A‬‬
‫‪b‬‬
‫‪A*2‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪B*2‬‬
‫‪62‬‬
‫کنترل ترتیب بین دستورات‪:‬برنامه های بنیادی‬
‫قضیه ساخت یافته‬
‫• نتیجه ی کار باهوم و جاکوبینی‪:‬‬
‫• الزم نیست از ‪ goto‬پرهیز کرد‪.‬‬
‫• می توان الگوریتم را به هرشیوه ای پیاده سازی کرد و سپس آن را با استفاده از قضیه ی ساخت یافته به‬
‫برنامه ی ساخت یافته تبدیل کرد‪.‬‬
‫• تمام برنامه ها را میتوان فقط با ساختارهای کنترلی استاندارد نوشت‪.‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪63‬‬
‫ترتیب در عبارات غیر محاسباتی‬
‫تطابق الگو‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪64‬‬
‫ترتیب در عبارات غیر محاسباتی‬
‫تطابق الگو‬
‫• یک عملیات حیاتی در زبانهایی مثل اسنوبال ‪ ،‬پرولوگ و ام ال تطابق الگو است‪.‬‬
‫• با تطابق و انتساب مجموعه ای از متغیر ها به الگوی از پیش تعیین شده‪ ،‬انجام می شود‪.‬‬
‫• اسنوبال‪:‬‬
‫•‬
‫•‬
‫•‬
‫•‬
‫•‬
‫فصل هشتم‬
‫برای شبیه سازی درخت تجزیه ی رشته ایجاد شده است‪ .‬در زبانهای دیگر به سختی می توان برنامه ای به‬
‫کوتاهی و قدرتمندی این زبان برای تشخیص ‪ BNF‬نوشت‪.‬‬
‫پیاده سازی آن مستقل از معماری ماشین طراحی شده است و برای ماشین مجازی پردازنده ی رشته طراحی‬
‫شد‪.‬‬
‫از اولین زبانهایی بود که تقریبا در هر ماشینی موجود بود‪.‬‬
‫معنای آن تقریبا در هر پیاده سازی یکسان بود‪.‬‬
‫برای عملیات تطابق الگوی خود از جایگزینی رشته استفاده می کند‪.‬‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪65‬‬
‫ترتیب در عبارات غیر محاسباتی‬
‫بازنویس ی ترم‬
‫• بازنویس ی ترم شکل محدود شده ای از تطابق الگو است که در دامنه زبانهای برنامه سازی کاربردهای‬
‫فراوانی دارد‪.‬‬
‫• برای مثال برای رشته ‪ a1a2...an‬و قاعده ی بازنویس ی ‪ ai=b‬می گوییم ‪ a1a2…ai-1b...an‬بازنویس ی‬
‫ترم ‪a1a2...an‬‬
‫• تولید مشتقی از یک رشته در یک زبان با استفاده از گرامر ‪ ، BNF‬شکلی از فرآیند بازنویس ی است‪.‬‬
‫• بازنویس ی تابع بازگشتی فاکتوریل می تواند به صورت زیر باشد‪.‬‬
‫;)‪Fun fact(n) = 1 | fact(N:int)=N*fact(N-1‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪66‬‬
‫ترتیب در عبارات غیر محاسباتی‬
‫اتحاد(یکسان سازی)‬
‫• عبارتی حاوی یک یا چند متغیر یک تقاضا نام دارد و رابطه ناشناخته ای را نشان می دهد‪.‬‬
‫• پرولوگ‪،‬برای تطابق الگو از اتحاد یا جایگیزینی استفاده می کند تا تعیین کند آیا تقاضا شامل جانشینی معتبری‬
‫است که با قواعد و حقایق موجود در بانک اطالعاتی سازگار باشد یا خیر ‪.‬‬
‫• اتحاد را می توان به عنوان توسعه ای از خاصیت متداول جانشینی دانست‪.‬‬
‫• جانشینی‪ :‬یکی از اولین اصولیست که در برنامه نویس ی آموخته می شود‪.‬یک اصل کلی در ارسال پارامتر‬
‫ها و بسط ماکرو ها است‪.‬‬
‫)‪”,8‬درس طراحی زبان ها ی برنامه سازی درس ‪• Printf)“%d‬‬
‫• می توان عبارات را به جای اعداد به کار برد‪.‬‬
‫• این جانشینی را می توان به یک عالمت ”?” هم انتساب داد‪ .‬که در آن صورت با استفاده از دو دستور یا عبارت‬
‫می توان بعض ی از آنها را حل کرد‪.‬‬
‫)?‪• Mymacro(x+y,z/2,‬‬
‫)?‪mymacro(x+y,z/2,‬‬
‫)‪• Mymacro(?,?,myvar+3‬‬
‫)?‪mymacro(?,z+7,‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪67‬‬
‫ترتیب در عبارات غیر محاسباتی‬
‫اتحاد(یکسان سازی)‬
‫• اتحاد عمومی‪:‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪68‬‬
‫ترتیب در عبارات غیر محاسباتی‬
‫عقب گرد‬
‫• اگر به آخرین هدف ممکن برسیم و آن نیز با شکست مواجه شود می گوییم هدف فرعی فعلی‬
‫شکست خورده است چون مجموعه ای از هدف ها در پشته قرار گرفته اند آن را جستجو می کنیم‬
‫و به هدف فرعی قبلی بر می گردیم که تطبیق صورت گرفته است و تالش می کنیم هدف دیگری با‬
‫آن تطابق کند‪.‬‬
‫• در هر زبانی که ساختار های درختی را ایجاد می کند ‪ ،‬عقبگرد یک تکنیک برنامه نویس ی عمومی است‪.‬‬
‫• در لیسپ پیاده سازی عقبگرد ساده است‪.‬‬
‫• در پرولوگ عقبگرد یک ویژگی درونی است‪.‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪69‬‬
‫ترتیب در عبارات غیر محاسباتی‬
‫اصل راه حل‬
‫• در دهه ‪ 1965‬رابینسون اصل راه حلل را اراهله کلرد کله نتیجله پیلاده سلازی آن‪ ،‬پروللوگ در سلال ‪1972‬‬
‫بود‪.‬‬
‫• هللدف فضللای جسللتجوی پرولللوگ متحللد کللردن ‪ Q1…..Qn‬اسللت و پرولللوگ در انتخللاب قاعللده ای‬
‫مثللل ‪ P‬از بانللک اطالعللاتی آزاد اسللت تللا آن را بلله عنللوان فرضللیه ای در نظللر بگیللرد کلله تفکیللک را در آن‬
‫انجام دهد‪ .‬اگر با موفقیت انجام شود ‪ Б‬پاسخ به تقاضا را توصیف می کند اگلر بلا شکسلت مواجله‬
‫شود نیاز به قاعده ‪ P‬داریم تا جانشین معتبری را بیابد‪.‬‬
‫فصل هشتم‬
‫طراحی و پياده سازی زبان های برنامه‬
‫نويسی‬
‫‪70‬‬

similar documents