Document

Report
‫به نام خدا‬
‫‪2‬‬
‫طراحی‬
‫کامپایلرها‬
‫‪40-414‬‬
‫ی‬
‫دورنمای تحلیلگر لغو ‌‬
‫تحلیلگر‬
‫نحوی‌‬
‫نشانه‌ها‬
‫تحلیلگر لغوی‌‬
‫نشانه‌ی بعدی‬
‫جدول‬
‫عالیم‬
‫‪ o‬پرسش مهم‪ :‬وظیفه‌ی هر جعبه چیست؟‬
‫‪‬‬
‫‪1‬‬
‫ً‬
‫فعال بر تحلیلگر لغوی و تحلیلگر نحوی تمرکز می‌کنیم‬
‫برنامه‌ی‬
‫مبدأ‬
‫چرا تحلیل لغوی و نحوی را جدا کنیم؟‬
‫‪ o‬سادگی طراحی‬
‫‪ o‬بهبود کارایی کامپایلر‬
‫‪ o‬رعایت اصول برنامه نویس ی پیمانه ای‬
‫‪2‬‬
‫نشانه‪ ،‬الگو‪ ،‬و ‪)1( Lexeme‬‬
‫‪ o‬نشانه‪ ،‬یک زوج است‪ :‬نام نشانه‪ ،‬و یک ویژگی اختیاری‌‬
‫‪ o‬الگو‪ ،‬شکلی را توصیف می‌کند که ‪ lexeme‬های یک نشانه ممکن‬
‫است در متن داشته باشند‬
‫‪ ،lexeme o‬توالی‌ای از نویسه‌ها در متن برنامه‌ی مبدأ است که با الگو‬
‫مطابقت دارد‬
‫‪3‬‬
‫نشانه‪ ،‬الگو‪ ،‬و ‪)2( Lexeme‬‬
‫‪ o‬مثال‪:‬‬
‫‪4‬‬
‫نشانه‬
‫توصیف غیررسمی‬
‫نمونه‌ی ‪lexeme‬‬
‫‪if‬‬
‫نویسه‌های ‪ i‬و ‪f‬‬
‫‪if‬‬
‫‪else‬‬
‫نویسه‌های ‪ ،s ،l ،e‬و ‪e‬‬
‫‪else‬‬
‫‪relation‬‬
‫<یا >یا =>یا =<یا ==یا =!‬
‫=<‪!= ،‬‬
‫‪id‬‬
‫حروفی که به دنبال آن‌ها‬
‫حرف یا عدد بیاید‬
‫‪ ،score ،pi‬و ‪D2‬‬
‫‪number‬‬
‫هر عدد ثابت‬
‫‪ ،0 ،3.14159‬و‬
‫‪6.02e23‬‬
‫‪literal‬‬
‫هر چیزی جز “ که توسط “‬
‫محصور شده باشد‬
‫”!‪“Hello World‬‬
‫استفاده از میانگیر برای بهبود کارایی‬
‌‫نشانه‌ی جاری‬
E
=
M *
C * * 2
lexeme ‫شروع‬
‫بلوک‬
I/O
forward
‫به جلو حرکت می‌کند تا یک‬
‫انطباق با الگو را پیدا کند‬
if forward at end of first half then
begin
reload second half ;
forward := forward + 1
end
else if forward at end of second half then
begin
reload first half ;
move forward to beginning of first half
end
else forward := forward + 1 ;
5
‫ میانگیر با نگهبان‬:‫الگوریتم‬
lexeme ‫شروع‬
E
=
M *
‌‫نشانه‌ی جاری‬
C * * 2
forward := forward + 1;
if forward is at eof then
begin
if forward at end of first half
then
begin
reload second half ;
forward := forward + 1
‫ بلوک‬end
else if forward at end of second
I/O half then
begin
reload first half ;
move forward to beginning
of first half
end
else /*‫ معرف پایان ورودی است‬،‫ در میانگیر‬eof*/
terminate Lexical Analysis
end
‫ یعنی چیزی از ورودی باقی نمانده‬eof ‫دومین‬
forward
‫به جلو‬
‫حرکت‬
‫می‌کند تا یک‬
‫انطباق با‬
‫الگو را پیدا‬
‫کند‬
6
‫سلسله‌مراتب چامسکی‬
‫‪7‬‬
‫‪0‬‬
‫نامحدود‬
‫‪1‬‬
‫حساس به متن‬
‫|‪|LHS|≤ |RHS‬‬
‫‪2‬‬
‫مستقل از متن‬
‫‪|LHS|= 1‬‬
‫‪3‬‬
‫منظم‬
‫‪αAβ → αγβ‬‬
‫‪ 2‬یا ‪|RHS|= 1‬‬
‫یا ‪A → a | aB,‬‬
‫‪A → a | Ba‬‬
‫عملیات روی زبان‌ها (‪)1‬‬
‫‪8‬‬
‫عمل‬
‫چه‌طور‬
‫بنویسیم؟‬
‫تعریف‬
‫اجتماع دو زبان‬
‫‪ L‬و‪M‬‬
‫‪LM‬‬
‫} ‪ M‬در ‪ s‬یا ‪ L‬در ‪L  M = { s | s‬‬
‫الحاق دو زبان ‪L‬‬
‫و‪M‬‬
‫‪LM‬‬
‫} ‪ M‬در ‪ t‬و ‪ L‬در ‪LM = { st | s‬‬
‫بستار کلین ‌زبان‬
‫‪L‬‬
‫بستار مثبت‬
‫زبان ‪L‬‬
‫*‪L‬‬
‫‬
‫∞ = *‪L‬‬
‫ =‬
‫(هیچ بار‪ ،‬یا بیش‌تر الحاق ‪)L‬‬
‫‪L+‬‬
‫‬
‫∞ = ‪L+‬‬
‫‬
‫=‬
‫(یک بار‪ ،‬یا بیش‌تر الحاق ‪)L‬‬
)2( ‫عملیات روی زبان‌ها‬
:‫ مثال‬o
LD
=
{ A, B, C, D, 1, 2, 3 }
LD
=
{ A1, A2, A3, B1, B2, B3, C1, C2, C3, D1, D2, D3 }
L2
=
{ AA, AB, AC, AD, BA, BB, BC, BD, CA, …, DD }
L4
=
L2L2
L*
=
} ε ‫ به همراه‬L ‫{ همه‌ی رشته‌های ممکن‬
L+
=
L*
= ?
- ε
L (L  D)
= ?
L
L (L  D)*
= ?
D =
=
{ A, B, C, D }
{ 1, 2, 3 }
9
‫زبان‌ها و عبارات منظم‬
‫‪ o‬یک عبارت منظم‪ ،‬مجموعه‌ای از قواعد یا روش‌هاست که برای ساختن‬
‫رشته‌هایی (توالی‌ای از نمادها) از یک الفبا مورد استفاده قرار می‌گیرد‬
‫‪ o‬اگر ‪ Σ‬یک الفبا‪ ،‬و ‪ r‬یک عبارت منظم باشد‪ L(r) ،‬زبانی است که با‬
‫قواعد ‪ r‬ساخته می‌شود‬
‫‪10‬‬
‫قواعدی برای تبیین عبارات منظم (‪)1‬‬
‫‪ o‬اگر ‪ Σ‬را الفبایی ثابت و مشخص در نظر بگیریم‪:‬‬
‫‪‬‬
‫‪ ε‬عبارت منظمی است که با } ‪ { ε‬مشخص می‌شود‬
‫‪‬‬
‫اگر ‪ a‬عضو ‪ Σ‬باشد‪ a ،‬عبارت منظمی است که با } ‪ { a‬نمایش داده می‌شود‬
‫‪‬‬
‫فرض کنید ‪ r‬و ‪ s‬به ترتیب عبارات منظمی با زبان‌های )‪ L(r‬و )‪ L(s‬باشد‪:‬‬
‫تقدم‬
‫‪.I‬‬
‫)‪ (r) | (s‬عبارت منظمی است با زبان )‪L(r)  L(s‬‬
‫‪.II‬‬
‫)‪ (r) (s‬عبارت منظمی است با زبان )‪L(r) L(s‬‬
‫‪ (r)* .III‬عبارت منظمی است با زبان *))‪(L(r‬‬
‫‪ r .IV‬عبارت منظمی است با زبان )‪L(r‬‬
‫‪‬‬
‫این عملگرها همه از چپ شرکت‌پذیری دارند‪ ،‬و پرانتزها با توجه به «تقدم» از بین‬
‫می‌روند‬
‫‪11‬‬
)2( ‫قواعدی برای تبیین عبارات منظم‬
:‫ مثال‬o
A|B|C|D
=
L
(A|B|C|D)(A|B|C|D)
=
L2
( A | B | C | D )*
=
L*
( A | B | C | D ) ( ( A | B | C | D) ( 1 , 2, 3 ) )
=
L (L  D)
L
=
D =
{ A, B, C, D }
{ 1, 2, 3 }
12
‫خواص جبری عبارات منظم‬
‫خاصیت‬
‫توضیح‬
‫‪r|s=s|r‬‬
‫| خاصیت جابه‌جایی دارد‬
‫| خاصیت شرکت‌پذیری دارد‬
‫‪r|(s|t)=(r|s)|t‬‬
‫)‪(rs)t=r(st‬‬
‫‪r(s|t)=rs|rt‬‬
‫‪(s|t)r=sr|tr‬‬
‫‪13‬‬
‫الحاق خاصیت جابه‌جایی دارد‬
‫الحاق روی | خاصیت پخش ی دارد‬
‫‪εr=r‬‬
‫‪rε=r‬‬
‫عنصر همانی در الحاق است‬
‫‌‬
‫‪ε‬‬
‫*)‪r*=(r|ε‬‬
‫ارتباط * و ‪ε‬‬
‫*‪r**=r‬‬
‫تعداد دفعات اعمال * تأثیری در نتیجه‬
‫ندارد‬
‫تشخیص نشانه‌ها (‪)1‬‬
‫‪ o‬چه‌طور می‌توانیم از آن‌چه تا اآلن یاد گرفته‌ایم برای توصیف الگ ‌وهای‬
‫نشانه‌ها استفاده کنیم؟‬
‫‪if‬‬
‫‪then‬‬
‫→ ‪then‬‬
‫‪else‬‬
‫→ ‪else‬‬
‫>< | = | => | > | =< | <‬
‫→ ‪relop‬‬
‫* ) ‪letter ( letter | digit‬‬
‫→ ‪id‬‬
‫? ) ‪digit + ( . digit + ) ? ( E ( + | - ) ? digit +‬‬
‫‪14‬‬
‫→ ‪if‬‬
‫→ ‪num‬‬
‫تشخیص نشانه‌ها (‪)2‬‬
‫عبارت منظم‬
‫نشانه‬
‫ویژگی‪-‬مقدار‬
‫‪ws‬‬
‫‪-‬‬
‫‪-‬‬
‫‪if‬‬
‫‪if‬‬
‫‪-‬‬
‫‪then‬‬
‫‪then‬‬
‫‪-‬‬
‫‪else‬‬
‫‪else‬‬
‫‪-‬‬
‫‪id‬‬
‫‪id‬‬
‫اشاره‌گری به یک سطر جدول‌‬
‫‪num‬‬
‫‪num‬‬
‫اشاره‌گری به یک سطر جدو ‌ل‬
‫>‬
‫‪relop‬‬
‫‪GT‬‬
‫=>‬
‫‪relop‬‬
‫‪GE‬‬
‫<‬
‫‪relop‬‬
‫‪LT‬‬
‫=<‬
‫‪relop‬‬
‫‪LE‬‬
‫=‬
‫‪relop‬‬
‫‪EQ‬‬
‫><‬
‫‪relop‬‬
‫‪NE‬‬
‫‪ o‬هر نشانه‪ ،‬شناسه‌ای یکتا دارد که رده‌ی ‪ lexeme‬را مشخص می‌کند‬
‫‪15‬‬
)1( ‫نمودارهای انتقال حالت‬
relop
‫شر ‌و‬
‫ع‬
0
<
1
‫ نمودار مربوط به تشخیص‬o
=
>
‫غیره‬
=
2
return (relop, LE)
3
return (relop, NE)
4
5
>
*
return (relop, LT)
return (relop, EQ)
=
6
‫غیره‬
7
8
return (relop, GE)
*
return (relop, GT)
16
‫نمودارهای انتقال حالت (‪)2‬‬
‫‪ o‬نمودار مربوط به تشخیص‬
‫))(‪return (getToken(), InstallID‬‬
‫*‬
‫‪ id‬و کلمات کلیدی‬
‫‪11‬‬
‫غیره‬
‫‪10‬‬
‫حرف یا رقم‬
‫‪17‬‬
‫حرف‬
‫‪9‬‬
‫نمودارهای انتقال حالت (‪)3‬‬
‫‪num‬ی‌عالمت)‬
‫(ب‬
‫‪ o‬نمودار مربوط به تشخیص‬
‫‪E‬‬
‫رقم‬
‫‪17‬‬
‫‪ +‬یا ‪-‬‬
‫‪16‬‬
‫‪E‬‬
‫‪15‬‬
‫رقم‬
‫رقم‬
‫‪14‬‬
‫‪.‬‬
‫‪13‬‬
‫رقم‬
‫‪18‬‬
‫غیره‬
‫*‬
‫‪18‬‬
‫‪19‬‬
‫غیره‬
‫رقم‬
‫*‬
‫‪21‬‬
‫غیره‬
‫*‬
‫‪20‬‬
‫رقم‬
‫‪12‬‬
‫نمودارهای انتقال حالت (‪)4‬‬
‫‪ o‬نمودار مربوط به تشخیص فضای خالی (‪)whitespace‬‬
‫*‬
‫‪24‬‬
‫غیره‬
‫‪23‬‬
‫جداکننده‬
‫‪19‬‬
‫جداکننده‬
‫‪22‬‬
‫ی‪LEX :‬‬
‫تولیدکننده‌ی تحلیلگر لغو ‌‬
‫‪lex.yy.c‬‬
‫برنامه‌ای‬
‫به زبان ‪C‬‬
‫کامپایلر‬
‫لغوی‬
‫(‪)LEX‬‬
‫‪a.out‬‬
‫برنامه‌ی قابل‬
‫اجرای‬
‫تحلیلگر لغوی‌‬
‫‪lex.1‬‬
‫برنامه‌ی‬
‫مبدأ ‪LEX‬‬
‫‪lex.yy.c‬‬
‫کامپایلر ‪C‬‬
‫برنامه‌ای‬
‫به زبان ‪C‬‬
‫‪a.out‬‬
‫توالی‌ای ‌از‬
‫نشانه‌ها‬
‫‪20‬‬
‫برنامه‌ی قابل‬
‫اجرای‬
‫تحلیلگر لغوی‌‬
‫جریان‬
‫ورودی‬
‫ی‬
‫خطاهای لغو ‌‬
‫‪ o‬بعض ی خطاها را تحلیلگر لغوی نمی‌تواند کشف کند؛ مثل‪:‬‬
‫) )‪fi ( a == f (x‬‬
‫‪ o‬اما بعض ی‌ها را می‌تواند؛ مثل‪:‬‬
‫; ‪d = 2r‬‬
‫‪ o‬خطاهایی مثل خطای اخیر زمانی کشف می‌شوند که هیچ الگویی بر توالی‬
‫موجود نویسه‌ها (در متن برنامه‌ی مبدأ) منطبق نباشد‬
‫‪21‬‬
‫اصالح خطا‬
‫‪ o‬حالت وحشت‪ :‬نویسه‌های متوالی تا رسیدن به یک نشانه‌ی معتبر‪ ،‬دور‬
‫انداخته می‌شوند‬
‫‪ o‬حذف یک نویسه از باقی‌مانده‌ی ورودی‬
‫‪ o‬درج نویسه‌ی مفقود (مورد نیاز) در باقی‌مانده‌ی ورودی‬
‫‪ o‬جای‌گزینی یک نویسه با نویسه‌ای دیگر‬
‫‪ o‬جابه‌جایی دو نویسه‌ی کنار هم‬
‫‪ o‬روش فاصله‌ی کمینه‬
‫‪22‬‬

similar documents