کامپایلر compiler

صفحه 1:
#inlcude<iostream.h> #inlcude<stdlib.h> #inlcude<stdio.h> int main(){ int state; char ch; state= switch(state){ case 1: ch= gete(stdin); if (ch=="a’) state= ose As (>) cout<<"Failed"; ‏ی‎ ©) exit(0); = break; case 2: ch=gete(stdin); if(ch=="\n') cout<<"Accepted"; else cout<<"Failed"; exit(0); return(0); 

صفحه 2:
#inicude<iostream.h> #inicude<stdlib.h> #inicude<stdio.h> int main(){ int state; char ch; state=1; while(1){ switch(state){ a case 1: ch = getc(stdin); if (cl 79 state 'b') state: | else { cout<<"Failed"; exit(0); cout<<"Accepted"; ‏عواع‎ cout<<"Failed"; exit(0); 7 1 return(0); 

صفحه 3:
[a-zA-Z0-9] Y 8B ‏ددرا"‎ DI} eb سا کم ‎ao:‏ ‏سک ‎‘oi‏ ‏اعحام) || درا هق '(اسهام) |إ( ‎she ((ch> = BB sob‏ سه )سد السلف عور ‎eal DY,‏ امم ا 

صفحه 4:
‎i‏ ل | | ل ا 0 يلمر | 1 | ‏۵ موتو 

صفحه 5:
int fail(int start) int nextstart; switch(start) { case l:nextstart=3; // ‏لعداد اعشاري‎ break; case 3:nextstart=6; // ‏لعداد صحیح‎ break; case 6:nextstart=8; // ‏فضاوخالي‎ ‎break; t return nextstart; 1 

صفحه 6:
اس بر زارسی‌صو بر ‎vkar ok;‏ ‎PLE *Pp;‏ ‎"r");‏ )سر( :)سوه :)تسو ‎wwhte(()‏ ‎surich(state){‏ ‏:(و 0 (۳)سحه ‎B((ch>='c! && ch<="2/) || (ch>="@! &R vh<="L'))‏ ‎shie=O;‏ ‏اه ‎oka=Poll sk);‏ زک ۵۵۵0۵6 سس } ‎brook;‏ 

صفحه 7:
AP); 'd! && ch<="2') || (h>="O' BB ch<="L') || (ch>="O' BB vch<='9')) ==! ||| c=" ch== BOP) ‏کت‎ "5 ‏زرد‎ ‎1 ‏سس‎ ‏(سممف سود‎ ‏سورد‎ ‎| ‎1 

صفحه 8:
اولویت ها ممكن است بخشى از يك دنباله از كاراكد ‎١‏ ۱ بخشی اب باله از کاراکترها با یک عبارت باقاعده و بخث دیگری منطبق شود. به عنوان متال دنباله 123۰65 ‎Ne‏ ‏بارت با قاعده ذيل را در نظر ‎cd ot‏ ‎[d-O][O-9] ۱ .‏ ‎[d-O][0-9]*. [0-9 ][d-9]‏ پذیرش طولاني ترین دنباله است 

صفحه 9:
ممکن یک دنباله از کاراکترها (نه بخشی از یک دنباله ) با دو یا چند عبارت باقاعده منطبق شود به عنوان مثال رشته 4 می تواند توسط دو عبارت باقاعده ذیل تولید شود. 5 *[©-00 ,1ك ملسم عبارت با قاعده اي که اولویت بيشتري دارد؛ ابتدا مقايسه .مي شود 

صفحه 10:
14 Polit or) مت نم ‎switch (stert){‏ اعداد صحیح || :متا مه لا rae O:aextstrt=O; bredk; اعداد اعشاري ‎I‏ :مه مه ‎breck;‏ } مس مسج } 

صفحه 11:
استفاده از ابزارها داراي مزایا و معايبي است که عبارتند از؛ افزایش سرعت ایجاد تغییرات کاهش زمان ساخت تحلیلگر لغوي افزايش محدودیتها 

صفحه 12:
پیاده سازی تحلیلگ لغوی به وسیله تولید کننده تحلیلگ لغوی ‎Flex‏ برنمه به بان ‎slay Lin Flex ‏با پاسکال > برنمه ‎Obj a‏ ‏© كامبابل بوسيله كامبايلر ‎ ‏تحلیلگر لغوي ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 13:
c:\> flex 0۵569۱. scanner.c ‏بعد از کامپایل و تولید فایل اجرایی‎ c:\> scanner.exe< pl c:\> scanner.exe <p1> result رشته هایمورد نظر ‎c:\> scanner.exe‏ 

صفحه 14:
نحوه بیان عبارات پا قاعده lee ۲+ re X{2,5} r{m,n} ‏اس‎ ‎۳/ ۳1/۳۹2 ۳1۳2 21 ‏[مجموعه کاراکترها]‎ [“afk] ‏كاراكترهاي مورد نظر[+‎ بجز سر خط ] کاراکتر مقصد- کاراکترمبدا[ ‎[b-f]‏ 

صفحه 15:
ساختر برنامه بسه زبا166 تعاریف 0۹/6 ترجمه ها 0۹/6 توابع 

صفحه 16:
مثال ]0-9[ [a-z] [A-Z] lower|upper {letter}|({letter}|{digit})* [\n\t]+ {} {printf(“l found ‘IF’ keyword”);} {printf(“l found ‘ELSE’ keyword”);} {printf(“l found variable “);} digit lower upper letter var ws %% ws “ign “else” var %% 

صفحه 17:
» اگر متن ذیل به عنوان ورودي به اين تحلیلگر داده شود. ‎‘if temp else if id 34‏ * خروجي به صورت ذیل خواهد بود. * | found ‘if’ keyword * | found variable * | found ‘ELSE’ keyword * | found ‘if’ keyword * | found variable 

صفحه 18:
%option noyywrap 5261 int nchar,nline; %y 9096 Qn] {nline++;} 5 {nchar++;} 1 %% int main(void){ yylex(); printf("%d = %d",nchar,nline+1); return (0); 1 

صفحه 19:
روش اول ‎[a-zA-Z]([a-zA-Z0-9])* printf("ID ");‏ ‎"program" printf("PROGRAM‏ ۳ ‎"var" printf("VAR ");‏ ‎"begin" printf("BEGIN ");‏ "end" printf("END "); 

صفحه 20:
void toupper(char k[]) ine é 5 “3 int is keyword(char id{]) { char keyword[40][20]= "ARRAY", "BEGIN", "CAS RN", "FILE", "FOR", "FORWARD", "FUNCTION", "GOTO", "IF*,"IN","LABEL","MOD","NIL","NOT*,"OF*,"OR","O THERWISE", "PROCEDURE", "PROGRAM","RECORD","REPEAT","THEN","TO","TYPE","UNTIL","VAR","WHILE","WITH"}; ‘AND", ‘ONST","DIV*,"DO","DOWNTO","ELSE", ND","EXTERNAL","EXTE O;i<40;i++) if(stremp(id, keyword{i]) return return -1; } 9 0) 

صفحه 21:
[a-zA-Z]([a-zA-Z0-9])* {toupper(yytext); if (is_keyword(yytext)!=-1) printf("keword= %s",yytext); else printf("ID "); } 

صفحه 22:
* A [aA] ۰ 8 ]08[ ۰ C [cC] * D[dD] * E [eE] 

صفحه 23:
* {A} {N}{D} return(AND); * {A}{R}{R}{A}{Y} return(ARRAY); © {C}{A}{S}{E} return(CASE); * {C}{O}{N}{S}{T} return(CONST); * {D} {I} {V} return(DIV); * {D}{O} return(DO); 

صفحه 24:
حساس به حالت روش دوم [a-zA-Z]([a-zA-Z0-9])* {toupper(yytext); if (is_keyword(yytext)!=- 1) return (KW); else return(IDENTIFIER ); 

صفحه 25:
فاکتور گیس‌ی چپ * براي يك غیر پایانه ممکن است انتخابهاي مختلفي وجود داشته باشد به طوريكه شروع یکسان داشته باشند. به عنوان مثال به گرامرهاي ذیل دقت کنید. داح | 5 و ب۸ ۰ ‎els‏ ‎A>cdB|cdgD‏ * 

صفحه 26:
+ A> af, | of, | of; ... | a, ‏شروع مشترك‎ : ٠» ‏قسمت غير مشترك‎ 8: + ‏كرامر فوق را مىتوان به صورت ذيل نشان داد كه همان‎ ٠» ‏زبان را توليد مىكند:‎ ‏8ن عدم‎ *R>6, |B 1 83] -- 

صفحه 27:
متال م و609 | 5 00 حم ‎٠‏ ‏6 | 08ات8 ۰ ‎D-dDle‏ * ‎٠‏ باتوجه به ‎Gul Cd dibs Gad AcdB] cdgD‏ در نتیجه: ‎a=cd‏ * ‎B,=gD‏ * ‎B.=B‏ * . _گرامر را می‌توان به صورت ذیل نشان داد. 8 ب۸ ۰ 0 و | 8 ۲۲ ۰ 6 | 08ات8 ۰ ‎D-dDle‏ * 

صفحه 28:
تحلیلگر لغوي برنامه مبدا را به دنباله‌اي از نشانه‌ها تبدیل * کرده و به تحلیلگر نحوي ارسال می‌کند. اگر اين دنباله توسط گرامر زبان مبدا قابل تولید باشد» برنامه مبدا از نظر نحوي صحیح است در غير این صورت داراي خطاي ,نحوي است 

صفحه 29:
تجزیه فرایند تجزیه نشان می‌دهد آیا دنباله‌اي از نشانه‌ها توسط ‎٠‏ گرامر قابل تولید است يا خیر. روالي که فرایند تجزیه را .انجام می‌دهد» تجزیه کننده نامیده می شود 

صفحه 30:
انواع تجزیه کننده‌ها * - تجزیه كنندههاي بالا به پایین * - تجزیه كنندههاي يايين به بالا 

صفحه 31:
ترتیب ساخته شدن درخت تجزیه :بالابه پایی)ع ۴۲60۲0 :پایین‌به با-۴۵5۸0۲۵06 

صفحه 32:
ترتیب ساختن درخت تجزیه در روش بالا به پایین © 9 © 5 » 5 ک QOO® 

صفحه 33:
ترتیب ساختن درخت تجزیه در روش پایین به بالا ۵ ک د © © 60 © 

صفحه 34:
مثال ۳۱۰۲+ بع ۴ ۲۱۲/۳۴ * ۲ م1 0 +۲ : نحوه ساختن درخت تجزیه برای رشته ‎Id+id+id‏ 

صفحه 35:
مثال بدا بسر ]سمي 

صفحه 36:
id id id 

صفحه 37:


صفحه 38:
id id id 

صفحه 39:
id id id id 

صفحه 40:


صفحه 41:
first(a) ۲51 ‏مجموعه‎ ath all pe 5 ball 5! lbs o ‏اگر‎ ‏مربوط به 0 پايانه‌هايي را مشخص مي‌کند که رشته‌هاي مشتق‎ ‏شده از + با آنها شروع مي‌شوند.‎ ‏اگر .ن بتواند ح را تولید کند» ع نیز به (,۲51)6[] اضافه‎ ‏مي‌شود.‎ 

صفحه 42:
مثال 860 حم > | 6 | 08 8 اعوج به رشتههايي كه از 80:0 مشتق شدهاند دقت كنيد. 860-0 800-0 ‎bBd‏ ‎bd‏ ‎BCdeCd Firsi((BCd)={d,b,2,}‏ ‎ed‏ ‏800-۵ ‎acd‏ ‎ad‏ 

صفحه 43:
» با توجه به گرامر ذیل (۳5۲)8۸ و (6۲5)۵8 را محاسبه کنید. A> aAlaB B> b Bi c » با توجه به گرامر» رشته‌هاي مشتق شده از 2۸ فقط با ج و رشته‌هاي مشتق شده از 38 فقط با ج شروع ميشوندء بنابراين: ‎first(aA) = {a }‏ ‎first(aB) = {a }‏ 

صفحه 44:
قونیرم حاسبه]1]5] 0اگر » پایانه باشد آنگاه()۳51] برابر مجموعه (0) است. ‎٠‏ مثال در گرامر فوق دارییم: ‎first(a)={a}‏ * ‎first(b)={b}‏ * 

صفحه 45:
ماگر بم بتواند > را تولید کنده آنگاه > به مجموعه ‎first(a)‏ اضافه می‌گردد. ‎a‏ غير يايانه و م ...۸۷۱۷۷ باشد و ‎Jas first(Y,),first(Y,),...first(Y,) gate sn0‏ > باشند يعني همه ,۷ بتوانند تهي را تولید کنند. در نتیجه ( نیز می‌تواند ع را تولید کند که در این صورت ع به مجموعه ()۲5۲ اضافه می‌گردد. مثال:(61۲5۲)26 5 ۰ > | 2 | 08 | 2۸ ۸۲ ۰ | ظ | 98 ب 8 ۰ 

صفحه 46:
cat ۷,۳۷... ‏اگر 6( غیر پایانه و‎ - ٠ 1۳5۲02( ‏مجموعه (,1۳5۲)۷] (به جز ع)به مجموعه‎ ‏اضافه می‌گردد. زیرا (,3۲5/)۷] مجموعه پايانه‌هايي‎ ‏هستند که در شروع رشته‌هايي که توسط, ۷ تولید می‌شوند‎ ‏قرار دارند از آنجايیکه 6( با ,۷ شروع می‌شود» پس با‎ ‏پايانه‌هاي (,۲51)۲[] شروع مي‌شوند در نتيجه‎ >» Se sthel first(X) 4 first(Y,) 

صفحه 47:
‎oS!‏ لا غير يايانه و ,۷:۰..۷ ,2-۲۷۱۷ باشد و ع در مجموعه (,1۳5۲)۷] باشد (,۷ می‌تواند > را تولید کند) در این صورت علاوه بر (,1۲5)۷] (به جزع) مجموعه ‎(e554) first(Y,)‏ 38 به (۴[۲56)06 اضافه می‌گردد. ‎٠»‏ به كرامر ذيل دقت كنيد 860 دم ‎٠‏ ‎*Boc|dle‏ 

صفحه 48:
follow(A ‎Gadde |) pall follow(A) 4+ 5x0 ٠‏ می‌کند که در اشتقاق‌هاي مختلف بلافاصله در سمت راست ۸ قرار می‌گیرند اين مجموعه را با (0۱۱0۷۷)۸۵] نشان می دهیم. 

صفحه 49:
X >aXAad | a A>Ac|Afleé ‏محاسبه‎ 20 (۲۵2۵۵0 0 (۲۵2۵۵0 20۸63 7 0 با توجه به مراحل بالا می‌توان نتیجه گرفت که: ‎follow(A)={a,c,f}‏ * 

صفحه 50:
قوانین - اگر. 5 نماد شروع باشد 6 (5 نشان دهنده آخر رشته ورودي است) به (۴0۱۱0۷۷/)5 اضافه می‌شود. 

صفحه 51:
۰ (.- براي هر قاعده توليدي به صورت !0+ » تمام پايانه‌هاي موجود در (1۲516] ( به جز ع) به (۲0۵۱۱0۷۷۲۱۷ اضافه می‌شود. A> AXZ|€ Z->aZ|bZ|cle Xa follow(X)= {a,b,c} 

صفحه 52:
۰ براي هر قاعده اي به صورت !۳+0۱ و یا ۱-۲۵۷۵ در صورتيكه © عضو (1۲5)0] باشد يعني 6 بتواند رشته تهي با ع را تولید کند» تمام پايانه‌هاي مجموعه ‎follow(M)‏ 4 (۲0۵۱۱0۷۷)۱۷ اضافه مي‌شود. 

صفحه 53:
مثال + باتوجه به كرامر ‎follow(B) Ja‏ 15 محاسبه كنيد. ۸۵ ۰ ٠ ۲۴ * Eoale * Bob :جواب follow(B)={a,b} 

صفحه 54:
تجزیه کننده بالا به پایین :انواع تجزیه كننده هاى بالا به يايين تجزيه كنندم هاويازكشتى- ۳۹ جزيه > نندم غير بازكشت - 

صفحه 55:
تجزیه کننده های باز گشتم - در این تجزیه کننده یک متغیر پیشنگ. (۱0011620) همواره به نماد جاری رشته ورودی اشاره می کند - تجزیه کننده سعی می کند نمادی که پیشنگر به آن اشاره می کند را تولید کند. - هرگاه نماد مورد نظر پیشنگر تولید شد» پیشنگر به نماد بعدی اشاره می کند. برلىهر غير يايانه يكتابع ليجاد می‌شود - 

صفحه 56:
مثال aR 5 ‏85م‎ ‎+ 68| 

صفحه 57:
تابع کمکی ۳26: هرگاه نماد مورد انتظار گرامر ‎(lookahead) 2555 4445 Gls sti b (Symbol)‏ یکسان شد. یعنی یکی از نمادهای رشته جاری تولید شده است و پیشنگر باید به جلو حرکت کند. وگرنه خطا است. ‎void match(char symbol){‏ ‎if ( lookahead== symbol)‏ ‎lookahead=getche();‏ ‎else{‏ ‎cout<<" error";‏ ‎exit(0);‏ ‏} 

صفحه 58:
6 حم void A(){ match('a'); R(); } 

صفحه 59:
R= A|B ‏«-8ظ8‎ 68| first(A)={a} first(B)={b,c} void R(){ if(lookahead=='a') A(); else if (lookahead=='b' || lookahead=='c') BQ); else{ cout<"error";exit(0);} 1 

صفحه 60:
8« 6 void B(){ if(lookahead=='b'){ match('b'); BO); 0 else if(lookahead=='c'){ match('c'); cout<<"Accepted"; exit(0); } } 

صفحه 61:
int main(){ lookahead= getche(); AQ); return 0; 

صفحه 62:
مشکلات روش پیشگوی غیر بازگشتی ‎٠‏ برخورد ۲5۱/۲۱۲5۲ فرض کنید قانون زیر بخشی از گرامر. است. 6 مق 8+ 2 First(a1) nfirst(a2) #@ ‏:ٍراه حل: فاکتور گیری چپ‎ B= bB|bc B> bR + 

صفحه 63:
first/follow ‏برخورد‎ A> Bed 8 + ۱۵| ‏ع‎ 

صفحه 64:
char lookahead; void A(){ BQ); ‏گرامر‎ ‎match(‘e'); ‏لح مه‎ match(‘d"); ® eh] € 2 void B(){ if (lookahead =='e'){ match(‘e'); else if (lookahead =="'a') match(‘a'); else ; ‏عملکرد تجزیه کننده برای دو رشته لس و لس‎ return ; ‏جيست.‎ ‎} ‎int main(){ lookahead=getche(); AQ); return 0; 

صفحه 65:
* برخورد /۲۱۲5۱/۲0۱۱0۷ در قاعده توليدي به صورت ۸-۲06 شرایط ذیل برقرار باشد. 0- 6 بتواند ع را تولید کند. 2- حداقل يك نماد وجود دارد که هم می‌تواند در شروعن و هم بعد از باشد. یا به عبارت دیگر رابطه ذیل برقرار باشد. first(a) M follow(A)#o 

صفحه 66:
A> Bed |6۵ -ظ ‎a=e SI‏ 5 < باشد» ‎first(e)={e}‏ ‎follow(B)={e}‏ ‏در نتیجه: ‎۲۱۲5۲)6( 6 ۲۵۱۱۵۷۷ )5(< )6( 0 

صفحه 67:
تجزیه کننده پیشگوی غیر ‎SES Sb‏ Adc Cre c AvC لعجن جدول *“-1 _جدول تجزيه 1 A>B Bof ۸ B— bB | f ) ‏ب‎ 0۱ 6 AB B> bB Oa) > 

صفحه 68:
expr — term rest rest > + expr |-expr|¢€ term — id ابتدا۳5۸[] تمام سمت راستهاي قواعد تولید و 0۱۱0۷۷ تمام غیر پایانه‌ها را محاسبه مىكنيم. first(term rest)=first(term)={id} first(+expr)=first(+)={+} first(-expr)=first(-)={-} first(e)={e} ar + ۳ 3 first(id)={id} [expr | exproiern rest follow(expr) = = sue resttexpr test-y-expr | teste follow(term)={+,-,5} follow(rest)={$} 

صفحه 69:
ساختار تجزیه کننده پیشگوی غیر باز گشتم 58 | acs = 

صفحه 70:
Teste ماحل تجزيه ‎id+id-id‏ Test - expr rest >+expr id ‏ساره‎ test term id expr rest 

صفحه 71:
گرامرهای (1)-1] اگر در ساخت درخت تجزیه فقط با رویت يك نشانه بعدي از رشته ورودي در پیمایش چپ به راست. بتوان غیر پایانه بعدي را براي گسترش تشخیص داد در این صورت گرامر مستقل از متن را (1)1] مي‌ناميم. مثال: 0 | 8 حم ‎٠‏ ‎B> bB Ic‏ * ‎cui LL(1) 2 So!‏ 

صفحه 72:
-گرامرهاي داراي بازگشتي چپ (1)1| نیستند. - گرامرهاي مبهم (1)1| نیستند. - اگر جدول تجزیه غيربازگشتي پیشگو داراي خانه‌اي با بیش از يك وارده باشد. گرامر (1)1| نیست و به عکس اگر جدول تجزیه پیشگوی غیر؛ داراي خانه‌اي با بیش از يك وارده نباشد» كرامر (1)1 | است. در نتيجه توليد جدول تجزیه يكي از مهمترین روشهاي تست (1.)1] بودن گرامر است. - گرامرهای دارای برخورد ۴۳56/۴1۳5 از نوع (1)1| نيستند. گرامرهای دارای برخورد ۶۱۳5۲/۶۵۱۱0۷۷ از نوع (1)1] نيستند. اگر در گرامر» قاعده توليدي به صورت ۸۲6/6 وجود داشته باشد به طوریکه ‏ و هر دو رشته تهي را تولید کننده گرامر (1)1] نیست. 

صفحه 73:
* گرامر ذیل را در نظر بگیرید. ع | ۸8 ۰ ع | 08اب ۰ | 60 ب ۰ 

صفحه 74:
نماد ورودي a A> aCbAB e Boe BoeA ٠ A> aCbAB | d Coc * Bo 6۸| ۰ ‏ب)‎ » جم be ۱۱ 

صفحه 75:
- استفاده از قوانین تولید خطا: اگر خطاهايي که در برنامه رخ می‌دهد را بتوان بيش بيني کرد می‌توان قواعد توليدي به گرامر اضافه کرد تا اين خطا را نیز شامل گردد. در این صورت تجزیه کننده با کاهش چنین گرامري خطا را کشف می‌کند و می‌تواند به تجزیه نیز ادامه دهد. گرامر ذیل نشان می‌دهد که بعد از هر دستور سمي کالن قرار دارد. ‎stmt—stmt ; stmt_list | stmt ;‏ با توجه به آمار» يكي از خطاهايي که معمولا در برنامه رخ می‌دهد عدم درج سمي کالن است در نتیجه قاعده توليدي به صورت ذیل نیز به گرامر اضافه می‌گردد. ‎stmt_error-stmt stmt_list | stmt‏ در نتیجه اگر برنامه نویس سمي کالن را درج نکند دستورات به جاي ‎U stmt‏ ۲ 5۱ کاهش می‌یابد بنابراین تجزیه کننده متوقف نمی‌گردد بلکه پیغام مناسب را صادر و تجزیه ادامه می‌یابد. 

صفحه 76:
"مهمترین روشهای تصحیح خطا عبارتند از 0- تصحیح حالت اضطراري: در اين روش تجزیه کننده هنگام کشف يك خطاء نمادهاي ورودي را تا رسیدن به يك علامت هماهنگ کننده که به وسیله طراح کامپایلر معین شده است نادیده می‌گیرد. به عنوان مثال علامت سمي كالن در زبان ) يك علامت هماهنگ کننده است. 

صفحه 77:
مدیریت خطا ۰ اگر پايانه‌اي مانند ‏ بالاي یه باشد که با نماد جاري یکسان نباشد» خطا رخ مي‌دهد. به منظور پوشش خطاء نماد 3 را به ورودي اضافه می‌کنيم. ۸و AvaA * SobcA ۰ ۸۲۵۸ 5 4 

صفحه 78:
۸ ‏ربا به عنوان مجموعه هماهنگ کننده‎ first(A) slats ‏در نظر می‌گیریم . بنابراین اگر يكي از نمادهاي‎ ‏ظاهر شود تجزیه بر اساس ۸ ادامه‎ 5255 9 first(A) ‏می‌یابد.‎ نمادهاي () ۲01۱0۷۷ را به عنوان نمادهاي هماهنگ کننده ۸ در نظر می‌گیریم. 

صفحه 79:
تجزیه کننده پایین به بالا - تجزیه کننده های عملگر اولویت - تجزیه کننده های 1 

صفحه 80:
:مثالی از نحوه عملکرد تجزیه کننده پایین به بالا ‎expr— expr + term | expr - term |‏ ۵ «16۲۳۱] 441-2 term +1-2 expr + 1-2 expr + term -2 expr - 2 expr - term expr 

صفحه 81:
1+2-+3 term+ 2-+3 expr + 2-+3 expr + term -+3 expr -+ 3 expr -+ term expr-+ expr 

صفحه 82:
جدول ۱-۲ انوا روش اول روشها 12 4+ term 2 4+ term term term + term -term expr + term -term expr- term expr روش سوم 4+12 دمع - 1 ج4 4+ term ‏تمع‎ term + expr -ferm term + expr (عدم موفتیت در تجزیه ) كاهش رشته 4+12 به_نماد شرو روش دوم 4132 term +1-2 expr +1-2 expr + term -2 expr-2 expr- term expr ‏روش چهارم‎ 4+12 4+ 1-term 4+ term -term term + term -term expr + term -term expr term. expr 

صفحه 83:
دستگیره دستگیره» دنباله‌اي است که منطبق بر سمت راست يك ‎٠‏ ‏قاعده تولید بوده و کاهش آن به سمت چپ قاعده تولید يك .مرحله از مراحل معکوس سمت راست‌ترین اشتقاق است 

صفحه 84:
تجزیه بایین به بالا 13 term +1-2 expr+ 1-2 expr + term -2 expr - expr expr term جدول ۱۷-۳ مقایمه تجزیه پایین به بالا با سمتر است ترين اشتقاق اقتقاق ‎expr‏ expr - term expr - 2 expr + term - expr+1- 2 term+1- 2 4+1-2 

صفحه 85:
جدول_ ۱۸-۳ دسنگیره ما es 4 term 1 expr_+ term 2 ‎term‏ عوك ‎ ‎ ‎Gaal ‎1-1-2 ‎1 11-2 expr 12 expr + term -2 expr=2 ‎expr - term expr ‎ ‏در تجزيه يابين به بالا رشته ‏قاعده تولید مورد استفاده ‎term>4‏ ‎expr>term,‏ ‎term 1‏ ‎expr expriterm‏ ‎term—>2‏ ‎expr >expriterm‏ ‎ ‎441-2 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 86:
+ دستگیره‌ها را در کاهش رشته 06606 با توجه به گرامر ذیل ۴و 86 ‎Ge‏ ابتدا رشته 6606۴ را بوسیله سمت راست ترین اشتقاق تولید می‌کنیم. جدول ۱۹-۳ دستگیره 6 Bed 8 bBCE دسنگیره هاي کاهش رشته ‎becdef‏ 5 bBCf bBef bBcdef bccdef 

صفحه 87:
عملکرد تجزیه کننده های ۳ - یافتن دستگیره - کاهش دستگیره 

صفحه 88:
ساختار تجزیه کننده های ۳ 2 29 5 Ba bn Coes DLR + ‎action goto‏ حالات ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 89:
مثال گرامر ذیل را در نظر می‌گيریم. ,گرامر به شکل زیر تغییرمی کند جدول۲۲-۲ جدول نجزبه 18 action goto id + I 9 1 1 sh 3 error 2 3 rh rt 1 3 3 3 error 0 accept 51 7 error 5 7 7 7 ae wa} a} ea} ‏احات أن‎ E>E+T |T Tid 1-5 ‏غ ه‎ 2- E>E+T 3- ExT 4- Tid 

صفحه 90:
مر‌احل تحنریه رشته 10+ 0] جدول ۷۲۲-۳ مراحل تجزیه_ رشته 1010 توفیحات با توجه به کننده ‎id‏ و سپس 1 « action[0,id]=s1 ‏را به‎ منتقر می‌کند. لتیجه تجزیه پشته اين تغيير در مرحله بعد نشان داده_شده_ است. با توجه به همه و با توجه به اینکه قاعده تولید شماره 4 قاعده تونید ۲:۵ است» تجزیه کننده 1 و ۱ را از بالاي پشته حذف می‌کند. در نتیچه حالت بالاي پشته 0 است. با خروج 4 11 as 1 

صفحه 91:
id id E+T جدول ۲۶-۳۲ _دستگیره ها قواعد تولیه خروجي تجزیه کننده ‎LR‏ ‎Tid‏ ‎B>T‏ ‎Tid‏ ‎ESE+T‏ رشته idtid THid Et+id Eer 

صفحه 92:
مهمترین روشهاي موجود عبارتند از: 0- : (1)0 | ساده ترين و ضعيفترين روش است. ©2- اا (5115)1) ساده): اين روش از (1)0 | قويتر است 9- (8)1ا يا 8 متعارف: قویترین روش ساخت جدول تجزیه | است. CLR(1) 5! 5 susi SLR(1) Vas 3) :LALR(1) -# ‏ضعیفتر است.‎ 

صفحه 93:
روش (1)0! عنص ر(8)0 ا : يك قاعده توليد است كه نقطه اى در سمت راست آن قرار دارد( مانند: 590.۵ ). مکان نقطه در عنصر 2 میزان پیشرفت. در كاهش غير پایانه سمت چپ(مانند ) را نشان می‌دهد. 5.2 52 52 5۰ 

صفحه 94:
* عنصر کاهشی: عنصری که نقطه در آحر سمت راست قاعده توليد قرار دارد. اين نوع عنصر نشان دهنده یافتن یک دستگیره است. به عنوان مثال عنصر 5-0 نشان می‌دهد که ۶ یک دستگیره است که می‌توان آن را به ‎٩‏ کاهش داد. عنصر انتقالی: عنصری که کاهشی نباشد. به عنوان مثال ‎٩-2‏ یک عنصر انتقالی است. هر عنصر انتقالی نشان دهنده فرضیه‌ای در مورد دستگیره بعدی است به عنوان مثال 9-2 نشان می‌دهد که دستگیره ممکن است از ۷ به دست آید. 

صفحه 95:
ساخت ماشين متناهى ESE+T|T T>id E>E+T ‏امع‎ ‎10 ‏بو‎ ‎ESE+T ‏آبع‎ ‎10 

صفحه 96:
.بو ‎S>.E‏ ‎E>.E+T‏ ‎E>.T‏ ‏.بو ‎E>.E+T‏ ‏جع ‎T-.id‏ 

صفحه 97:
شکل ۳۲-۳ ماشین خودکار (1800 

صفحه 98:


صفحه 99:


صفحه 100:


صفحه 101:


صفحه 102:
جدول_ ۲۵-۳ _ساختار_جدول_تجزیه 

صفحه 103:
E>E+T \T Tid جدود_ ۷۶-۳ ساختار_جدود_تجزیه ‎action goto‏ id + 5 1 1 حالات ها ده ام اح نت 

صفحه 104:
اس goto اد جدود_ ۳۲-۳ جدول_تجزیه 5 error 1 3 ‘accept 2 action = error 11 13 sf 2 LRO) id ۳1 3 error 2 ae أت إن اناس أحد ام 

صفحه 105:
برخورد انقال /کاهش بو ‎ese‏ ‎eo?‏ ‎Dordt‏ ‏[6] ۲۷ 51 

صفحه 106:
برخورد کاهش /کاهش SE E>E+T ET ‏لامع‎ ‏0ه‎ X> id 

#inlcude<iostream.h> #inlcude<stdlib.h> #inlcude<stdio.h> int main(){ int state; char ch; state=1; switch(state){ case 1: ch= getc(stdin); if (ch==’a’) state=2; else { cout<<"Failed"; exit(0); } break; case 2: ch=getc(stdin); if(ch=='\n') cout<<"Accepted"; else cout<<"Failed"; exit(0); } return(0); } 1 a 2 #inlcude<iostream.h> #inlcude<stdlib.h> #inlcude<stdio.h> int main(){ int state; char ch; state=1; while(1){ a switch(state){ case 1: ch = getc(stdin); if (ch==’a’) state=1; else if(ch == 'b') state=2; else { cout<<"Failed"; exit(0); } break; case 2: ch=getc(stdin); if(ch=='\n') cout<<"Accepted"; else cout<<"Failed"; exit(0); } } return(0); } b 1 2 #inlcude<iostream.h> #inlcude<stdlib.h> #inlcude<stdio.h> int main(){ int state; char ch; state=1; while(1){ [a-zA-Z0-9] switch(state){ case 1: ch = getc(stdin); if ((ch>=’a’ && 'z'>=ch )|| (ch>=’A’ && 'Z'>=ch) ) state=2; else { cout<<"Failed"; exit(0); } break; [a-zA-Z] [a-zAcase 2:ch = getc(stdin); 1 if(ch=='\n'){ 2 Z cout<<"Accepted"; exit(0); } else if ((ch>=’a’ && 'z'>=ch )|| (ch>=’A’ && 'Z'>=ch) || (ch>=’0’ && '9'>=ch)) state=2; else { cout<<"Failed"; exit(0); } exit(0); break; } return(0); } [a-zA-Z0-9] [0-9] [a-zA-Z] 1 [1-9] 2 6 7 [0-9] [0-9] [ \n] . [1-9] 3 4 4 5 8 • • • • • • • • • • • • • int fail(int start) { int nextstart; switch(start){ case 1:nextstart=3; // break; case 3:nextstart=6; // break; case 6:nextstart=8; // break; } return nextstart; } عشاري6عداد ا6ا حيح66عداد ص6ا لي66ا6ضايخ666ف int main{ int state,start,loc; char ch; FILE *fp; fp=fopen("source.txt","r"); state=1; start=1; while(1) switch(state){ case 1: loc=ftell(fp); ch=getc(fp); if((ch>='a' && ch<='z') || (ch>='A' && ch<='Z')) state=2; else{ start=fail(start); state=start; fseek(fp,loc,SEEK_SET); } break; case 2:ch=getc(fp); if((ch>='a' && ch<='z') || (ch>='A' && ch<='Z') || (ch>='0' && ch<='9')) state=2; else if (ch==' '|| ch=='\n'|| ch==EOF){ cout<<"ID "; state=8; } else{ start=fail(start); state=start; fseek(fp,loc,SEEK_SET); } break; case 3: loc=ftell(fp); ch=getc(fp); if(ch>='1' && ch<='9') state=4; else { start=fail(start); state=start; fseek(fp,loc,SEEK_SET); } break; اولویت ها ممكن است بخشي از يك دنباله از كاراكترها با يك عبارت باقاعده و بخش ديگری با عبارت باقاعده ديگري منطبق شود .به عنوان مثال دنباله 123.65و دو عبارت با قاعده ذيل را در نظر مي گيريم. *][1-9][0-9 *][1-9][0-9]*. [0-9][1-9 . پذيرش طوالني ترين دنباله است ممكن يك دنباله از كاراكترها (نه بخشي از يك دنباله) با دو يا چند عبارت باقاعده منطبق شود به عنوان مثال رشته ifمي تواند توسط دو عبارت باقاعده ذيل توليد شود. ‏if *][a-zA-Z][a-zA-Z0-9 عبارت با قاعده اي كه اولويت بيشتري دارد ،ابتدا مقايسه .مي شود case 1:nextstart=6; // case 6:nextstart=3; // int fail(int start){ int nextstart; switch(start){ ا;عداد ص;;حيح break; case 3:nextstart=8; break; ا;عداد ا;عشار;ي break; } return (nextstart); } توليد خودكار تح:ليلگر لغوي • • • • استفاده از ابزارها دار6اي مز6ايا و معايبي است كه عبارتند از: افزايش سرعت ايجاد تغييرات كاهش ز6مان ساخت تحليلگر لغوي افزايش محدوديتها پياده سازي تحليلگر لغوي به وسيله توليدكننده تحليلگر لغوي FLexبرنامه به زبان Flexكامپايل بوسيله يا پاسكال Cبرنامه به زبان Cكامپايل; بوسيله كامپايلر تحليلگر لغوي • • • • c:\> flex pascal.l scanner.c بعد از کامپایل و تولید فایل اجرایی c:\> scanner.exe< p1 c:\> scanner.exe <p1> result • c:\> scanner.exe ظر66 هايمورد ن6رشته نحوه بيان عبارات با قاعده *r ‏r+ ?r }r{m,n }X{2,5 ‏r1r2 ‏r1/r2 (If/ ‏r1|r2 ]مجموعه 6ك6ارا6كترها[ ][afk كاراكترهاي مورد نظر[^ ][^afk . بجز سر خط ] كاراكتر مقصد -كاراكترمبدا[ ][b-f س اختار ب رنام ه ب ه زبانflex تعاريف %% ترجمه ها %% توابع • • • • • مثال digit [0-9] lower [a-z] upper [A-Z] letter lower|upper var {letter}|({letter}|{digit})* ws [ \n\t]+ %% ws {} “if” {printf(“I found ‘IF’ keyword”);} “else” {printf(“I found ‘ELSE’ keyword”);} var {printf(“I found variable “);} %% .• اگر متن ذيل به عنوان ورودي به اين تحليلگر داده شود • if temp else if id 34 .• خروجي به صورت ذيل خواهد بود • I found ‘if’ keyword • I found variable • I found ‘ELSE’ keyword • I found ‘if’ keyword • I found variable %option noyywrap %{ int nchar,nline; %} %% [\n] {nline++;} . {nchar++;} } %% int main(void){ yylex(); printf("%d %d",nchar,nline+1); return (0); } کلمات کلیدی روش اول [a-zA-Z]([a-zA-Z0-9])* "program" "); "var" "begin" "end" printf("ID "); printf("PROGRAM printf("VAR "); printf("BEGIN "); printf("END "); void toupper(char k[]) { int i; for(i=0;i<=strlen(k);++i) if(k[i]<='z' && k[i]>='a') k[i]-=32; } int is_keyword(char id[]) { char keyword[40][20]={"AND", "ARRAY","BEGIN","CASE","CONST","DIV","DO","DOWNTO","ELSE","END","EXTERNAL","EXTE RN","FILE", "FOR","FORWARD","FUNCTION","GOTO","IF","IN","LABEL","MOD","NIL","NOT","OF","OR","O THERWISE", "PROCEDURE", "PROGRAM","RECORD","REPEAT","THEN","TO","TYPE","UNTIL","VAR","WHILE","WITH"}; int i; for(i=0;i<40;i++) if(strcmp(id,keyword[i])==0) return i; return -1; } %} کلمات کلیدی روش دوم [a-zA-Z]([a-zA-Z0-9])* {toupper(yytext); if (is_keyword(yytext)!=-1) printf("keword= %s",yytext); else printf("ID "); } حساس به حالت • • • • • . . . A [aA] B [bB] C [cC] D [dD] E [eE] • {A}{N}{D} return(AND); • {A}{R}{R}{A}{Y} return(ARRAY); • {C}{A}{S}{E} return(CASE); • {C}{O}{N}{S}{T} return(CONST); • {D}{I}{V} return(DIV); • {D}{O} return(DO); حساس به حالت روش دوم [a-zA-Z]([a-zA-Z0-9])* {toupper(yytext); if (is_keyword(yytext)!=1) return (KW); else return(IDENTIFIER ); } فاكتور گيري چپ • بر6اي يك غير پايانه ممكن است انتخابهاي مختلفي وجود داشته باشد به طور6يكه شروع يكسان داشته باشند .به عنوان مثال به گرامرهاي ذيل دقت كنيد. • A a B | aD و يا • • A cd B | cdg D حذف بازگشتی چپ • A  1 | 2 | 3 ... | n • :ش66روع مشترك • i:قسمت غير مشترك • گرامر فوق را می‌توان به صورت ذيل نشان داد كه همان زبان را توليد می‌كند: • ‏A  R • R  1 | 2 | 3 | .. مثال • A cd B | cdg D • BbB | c • DdD | e • با توجه به AcdB|cdgDقسمت مشترك cdاست در نتيجه: • = cd • 1=gD • 2=B • گرامر را می‌توان به صورت ذيل نشان داد. • A cd R • R B | g D • BbB | c • DdD | e تحليلگر لغوي بر6نامه مبدا را به دنباله‌اي از نشانه‌ها تبديل • كرده و به تحليلگر نحوي ارسال می‌كند .اگر اين دنباله توسط گر6امر زبان مبدا قابل توليد باشد ،برنامه مبدا از نظر نحوي صحيح است در غير اين صورت داراي خطاي .نحوي است تجزیه فرايند تجزيه نشان می‌دهد آيا دنباله‌اي از نشانه‌ها توسط • گرامر 6قابل توليد است يا خير .روالي كه فرايند تجزيه را .انجام می‌دهد ،تجزيه كننده ناميده می شود • -تجزيه كنندههاي باال به پايين • -تجز6يه كننده‌هاي پايين به باال ترتیب ساخته شدن درخت تجزیه :ب666ا66الب666ه 6پ666ایینPreorder :پ666ایینب666ه 6ب666ا66الPostorder ترتیب ساختن درخت تجزیه در روش باال به پایین ترتیب ساختن درخت تجزیه در روش پایین به باال مثال • E E + T | E - T | T • T T * F | T / F | F • F id :نحوه ساختن در6خت تجزیه برای رشته • • Id+id+id مثال )first( دنبالهاي از پايانه‌ها و غير پايانه‌ها باشد ،مجموعه first ‌ اگر 6 پايانههايي را مشخص مي‌كند كه رشته‌هاي مشتق ‌ مربوط به  شده از با آنها شروع مي‌شوند. اگر  6بتواند را توليد كند  ،نيز به ) first(اضافه مي‌شود. A BCd B bB | e |  C aC |  مثال . مشتق شده‌اند دقت كنيدBCd به رشته‌هايي كه از BCdd BCdbBCd bBd bd BCdeCd ed BCdCd aCd ad first(BCd)={d,b,e,a} • با تو6جه به گرامر ذيل ) first(aAو ) first(aBرا محاسبه كنيد. • A→ a A|a B • B→ b B| c • با توجه به گرامر ،رشته‌هاي مشتق شده از aAفقط با aو6 رشته‌هاي مشتق شده از aBفقط 6با aشرو6ع مي‌شوند ،بنابراين: } • first(aA) = {a } • first(aB) = {a • ق وان ینم حاسبهfirst -1اگر پايانه باشد آنگاه) first(بر6ابر مجموعه {} است. • مثال در گرامر 6فوق دار6يم: }• first(a)={a }• first(b)={b • -2اگر بتواند را توليد كند ،آنگاه به مجموعه ) first(اضافه می‌گردد. -3اگر Xغير پايانه و XY1Y2Y3...Ynباشد و مجموعههاي ) first(Y1),first(Y2),...first(Ynشامل ‌ باشند يعني همه Yiبتوانند تهي را توليد كنند .در نتيجه X نيز می‌تواند را توليد كند كه در اين صورت به مجموعه ) first(Xاضافه می‌گردد. مثالfirst(X): • S  AB • A aA | bB | a |  • B  bB | b |  • -4اگر Xغير پايانه و XY1Y2Y3...Ynباشد، مجموعه )( first(Y1به جز )به مجموعه )first(X اضافه می‌گردد .زيرا ) ‌first(Y1مجموعه پايانه‌هايي هستند كه در شروع رشته‌هايي كه توسط Y1توليد می‌شوند قرار 6دارند از 6آنجاييكه Xبا Y1شروع می‌شود ،پس Xبا پايانه‌هاي ) first(Y1شروع مي‌شوند ،در نتيجه ) first(Y1به ) first(Xاضافه می‌گردد. اگر X 6غير پايانه و XY1Y2Y3...Ynباشد و در6 مجموعه ) first(Y1باشد ( Y1می‌تواند ر6ا توليد كند) در اين صورت عالوه بر( first(Y1) 6به جز )6مجموعه )( first(Y2به جز )نيز به ) first(Xاضافه می‌گردد. • به گرامر ذيل دقت كنيد • A  Bab • Bc|d| follow(A • • مجموعه ) follow(Aپايانه‌هايي را مشخص می‌كند كه در اشتقاق‌هاي مختلف بالفاصله در سمت راست Aقرار6 می‌گيرند اين مجموعه را با ) follow(Aنشان می دهيم. X aXAad | a A  Ac | Af |  محاسبه XaXAad XaXAad aXAcad XaXAad aXAcad aXAfcad :با توجه به مراحل باال می‌توان نتيجه گرفت كه • follow(A)={a,c,f} قوانین اگر S 6نماد شر6وع باشد $( $نشان دهنده آخر رشتهورودي است) به ) follow(Sاضافه می‌شود. • -2براي هر قاعده توليدي به صورت ، MNتمام پايانههاي موجود در ) ( first(به جز )به ‌ ) follow(Nاضافه می‌شود. ‏A AXZ |  ‏Z  aZ | bZ | c | ‏X a }follow(X)= {a,b,c • بر6اي هر قاعده اي به صور6ت MNو يا MN در 6صور6تيكه عضو ) first(باشد يعني بتواند رشته تهي يا ر6ا توليد كند ،تمام پايانه‌هاي مجموعه ) follow(Mبه ) follow(Nاضافه مي‌شود. مثال . را محاسبه كنيدfollow(B) • با توجه به گرامر ذيل • AAXb • Xd|dB|eBE • Ea| • Bb جواب: follow(B)={a,b} تجزيه كننده باال به پايين :انواع تجزیه کننده های باال به پایین ت666جزیه 6ک666ننده 6هایب666ازگ6شتی- ت666جزیه 6ک666ننده 6غیر ب666ازگ6شتی- تجزیه کننده های بازگشتی در 6این تجزیه کننده یک متغیر پیشنگر)lookahead( 6همواره به نماد جاری ر6شته ورودی اشاره می کند تجزیه کننده سعی می کند نمادی که پیشنگر به آن اشاره میکند را تولید کند. هرگاه نماد مورد نظر پیشنگر 6تولید شد ،پیشنگر 6به نمادبعدی اشاره می کند. ب666را6یهر غیر پ666ایانه 6یکت666ابع 6ا6یجاد میش66ود - A→ aR R→ A|B B→ bB|c مثال تابع کمکی :matchهرگاه نماد مورد انتظار گرامر ( )symbolبا نماد جاری رشته ورودی ()lookahead یکسان شد .یعنی یکی از نمادهای رشته جاری تولید شده است و پیشنگر باید به جلو حرکت کند .وگرنه خطا است. {)void match(char symbol )if ( lookahead== symbol ;)(lookahead=getche {else ;"cout<<" error ;)exit(0 } } A→ aR void A(){ match('a'); R(); } R→ A|B B→ bB|c first(A)={a} first(B)={b,c} void R(){ if(lookahead=='a') A(); else if (lookahead=='b' || lookahead=='c') B(); else{ cout<"error";exit(0);} } B→ bB|c void B(){ if(lookahead=='b'){ match('b'); B(); } else if(lookahead=='c'){ match('c'); cout<<"Accepted"; exit(0); } } int main(){ lookahead= getche(); A(); return 0; } مشکالت روش پیشگوی غیر بازگشتی • بر6خورد first/first فرض کنید قانون زیر 6بخشی از گرامر 6است. ‏B→ bB|bc ‏B→ α1|α2 ‏First(α1) ∩first(α2) ≠φ :راه حل :فاکتور گیری چپ ‏B→ bB|bc ‏B→ bR ‏R→ B|c first/follow برخورد A→ Bed B → e|a|  char lookahead; void A(){ B(); match('e'); match('d'); } void B(){ if (lookahead =='e'){ match('e'); else if (lookahead =='a') match('a'); else ; return ; } int main(){ lookahead=getche(); A(); return 0; } گرامر A→ Bed B → e|a|  eed وed عملکرد تجزیه کننده برای دو رشته .چیست • برخور6د first/follow • • • • در قاعده توليدي به صورت A|شر6ايط ذيل بر6قرار باشد.  -1بتواند را توليد كند. -2حداقل يك نماد وجود دارد كه هم می‌تواند در شروع و هم بعد از Aباشد .يا به عبارت ديگر 6ر6ابطه ذيل برقرار باشد. ‏first()  follow(A) A→ Bed B→ e|a| ، باشد= و=e اگر first(e)={e} follow(B)={e} :در نتيجه first(e)  follow(B)={e} تجزيه كننده پيشگوي غير بازگشتي ‏AB|C ‏B  bB | f ‏C  cC | e expr  term rest rest  + expr | - expr |  term  id تمام غير پايانه‌هاfollow تمام سمت راستهاي قواعد توليد وfirstابتدا .را محاسبه می‌كنيم first(term rest)=first(term)={id} first(+expr)=first(+)={+} first(-expr)=first(-)={-} first()={} first(id)={id} follow(expr)={$} follow(term)={+,-,$} follow(rest)={$} ساختار تجزیه کننده پیشگوی غیر بازگشتی مراحل تجزيه id+id-id گرامرهای )LL(1 اگر در ساخت درخت تجزيه فقط با رويت يك نشانه بعدي از رشته ور6ودي در پيمايش چپ به راست ،بتوان غير پايانه بعدي را براي گسترش تشخيص داد در اين صورت گرامر مستقل از متن ر6ا ) LL(1مي‌ناميم. مثال: • A aB | aad • B bB | c این گرامر LL(1) 6نیست. • • • • • گرامرهاي داراي بازگشتي چپ ) LL(1نيستند. گرامرهاي مبهم ) LL(1نيستند. اگر جدول تجزيه غيربازگشتي پيشگو داراي خانه‌اي با بيش از يك واردهباشد ،گرامر ) LL(1نيست و به عكس اگر جدول تجزيه پيشگوی غيربازگشتي داراي خانه‌اي با بيش از يك وارده نباشد ،گرامر ) LL(1است .در نتيجه توليد جدول تجزيه يكي از مهمترين روشهاي تست ) LL(1بودن گرامر است. گرامرهای دارای برخورد first/firstاز نوع ) LL(1نیستند.گرامرهای دارای برخورد first/followاز نوع ) LL(1نیستند. • اگر در گرامر ،قاعده توليدي به صورت A|وجود داشته باشد به طوريكه  و هر دو رشته تهي را توليد كنند ،گرامر ) LL(1نيست. • گرامر ذيل را در نظر بگير6يد. • ACB |  • BbB |  • C cC | • A aCbAB | d • B eA| • C c  استفاده از قوانين توليد خطا :اگر خطاهايي كه در برنامه رخ می‌دهد را بتوانپيش بيني كرد می‌توان قواعد توليدي به گرامر اضافه كرد تا اين خطا را نيز شامل گردد .در اين صورت تجزيه كننده با كاهش چنين گرامري خطا را كشف می‌كند و می‌تواند به تجزيه نيز ادامه دهد. گرامر ذيل نشان می‌دهد كه بعد از هر دستور سمي كالن قرار دارد. ; stmtstmt ; stmt_list | stmt با توجه به آمار ،يكي از خطاهايي كه معموال در برنامه رخ می‌دهد عدم درج سمي كالن است در نتيجه قاعده توليدي به صورت ذيل نيز به گرامر اضافه می‌گردد. ‏stmt_errorstmt stmt_list | stmt در نتيجه اگر برنامه نويس سمي كالن را درج نكند دستورات به جاي stmtبا stmt_errorكاهش می‌يابد بنابراين تجزيه كننده متوقف نمی‌گردد بلكه پيغام مناسب را صادر و تجزيه ادامه می‌يابد. :مهمترين روشهاي تصحيح خطا عبارتند از • -1تصحيح حالت اضطراري :در اين روش تجزيه كننده هنگام كشف يك خطا ‌،نمادهاي ورودي را تا رسيدن به يك عالمت هماهنگ كننده كه به وسيله طراح كامپايلر معين شده است ناديده می‌گيرد .به عنوان مثال عالمت سمي كالن در زبان Cيك عالمت هماهنگ كننده است. مدیریت خطا پايانهاي مانند aباالي پشته باشد كه با نماد جاري يكسان نباشد، ‌ • -1اگر خطا رخ مي‌دهد ،به منظور پوشش خطا ،نماد aرا به ورودي اضافه می‌كنيم. • SbcA • AaA|c رشته bdcc • نمادهاي ( first(Aر6ا به عنوان مجموعه هماهنگ كننده A در نظر می‌گيريم .بنابراين اگر يكي از نمادهاي ) first(Aدر ورودي ظاهر شود تجزيه بر 6اساس Aادامه می‌يابد. • نمادهاي ) follow(Aرا به عنوان نمادهاي هماهنگ كننده Aدر 6نظر 6می‌گيريم. تجزيه كننده پايين به باال تجزیه کننده های عملگر 6اولویت -تجزیه کننده های LR یه کننده پایین به باال6مثالی از نحوه عملکرد تجز: expr expr + term | expr - term | term term 1|2|3|4 4+1-2 term +1-2 expr + 1 -2 expr + term -2 expr - 2 expr - term expr • • • • • • • 1+2-+3 term+ 2-+3 expr + 2 -+ 3 expr + term -+3 expr -+ 3 expr -+ term expr -+ expr دستگیره دستگيره ،دنباله‌اي است كه منطبق بر 6سمت راست يك • قاعده توليد بوده و كاهش آن به سمت چپ قاعده توليد يك .مرحله از مراحل معكوس سمت راست‌ترين اشتقاق است • دستگيرهها را در كاهش رشته bccdefبا توجه به گرامر ذيل ‌ مشخص كنيد. ‏SbBCf ‏BBcd|c ‏Ce ابتدا رشته bccdefرا بو6سيله سمت 6راست 6ترين اشتقاق توليد می‌كنيم. ‏S ‏bBCf ‏bBef ‏bBcdef ‏bccdef عملکرد تجزیه کننده های LR یافتن دستگیره -کاهش دستگیره ساختار تجزیه کننده های LR مثال گرامر ذيل را در نظر می‌گيريم. ‏E→E+T | T ‏T→id .گرامر به شکل زیر تغییرمی کند ‏S→E ‏E→E+T ‏E→T ‏T→id 1234- مراحل تجزيه رشته id+id مهمترين روشهاي موجود عبارتند از: LR(0) : -1ساده ترين و ضعيفترين روش است. )SLR(1) LR -2ساده) ‌:اين روش از ) LR(0قويتر است. LR(1) -3يا LRمتعارف :6قويترين ر6وش ساخت جدول تجزيه LRاست. ‌ )CLR(1 :LALR(1) -4از 6ر6وش ) ‌SLR(1قويتر و از ضعيفتر است. روش )LR(0 عنصر): LR(0 يك قاعده توليد است كه نقطه اي در سمت راست آن قرار دارد( مانند .) S→α.β :مكان نقطه در عنصر LRميزان پيشرفت، در كاهش غير پايانه سمت چپ(مانند )Sرا نشان می‌دهد. ‌S→.XYZ ‌S→X.YZ ‌S→XY.Z ‏S→XYZ‌. • عنص/ر كاهش/ي :عنص/ري ك/ه نقط/ه در آخ/ر س/مت راس/ت قاعده تولي/د قرار دارد .اي/ن نوع عنص/ر نشان دهنده يافت/ن ي/ك دس/تگيره اس/ت .ب/ه عنوان مثال‌ عنص/ر ‌.S→XYZنشان می‌ده/د ك/ه ‌XYZيك دستگيره است كه می‌توان آن را به ‌Sكاهش داد. • عنص//ر انتقال//ي :عنص//ري ك//ه كاهش//ي نباشد .ب//ه عنوان مثال S→X.YZي/ك عنص/ر انتقال/ي اس/ت .ه/ر عنص/ر انتقال/ي نشان دهنده فرضيه‌اي در مورد دس/تگيره بعد/ي اس/ت ب/ه عنوان مثال S→X.YZنشان می‌ده/د ك/ه دس/تگير/ه ممك/ن اس/ت از Yب/ه دست آيد. ساخت ماشین متناهی E→E+T‌|T T→id E→E+T‌ E→T T→id S→E E→E+T‌ E→T T→id S→.E S→.E E→.E+T‌ E→.T S→.E E→.E+T‌ E→.T T→.id E→E+T‌ |T T→id برخورد انتقال /کاهش ‏S→E ‌E→E+T ‏E→T ‏T→id ] T→id [ E کاهش/ برخورد کاهش S→E E→E+T‌ E→T E→X T→id X→ id