Payamvdn/NorthPersian_fa_wiki huggingface dataset:
اتوماتای سنگ ریزه (به انگلیسی: pebble automaton)، یک درخت را به عنوان ورودی می گیرد و روی گره های درخت از طریق یال ها حرکت می کند. به علاوه، این اتوماتا یک مجموعه ی متناهی با اندازه ی ثابت از «سنگ ریزه ها» دارد که از 1 تا k شماره گذاری شده اند و می تواند آن ها را روی گره های درخت بگذارد. در یک گام اتوماتا می تواند روی گره فعلی بماند، به گره پدر برود، به گره فرزند چپ یا راست برود. همین طور می تواند سنگ ریزه ی iم را بردارد، یا سنگ ریزه ی i-1م را رو گره فعلی قرار دهد. این که در هر گام اتوماتا چه تصمیمی می گیرد، بستگی به حالت فعلی اتوماتا، مجموعه ی سنگ ریزه هایی که روی گره فعلی قرار دارد، برچسب گره فعلی، و نوع گره فعلی (ریشه، فرزند چپ یا راست، برگ یا گره داخلی) دارد. تعریف دقیق. مجموعه ی {TYPE = {r, 0, 1} × {l, i، انواع ممکن برای یک گره را دربردارد. در این جا r برای ریشه، 0 فرزند برای فرزند چپ، 1 برای فرزند راست، l برای برگ، و i برای گره درونی در نظر گرفته شده است. مجموعه ی {MOVES = {ε, ←, →, ↑, lift, drop، انواع حرکت های ممکن را برای اتوماتا دربرمی گیرد. در این جا ↑ برای رفتن به گره پدر، ← برای رفتن به فرزند چپ،
→ برای رفتن به فرزند راست، drop برای گذاشتن سنگ ریزه، و lift برای برداشتن سنگ ریزه در نظر گرفته شده است. همین طور مجموعه ی توانی یک مجموعه مانند S را با (P(S نشان می دهیم. یک اتوماتای سنگ ریزه که k سنگ ریزه دارد، یک چندتاییِ (A = (Σ,Q, I, F, δ است، که Q مجموعه ای متناهی از حالت هاست، I ⊆ Q مجموعه ی حالات اولیه، F ⊆ Q مجموعه ی حالات پایانی، و δ رابطه ی گذر (به انگلیسی: transition relation) است. (δ ⊆ (Q × TYPES × {1, . . . , k + 1} × P({1, · · · , k}) × Σ) × (Q × MOVES چندتاییِ q, β, i, S, σ, q′,m) ∈ δ) بیان می کند که اگر A در حالت q باشد، سنگ ریزه های i تا k در درخت باشند، مجموعه ی S سنگ ریزه های گره فعلی را دربرداشته باشد، گره از نوع β باشد و برچسب σ داشته باشد، آن گاه A به حالت ′q می رود و باتوجه به m حرکت می کند. انواع. اتوماتای سنگ ریزه بسته به نحوه ی برداشتن سنگ ریزه ها، در دو نوع بررسی می شود: به صورت پیش فرض اتوماتا قوی در نظر گرفته می شود. قطعیت و عدم قطعیت. یک اتوماتای سنگ ریزه است، اگر δ یک (به انگلیسی: partial function) از Q × types × {1, · · · , k + 1} × P({1, · · · , k}) × Σ به Q × moves باشد. نم
ادگذاری. مجموعه ی زبان های تشخیص پذیر توسط اتوماتای سنگ ریزه ی قطعیِ قوی با n سنگ ریزه با sDPAn نشان داده می شود. همین طور مجموعه ی زبان های تشخیص پذیر توسط اتوماتای (به انگلیسی: tree walking automaton) با TWA و مجموعه ی زبان های تشخیص پذیر توسط اتوماتای (به انگلیسی: bottom-up tree automaton) با REG نشان داده می شود. یک نتیجه در منطق. اگر formula_9، مجموعه ی ویژگی های قابل توصیف درخت در (به انگلیسی: transitive closure first-order logic) باشد، و formula_10همان مجموعه در باشد، ثابت می شود که formula_11، و در واقع formula_12. یعنی مجموعه ی زبان های تشخیص پذیر توسط اتوماتای سنگ ریزه با مجموعه ی زبان‎های قابل توصیف در برابر است.
اتوماتون بوچی (زبان انگلیسی: Büchi automaton) را می توان به عنوان اتوماتونی در نظر گرفت که می توانند رشته های نامتناهی الفبا را بپذیرد. این اتوماتون اولین بار توسط ژولیوس ریچارد بوچی () منطق دان سوئیسی در سال ۱۹۶۲ معرفی شد. اگر ω را به عنوان مجموعه اعداد طبیعی و Σ رابه عنوان الفبا در نظر بگیریم یک کلمه نامتناهی (یا یک ω-کلمه) را می توان به عنوان یک تابع از ω به Σ در نظر گرفت به این ترتیب مجموعه تمام کلمه های نامتناهی را باformula_1 نشان می دهیم. تعریف. یک اتوماتون بوچی قطعی ۵ تایی formula_2 است که در ان: فرض کنید formula_2 یک اتوماتون بوچی متناهی باشد در این صورت یک تعمیم طبیعی از مفهوم اجرا (نسبت به اتوماتون قطعی متناهی) می تواند مطرح شود که به این صورت است که یک اجرا روی یک کلمه نامتناهی formula_7 را به صورت دنبالهٔ formula_8 تعریف می کنیم که از s شروع می کنیم و با formula_9 به formula_10 و سپس با formula_11 به formula_12 و… می رویم. به عنوان مثال در این اتوماتون: اگر formula_13 در اینصورت formula_14 یه اجرای A است. در این صورت می گوییم ماشین A رشته σ را قبول می کند اگر اجرایی وجود داشته باشد که در ان حداقل
یکی از حالات قبول را به تعداد نامتناهی دیده باشیم. در اتوماتون بوچی غیرقطعی به جای تابع انتقال، رابطهٔ انتفال مطرح است و مانند NFA هر حالت تحت رابطهٔ انتقال به مجموعه ای از حالات منجر می شود و به جای حالت آغازی مجموعه از حالات ابتدایی در نظر گرفته می شود. در حالت کلی وقتی کلمه اتوماتون بوچی را به تنهایی به کار می بریم منظورمان اتوماتون بوچی غیرقطعی است. زبان های قابل تشخیص توسط اتوماتون بوچی. مجموعه تمام ω-کلمه های را که یک بوچی اتوماتون قبول می کند زبان ان بوچی اتوماتون می گویند. حالا یک زبان formula_15 را بوچی تشخیص پذیر می گوییم اگر بوچی اتوماتون M ای پیدا شود که formula_16 . یک زبان بوچی تشخیص پذیر است اگر و فقط اگر یک زبان امگا ی منظم باشد. مثلاً formula_17 . ویژگی های بستاری. فرض کنید A,B دو بوچی اتوماتون باشند و C یک اتوماتون متناهی باشد در این داریم: کاربرد. از بوچی اتوماتون معمولاً در وارسی مدل به عنوان یه نسخه نظریه ماشینی از یک فرمول در منطق موقت خطی استفاده می شود. منابع. Computer and System Sciences 8 (1974) No. 2, 117–141.
این نوشتار به بررسی رویدادها و اتفاقات مهم سینما در سال ۱۹۹۱ می پردازد. پرفروش ترین فیلم ها. ده فیلم پرفروش سال ۱۹۹۱: جوایز. شصت و چهارمین دوره جوایز اسکار چهل و نهمین مراسم گلدن گلوب نخل طلا (جشنواره فیلم کن): شیر طلایی (جشنواره فیلم ونیز): جشنواره بین المللی فیلم برلین (جشنواره فیلم برلین): فیلم های مشهور منتشر شده در سال ۱۹۹۱. ایالات متحده unless stated A-D. A B C D E-K. E F G H I J K L-Q. L M N O P-Q R-Y. R S T U-V W Y
تحلیل مستعار مجموعه ای از روش هایی است که تعیین می کند که آیا دو اشاره گر به شیء یکسانی در حافظه اشاره می کنند یا نه. الگوریتم های مختلفی برای تحلیل مستعار و راه های زیادی برای دسته بندی آن ها وجود دارد که عبارت است از: الگوریتم غیرحساس به جریان، الگوریتم حساس به متن و الگوریتم غیر حساس به متن، الگوریتم حساس به میدان و الگوریتم غیر حساس به میدان، مبتنی بر متحدسازی و مبتنی بر زیرمجموعه و غیره. در صورتی که دو اشاره گر به یک مکان اشاره کنند به آن ها مستعار می گویند. در نتیجه هر دو متغیری که می توانند مقادیرشان را از دو مقدار رسمی مجزا بگیرند نیز مستعار خواهند بود. در ابتدا تحلیل گرهای مستعار به یک جستار با کلماتی مثل: must, may و no جواب می دادند که نشان می داد که دو اشاره گر همیشه به یک شیء یکسان اشاره می کنند یا نه. وجود متغیرهای مستعار عملیات بهینه سازی را سخت تر می کنند زیرا نمی توانیم تشخیص دهیم که این کدام متغیر تغییر کرده است. بررسی اجمالی کلاس تحلیل مستعار. کلاس تحلیل مستعار یک رابط(interface) تعریف می کند که پیاده سازی های مختلفی از تحلیل مستعار باید آن را پشتیبانی کنند. این کلاس دو enum مهم به نام های
AliasResult و ModRefResult دارد که به ترتیب نتیجهٔ یک جستار مستعار یا یک جستار mod/ref را نشان می دهند. رابط AliasAnalysis اطلاعات حافظه را به روش های مختلف نمایش می دهد. به خصوص شی های حافظه به عنوان آدرس شروع و اندازه، و فراخوانی توابع به صورت دستور یک فراخوانی واقعی که فراخوانی را انجام می دهند نشان داده می شوند. علاوه بر این رابط AliasAnalysis چند روش کمک کننده که به شما امکان گرفتن اطلاعات mod/ref را برای دستور دلخواه را می دهد. در در همهٔ رابط های AliasAnalysis باید در جستارهای شامل مقدارهای چندگانه، مقدارهایی که ثابت نیستند باید در همان تابع تعریف شوند. به طور کلی تحلیل مستعار تعیین می کند که آیا ارجاع به حافظه به قسمت یکسانی اشاره می کند یا نه. در نتیجه این اجازه به کامپایلر داده می شود که مشخص کند که متغیرهای برنامه توسط یک بخش از برنامه عوض می شوند یا خیر. برای مثال قطعه کد زیر را در نطر بگیرید: *p.foo = ۱ *q.foo = ۲ *i = p.foo + 3 سه حالت مستعار برای این کد وجود دارد: در صورتی که مستعار نباشند آنگاه i برابر ۴ خواهد شد. اگر حالت دوم پیش بیاید i برابر ۵ می شود، چون p.foo + 3 = q.foo + 3. در هر دو حال
ت می توانیم بهینه سازی را روی آن ها اجرا کنیم. از طرفی، اگر نمی دانیم که این دو متغیر مستعار هستند یا نه نمی توان بهینه سازی را انجام داد و کل برنامه باید اجرا شود تا نتیجه به دست آید. در صورتی که وضعیت مستعار بودن دو ارجاع به حافظه نامشخص باشد می گوییم رابطهٔ may_alias دارند. پیاده سازی یک AliasAnalysis جدید. نوشتن یک تحلیل مستعار برای LLVM کار نسبتاً ساده ای است. پیاده سازی های مختلفی وجو دارد که می توان از آن ها استفاده کرد. در اولین مرحله باید مشخص کنیم چه نوع LLVM pass ای برای استفاده در تحلیل مستعار نیاز داریم. همانند سایر تحلیل ها و تبدیل ها، پاسخ باید از نوع مسئله ای که می خواهیم حل کنیم واضح باشد: انواع تحلیل مستعار. در تحلیل مستعار حافظهٔ برنامه را به کلاس های مستعار تقسیم می کنیم. کلاس های مستعار مجموعه های مجزایی از محل های حافظه هستند که نمی توانند مستعار هم دیگر باشند. در اینجا فرض می شود که بهینه سازی روی نمایش سطح پایین برنامه اتفاق می افتد. چون برنامه ای که کامپایل می شود اعمال دودویی، پرش ها، حرکت بین ثبات ها، حرکت بین ثبات ها و حافظه، انشعاب و فراخوانی و برگرداندن توابع را انجام می دهد. تحل
یل مستعار مبتنی بر نوع. اگر زبانی که کامپایل می شود از نظر نوع امن باشد، بررسی کننده نوع(type checker) درست کار می کند و برنامه قادر به ایجاد اشاره گرهای اشاره کننده به متغیرهای محلی نیست. حال بهینه سازی های مفیدی می توان انجام داد. حالت های مختلفی وجود دارد که می دانیم دو محل از حافظه باید در کلاس های مستعار مختلفی باشند: وقتی تحلیل مستعار برای برنامه اجرا می شود هر عمل بارگذاری و ذخیره در حافظه باید با کلاسش برچسب گذاری شود. آنگاه اگر محل های formula_1 و formula_2 از حافظه را با کلاس های formula_3 و formula_4 در نظر بگیریم اگر formula_5 آنگاه formula_1 و formula_2 با هم may-alias خواهند بود و اگر formula_8 مستعار یکدیگر نخواهند بود. تحلیل مستعار مبتنی بر جریان. تحلیل مستعار مبتنی بر جریان را بر خلاف تحلیل مستعار مبتنی بر نوع می توان در برنامه های یک زبان با ارجاعات و تغییر نوع استفاده کرد. این نوع از تحلیل را می توان به جای تحلیل مبتنی بر نوع مکمل استفاده کرد. در این تحلیل کلاس های مستعار برای هر تخصیص از حافظه و برای هر متغیر محلی و سراسری که آدرس آن استفاده می شود، ایجاد می شود. ارجاعات به حافظه ممکن است
به بیش از یک مقدار در طول زمان اشاره کنن و در نتیجه در بیش از یک کلاس مستعار باشند و این بدان معناست که هر تخصیص حافظه یک مجموعه از کلاس ها به جای یک کلاس مستعار دارد.
منطق زمانی خطی (Linear temporal logic) در منطق، منطق زمانی خطی یا منطق زمانی خطی (در انگلیسی linear temporal logic or linear-time temporal logic(یک منطق زمانی موجهاتی است با توجیهاتی به زمان. در منطق زمانی خطی یک مسئله می تواند بررسی فرموله کردن آینده یک مسیر می باشد مثلاً این که یک شرط در نهایت درست خواهد شد یا … منطق زمانی خطی خود یک قسمتی از منطق پیچیده تر CTL* می باشد که اجازه شاخه شاخه شدن حالات زمان و سنجه ها را می دهد. همچنین منطق زمانی خطی را منطق زمانی گزاره ای (به انگلیسی propositional temporal logic , PTL) نیز می نامند. منطق زمانی یک فرمالیسم مناسب برای مشخص کردن و تصدیق خاصیت های یک سیستم واکنشی است. یک فرمول از منطق زمانی یک مجموعه از دنباله های نامتناهی را توصیف می کند که برای هر یک از فرمول ها کدام درست است. (که به آن خواص زمانی نیز گفته می شود) یک سیستم پیشنهادی یک خاصیت را زمانی تأیید می کند که تمامی محاسباتش مربوط به این مجموعه باشد. یک مدل منطق زمانی خطی یک دنباله نامتناهی از حالاتی است که هر نقطه در هر لحظه از زمان دارای پیآمد (successor) خاصی است. شروع و انگیزه. منطق زمانی خطی ابتدا برای
صحت یابی رسمی برنامه های کامپیوتری در سال ۱۹۷۷ توسط امیرپنئولی در مقاله ای به نام "منطق زمانی برنامه ها (به انگلیسی: The Temporal Logic Of Programs) پیشنهاد شد. او در خلاصه این مقاله می نویسد:یک روش جامع و یکپارچه برای تصدیق (verification) پیشنهاد شده که برای برنامه های موازی و پی درپی قابل پیاده سازی است. روش اصلی اثبات پیشنهادی، استدلال زمانی است با این پیش فرض که اتفاقات دارای وابستگی زمانی می باشند.دو سیستم رسمی (formal systems) برای برآورده کردن اصول مورد نیاز استدلال زمانی معرفی شده است.یکی از فرم ها، فرمالیسم روش اثبات متناوب (method of intermittent assertions) است و دیگری انطباق با سیستم محکم (adaptation of the tense logic system Kb) که کاملاً برای استدلال در مورد رویدادهای همزمان مناسب است. نحو. منطق زمانی زمانی یک دسته متناهی از متغیرهای گزاره (propositional variables)، عملگرهای منطقی ¬ و ∨، و در کنار ارتباط دهندگان معمول، فرمول های زمانی می توانند با عملگرهای زمانی تولید شوند. معنا. یک فرمول منطق زمانی خطی می تواند با استفاده از یک رشته از حقیقت سنج هایی که زیر مجوعه از متغیرهای گزاره هستنند اثبات
شوند. یک فرمول منطق زمانی p تصدیق پذیر است اگر که یک دنباله از حالات S باشد به صورتی "S,0" |= "p. این زمانی درست خواهد بود که نفی آن غیرقابل تصدیق باشد. یک فرمول منطق گزاره ای زمانی یک فرمول زمانی هست اگر همه اتم های آن متغیرهای گزاره ای باشند. (یک فرمول زمانی گزاره ای در نتیجه شامل مقدار سنج ها و مسندهای مرکب نخواهد بود)" اگر w = a0,a1,a2... را یک ω-کلمه در نظر بگیریم. w(i) = ai. wi =... , ai,ai+1 به صورت رسمی، رابطه تصدیق پذیری |= بین یک کلمه و یک فرمول منطق زمانی زمانی به صورت زیر تعریف می شود: w |= p اگر p ∈ w(0) w |= ¬ψ اگر w |= ψ w |= φ ∨ ψ اگر w |= φ یا w |= ψ w |= X ψ اگر w1 |= ψ (در زمان گام بعدی ψ باید صحیح باشد) w |= φ U ψ اگر وجود داشته باشد i ≥ ۰ به صورتی که wi |= ψ، برای همه 0k و φ |= "w"k (φ باید صحیح بماند تا زمانی که ψ صحیح بشود)
بررسی گونه (Type checking ):. بررسی گونه فرایندی است برای اثبات اینکه هر عملیاتی که در برنامه اجرا می شود قواعد گونه ای زبان را رعایت می کند. به طور کلی به این معناست که تمامی عملوندها در تمامی گزاره ها دارای گونه مناسبی هستند. بررسی کردن معنایی بر دو قسم است: بررسی گونه ای ایستا. یک زبان ایستا گونه است اگر گونه متغیرها به جای زمان اجرا در زمان کامپایل مشخص شود. از مثال های معروف از زبان های ایستا-گونه می توان به زبان های Ada, C, C++, C#, JADE, Java, Fortran, Haskell, ML, Pascal, and Scala اشاره کرد. مزیت بزرگ زبان هایی که از بررسی گونه ایستا استفاده می کنند این است که می توانند بسیاری از خطاها و اشتباهات را به سرعت در مرحله توسعه شناسایی کنند. ایستا گونگی معمولاً کدهای کامپایل شده ای را نتیجه می دهند که سریع تر اجرا می شوند زیرا زمانی که کامپایلر می داند که دقیقاً از چه گونه اطلاعاتی استفاده می کند می تواند کدهای ماشین بهینه تری تولید کند. ( کدهایی که سریع ترند یا حافظه کمتری اشغال می کنند) استفاده کنندگان از بررسی گونه ایستا تنها از اطلاعاتی که در زمان کامپایل مشخص شده است استفاده می کنند اما می توانند مطمئ
ن باشند که برای تمامی حالات اجرا، برنامه در حالت صحیح باقی می ماند، که این نیاز به تکرار بررسی گونه را در زمان اجرا از بین می برد. یک بررسی کننده گونه ایستا به سرعت خطاهای گونه ای را در مسیرهای کد کمتر مورد استفاده پیدا می کند اما بدون بررسی ایستا گونه حتی با وجود پوشش 100% کد با تست ممکن است این چنین خطاهایی کشف نشوند. نقطه منفی بررسی ایستا این است که اگر شما بخواهید در یک زبان با بررسی کننده گونه ایستا یک برنامه با خطا گونه ای را به صورت دستی اجرا کنید ، حتماً بررسی کننده گونه متوجه می شود و یک خطای گونه ای را ایجاد می کند و مانع اجرا برنامه شما می شود. بررسی گونه ای پویا. بررسی گونه پویا فرایندی است که ایمن بودن گونه های یک برنامه را در زمان اجرا تصدیق کند. زبان های معروف با بررسی کننده گونه پویا عبارتند از : Groovy, JavaScript, Lisp, Lua, Objective-C, PHP, Prolog, Python, Ruby, Smalltalk and Tcl. بیشتر زبان های ایمن-گونه دارای سبکی از بررسی گونه پویا هستند حتی اگر آن ها از یک بررسی کننده ایستا نیز استفاده کنند. دلیل این امر این است که بررسی گونه ای ایستای بسیار از ویژگی ها و خواص مفید غیرممکن (یا بسیار دش
وار) است. برای مثال برنامه ای را در نظر بگیرید که دو گونه A , B را تعریف کرده که A زیرگونه B است. اگر برنامه سعی کند که یک مقدار از گونه A را به گونه B تبدیل کند که تبدیل رو به پایین این عمل زمانی مجاز خواهد بود که مقدار تبدیل شونده خود از گونه B باشد بنابراین یک بررسی کننده پویا گونه لازم است که تصدیق کند که این عمل ایمن است. از دیگر قابلیت های زبانی که بررسی پویا گونه اجازه می دهد می توان به dynamic dispatch, late binding, و reflection اشاره کرد. برخلاف بررسی کننده های گونه ایستا ، بررسی کننده های گونه پویا ممکن است باعث خرابی برنامه در زمان اجرا به علت خطاهای گونه ای شوند. در بعضی از زبان های برنامه نویسی این قابلیت وجود دارد که از این خطاها به وسیله روش های حل خطا و یا روش های ایمنی ضعیف خارج شد. در سایر زبان ها خطاهای گونه ای کشنده قلمداد می شود . به علت سخت بودن تشخیص خطاهای گونه ای در زبان های با بررسی گونه ای پویا یک روش مرسوم استفاده از آزمایش واحد می باشد. در مجموع زبان های با بررسی گونه ای پویا معمولاً کدهای غیربهینه تری را نسبت به زبان های با بررسی گونه ایستا تولید می کنند ، احتمال خطای گونه ای در
زمان اجرا را زیاد می کنند و مجبور می شوند که بررسی های گونه ای زمان اجرا داشته باشند. ( در مقابل بررسی کننده های ایستا که فقط یک بار در زمان کامپایل بررسی می کنند). با این حال بررسی کننده های پویا امکان ساختن زبان هایی را می دهند که دارای با قدرت بیشتر و امکانات بهتری باشند و توسعه محصولات را به صورت چشم گیری آسان تر کنند.
یک گرامر ماتریسی (انگلیسی:Matrix grammar), یک گرامر منظم است که در آن به جای قانون های تکی، قانون ها در دنباله های متناهی باهم گروه شده اند. یک قانون نمی تواند به صورت مجزا اعمال شود، بلکه هر قانون به صورت دنباله ای از قانون ها اعمال می شود. به عنوان مثال برای اعمال یک قانون چندین بار باید بازنویسی انجام شود، به این صورت که ابتدا قانون اول انجام می شود سپس قانون دوم و به همین ترتیب تا آخرین قانون پیش می رود. این دنباله از قانون ها در یک ماتریس نمایش داده می شود. گرامر ماتریسی گسترشی از گرامر بدون محتوا است. تعریف دقیق. یک گرامر ماتریسی یک پنج تایی مرتب به صورت زیر است: که دارای خاصیت های زیر می باشد: خصیصه ها. فرض کنید formula_7 مجموعه زبان هایی باشد که با گرامر ماتریسی تولید می شود و formula_8 مجموعه زبان هایی باشد که با گرامر ماتریسی بدون formula_9 تولید می شود. خصیصه های زیر وجود دارد: مثال. گرامر formula_15 را در نظر بگیرید که در آن M مجموعه ماتریس های زیر است: [S → XY], [X → aXb, Y → cY], [X → ab, Y → c] این ماتریس ها که شامل قوانین زبان بدون محتوا می شوند، زبان زیر را تولید می کنند: formula_16 این مثال
از اقتباس شده است. مسئله حل نشده. دوتا مسئله در زمینه این گونه گرامرها همچنان به صورت حل نشده باقی مانده است.
تجزیه کننده استاندارد LR در علوم کامپیوتر یا تجزیه کننده (۱)LR، یک تجزیه کننده (LR(k به ازای k=۱، یعنی با یک پایانه پیشرو است. ویژگی خاص این تجزیه کننده این است که هر گرامر (LR(k با k&gt;1 را می توان به گرامر (۱)LR تبدیل کرد. این تجزیه کننده می تواند تمام زبان های مستقل از متن قطعی را مدیریت کنند. در گذشته، تجزیه کننده (LR(k به دلیل نیاز به حافظهٔ زیاد و وجود جایگزین هایی با قدرت کمتر مانند تجزیه کننده LALR و (۱)LL، کمتر مورد استفاده قرار می گرفت. با این حال اخیراً یک تجزیه کننده (۱)LR کمینه ارائه شده است که نیاز به حافظه آن نزدیک به تجزیه کننده LALR است که توسط چند تولیدکنندگان تجزیه کننده ارائه می شود. تاریخچه. در سال ۱۹۶۵، دانلد کنوت، تجزیه کننده (LR(k را که یک نوع تجزیه کننده انتقال-کاهش بود را اختراع کرد. این تجزیه کننده دارای پتانسیل شناخت تمام زبان های مستقل از متن قطعی بوده و می تواند هر دو اشتقاق چپ و راست ورودی را تولید کند. کنوت اثبات کرد که قدرت پذیرش زبان برای K=۱ در حالت بیشینه است و یک روش برای تبدیل گرامر (LR(k با K&gt;1، به گرامر (۱)LR ایجاد کرد. بزرگترین مشکل تجزیه کننده استاندارد (۱)LR نیاز
به حافظهٔ زیاد برای ایجاد جدول-پارس داخلی خود است. در سال ۱۹۹۱ فرانک دو نسخه ساده شده از تجزیه کننده LR را به نام LALR و SLR را پیشنهاد کرد. این تجزیه کننده ها نیاز به حافظه کمتری نسبت به تجزیه کننده استاندارد (۱)LR دارند، اما قدرت تشخیص-زبان کمتری دارد. تجزیه کننده (۱)LALR رایج ترین پیاده سازی برای تجزیه کننده LR بوده اند. با این حال یک نوع جدید تجزیه کننده (LR(۱ با نام تجزیه کننده (۱)LR کمینه در سال ۱۹۷۷ توسط دیوید پابر معرفی شد که نشان داد که می توان یک تجزیه کننده (۱)LR ایجاد کرد که حافظهٔ مورد نیاز آن نزدیک تجزیه کننده (۱)LALR می باشد. اخیراً بعضی از تولیدکنندگان تجزیه کننده ها، تجزیه کننده (۱)LR کمینه را ارائه می دهند که مشکل حافظه را حل کرده اند. ساخت جداول تجزیه ال آر. جداول تجزیه (LR(۱ همانند جداول تجزیه (LR(0 با تفاوت که در آن هر قطعه شامل یک پایانه پیشرو است. این بدان معنی است که برخلاف تجزیه کننده (LR(0، یک عملیات متفاوت ممکن است اجرا شود، اگر قطعه مورد پردازش با یک پایانه متفاوت دنبال شود. قطعه های تجزیه کننده. با شروع براساس قوانین تولید یک زبان، ابتدا باید مجموعه های قطعه ها را برای این زبان ب
سازیم. به عبارت ساده تر می توان گفت یک مجموعه از قطعه ها، فهرستی از قوانین تولید است که نماد پردازش در حال حاضر ممکن است بخشی از آن باشد. یک مجموعه از قطعه ها رابطه یک به یک با حالت تجزیه کننده دارد، همچنین قطعه های موجود در مجموعه همراه با نماد بعدی، برای تصمیم گیری در مورد تغییرات حالت و عملیات تجزیه کننده استفاده می شود. هر قطعه حاوی یک نشانگر است که به جایی که نماد فعلی در آن نقطه از قطعه قرار خواهد گرفت اشاره می کند. برای تجزیه کننده (LR(۱ هر قطعه دارای یک پایانه پیشرو است. به عنوان مثال فرض کنید که زبان شامل نمادهای پایانه 'n'، '+'، '('، ')'، و غیرپایانه های 'E', 'T'، و قانون شروع 'S' که قوانین تولید زیر را شامل می شود: مجموعه قطعه های ۰ که نشان دهنده وضعیت اولیه است، از قانون شروع تولید می شود. [$ ،S → • E] علامت '•' نشانگر موقعیت فعلی تجزیه کننده در این قانون است. پایانه پیشرو در این قاعده بعد از کاما ذکر شده است. علامت '$' برای نشان پایان ورودی مورد انتظار است. مجموعه بالا، مجموعه قطعه کامل شماره ۰ نیست. هر مجموعه قطعه ها باید بسته باشد، یعنی تمام قوانین تولید برای هر غیرپایانه که بعد از '•' بیاید با
ید به صورت بازگشتی در مجموعه قطعه ها قرار داده شود تا همه غیرپایانه مورد بررسی قرار گیرد. نتیجه این عملیات را بستار آن قطعه می گوییم. در (LR(۱ برای هر قانون تولید، یک قطعه باید برای هر پایانه پیشرو ایجاد شود. برای زبان های پیچیده تر این معمولاً به مجموعه های بسیار زیادی از قطعه ها منجر می شود که همین دلیل استفاده از حافظهٔ بزرگ برای تجزیه کننده (LR(۱ است. در مثال بالا علامت شروع ما نیاز به پایانه 'E' دارد که 'E' خود نیاز به 'T' دارد و در نتیجه تمام قوانین تولید در مجموعه قطعه شماره ۰ ظاهر می شوند. در ابتدا، ما مسئله پیدا کردن پیشرو را نادیده گرفتیم و فقط به (LR(0 پرداختیم که قطعات آن شامل پایانه پیشرو نبودند؛ بنابراین مجموعه قطعه شماره ۰ دارای قطعه های زیر خواهد بود: مجموعه های FIRST و FOLLOW. برای تعیین پایانه های پیشرو، از مجموعه های به اصطلاح FIRST و FOLLOW استفاده می شود. مجموعه (FIRST(A شامل پایانه هایی است که می توانند به عنوان اولین قسمت از هر زنجیره از قوانین تولید که از غیرپایانه A شروع شود. (FOLLOW(A شامل پایانه هایی است که می تواند دقیقاً بعد از A ظاهر شوند. در مثال ما، (FIRST(S و (FIRST(E برابر {
')' ,'+' ,n } و (FIRST(T برابر {'+' ,n } می شود، همچنین (FOLLOW(S برابر { '$' } و (FOLLOW(E برابر { '(' ,'$' } همچنین (FOLLOW(T برابر { '(' ,'$' ,'+' } می شود. تعیین پایانه های پیشرو. با داشتن مجموعه های FOLLOW می توان مجموعه کامل قطعه ها را برای یک تجزیه کننده (LR(۱ ایجاد کرد، به این صورت که به ازای هر قطعه در مجموعه بستار آن (مانند (LR(0) و هر پایانه در مجموعه FOLLOW غیرپایانه سمت چپ یک قطعه جدید ایجاد کنیم. ایجاد مجموعه قطعه های جدید. بقیه مجموعه قطعه ها را می توان با الگوریتم زیر ایجاد نمود. در مثال ما پنج مجموعه جدید از مجموعه قطعه شماره ۰ ایجاد می شود. مجموعه قطعه شماره ۱ برای غیرپایانه E [$ ،• S → E] مجموعه قطعه شماره ۲ برای غیرپایانه T [$ ،• E → T] [$ ،T → T • + n] [+ ,T → T • + n] مجموعه قطعه شماره ۳ برای پایانه 'n' [$ ،• T → n] [+ ،• T → n] [( ،• T → n] مجموعه قطعه شماره ۴ برای پایانه '+' [$ ،T → + • T] [+ ,T → + • T] [$ ،T → • n] [+ ,T → • n] [$ ،T → • + T] [+ ,T → • + T] [$ ،T → • T + n] [+ ،T → • T + n] مجموعه قطعه شماره ۵ برای پایانه ')' [$ ،( E → ( • E] [( ,E → • T] [( ,( E → • ( E] [( ,T → • n
] [+ ,T → • n] [( ,T → • + T] [+ ,T → • + T] [( ,T → • T + n] [+ ،T → • T + n] از مجموعه قطعه های ۲ و ۴ و ۵ چندین مجموعه قطعه دیگر تولید خواهد شد. لیست کامل آن بسیار طولانی می باشد و بنابراین در اینجا بیان نمی شود. عملیات انتقال. اگر [A → α • b β, a] در حالت شماره k بوده و حالت شماره k با b به حالت شماره m برود، عملیات [action[k, b = 'انتقالm' را اضافه می کنیم. عملیات کاهش. اگر [A → α •, a] در حالت شماره k باشد، عملیات [action[k, a = 'کاهش A → α' را اضافه می کنیم.
معاون ریاست جمهوری افغانستان دومین مقام سیاسی در افغانستان است. معاونین کنونی ریاست جمهوری افغانستان به همراه رئیس جمهور توسط انتخابات تعیین می شود. هر کاندید ریاست جمهوری قبل از انتخاب دو معاون برای خود تعیین می کند. معاونین پیشین ریاست جمهوری افغانستان امرالله صالح (معاون اول ریاست جمهوری) و سرور دانش (معاون دوم ریاست جمهوری) است. با آنکه سردار محمد داوود خان پایه گذار جمهوری افغانستان و نخستین رئیس جمهور افغانستان بود، اما مقام معاون برای نخستین بار در افغانستان توسط شاه امان الله خان هنگامی بوجود آمد که نامبرده در سال ۱۹۲۶ سلطنت مشروطه اعلام کرد و مقام "یاور" (بعداً "معاون") را تشکیل داده و یاور محمود شاغاسی را منحیث "یاور اول حضور" (بعداً "معان اول") منتخب کرده بدین سمت برای بار نخست تقرر داد. جمهوری دموکراتیک افغانستان. معاون رئیس جمهور، معاون شورا انقلاب بین آوریل ۱۹۷۸ و آوریل ۱۹۸۸ بود. جمهوری دموکراتیک افغانستان. معاونان ریاست جمهوری پس از قانون اساسی جدید منصوب و انتخابات صورت گرفت. چهار معاون ریاست جمهوری توسط رئیس جمهور انتخاب شدند و توسط مجلس ملی موافقت شد. دولت اسلامی افغانستان. در این دوره معاون
ریاست جمهوری توسط رئیس جمهور منصوب می شد. دولت موقت افغانستان. در طول اداره دولت موقت و دولت انتقالی افغانستان و تا زمانی که لویه جرگه قانون اساسی جدید را تصویب نکرده بود بیش از دو معاون در دولت موقت وجود داشت. جمهوری اسلامی افغانستان. پس از سال ۲۰۰۴ معاونین رئیس جمهور به همراه رئیس جمهور از طریق انتخابات تعیین می شوند.