کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875566 1441970 2018 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Linear-space recognition for grammars with contexts
ترجمه فارسی عنوان
تشخیص خطی فضا برای گرامرها با زمینه
کلمات کلیدی
گرامرهای متنباز، گرامرهای مفصل، گرامرهای حساس به متن، پیچیدگی فضا، تجزیه،
ترجمه چکیده
گرامرها با حوزه ها، فرمت گرامرهای متن باز هستند که مجهز به اپراتورها برای اشاره به چپ و راست محدوده های تعریف شده هستند. این گرامرها برای داشتن یک الگوریتم تجزیه و تحلیل زمان مکعب، و همچنین برای توانایی توصیف برخی از ساختارهای مفید نحوی مانند اعلان قبل از استفاده قابل توجه است. در این مقاله ثابت شده است که هر زبان که توسط یک گرامر با حوزه های توصیف شده است می تواند در فضای خطی قطعی شناخته شود.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
تشخیص خطی فضا برای گرامرها با زمینه
چکیده انگلیسی
Grammars with contexts are an extension of context-free grammars equipped with operators for referring to the left and the right contexts of a substring being defined. These grammars are notable for still having a cubic-time parsing algorithm, as well as for being able to describe some useful syntactic constructs, such as declaration before use. It is proved in this paper that every language described by a grammar with contexts can be recognized in deterministic linear space.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 719, 6 April 2018, Pages 73-85
نویسندگان
, ,