(۰۵ اردیبهشت ۱۳۹۲ ۰۷:۱۸ ب.ظ)post98 نوشته شده توسط:  با سلام به تمامی دوستان

من این دو تا سوال برام پیش اومده کسی میتونه کمکم کنه ممنون میشم

آیا ارتباطی بین گرامرهای ساده و گرامرهای LL(1) وجود دارد؟ توضیح دهید.؟
مرتبه زمانی تجزیه یک رشته به طول n توسط پارسر LL(k) چقدر می باشد؟ توضیح دهید؟

ممنون

سلام.
در مورد سوال اولتون هر گرامر ساده ای گرامر LL1 هست. اما عکس این موضوع درست نیست و عمومیت نداره و میشه گرامر LL1 نوشت که ساده نباشه(یعنی شکل گرامرش با تعریفی که در پایین اوردم تفاوت داشته باشه) برای دیدن همچین گرامرهایی می تونید به کتابای مختلف مراجعه کنید(مثلا کتاب ال شیخ از پوران پژوهش). توضیح گرامر ساده بصورت زیر هست:
"گرامر مستقل از متن بصورت [tex]P = (V , T , S , P)[/tex] را گرامر ساده گوییم هرگاه تمام قوانین گرامر بصورت[tex]A\rightarrow ax[/tex]
باشد که در آن [tex]A\, \epsilon\, V , a\, \epsilon \, T,x\, \epsilon \, V^{*}[/tex] باشد و هر زوج [tex](A,a)[/tex] حداکثر یکبار در قوانین ظاهر شود."
------------------------------------------------
درمورد سوال دومتون یک متنی رو قرار میدم که از آدرس
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
گرفتم:
Characterizations of the LL(k) property for context-free grammars are given, which lead to efficient algorithms for testing an arbitrary context-free grammar for the LL(k) property. The characterizations are based on succinct nondeterministic representations of a finite-state automaton used for constructing a canonical LL(k) parser. The resulting testing algorithms are usually of the same order to time complexity as their LR(k) counterparts. For example, one characterization (the LR(k) counterpart of which has been used by Hunt, Szymanski and Ullman for obtaining the fastest known algorithm for LR(k) testing) implies an [tex]0(n^{k 2})[/tex]
algorithm for LL(k) testing, where n is the size of the grammar in question and k is considered to be a fixed integer. This time bound for LL(k) testing has previously only been obtained indirectly, by a linear time-bounded reduction of LL(k) testing to LR(k) testing. Moreover, it is shown that the LL(k) property allows an especially convenient characterization,one which allows an [tex]0(n^{k 1})[/tex]
algorithm for LL(k) testing. This new time bound suggests that the LL(k) property might be strictly easier to test than the LR(k) property