بخشی از پاورپوینت
اسلاید 1 :
گرامرها و ماشینهای متناهی
فصل دوم
اسلاید 2 :
با توجه به استفاده از مفاهیمی چون گرامر، زبان و ماشینهای متناهی در فصلهای بعد، در این فصل آنها را مرور خواهیم کرد.
در این فصل گرامرهای مبهم تشریح شده و مفهوم درختهای اشتقاق بیان می شود.
ماشینهای متناهی یکی از ابزارهای طراحی و پیاده سازی تحلیلگر لغوی هستند.
ماشینهای متناهی ابزار پذیرش زبانهای منظم هستند.
با طراحی ماشین متناهی برای یک زبان، می توان از الگوریتمهای موجود برای تولید گرامر منظم، عبارت منظم و . استفاده کرد.
2-1 - چکیده
اسلاید 3 :
الفبا؛ مجموعه ای از نمادهاست که با ∑ نمایش داده میشود.
بطور مثال؛ = { a , b} ∑
رشته؛ با کنار هم قرار دادن یک سری از کاراکترهای مجزا، رشته ها ساخته میشوند.
بطور مثال؛ طبق الفبای تعریف شده در بالا،
W = aaaabba , V= aabbba
V و W رشته هایی روی الفبای ∑ هستند .
رشته تهی؛ رشته ای است که شامل هیچ نمادی نباشد و با علامت λ نشان داده میشود. | λ| = 0 , λW = W λ = W
2-2 - زبان
اسلاید 4 :
2-2 – تعریف *∑ و +∑ ( ادامه زبان )
اسلاید 5 :
تعریف زبان ؛
هر مجموعه ای از رشته ها روی ∑ میتواند یک زبان در نظر گرفته شود.
بطور مثال؛ مجموعه ی L1 = { a , aa , aab } یک زبان بر روی ∑ تعریف شده در مثال قبل است.
از آنجایی که تعداد جملات آن متناهی است به آن زبان متناهی میگوییم.
و اگر تعداد جملات زبانی متناهی نباشد به آن زبان نامتناهی می گویند.
L2 = { anbn | n>=0} L3 = { 0n1m | n>=0 , m>=0 }
اسلاید 6 :
اغلب زبانهای مورد استفاد متناهی هستند .
یک زبان، زیر مجموعه ای از *∑ است.
اسلاید 7 :
2-3 – گرامر
گرامرها ابزار توصیف ساختار جمله ها و رشته های یک زبان می باشند.
هر گرامر با چهارتاییG = ( S , Σ , V , R ) تعریف می شود.
علامت شروع گرامر ( ممکن است جزو غیر پایانه ها باشد)
پایانه ها ( اعضای الفبای زبان)
غیرپایانه ها
قواعد تولید
اسلاید 8 :
2-3 – گرامر
قرار داد :
غیرپایانه ها را با حروف الفبای بزرگ نمایش میدهیم و هر چیزی غیر از پایانه محسوب می شود ( حروف الفبای کوچک و اعداد).
مثال: G1 :
S A
A 0A1
A 01
الفبای شروع
غیر پایانه
NonTerminal
پایانه ها
Terminals
مثال: S aSb | λ
با استفاده از قوانین تولید می توان بررسی کرد چه رشته هایی عضو زبان است.
اسلاید 9 :
2-3 – گرامر ( ادامه )
گرامر G1 را در نظر بگیرید؛ آیا رشته 000111 توسط این گرامر تولید میشود ؛
G1 :
S A
A 0A1| 01
S A 0A1 00A11 000111
زبان گرامر G1 ،
L(G1) = {0n1n | n>=1}
اسلاید 10 :
2-4 - اشتقاق (Derivation)
عملیات انجام شده به ترتیب بر اساس قواعد تولید را اشتقاق می گویند.
بطور مثال بر اساس گرامر G1 مثال قبل ؛
S → A → 01
اگر نتوان برای رشته ای اشتقاق نوشت می توان گفت آن رشته جزو زبان گرامر نیست.
اسلاید 11 :
2-4 – اشتقاق (ادامه)
کدامیک از رشته ای زیر عضو زبان L(G2) می باشد
زبان گرامر G2 را بنویسید.
G2 :
S A
A 0A| 0 | 1B
B 1B| 1
زبان گرامر G2 ،
L(G2) = {0n1m | m>=2 ˅ (m=0 ˄ n>=1}
اسلاید 12 :
2-5 – طبقه بندی گرامرها
هرچه شکل قواعد پیچیده تر باشد، نوع زبان نیز پیچیده تر می شود.
بر اساس دسته بندی چامسکی، زبانها به چهار دسته تقسیم می شوند.
اسلاید 13 :
2-5 – طبقه بندی گرامرها (ادامه)
زبانهای نوع 3 یا منظم (regular)
زبانهای نوع 2 یا مستقل از متن (context free)
زبانهای نوع 1 یا وابسته به متن (context sensetive)
زبانهای نوع صفر یا بدون محدودیت (Unrestricted)
اسلاید 14 :
2-5-1 – گرامرخطی
گرامر خطی گرامری است که در آن حداکثر یک غیرپایانه در سمت راست قواعد میتواند یافت شود.
بطور مثال ؛
A aaaaBbc
A aabBacaa
A Bbcaaaab
A aaabbbbaB
خطی از چپ
خطی از راست
به گرامری که غیر پایانه آخرین حرف باشد، گرامر خطی راست و
اگر غیرپایانه اولین حرف باشد، خطی از چپ می گویند.
اسلاید 15 :
2-5-2 – گرامرهای منظم
گرامر منظم گرامری است که قواعد آن به فرم خطی از چپ یا خطی از راست باشد.
فرم قواعد گرامر خطی از راست :
فرم قواعد گرامر خطی از چپ :
اسلاید 16 :
2-5-2 – گرامرهای منظم ( ادامه )
به عنوان مثال گرامر زیر یک گرامر منظم خطی از راست است:
اما گرامرهای زیر منظم نیستند:
خطی است
ولی منظم نیست
اسلاید 17 :
2-5-2 – گرامرهای منظم ( ادامه )
به عنوان مثال؛
گرامر فوق یک گرامر منظم (خطی از راست ) است و زبان a+b* را تولید می کند
اسلاید 18 :
گرامرهای مستقل از متن
2-5-3 – گرامرهای مستقل از متن
گرامر مستقل از متن گرامری است که قواعد آن به فرم زیر باشد:
Aα , AεV, αε(Σ+V)*
با استفاده از این نوع گرامرها، زبانهای پیچیده تری را می توان تعریف کرد.
گرامر زیر یک گرامر مستقل از متن است:
اسلاید 19 :
2-5-3 – گرامرهای مستقل از متن
گرامرهای مستقل از متن
S aSbS | bSaS | λ
این گرامر زبان مستقل از متنی را تولید می کند که در آن تمامی رشته ها دارای تعداد یکسانی a و b هستند.
توجه کنید که زبانهای منظم زیرمجموعه زبانهای مستقل از متن اند.
هر زبان متناهی منظم (و در نتیجه) مستقل از متن است.
اسلاید 20 :
2-5-3 – گرامرهای مستقل از متن
گرامرهای مستقل از متن
توجه کنید که هر زبان متناهی (محدود) حتماً منظم است:
