Document

Report
‫به نام خدا‬
‫‪6‬‬
‫طراحی‬
‫کامپایلرها‬
‫‪40-414‬‬
‫تحلیل نحوی پایین به باال‬
‫‪3‬‬
‫‪ o‬تحلیل نحوی «انتقال‪-‬کاهش»‬
‫‪ o‬کاهش یک رشته به نماد شروع گرامر‬
‫‪ o‬در هر گام یک زیررشته‌ی مشخص (از چپ به راست) با سمت راست یکی‬
‫از قاعده‌ها منطبق‪ ،‬و با سمت چپ همان قاعده جای‌گزین‬
‫می‌شود‬
‫‪abbcde‬‬
‫‪1‬‬
‫‪S → aABe‬‬
‫‪aAbcde‬‬
‫‪→ d‬‬
‫‪B‬‬
‫‪4‬‬
‫‪2‬‬
‫‪→ Abc|b‬‬
‫‪A‬‬
‫‪2-3‬‬
‫‪aAde‬‬
‫‪4‬‬
‫‪aABe‬‬
‫‪1‬‬
‫‪S‬‬
‫‪:)Rightmost‬‬
‫‪ o‬اشتقاق راست‌گرد (‬
‫‪1‬‬
‫‪abbcde‬‬
‫‪3‬‬
‫‪rm‬‬
‫‪aAbcde‬‬
‫‪2‬‬
‫‪rm‬‬
‫‪aAde‬‬
‫‪4‬‬
‫‪rm‬‬
‫‪aABe‬‬
‫‪1‬‬
‫‪rm‬‬
‫‪S‬‬
‫دستگیره‌ها (‪)1‬‬
‫‪ o‬دستگیره‌ی یک رشته‪ ،‬زیررشته‌ای از آن است که با سمت راست یکی از‬
‫قواعد انطباق دارد‪‌ ،‬و کاهش آن به سمت چپ قاعده‪ ،‬بخش ی از‬
‫معکوس یک انبساط راست‌ است‬
‫‪ o‬به شکل رسمی‌تر‪:‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫‪‬‬
‫ً‬
‫یک «عبارت» زیررشته‌ای از یک فرم جمله‌ای است که دقیقا از یک غیرپایانه مشتق شده‬
‫باشد‬
‫یک عبارت ساده عبارتی است که در یک گام ایجاد شده باشد‬
‫دستگیره‪ ،‬عبارت ساده‌ی است که در یک فرم جمله‌ای راست‌ ظاهر شود‬
‫ً‬
‫مثال ‪ A → β‬دستگیره‌ای برای ‪ α β x‬است (‪ x‬رشته‌ای از پایانه‌هاست) اگر‪:‬‬
‫‪αβx‬‬
‫‪‬‬
‫‪‬‬
‫‪2‬‬
‫‪αAx‬‬
‫‪rm‬‬
‫*‬
‫‪rm‬‬
‫‪S‬‬
‫یک فرم جمله‌ای می‌تواند دستگیره‌های متفاوتی داشته باشد‬
‫اما فرم جمله‌ای راست‌گرد یک گرامر نامبهم‪ ،‬یک دستگیره یکتا دارد (هرچند چندین‬
‫زیررشته ممکن است دستگیره به نظر آیند)‬
‫دستگیره‌ها (‪)2‬‬
‫‪ o‬مثال ‪:1‬‬
‫‪aAbcde‬‬
‫‪abbcde‬‬
‫‪rm‬‬
‫‪→ Abc|b‬‬
‫‪A‬‬
‫‪→ d‬‬
‫‪B‬‬
‫‪aAde‬‬
‫‪rm‬‬
‫‪ o‬به این ترتیب‪:‬‬
‫‪3‬‬
‫‪→ aABe‬‬
‫‪S‬‬
‫‪‬‬
‫‪ (S →) a A B e‬دستگیره‌ای برای ‪ a A B e‬است‬
‫‪‬‬
‫‪ (B →) d‬دستگیره‌ای برای ‪ a A d e‬است‬
‫‪‬‬
‫‪ (A →) A b c‬دستگیره‌ای برای ‪ a A b c d e‬است‬
‫‪‬‬
‫‪ (A →) b‬دستگیره‌ای برای ‪ a b b c d e‬است‬
‫‪aABe‬‬
‫‪rm‬‬
‫‪S‬‬
‫‪rm‬‬
‫دستگیره‌ها (‪)3‬‬
‫‪ o‬مثال ‪:2‬‬
‫‪→ aABe‬‬
‫‪S‬‬
‫‪→ Abc|b‬‬
‫‪A‬‬
‫‪→ d‬‬
‫‪B‬‬
‫‪ a A b c d e o‬را در نظر بگیرید (فرم جمله‌ای راست)‪ .‬آیا‬
‫]‪ [A → b, a A b c d e‬یک دستگیره است؟‬
‫‪‬‬
‫اگر چنین باشد باید داشته باشیم‪:‬‬
‫‪aAAbcde‬‬
‫‪aAbcde‬‬
‫‪rm‬‬
‫‪‬‬
‫‪rm‬‬
‫اما به هیچ‌وجه امکان ندارد در هیچ مرحله‌ای به دو ‪ A‬متوالی برسیم‪ .‬بنابراین پاسخ‬
‫سوال باال منفی است‪.‬‬
‫‪4‬‬
‫…‬
‫‪rm‬‬
‫‪S‬‬
‫دستگیره‌ها (‪)4‬‬
‫‪ o‬مثال ‪:3‬‬
‫‪→ aABe‬‬
‫‪S‬‬
‫‪→ Abc|b‬‬
‫‪A‬‬
‫‪→ d‬‬
‫‪B‬‬
‫‪ a A b c d e o‬را در نظر بگیرید (فرم جمله‌ای راست‌گرد)‪ .‬آیا‬
‫]‪ [B → d, a A b c d e‬یک دستگیره است؟‬
‫‪‬‬
‫اگر چنین باشد باید داشته باشیم‪:‬‬
‫‪aAbcBe‬‬
‫‪aAbcde‬‬
‫‪rm‬‬
‫‪‬‬
‫‪5‬‬
‫‪rm‬‬
‫پس می‌خواهیم ‪ a A b c B e‬را به دست آوریم‪:‬‬
‫‪aAbcBe‬‬
‫‪‬‬
‫…‬
‫‪rm‬‬
‫‪S‬‬
‫اما این یک فرم جمله‌ای راست‌گرد نیست‪.‬‬
‫?‬
‫‪S‬‬
‫‪aABe‬‬
‫‪rm‬‬
‫تحلیل نحوی انتقال‪-‬کاهش با انباره (‪)1‬‬
‫‪ o‬چالش اصلی‪ :‬یافتن دستگیره در یک فرم جمله‌ای داده‌شده‬
‫‪ o‬ایده‌ی کلی تحلیل نحوی انتقال‪-‬کاهش به کمک انباره‪:‬‬
‫‪‬‬
‫(‪ )1‬در «انتقال»‪ ،‬نشانه‌های ورودی روی انباره قرار می‌گیرند‪ ،‬تا زمانی که یک دستگیره‬
‫روی انباره یافت شود‬
‫‪‬‬
‫(‪ )2‬در «کاهش»‪ ،‬دستگیره با غیرپایانه‌ی مربوط جای‌گزین می‌شود‬
‫‪‬‬
‫(‪ )3‬پذیرش ورودی زمانی میسر خواهد بود که نشانه‌های ورودی تمام شوند‪ ،‬و تنها نماد‬
‫شروع گرامر در انباره باقی مانده باشد‬
‫‪‬‬
‫(‪ )4‬در صورت بروز خطا‪ ،‬مدیر خطا فراخوانی می‌شود‬
‫‪ ‬پیشوند معتبر (‪ :)Viable Prefix‬پیشوندی از یک فرم جمله‌ای راست‌‬
‫است که روی انباره‌ی یک تحلیلگر نحوی انتقال‪-‬کاهش ظاهر می‌شود‬
‫‪6‬‬
‫تحلیل نحوی انتقال‪-‬کاهش با انباره (‪)2‬‬
‫‪ o‬اگر گرامر مبهم باشد چه؟‬
‫ً‬
‫‪ o‬مثال در‪:‬‬
‫‪→ E+E‬‬
‫‪E*E‬‬
‫|‬
‫)‪(E‬‬
‫|‬
‫‪id‬‬
‫|‬
‫‪E‬‬
‫‪ o‬رشته‌ی ‪ id + id * id‬از طریق دو انبساط راست متفاوت می‌تواند به‬
‫دست آید‬
‫‪7‬‬
‫تحلیل نحوی انتقال‪-‬کاهش با انباره (‪)3‬‬
‫‪ o‬مثال‪:‬‬
‫‪→ E+E‬‬
‫‪E‬‬
‫ورودی‬
‫مالحظات‬
‫انتقال‬
‫‪E*E‬‬
‫|‬
‫)‪(E‬‬
‫|‬
‫انتقال‬
‫‪id‬‬
‫|‬
‫انتقال‬
‫‪id + id * id $‬‬
‫‪$‬‬
‫کاهش ‌از طریق ‪E → id‬‬
‫‪+ id * id $‬‬
‫‪$ id‬‬
‫‪+ id * id $‬‬
‫‪$E‬‬
‫‪id * id $‬‬
‫کاهش ‌از طریق ‪E → id‬‬
‫‪* id $‬‬
‫هم کاهش از طریق ‪ E → E + E‬و هم‬
‫انتقال می‌تواند رخ دهد‪ .‬بنابراین‬
‫می‌گوییم «تداخل انتقال‪-‬کاهش»‬
‫اتفاق افتاده است‪.‬‬
‫‪8‬‬
‫انباره‬
‫‪$E+‬‬
‫‪$ E + id‬‬
‫‪$E+E‬‬
‫تداخل‌ها (‪)1‬‬
‫‪ o‬تداخل‌ها (که در صورت مبهم‌بودن گرامر رخ می‌دهند) یا از نوع «انتقال‪-‬‬
‫کاهش» اند یا از نوع «کاهش‪-‬کاهش»‬
‫‪ o‬مثال دیگری از تداخل انتقال‪-‬کاهش‪:‬‬
‫‪if expr then stmt‬‬
‫‪if expr then stmt else stmt‬‬
‫|‬
‫‪other‬‬
‫|‬
‫مالحظات‬
‫تداخل انتقال‪-‬کاهش‬
‫‪9‬‬
‫→‬
‫ورودی‬
‫… ‪else‬‬
‫‪stmt‬‬
‫انباره‬
‫‪if … then‬‬
‫تداخل‌ها (‪)2‬‬
‫‪ o‬مثالی از تداخل کاهش‪-‬کاهش‪:‬‬
‫‪‬‬
‫‪→ id ( parameter-list ) | expr := expr‬‬
‫‪stmt‬‬
‫‪→ parameter-list, parameter | parameter‬‬
‫‪parameter-list‬‬
‫‪→ id‬‬
‫‪parameter‬‬
‫‪→ expr-list, expr | expr‬‬
‫‪expr-list‬‬
‫) ‪→ id | id ( expr-list‬‬
‫‪expr‬‬
‫متناظر آن )‪ id(id,id‬خواهد‬
‫‌‬
‫رشته‌ی ورودی )‪ A(I,J‬را در نظر بگیرید‪ .‬رشته‌ی نشانه‌های‬
‫بود‪.‬‬
‫‪‬‬
‫بعد از ‪ 3‬بار انتقال‪ ،‬ورودی و انباره به صورت زیر در خواهند آمد‪:‬‬
‫ورودی‬
‫‪‬‬
‫‪10‬‬
‫)‬
‫‪id‬‬
‫‪,‬‬
‫‪id‬‬
‫(‬
‫‪id‬‬
‫انباره‬
‫تداخل کاهش‪-‬کاهش‪ :‬از کدام قاعده (پنجم یا هفتم) باید استفاده کنیم؟ (در واقع‬
‫انتخاب درست وابسته است به این که ‪ A‬یک آرایه است یا یک تابع)‬
‫تداخل‌ها (‪)3‬‬
‫‪ o‬حذف تداخل‌ها‬
‫‪ o‬یک راه حل‪ ،‬تغییر گرامر است‬
‫•‬
‫مشابه کاری که در روی‌کرد تحلیل نحوی باال به پایین‪ ،‬برای تبدیل یک گرامر به )‪ LL(1‬انجام‬
‫دادیم‬
‫‪ o‬در غیر این صورت‪ ،‬همانطور که بعدا خواهیم دید‪ ،‬با این تداخل‌ها‪ ،‬پس از شناسایی‬
‫آن‌ها‪ ،‬بهتر می‌توان برخورد کرد‬
‫•‬
‫‪11‬‬
‫حتی ممکن است سبب شود تحلیلگر نحوی کاراتری‌ به دست آید‬
‫تحلیل نحوی تقدم عملگر ( ‪Operator‬‬
‫‪)Precedence‬‬
‫‪ o‬مشکالتی که تا این‌جا به آن‌ها برخوردیم‪:‬‬
‫‪‬‬
‫مشخص‌کردن دستگیره‌ها‬
‫‪‬‬
‫حذف تداخل‌ها (در صورت وجود)‬
‫‪‬‬
‫گرامرهای عملگر‪ :‬دسته‌ای از گرامرها که مشخص‌کردن دستگیره‌ها و مواجهه با تداخل‌ها‬
‫در آن‌ها ساده است‬
‫‪ o‬گرامرهای عملگر‪ :‬سمت راست هیچ‌یک از قواعد ‪ ε‬نیست و دو‬
‫ً‬
‫مثال‪:‬‬
‫غیرپایانه‌ی پشت سر هم ندارد؛ ‌‬
‫‪‬‬
‫‪12‬‬
‫‪→ E - E | E + E | E * E | E / E | E ^ E | - E | ( E ) | id‬‬
‫ً‬
‫این گرامرها معموال مبهم‌اند‪.‬‬
‫‪E‬‬
‫تحلیل نحوی تقدم عملگر (‪)2‬‬
‫‪ o‬ایده‌ی اولیه‪ :‬بین هر دو پایانه‌ی گرامر‪ ،‬رابطه‌هایی به شکل ‪ <.‬و >‪ .‬و ‪.=.‬‬
‫تعریف می‌کنیم‬
‫‪‬‬
‫‪ a <. b‬به این معنی است که ‪ a‬از ‪ b‬تقدم کم‌تری‌ دارد‬
‫‪‬‬
‫برابر است‬
‫‪ a .=. b‬به این معنی است که تقدم ‪ a‬با ‪‌ b‬‬
‫‪‬‬
‫‪ a .> b‬به این معنی است که ‪ a‬از ‪ b‬تقدم بیش‌تری‌ دارد‬
‫•‬
‫ً‬
‫مثال فرض کنید که تعریف کنیم ‪ * .> +‬یا به طور مشابه * ‪+ <.‬‬
‫‪ o‬در هر مرحله از تحلیل نحوی به این روش‪ ،‬دستگیره‌های مختلفی ممکن‬
‫است وجود داشته باشند‪ .‬برای یافتن دستگیره‌ی صحیح‪ ،‬از روابط ‪ <.‬و‬
‫>‪ .‬و ‪ .=.‬استفاده می‌کنیم (دستگیره‌ای را انتخاب می‌کنیم که این روابط‬
‫را رعایت کند)‬
‫‪13‬‬
‫تحلیل نحوی تقدم عملگر (‪)3‬‬
‫‪ o‬چه‌طور‌ از روابط گفته‌شده استفاده می‌کنیم؟‬
‫‪ o‬هدف‪ ،‬مشخص‌کردن و جداسازی دستگیره‌ی یک فرم جمله‌ای راست‌‬
‫است‬
‫‪‬‬
‫‪ <.‬ابتدا‪ ،‬و >‪ .‬انتهای دستگیره را مشخص می‌کند و ‪ .=.‬در میان این دو ظاهر می شود‬
‫‪ o‬از آن‌جا که در سمت راست هیچ‌یک از قواعد‪ ،‬دو غیرپایانه‌ی پشت سر‬
‫هم وجود ندارد‪ ،‬شکل کلی فرم جمله‌ای به این صورت خواهد بود‪:‬‬
‫‌اند‪β0 a1 β1 )aε2(β‬‬
‫که در آن ‪ βi‬ها غیرپایانه‪ ،‬یا رشته ‪βn‬‬
‫‌های‪an‬تهی‬
‫…‪2‬‬
‫‪14‬‬
‫تحلیل نحوی تقدم عملگر (‪)4‬‬
‫‪ o‬در هر مرحله از تحلیل نحوی‪ ،‬تحلیلگر‪ a ،‬یعنی باالترین پایانه‌ی روی‬
‫انباره (باالترین عنصر‪ ،‬یا یکی مانده به باالترین عنصر) و ‪ b‬یعنی‬
‫نشانه‌ی جاری را در نظر می‌گیرد‪:‬‬
‫‪‬‬
‫اگر ‪ ،a .=. b‬آن‌گاه ‪ b‬را به انباره‌ انتقال می‌دهد‬
‫‪‬‬
‫اگر ‪ ،a <. b‬آن‌گاه ابتدا ‪ <.‬را روی انباره قرار می‌دهد‪ ،‬و سپس ‪ b‬را به انباره منتقل‬
‫می‌کند‬
‫‪‬‬
‫اگر ‪ ،a >. b‬آن‌گاه باالترین ‪ <.‬را در انباره می‌یابد و عناصر بین آن (عالمت اخیر)‪ ،‬و‬
‫باالترین عنصر انباره را (به همراه غیرپایانه‌ی زیر ‪ <.‬در صورت وجود) به عنوان دستگیره‬
‫در نظر می‌گیرد‪ ،‬و آن‌ها را از روی انباره برمی‌دارد‪ .‬سپس یک غیرپایانه نوعی (مثال ع ‌المت‬
‫شروع گرامر) را روی انباره قرار می‌دهد‬
‫‪‬‬
‫‪15‬‬
‫دستگیره حذف شده بایستی با سمت راست یکی از قواعد به صورت ضعیف تطبیق کند‬
‫(یعنی کافیست که پایانه ها و فقط محل غیرپایانه ها تطبیق کند)‬
)5( ‫تحلیل نحوی تقدم عملگر‬
‫انباره‬
$
‫ورودی‬
‫مالحظات‬
:‫ مثال‬o
id + id * id $
$ <. id
$ <. id
+ id * id $
id .> +
$E
+ id * id $
$ <. +
1-2
E
→ E+T|T
id * id $
+ <. id
3-4
T
→ T*F|F
$ E <. + <. id
* id $
id .> *
$ E <. + E
* id $
+ <. *
5-6
F
→ ( E ) | id
id $
* <. id
$ E <. + E <. * <. id
$
id .> $
$ E <. + E <. * E
$
* .> $
$ E <. + E
$
+ .> $
$E
$
‫پذیرش‬
$ E <. +
$ E <. + E <. *
‫جدول تحلیل‬
+
*
(
)
id
$
+
.>
<.
<.
.>
<.
.>
*
.>
.>
<.
.>
<.
.>
(
<.
<.
<.
.=.
<.
)
.>
.>
.>
.>
id
.>
.>
.>
.>
$
<.
<.
<.
<.
.=.
16
)6( ‫تحلیل نحوی تقدم عملگر‬
‫ ساخت جدول تحلیل‬o
FirstTerm(A)
=
{ a | A + a α ‫ یا‬A + B a α }
LastTerm(A)
=
{ a | A + α a ‫ یا‬A + α a B }
a .=. b   U → α a b β   U → α a B b β
a <. b   U → α a B β  b  FirstTerm(B)
a .> b   U → α B b β  a  LastTerm(B)
17
)7( ‫تحلیل نحوی تقدم عملگر‬
‫ مثال‬o
FirstTerm(E)
=
{ +, *, id, ( }
FirstTerm(T)
=
{ *, id, ( }
FirstTerm(F)
=
{ id, ( }
LastTerm(E)
=
{ +, *, id, ) }
LastTerm(T)
=
{ *, id, ) }
LastTerm(F)
=
{ id, ) }
1-2
E
→ E+T|T
3-4
T
→ T*F|F
5-6
F
→ ( E ) | id
18
‫تحلیل نحوی تقدم عملگر (‪)8‬‬
‫‪ o‬توابع تقدم در مقابل رابطه‌ها‬
‫‪19‬‬
‫‪‬‬
‫هرگاه ‪ ،a <. b‬آن‌گاه )‪f(a) < g(b‬‬
‫‪‬‬
‫هرگاه ‪ ،a .=. b‬آن‌گاه )‪f(a) = g(b‬‬
‫‪‬‬
‫هرگاه ‪ ،a .> b‬آن‌گاه )‪f(a) > g(b‬‬
‫‪$‬‬
‫‪id‬‬
‫)‬
‫(‬
‫‪‬‬
‫‪/‬‬
‫*‬
‫‪-‬‬
‫‪+‬‬
‫‪0‬‬
‫‪6‬‬
‫‪6‬‬
‫‪0‬‬
‫‪4‬‬
‫‪4‬‬
‫‪4‬‬
‫‪2‬‬
‫‪2‬‬
‫‪f‬‬
‫‪0‬‬
‫‪5‬‬
‫‪0‬‬
‫‪5‬‬
‫‪5‬‬
‫‪3‬‬
‫‪3‬‬
‫‪1‬‬
‫‪1‬‬
‫‪g‬‬
‫تحلیل نحوی تقدم عملگر (‪)9‬‬
‫‪ o‬ساخت توابع تقدم‬
‫‪20‬‬
‫‪f id‬‬
‫‪g id‬‬
‫*‪g‬‬
‫*‪f‬‬
‫‪f+‬‬
‫‪g+‬‬
‫‪g$‬‬
‫‪f$‬‬
‫‪$‬‬
‫‪id‬‬
‫*‬
‫‪+‬‬
‫‪0‬‬
‫‪4‬‬
‫‪4‬‬
‫‪2‬‬
‫‪f‬‬
‫‪0‬‬
‫‪5‬‬
‫‪3‬‬
‫‪1‬‬
‫‪g‬‬
‫تحلیل نحوی تقدم عملگر (‪)10‬‬
‫‪ o‬مدیریت خطا در حین کاهش‬
‫‪‬‬
‫فرض کنید ‪ a b E c‬از روی انباره برداشته شده‪ ،‬اما سمت راست هیچ قاعده‌ای با آن‬
‫َ‬
‫نمی‌خواند‬
‫•‬
‫اگر سمت راست قاعده‌ای ‪ a E c‬بود‪ ،‬باید پیامی به این مضمون نمایش دهیم‪« :‬وجود ‪ b‬در‬
‫خط ‪ x‬غیرمجاز است»‬
‫•‬
‫اگر سمت راست قاعده‌ای ‪ a b E d c‬بود‪ ،‬باید پیامی به این مضمون نمایش دهیم‪ d« :‬در‬
‫خط ‪ x‬پیدا نشد»‬
‫•‬
‫اگر سمت راست قاعده‌ای ‪ a b c‬بود‪ ،‬باید پیامی به این مضمون نمایش دهیم‪« :‬وجود ‪ E‬در‬
‫خط ‪ x‬غیرمجاز است» (که ‪ّ E‬‬
‫معرف یک مفهوم در نحو زبان است که آن را با غیرپایانه‌ی ‪E‬‬
‫نشان می‌دهیم)‬
‫‪21‬‬
‫تحلیل نحوی تقدم عملگر (‪)11‬‬
‫‪ o‬مدیریت خطاهای انتقال‪-‬کاهش‬
‫‪‬‬
‫‪e1‬‬
‫•‬
‫•‬
‫•‬
‫‪‬‬
‫‪e2‬‬
‫•‬
‫•‬
‫•‬
‫‪‬‬
‫زمانی که ‪ id‬یا پرانتز باز‪ ،‬بعد از ‪ id‬یا پرانتز بسته بیاید‬
‫‪ +‬را به ورودی اضافه می‌کنیم‬
‫عملگر پیدا نشد» را نمایش می‌دهیم‬
‫‌‬
‫پیام «‬
‫‪e4‬‬
‫•‬
‫•‬
‫•‬
‫‪22‬‬
‫زمانی که عبارت با پرانتز بسته آغاز می‌شود‬
‫پرانتز بسته را از ورودی حذف می‌کنیم‬
‫پیام «یک پرانتز بسته اضافی دیده شد» را نمایش می‌دهیم‬
‫‪e3‬‬
‫•‬
‫•‬
‫•‬
‫‪‬‬
‫زمانی که کل عبارت پیدا نشده است‬
‫‪ id‬را به ورودی اضافه می‌کنیم‬
‫پیام «عملوند پیدا نشد» را نمایش می‌دهیم‬
‫زمانی که عبارت با پرانتز باز پایان می‌یابد‬
‫پرانتز باز را از روی انباره برمی‌داریم‬
‫عبارت «پرانتز بسته پیدا نشد» را نمایش می‌دهیم‬
‫‪$‬‬
‫)‬
‫>‪.‬‬
‫(‬
‫‪id‬‬
‫>‪.‬‬
‫‪e3 e3‬‬
‫‪id‬‬
‫‪.=. e4‬‬
‫‪<.‬‬
‫(‬
‫>‪.‬‬
‫‪e3 e3‬‬
‫)‬
‫‪e2 e1‬‬
‫‪<.‬‬
‫‪$‬‬
‫>‪.‬‬
‫‪<.‬‬
‫‪<.‬‬
‫تحلیل نحوی تقدم عملگر (‪)12‬‬
‫‪ o‬استخراج رابطه‌های تقدم از جدول تحلیل‬
‫‪E‬‬
‫*‬
‫‪<.‬‬
‫‪+‬‬
‫‪F‬‬
‫‪id‬‬
‫‪23‬‬
‫‪<.‬‬
‫‪id‬‬
‫*‬
‫‪→ E+T|T‬‬
‫‪E‬‬
‫‪1-2‬‬
‫‪→ T*F|F‬‬
‫‪T‬‬
‫‪3-4‬‬
‫‪→ ( E ) | id‬‬
‫‪F‬‬
‫‪5-6‬‬
‫‪T‬‬
‫‪+‬‬
‫*‬
‫‪T‬‬
‫‪E‬‬
‫تحلیل نحوی تقدم عملگر (‪)13‬‬
‫‪ o‬استخراج رابطه‌های تقدم از جدول تحلیل‬
‫‪E‬‬
‫‪T‬‬
‫‪F‬‬
‫*‬
‫‪24‬‬
‫‪→ E+T|T‬‬
‫‪E‬‬
‫‪1-2‬‬
‫‪→ T*F|F‬‬
‫‪T‬‬
‫‪3-4‬‬
‫‪→ ( E ) | id‬‬
‫‪F‬‬
‫‪5-6‬‬
‫>‪.‬‬
‫‪T‬‬
‫*‬
‫*‬
‫‪F‬‬
‫*‬
‫‪T‬‬
‫‪F‬‬
‫*‬
‫>‪.‬‬
‫‪id‬‬
‫‪id‬‬
‫تحلیل نحوی تقدم عملگر (‪)14‬‬
‫‪ o‬مزایا و کاستی‌ها‬
‫‪ +‬پیاده‌سازی آسان‬
‫‪ +‬جدول تحلیل کوچک‬
‫ قدرت بیان ضعیف (به این دلیل که دو غیرپایانه‌ی پشت سر هم را مجاز‬‫نمی‌داند)‬
‫ دقت نه چندان خوب (بعض ی از خطاهای نحوی به خاطر محدودیت روی‬‫غیرپایانه‌ها)‬
‫‪ o‬روش «عملگر ساده» شکلی از روش «تقدم عملگر» است که این‬
‫کاستی‌ها را ندارد‬
‫‪25‬‬

similar documents