تجزیه ایرلی

در علوم کامپیوتر، تجزیه ایرلی (به انگلیسی: Earley)، یک الگوریتم برای تجزیهٔ یک رشته است که متعلق به یک زبان مستقل از متن است

نام الگوریتم از وجود آورنده آن جی ایرلی گرفته شده، و این الگوریتم مبتنی‌بر برنامه‌نویسی پویا است. از این الگوریتم به‌طور عمده برای تجزیه در زبان‌شناسی محاسباتی استفاده می‌شود.

جذابیت تجزیه‌کننده‌های ایرلی در آن است که می‌توانند تجزیهٔ تمام زبان‌های مستقل از متن را نیز پشتیبانی کنند؛ این ویژگی در تجزیه‌کننده‌های LR ،LL که معمولاً بیشتر در کامپایلرها استفاده می‌شوند وجود ندارد و آن‌ها تنها می‌توانند کلاس‌های محدودی از زبان‌ها را پشتیبانی کنند.تجزیه ایرلی

در علوم کامپیوتریک تجزیه برای , یک الگوریتم برای تجزیه رشته است که متلق به یک زبان مستقل از متن در نظر گرفته شده‌است. هر چند بسته به نوع ممکن است با گرامرهای certain nullable grammar دچار مشکل شود. یک الگوریتم بر اساس اسم تولیدکننده ی آن ,نام گذاری می‌شود.(JAY EARLEY) این الگوریتم بر اساس نمودار برنامه‌نویسی پویاست به همین دلیل است که به‌طور عمده برای تجزیه در زبان‌شناسی محاسباتی استفاده می‌شود. این الگوریتم را برای اولین بار در پایان‌نامه خود در سال 1968 معرفی کرد و پس از آن به صورت مختصر و خوانا تر در مجله به چاپ رسید. تجزیه‌کننده ایرلی جذاب است زیرا : آنها می‌توانند تجزیه تمام زبان‌های مستقل از متن , برخلاف تجزیه‌کننده‌های LL ,LR که معمولاً بیشتر در کامپایلرها استفاده می‌شوند را انجام می‌دهد. این الگوریتم دارای پیچیدگی زمانی می‌باشد که در آن ,nطول رشته می‌باشد. درجه ی دو این زمان برای گرامرهای بدون ابهام است و خطی آن برای تمام گرامرهای LR(k) استفاده می‌شود. این الگوریتم برای بازگشتی‌ها خیلی خوب عمل می‌کند.

الگوریتم بالا شناخت ایرلی را توضیح می‌دهد. این شناسنده به سادگی تغییر می یابد تا یک درخت پارسه به عنوان شناسنده, بسازد. الگوریتم: بر اساس توضیحات بالا α, β, γ ,هر رشته در ترمینال یا غیر ترمینال(شامل رشته خالی) را ارائه می‌دهد.X,Yغیرترمینال و a ترمینال را نمایش می‌دهد. این الگوریتم از بالا به پایین می‌باشد. ما با استفاده از نماد نقطه‌ای این عملیات را توصیف می کنیم:

X → α • β این نماد نشتن دهنده α پارس شده و β در انتظار است.

موقعیت ورودی 0 ,موقعیتی است که هنوز چیزی وترد نشده و موقعیت n برای پذیرفتن n امین ورودی است. برای هر موقعیت ورودی پارسر یک state تعیین می‌کند. هر state چندتایی (X → α • β, i)شامل: ساختن به‌طور هم‌زمان (X → α β) موقعیت فعلی (ارایه شده با نقطه) موقعیتی که در آن تولید شروع می‌شود ,موقعیت مبدا موقعیت i در ورودی کخ موقعیت مبدأ می گویند. الگوریتم ایرلی شامل نگاه پیشرو در stateها است ولی پژوهش‌ها حاکی از آن است که بهرخ وری کمتری دارد و به همین دلیل پیاده‌سازی آن کاهش یافته‌است. State ای که در جایگاه K تعیین می‌شود : S(K) پارسری که با مقدار 0 مقدار دهی می‌شود در top قرار می‌گیرد. پارسر به‌طور مکرراین 3 عملیات پیش‌بینی و اسکن و اتمام را تکرار می‌کند. پیش بینی: برای هر state در s(k) با فرم (X → α • Y β, j) که در اینجا j در موقعیت مبدأ است همانطور که در بالا گفته شد. و (Y → • γ, k) برای هر تولیدی در گرامرکه در آن y در سمت چپ قرار دارد. اسکن: اگر a سمبل بعدی از رشته باشد برای هر state در s(k) به شکل (X → α • a β, j) .. (X → α a • β, j) را با S(k+1) جمع می کنیم. اتمام: برای هر state درs(k) با فرم (X → γ •, j)یک state در s(j) با فرم

(Y → α • X β, i)  که  (Y → α X • β, i) را با S(k). جمع می کنیم.

این مهم است که state تکراری وارد مجموعه stateها نشود. این سه عمل تا جایی تکرار مشود که state جدیدی وارد نشود. این مجموعه به‌طور کلی به صفی ازstateهای برای اجرا می‌باشد.

شبه برنامه :

function EARLEY-PARSE(words, grammar)

   ENQUEUE((γ → •S, 0), chart[0])
   for i ← from 0 to LENGTH(words) do
       for each state in chart[i] do
           if INCOMPLETE?(state) then
               if NEXT-CAT(state) is a nonterminal then
                   PREDICTOR(state, i, grammar)         // non-terminal
               else do
                   SCANNER(state, i)                    // terminal
           else do
               COMPLETER(state, i)
       end
   end
   return chart

procedure PREDICTOR((A → α•B, i), j, grammar)

   for each (B → γ) in GRAMMAR-RULES-FOR(B, grammar) do
       ADD-TO-SET((B → •γ, j), chart[j])
   end

procedure SCANNER((A → α•B, i), j)

   if B ⊂ PARTS-OF-SPEECH(word[j]) then
       ADD-TO-SET((B → word[j], j), chart[j + 1])
   end

procedure COMPLETER((B → γ•, j), k)

   for each (A → α•Bβ, i) in chart[j] do
       ADD-TO-SET((A → αB•β, i), chart[k])
   end

مثال:

= # the start rule

 ::= "+" <M> | <M> <M> ::= <M> "*" <T> | <T> <T> ::= "1" | "2" | "3" | "4"

منابع