وبلاگی برای حرف دل یک پساکنکوری

تجزیه | بخش سوم - تجزیه‌گرهای SLR، CLR و LALR

تجزیه‌گر SLR

تجزیه‌گر SLR مشابه تجزیه‌گر LR(0) است با این تفاوت در اعمال کاهشی. اعمال کاهشی تنها در Follow های متغیری که باید کاهش یابد نوشتهمی‌شود.

ساخت جدول تجزیه‌گر SLR

۱- مجموعه‌ی C={I0,I1,... , In} را -که مجموعه‌ی آیتم‌‌های ‌LR(۱) گرامر G’ است- بساز.

۲- حالت i از li ساخته می‌شود. اعمال تجزیه برای حالت i  بدین صورت معین می‌شود:

         * اگر [A -> ?.a?] در li است و GOTO(li,a)=lj در این صورت ACTION[i,a] را shift j قرار دهید. در این جا a باید یک ترمینال باشد.

         * اگر [A -> ?.] در li است در این صورت ACTION[i,a] را reduce A->? برای همه‌ی a های داخل FOLLOW(A)  قرار بده. در این‌جا A نباید S’ باشد.

         * اگر [S -> S.] در li است در این صورت ACTION[i,$] را accept قرار بده. اگر هرگونه برخوردی در action های اعمالی مراحل بالا وجود داشت می‌گوییم این گرامر SLR نیست.

۳- گزارهای goto برای حالت i برای همه‌ی nonterminal های A بدین صورت محاسبه می‌شود:

اگر GOTO(li,A)=lj  در این صورت GOTO[i,A]=j.

۴- همه‌ی خانه‌هایی که در مراحل ۲ و ۳ مقداردهی نشدند باعث وقوع خطا شوند.

نکته: اگر در خانه‌ای از جدول چند عمل داشته باشیم یک برخورد رخ داده است.

مثلا:

گرامر تکمیلی زیر را در نظر بگیرید:

E’ -> E
E -> T+E | T
T -> id

تجزیه‌گر CLR

ما در روش SLR روی آیتم‌های LR(0) کار می‌کنیم. در تجزیه‌گر CLR از آیتم‌های LR(1) استفاده می‌کنیم. آیتم‌های LR(k) آیتمی‌ست که با lookahead بطول k مشخص می‌شود. پس در واقع LR(1) آیتم‌های LR(0) را همراه lookahead مربوط به آن دارد.

تجزیه‌گر‌های LR(1) قوی‌تر هستند.

برای LR(1) توابع Closure و GOTO را اصلاح می‌کنیم.

Closure(I)
repeat
    for (each item [ A -> ?.B?, a ] in I )
        for (each production B -> ? in G’)
          for (each terminal b in FIRST(?a))
            add [ B -> .? , b ] to set I;
until no more items are added to I;
return I;

با یک مثال متوجه می‌شویم.

Goto(I,X)
Initialise J to be the empty set;
for ( each item A -> ?.X?, a ] in I )
    Add item A -> ?X.?, a ] to set J;/* move the dot one step */
return Closure(J);    /* apply closure to the set */

 

 

آیتم‌های LR(1)

Void items(G’)
Initialise C to { closure ({[S’ -> .S, $]})};
Repeat
    For (each set of items I in C)
        For (each grammar symbol X)
            if( GOTO(I, X) is not empty and not in C)
                Add GOTO(I, X) to C;
Until no new set of items are added to C;

 

ساخت‌ گراف GOTO

·  حالت l0. عبارت پایانی‌ آیتم LR(1) مربوطه.

·  با حالت قبل و به کمک DFA همه‌ی مجموعه‌ی آیتم‌های LR(1) را پیدا‌ کنید.

·  DFA را به جدول تجزیه‌ی LR(1) تبدیل کنید.

ساخت جدول تجزیه‌ی CLR

ورودی گرامر G’

۱- مجموعه‌ی C={I0,I1,... , In} را -که مجموعه‌ی آیتم‌‌های ‌LR(0) گرامر G’ است- بساز.

۲- حالت i از li ساخته می‌شود. اعمال تجزیه برای حالت i  بدین صورت معین می‌شود:

         * اگر [A -> ?.a? ,b] در li است و GOTO(li,a)=lj در این صورت ACTION[i,a] را shift j قرار دهید. در این جا a باید یک ترمینال باشد.

         * اگر [A -> ?. ,a] در li است در این صورت ACTION[i,a] را reduce A->? قرار بده. در این‌جا A نباید S باشد.

         * اگر [S -> S. ,$] در li است در این صورت ACTION[i,$] را accept قرار بده. اگر هرگونه برخوردی در action های اعمالی مراحل بالا وجود داشت می‌گوییم این گرامر CLR نیست.

۳- گزارهای goto برای حالت i برای همه‌ی nonterminal های A بدین صورت محاسبه می‌شود:

اگر GOTO(li,A)=lj  در این صورت GOTO[i,A]=j.

۴- همه‌ی خانه‌هایی که در مراحل ۲ و ۳ مقداردهی نشدند باعث وقوع خطا شوند.

مثلا گرامر تکمیلی زیر را در نظر بگیرید:

S’ -> S
S -> AaAb | BbBa
A -> ?
B -> ?
گراف goto برای این گرامر خواهد بود: 

 

نکته: اگر حالتی دو کاهش داشت و هر دو lookahead یکسانی داشتند در نتیجه برخورد رخ می‌دهد. اگر حالتی یک کاهش و یک جابجایی یا shift با ترمینالی یکسان با lookahead داشته باشد نیز برخورد رخ می‌دهد.

تجزیه‌گر LALR

تجزیه‌گر LALR مشابه تجزیه‌گر CLR است با یک تفاوت که اگر دو حالت تنها در lookahead ها تفاوت داشته باشند با هم ادغام می‌شوند. بعد از این کوچک‌سازی اگر در جدول برخورد وجود نداشت گرامر LALR نیز هست. 

مثلا:

گرامر تکمیلی زیر را در نظر بگیرید:

S’ -> S
S ->AA
A -> aA | b
نکته مهم:
حتی اگر CLR برخورد RR نداشته باشد ممکن است برای LALR چنین برخوردی رخ دهد.
نکته:
تجزیه‌گر‌های مختلفی که یادگرفتیم بر حسب تعداد حالت‌ها چنین دسته‌بندی می‌شوند:

۱۶ تیر ۹۷ ، ۰۱:۳۰ ۰ نظر موافقین ۰ مخالفین ۰
محسن فراهانچی

تجزیه | بخش دوم - تجزیه‌گر پایین به بالا یا جابجایی کاهینه

در این مقاله در مورد تجزیه‌گر پایین به بالا گفتگو می‌کنیم.

تجزیه‌گر پایین به بالا یا جابجایی کاهینه

 از برگ‌ها شروع می‌کند و درخت تجزیه را می‌سازد و به ریشه ختم می‌شود. تجزیه پایین به بالا بوسیله‌ی ردیابی اشتقاق راست از معکوس w تلاش می‌کند تا رشته‌ی ورودی w را به نماد آغازین یک گرامر محدود کند. 
مثلا

دسته‌بندی تجزیه‌گرهای پایین به بالا

یک تجزیه جابجایی-کاهینه عمومی تجزیه LR است. L به این معنی که ورودی را از چپ به راست می‌پوید و R به این معنی که از معکوس اشتقاق راست استفاده می‌کند. 
در اینجا با هر چهار شیوه تجزیه LR به ساخت گراف GOTO از یک گرامر می‌پردازیم. 

تجزیه‌گر LR(0)

ما به دوتابع نیاز داریم: Closure() و Goto()

گرامر تکمیلی

اگر G یه گرامر با نماد آغازین S باشد آنگاه G' (گرامر تکمیلی G) گرامری با نماد آغازین جدید S' و عبارت تولیدی S' -> S. هدف از افزودن این عبارت تولیدی جدید تشخیص اتمام تجزیه و اعلام پذیرش ورودی است. 
گرامر S -> AA را در نظر بگیرید.
A -> aA | b
گرامر تکمیلی گرامر بالا خواهد شد:
S' -> S
S -> AA
A -> aA | b

آیتم‌های LR(0) 

یک عبارت تولیدی گرامر G با یک نقطه در بخش راست همان عبارت است.
S -> ABC چهار آیتم را حاصل می‌شود
S -> .ABC
S -> A.BC
S -> AB.C
.S -> ABC

عبارت تولیدی A -> ε فقط یک آیتم A -> .ε را حاصل می‌کند. 


عملیات بستار(Closure)

اگر I یک مجموعه از آیتم‌های گرامر G باشد آنگاه closure(I) مجموعه‌ای از آیتم‌های ساخته‌شده از I است که توسط دو قاعده زیر ساخته می‌شوند. 
  1. ابتدائا همه‌ی آیتم‌های I به closure(I) اضافه می‌شود.
  2. اگر A -> α.Bβ در closure(I) باشد و B -> γ یک عبارت تولیدی باشد آنگاه آیتم B ->  را به I اضافه کن اگر هم‌اکنون نباشد. این قاعده را تا زمانی که هیچ آیتم دیگری را نتوان به closure(I) اضافه کرد ادامه بده. 
مثلا 

عملیات Goto

برای تابع Goto(I, X) ابتدا با جابجایی نقطه بعد از X به I اضافه کن. سپس عملیات closure را به قدم اول اعمال کن. 

ساخت گراف GOTO

  • وضعیت I0 - بستار عبارت تکمیلی LR(0) است. 
  • به کمک I0 تمام مجموعه‌های آیتم‌های LR(0) را به وسیله‌ی DFA پیدا کن
  • DFA حاصله را به جدول LR(0) تبدیل کن

تولید جدول تجزیه‌ی LR(0) 

تابع عمل(action) وضعیت I و پایانه‌ی a (یا $ که نماد پایان ورودی است) به عنوان ورودی می‌گیرد. مقدار ACTION[i, a] می‌تواند یکی از چهار حالت زیر باشد:
  1. جابجایی به j، که j خود یک حالت است.
  2. کاهش A -> β
  3. پذیرش
  4. خطا
ما تابع GOTO را گسترش می‌دهیم. مثلا GOTO[Ii, A] = Ij یعنی حالت i را با پایانه‌ی a به حالت j نگاشت می‌کند. 
مثلا:
گرامر S -> AA را در نظر بگیرید.
A -> aA | b
گرامر تکمیلی گرامر بالا خواهد شد:
S' -> S
S -> AA
A -> aA | b

جدول تجزیه LR(0) برای گراف GOTO بالا خواهد شد:

بخش عمل در جدول شامل همه‌ی پایانه‌های گرامر می‌شود در حالی که بخش goto شامل همه‌ی غیرپایانه‌هاست. برای هر حالت گراف goto تمام عملیات‌های goto را در جدول می‌نویسیم. اگر goto به یک پایانه اعمال شده آن را در بخش action می‌نویسیم و اگر به یک غیرپایانه اعمال شده در بخش goto در جدول می‌نویسیم. اگر در اعمال goto در یک عبارت تولیدی کاهش رخ می‌دهد(مثلا وقتی که نقطه به انتهای عبارت می‌رسد و بستار دیگری ممکن نیست) آنگاه با نماد Ri نشان می‌دهیم و اگر جابجایی رخ می‌دهد Si می‌نویسیم. 
اگر عبارت تولیدی کاهشی است باید زیر تمام پایانه‌های تجزیه‌گر LR(0) نوشته شود. 
اگر در حالتی نماد آغازین گرامر کاهش یابد، زیر نماد $ پذیرش نوشته می‌شود. 


نکته: اگر در حالتی کاهش و جابجایی یا دو کاهش متفاوت نشان‌ داده شود، گوییم یک برخورد رخ داده است و گرامر LR نیست.
نکته: دو عمل کاهش در یک حالت را برخورد RR می‌نامند و یک کاهش و یک جابجایی را برخورد SR نامند. 
اگر هیچ برخورد SR ویا RR رخ ندهد پس آن گرامر LR(0) است. 

نکته: برای تشخیص LR(0) بودن یا نبودن یک گرامر نیازی به رسم جدول نیست. کافیست در گراف goto حالتی یافت که با یک پایانه، دو عمل کاهش یا یک کاهش و یک جابجایی رخ داده باشد که در این صورت گرامر LR(0) نیست. اگر یک جابجایی با یک متغیر رخ دهد برخورد ایجاد نمی‌شود چون در جدول یکی در بخش action قرار می‌گیرد و دیگر در بخش action.




۱۵ تیر ۹۷ ، ۲۲:۱۸ ۰ نظر موافقین ۰ مخالفین ۰
محسن فراهانچی

مَلی و امتحان‌هایش

فیلم ملی و راه‌های نرفته‌اش روایت امتحان‌های خداست. از بزرگترین سختی‌ها و شکنجه‌های انسان در دنیا. 

ادامه مطلب...
۱۲ تیر ۹۷ ، ۱۵:۵۳ ۰ نظر موافقین ۱ مخالفین ۰
محسن فراهانچی

تغییر راهبرد تابستان- فناوران پیشرفت تمدن نوین

رفتم دانشکده تا جزوه‌ی ریاضی رو به احسان بدم. هادی آزاددل رو هم دیدم. 

از پارسیوت پرسیدم. گویا آقای قدمنان با کمیل صحبت کرده و تیمی برای اینترنت اشیاء خواسته تا در آرمان تشکیل بشه. کمیل، هادی شامقلی، هادی آزاد و صالحوف این جمع رو تشکیل دادن. حدود سه چهار ماه در مورد زیربخش‌های اینترنت اشیاء تحقیق کردند و در نهایت مکان‌یابی درون ساختمان رو برای رسیدن به محصول انتخاب کردن. در مورد ایده‌ی تشکیل تیم با دوستان خودم باهاش صحبت کردم. دید خوبی تونستم بگیرم.

تیم تشکیل دادن سختی های خودش رو داره. 

ادامه مطلب...
۳۰ خرداد ۹۷ ، ۰۱:۳۶ ۱ نظر موافقین ۰ مخالفین ۰
محسن فراهانچی

برای دیدن تو باید انقلاب کرد

این متن ابتدای ترم ۵ نوشتم-دوشنبه, ۶ شهریور ۱۳۹۶، ۰۳:۲۴ ق.ظ- و برای تحقق آن هم تلاش کردم اما نتیجه‌بخش نبود. البته باعث شد بهتر از توانایی هایم آگاهی پیدا کنم و در تصمیم‌های آینده این ویژگی‌ها را مدنظر قرار دهم.

ادامه مطلب...
۳۰ خرداد ۹۷ ، ۰۱:۲۴ ۰ نظر موافقین ۰ مخالفین ۰
محسن فراهانچی

جلسه-دو کرسی های آزاد اندیشی

بازنشر جلسات کرسی آزاداندیشی دانشگاه علم و صنعت

این جلسات مربوط به تابستان ۹۶ است و جمعی حدودا ۶ نفره پای کار بودند. اکنون بعد از حدود ۱ سال منتشر می‌کنم.

ادامه مطلب...
۲۶ خرداد ۹۷ ، ۱۸:۰۲ ۰ نظر موافقین ۰ مخالفین ۰
محسن فراهانچی

مهندسی مسافرکشی - آینده‌ی مهندسی کامپیوتر این است؟

هرساله قسمت مهمی از دانشجویان برتر کنکور سراسری رشته کامپیوتر را انتخاب می‌کنند. این انتخاب در سال‌های اخیر رونق بیشتری گرفته و رتبه‌های پایین‌تری وارد این رشته می‌شوند.  در نتیجه این روند در سال‌های آتی، نیروی انسانی توان‌مندتری را در این رشته خواهیم دید. بازارکار این رشته در فنی مهندسی زبان‌زد است. از هر پنجره‌ای یا به هر دیواری نگاه کنی پر است از آگهی استخدام برنامه‌نویس اندروید و لاراول و قس علی هذا. 

ادامه مطلب...
۲۶ خرداد ۹۷ ، ۱۳:۰۳ ۰ نظر موافقین ۰ مخالفین ۰
محسن فراهانچی

تکالیف متقابل خدا و موحد متوکل

نگاه مومن به نقش خدا در زندگی از عقیده‌ی توحیدی‌اش مایه می‌گیرد. هر چه باور اصیل و فهیمانه باشد، صراط مستقیم نمایان می‌شود. 

به راستی باور به وجودی الهی چه نمودی در سیر حیات دارد؟ 


افوض امری الی الله ان الله بصیر بالعباد

امورم را به خدا تفویض می‌کنم. 

ادامه مطلب...
۰۲ خرداد ۹۷ ، ۰۲:۵۸ ۰ نظر موافقین ۰ مخالفین ۰
محسن فراهانچی

درس برجام برای حرکت الگوی پیشرفت علم و صنعت

دقیقا ۲ ماه از مطلب قبلی‌م درباره تیم الگوی علم و صنعت میگذرد. اکنون فرصتی دیگر داریم تا گذشته را شفاف‌تر ببینیم و حرکت آینده خود را انتخاب کنیم. همانند کوه‌نوردانی که بعد از مدتی باید به عقب نگاه کنند و راهی را که طی کرده اند ببینند. سپس قله را و هدف را یادآوری کنند و خود را از روزمرگی یک تلاش کور آزاد کنند.

پیشرفت دو ماه گذشته را در یک کلام اگر بیان کنم میگویم تقریبا هیچ! با جلسات عدالت و پیشرفت -که بعد صحبت حاجاقا عابدینی در مورد بیان مهم رهبر در مورد عدالت بود- کمی علائم حیاتی به تیم برگشته بود. استاد هم بیشتر در گروه صحبت می‌کرد و اصرار بر تحقق آیین‌نامه بیشتر شد. جلسه ای هم که در این اثنا داشتیم منجر به ورود افراد جدید به گروه شد.
با حضور همه یک جلسه با استاد تشکیل شد. جمع آمادگی ذهنی نداشت و استاد بیشتر انگیزشی صحبت کرد. شروع کردیم آیین نامه را روی تخته نوشتن و بحث کردن. حال نیاز است تشکیلات شکل بگیرد و تکالیف معین شود. جلسه دیگری را باید داشته باشیم و در مورد زمانبندی کار و تعیین دبیر هم تصمیم گیری شود. چنین جلسه ای تا امروز تشکیل نشده.
یک جلسه قبل عید وقتی خیلی هامان در راهیان نور بودند تشکیل شد و مشروعیت تصمیم گیری نداشت و تنها مصوبه آن تدوین جلسات عدالت و پیشرفت توسط جدید الورودها بود

Muhsin

ویراست ها مطلوب استاد است اما بر تحقق آیین نامه تاکید دارد. گذشت و بخاطر جلسه سوم عدالت و پیشرفت به استاد زنگ می زنم که هماهنگ کنم جواب نمی‌دهد. پیامک می‌دهم و خبری نمی‌شود. روز جلسه در تماسم با سهند اتفاقی متوجه می‌شود استاد راهیان نور هست! خبری به ما نمی دهد. دوباره تماس می گیردم و باز بی پاسخ می مانم و کنسل می کنم. البته چون جلسه قبل تنها ۳ نفر بودیم نیاز به اطلاع رسانی هم نمی بینم و فقط یک پوستر با نوشته‌ی کنسل شد را درب سالن جلسات می چسبانم.
جلسه اول حضور بسیار خوب بود. چند نفر که نسبت به الگو سخنانی شنیده بودند و مایل بودند استاد را ببینند که کیست و چطور است آمده بودند. عقبه های تشکل ها بودند. چند نفر از جمله چند سردبیر نشریه و مسئول کرسی آزاد اندیشی و... آمده بودند. لحن صحبت و محتوای بحث به کلی ناامیدشان کرد.
تجربه ارزشمندی شد. نباید به چنین جلساتی با استاد برای کار عمومی امید بست و جلسه صرفا مناسب خودمان است.
تعطیلات سال نو تمام می‌شود و همچنان کار خوابیده است. استاد می‌گوید قبل از ۴۰ جلسه با حاج آقا هماهنگ کنید که جلسات کوتاه مدت برگزار کنید و آماده شوید. حاج آقا که جواب ما را ۷ ماه است نداده گویا خود استاد هم ارزشی پیش حاج آقا ندارد و الا باید وظیفه رابط بودن را ادا می کرد.

Muhsin

بعد از عید هیچ جلسه مفیدی نداشتیم بجز یک جلسه که یک بند آیین نامه را تصمیم گرفتیم. هرچند آن هم بدون حضور همه بود. کار معطل یک بام و دو هوای استاد و حاج آقا است. از اعضا هم انسجام و پیگیری لازم وجود ندارد بجز یک نفر، محمدعلی. او از این و از آن پیگیر است از استاد از سهند. خیلی هم امیدوار است. غافل از اینکه تعامل با شورای راهبردی تجربه آزموده شده ایست و او ابتدای مسیریست که علی رفته سهند انتهایش است و من داشتم شروع می‌کردم.
محرم جلسه ای داشتیم با حاج اقا عابدینی در مورد الگو. حاج اقا در مورد رابطه مان با شورا پرسیدند و گفتیم گفته اند باید برادریمان را ثابت کنیم. حاجاقا گفت «برادری غریبانه که نمیشود!» آن روز علی مثل امروز محمدعلی خوش بین بود و راه را در اثبات برادری می دید.

Muhsin

کمی بعد که علی متوجه حقایق می شود، خوش بینی به سهند منتقل می شود. بیش از همه با استاد در تعامل است در گروه فعال است و دغدغه مندی اش را نشان می دهد و اتفاقا شرایط را رو بهبود می بیند. مسیر رفته شده به فرماندهی علی را تخطئه می کند حال آن که خودش ابتدای آن راه است.
من هم تجربه ای داشتم در تعامل با استاد. ابتدا نسبت به موقعیتی که میتوان با موضوع عدالت به مسئله الگوی پیشرفت رسید امیدوار شدم. اوضاع را رو به بهبود دیدم. در برهه ای بیشتر از همه فعالیت کردم و حتی کانال الگو در پیامرسان های ایرانی را گرفتم. بسیار با انگیزه کار را تقریبا تنهایی جلو بردم اما به همان نتیجه ی علی رسیدم.

Muhsin

اکنون مدتیست که حاج آقا و استاد به سهند -که او را به عنوان دبیر تیم میشناسند- یا اساسا جواب نمی دهند یا جواب سر بالا می دهند و دست به سر می کنند.
اما امروز یک خوش‌بین دیگر همچون علی و سهند و من پیدا شده. گروه زده کانال زده با استاد در تماس است فعالیت فراوانی در گروه دارد. رفتار ها هم همان تخطئه قبلی ها و امید به آینده است با این تفاوت که امروز حق مبین تر شده و باطل بودن مسیر فعلی با تجربه ی سه نفر اثبات شده. اگر امروز به دلخوش کنک های تکراری دل بدهد و از مطرح شدن تجربه های گذشته هراس داشته باشد و متقدمین الگو را پس بزند، راه مشابه برجام را شروع کرده است. نباید بر عموسام ها تکیه کند بلکه خاضع شود و به همراهی جمع راه سومی را پیدا کنیم.

۲۴ ارديبهشت ۹۷ ، ۱۳:۰۴ ۱ نظر موافقین ۰ مخالفین ۰
محسن فراهانچی

دین مقتدر؛ جلسه اول

♻ دین را از نو باید شناخت

در مواجهه با دین در مقام فردی ناآشنا به آن، باید دنیایی که در آن زندگی می‌کنیم را نشانش دهیم! بگوییم #ببین_دین_عزیز! در دنیایی که من زندگی می‌کنم، هر جامعه و هر حاکمیتی حول #محور_قدرت رقابت می‌کنند. علم، اقتصاد، دیپلماسی و... همه در خدمت #زورآزمایی قدرت‌هاست. ای دین! آیا تو قدرت‌آفرین هستی؟ می‌توانی عزت و احترام بیافرینی؟

ادامه مطلب...
۲۱ فروردين ۹۷ ، ۲۲:۳۸ ۰ نظر موافقین ۰ مخالفین ۰
محسن فراهانچی