جمع آوری اطلاعات برای ساخت یک مفسر

[1485159]

سلام
من میخوام یه زبان برنامه نویسی مفسری طراحی کنم ولی نمیدونم که چطوری شروع کنم؟
تو کد نویسیش هیچ مشکلی ندارم و تا جاهایی پیش رفتم ولی بعضی جاهاش مشکل دارم:
1- فرض کنید کی فایل متنی دارم (فرض کنید هدر ها در سی++ یا یونیت ها در دلفی) که حدود 1000 تا تابع کار بر توی این فایل تعریف کرده. حالا وقتی کاربر مینویسه که از فلان تابع در درون فلان فایل استفاده کن باید تمام فایل جست و جو بشه و تابع مربوطه از درون اون فایل متنی استخراج بشه.! ولی این خیلی زمان میبره! و سرعت برنامه پایین میاد!
زبان های مفسری مثل پایتون و جاوا چطوری این کار رو میکنن؟

[tdkhakpur]

زبان های مفسری مثل پایتون و جاوا چطوری این کار رو میکنن؟
خب داخل ram انتقال داده بعد پردازش را انجام میدهند خوتان هم باید بدانید اینگونه فایلها به دلیل متنی بودن حجم چندان زیادی ندارند پس سریعترین راه انتقال انها داخل ram باید باشد.

[1485159]

خب داخل ram انتقال داده بعد پردازش را انجام میدهند خوتان هم باید بدانید اینگونه فایلها به دلیل متنی بودن حجم چندان زیادی ندارند پس سریعترین راه انتقال انها داخل ram باید باشد.
خوب فرض کنید یه فایل متنی 5000 سطری به رم انتقال داده شد. حال باید برای پیدا کردن تابع مورد نظر باید خط به خط خونده بشه! بازم که سرعت کم میشه!

[tdkhakpur]

حال باید برای پیدا کردن تابع مورد نظر باید خط به خط خونده بشه! بازم که سرعت کم میشه!
خب اصول کار همینه مگه اینطور نیست؟
در این قسمت باید پناه برد به توانایی سخت افزار و همچینی قدرت کلاک پالسی که cpu دریافت میکند.

[1485159]

خب اصول کار همینه مگه اینطور نیست؟
در این قسمت باید پناه برد به توانایی سخت افزار و همچینی قدرت کلاک پالسی که cpu دریافت میکند.
شاید اصول کار این باشه!
ببینید کامپایلر دلفی در پایین ترین سخت افزار ها هم خیلی سریع متن رو (هرچه قدر هم که طولانی باشه) کامپایل(به اصطلاح اسکن) میکنه!
من موندم مگه همهی کامپایلر ها کد برنامه رو کاراکتر به کاراکتر نمیخونن؟

[1485159]

در ضمن چطوری یه فایل متنی رو به رم انتقال بدم؟

[tdkhakpur]

من موندم مگه همهی کامپایلر ها کد برنامه رو کاراکتر به کاراکتر نمیخونن؟
در حالت کلی این بستگی به طراحی هم دارد که چگونه مفسر را بسازید ولی به احتمال زیاد کمتر کسی اطلاع داشته باشد که دلفی برای لود کردن فایلها داخل ram از چه روشی استفاده میکند.
مثلا آیا نمی شود یک هدر را خواند و انرا طوری در ram قرار داده که به جای کلمات چند حرفی - یک عدد 4 بایتی قرار بگیرید تا حجم داده ها کاهش پیدا کند.؟
ساختار زیر را در نظر بگیرید


struct Word_St
{
char word[126];
char *NextLink;
};

اگر شما داده ها را بصورت کلمه به کلمه داخل ساختار فوق که بصورت لیست پیوندی باشد قرار بدید به شرطی که کلمات مشابه را داخل لیست وارد نکنید میتوانید حجم داده ها را بسیار پایین بیاورید در ضمن اینکه برای هر کلمه یک کد دارید که شماره لیست پیوندی هست یعنی اولین لیست عدد 1 و دومین عدد 2 و الی اخر.
در راستای ایجاد همین الگوریتم شما قادر خواهید بود کل فایل را بصورت عدد در ram لود کنید یعنی از فایل کلمه را خوانده و آنرا در لیست پیوندی فوق جای داده و کد آنرا داخل مکانی از ram که برای لود شدن فایل در نظر گرفته اید قرار بدید.
به فرض شما بخواهید یک تابعی به اسم Paint رابیابید اولین کار شما مراجعه به دیکشنری لغات یا همان لیست پیوندی هست که با پیدا کردن لغت - شماره لیست را در دست خواهید داشت حالا داخل ram که داده های هدر شما بصورت کد قرار دارد - این عدد را جستجو میکنید و به تابع مورد نظر نزدیک خواهید شد.
البته این یک نظر شخصیه و به نحوه کار سایر کامپایلرها مربوط نمیشود.


در ضمن چطوری یه فایل متنی رو به رم انتقال بدم؟

خب اندازه فایل را بدست بیارید و به اون اندازه جا برایش در ram رزرو کرده و توسط توابع کار با فایل آنرا داخل ram کپی کنید.

[Pooria121]

بنده هم یک جوابی دارم،
تا اونجایی که بنده متوجه شدم، اولا که برای صرعت و راحتی parsere شما بهتر است، شما از گرامر هایی مانند LALR یا LL(1) استفاده کنید که بستگی به پیچیدگی زبان شما داره. کلا TopDown parser ها راحتر برای implement کردن هستند.

اما شما باید یک قسمت به عنوان Lexical Analyzer داشته باشید، که String هارو در برنامه شما بصورت Token برگردونه. و بعد از یک بار Scan کردن، یک Symbol Table، از نوع Dictionary(map) بسازد و اگر خواستی این Table رو برای هر فایل جدا ساز و بعد از پر کردنش ذخیره کنید.

به توسط این table شما میتوانید دفعات دیگر که درخواستی کانند نام Variable ، یا function شد، بجای scan 50000 خط، یک table 1000 رکوردی را scan کنید.

ولی به هر حال شما حد اقل یک بار باید هر فایل رو بصورت کامل scan کنید.
در مورد گرامر ها شما در مورد Context-Free Languages مطالعه بفرمایید و آسانترین parser که به ذهنم میرسه فعلا Predictive Parser است. Lexical Analyzer فراموش نشود.

درضمن، tools هایی زیادی برای ساختن Compiler و Interpreter وجود داره مانند Flex برای ساختن Lexical Analyzer و YACC برای ساختن Parser برای گرامر های LALR.

امیدوارم یک سرنخهایی داده باشم.

[Pooria121]

شاید اصول کار این باشه!
ببینید کامپایلر دلفی در پایین ترین سخت افزار ها هم خیلی سریع متن رو (هرچه قدر هم که طولانی باشه) کامپایل(به اصطلاح اسکن) میکنه!
من موندم مگه همهی کامپایلر ها کد برنامه رو کاراکتر به کاراکتر نمیخونن؟

خواندن فایل کاراکتر به کاراکتر، کار زمان برای نیست، parse کردن اون زمانبر است، که طبق اصولی که به شما گفتم در بالا، این زمان به حداقل میرسه.

برای parse کردن یک برنامه، مفسر اول یک Parse tree میسازد (شاید هم بصورت مجازی باشد و وجود خارجی در برنامه نداشته باشد) و اگر توانست این parse tree را بدون مشکل بسازد، بیان گر نداشتن Syntax error در کد ورودی آن است. بعد از داشتن parse tree شما با traverse کردن آن tree به راحتی عمل interpretation رو انجام میدهید.

ماجولی که فایل شما را scan میکنید، باید یک lexical analyzer باشد، که بعد خروجی اطلاعات را به parser میدهد.

Parser ها عنواع مختلفی دارد، و نحو ساختن آنها در صرعت اجرایی شما تائثیر زایدی دارد. به همین دلیل یک دسته از اصولی برای ساختن parser ها به قلم در آمده که بنده در بالا به آنها اشاره کردم، اگر در مورد آنها مطالعه کنید، خالی از لطف نخواهد بود.

[1485159]

سلام
tdkhakpur جان و Pooria121 جان دستتون درد نکنه واقعا نوشته هاتون مفید بودن.
چنتا سوال:
1- منظور از گرامر چیه؟
2- منظور از parse کردن یعنی اینکه تشخیص بدیم که مثلا کلمه x یک متغیره؟ یا یک رشته و...؟

[tdkhakpur]

- منظور از گرامر چیه؟

گرامر همان فانونی هست که شما برای تشخیص متغییر ها و یا دستورات به کار میبرید مثلا میتوانید بصورت دستورات c کدها را تفسیر کنید یا بصورت پاسکال به اینصورا که برای if پاسکال همیشه بعد از if باید دنبال پارانتز باز و بسته بود اما در تفسیر بصورت پاسکال شما باید محتوای بین if و then را ذر نظر بگیرید . اساسا سایر کارهای دیگر که اصول گرامر زبان هستند.

2- منظور از parse کردن یعنی اینکه تشخیص بدیم که مثلا کلمه x یک متغیره؟ یا یک رشته و...؟
در مورد parse اطلاعات زیادی ندارم ولی اگر parse کردن بتواند مفسر شما را آنالیز کند شما در ساخت مفسر اختیاری ندارید بلکه باید قوانینی را که parse آنرا می طلبد رعایت کنید.
البته اگر Pooria121 عزیز نحوه آنالیز parse را برای یک مفسر تا حدودی توضیح بدهند روشن خواهد شد که مفسر ساخته شما میشود یا مونتاژ شده توسط شما.

[1485159]

منتظر هستم.

[Pooria121]

گرامر: هر زبانی یک دستور زبان یا گرامر داره، و کلا زبانهای مختلفی وجود داره، Natural Language ، Regular Languages ، Context-Free Languages ، .....
کار Parser ترجمه کردن و پردازش کد است، حالا میتواند کد را به یک زبان ساده تر مانند Assembly تبدیل کند، میتواند کدهارا اجرا کند (که شما دنبال این هستید).
شما وقتی یک Parser رو میخواهید بنویسید، گرامری برای زبان خود مشخص میکنید، و اصولا زبان برنامه نویسی شما در گروه Context-Free Languages قرار میگره و Parseri که برای گرامری در این زبان بخواهید بنویسید، سریعتر عمل خواهد کرد.
گرامر شما در Context-Free Language ، میتواند مدل های مختلفی داشته باشد مانند LL(1) LALR LR و ... شما برای بهتر متوجه شدن این مباحث در مورد زبان ها، و اگر میخواهید که یک Interpreter یا Compiler کاربردی بسازید، باید به این اصول اشراف داشته باشید.

شما با توجه به گرامر، syntax زبان خودتون رو مشخص میکنید و وقتی یک parser رو برای آن گرامر میسازید، Parser شما با توجه به Action هایی که شما برای آن تعیین کردید، یک حرکت اجرایی را انجام میدهد.

به شما توصیه میکنم یک کتابی به موضوع
Automata Theory, Languages, and Computation رو مطالعه کنید، که این مباحث بصورت کامل در آن صحبت شده.

شما فرض کنید که ما یک Interperter ساده با استفاده از اصول طراحی کامپایلر میخواهید بنویسیم که عداد وارد شده بین کلمه کلیدی begin و end قرار دارد را بخواند، و آنهارا را محاصبه و چاپ کند.



begin
2+2;
3*3;
end.


و گرامر زیر که برای زبان قوع است:


S -> begin STMTS end
STMTS -> STMT;STMTS
STMTS -> epsilon
STMT -> num+ STMT
STMT - > num- STMT
STMT -> num


شما میتوانید برای ساختن این زبان یک Predictive Parser برای گرامر بالا بنویسید.
که اگر در گوگل این اسم را search کنید، حتما جوابی کاملتر میگیرد.

[tdkhakpur]

Parser شما با توجه به Action هایی که شما برای آن تعیین کردید، یک حرکت اجرایی را انجام میدهد.

این قسمت که بیان کردید قسمت اصلی به حساب میاد حالا شما میتوانید یک parser برای نمونه بزارید یا اگر اماده اش را دارید ارسال کنید که مثلا کد زیر را تشخیص داده و از آکولار اول بگذرد و دستورات بعد از آکولاد انتهایی را مورد اجرا قرار دهد؟


if(0)
{
}
k = k+1;

[Pooria121]

گرامری که بنده در بالا نوشتم، یک گرامر برای parser است که بداند چگونه و به چه ترتیب یک ورودی را بخواند، و شما action های مختلف را به خط ها و یا میان خط ها تقسیم مکینید، به عنوان مثال خط:

STMT -> num+ STMT

semantic action ای که به این خط میدهید، مثلا اگر با کد C بنویسید، وقتی parsere شما خطی که شامل token عداد ، '+' و دوباره عداد است را خواند، شما به عنوان action تعیین میکنید که num اول را با num دوم جمع کند، و printf() کند به خروجی.
به همین ترتیب شما برای دستور شرطی و حلقه عمل میکنید. شما در دستور شرطی میان پرانتز یک شرط دارید، که برای شرط هم یک گرامر دارید، و برای درستی و نادارستی آن هم شما یک actioni را به آن داده اید D:
و بعد به semantic actioni که برای if تغییر کرده اید، جواب true یا false بودن را میگیرد و بر مبنای آن تصمیم میگیرد که آیا میان {} را اجرا کنید یا نه،



CONIF -> if ( CONDSTMT ) { STMTS }

شما زمانی شروع به اجرای action ها کنید، که کل این token هارا دریافت کردید، و چون همه ی این token ها در موقع اجرای action از قبل به parser داده شده است، رد کردن و در نظر گرفتن آنها سادهتر میشود.

میدونم منظورم رو رسوندم یا نه.

و اما از برای کد ! کدای آماده ندارم، ولی اگر وقت کردم یکی آماده کنم، حتما تقدیم میکنم، ولی فکنم توی internet فراوان باشه.

[tdkhakpur]

وقتی parsere شما خطی که شامل token عداد ، '+' و دوباره عداد است را خواند، شما به عنوان action تعیین میکنید که num اول را با num دوم جمع کند، و printf() کند به خروجی.
به همین ترتیب شما برای دستور شرطی و حلقه عمل میکنید. شما در دستور شرطی میان پرانتز یک شرط دارید، که برای شرط هم یک گرامر دارید، و برای درستی و نادارستی آن هم شما یک actioni را به آن داده اید
اگه مثل بعضی از دوستان میگفتیم که ما هم اینا رو میدونستیم بد میشد.
ولی شما توضیحات را برای اینکه ما شرح حالی از parser داشته باشیم را دادید و باید تشکر کرد ولی این مطالب شما فقط شرح الگوریتم هست و بدون parser هم میتوان به پیاده سازی کرد .
بهتر بود نحوه کدینگ با parser را توضیح و ارسال میکردید بهتر بود نحوه کار با کلاس parser و چگونگی دادن پارامتر را شرح میدادید تا جهت نوشتن برنامه از این کلاس استفاده میشد.

[Pooria121]

(در اینجا) parser یک کلاس کلی، نیست، parser یا همان مفسر یک برنامه یا ماجول در یک Compiler است و برای یک گرامر باید نوشته شده بشه. عین است که شما میخواهید یک برنامه حساب داری بنویسید و بگویید یک کلاس حسابداری به شما بدهند و شما استفاده کنید ... بلکه شما باید همچین کلاسی را بنویسید.


خب شما توضیحات را برای اینکه ما شرح حالی از parser داشته باشیم را دادید و باید تشکر کرد ولی این مطالب شما فقط شرح الگوریتم هست و بدون parser هم میتوان به پیاده سازی کرد .

اما اینکه بدون parser اینکارو رو بکنید: به برنامه ای که این کار رو انجام داهد میگویند parser یا مفسر که شما مینویسید. و اما اگر منظورتون، پیروی نکردن از الگوریتم خاصی است، بله شما میتوانید بدون هیچ اصولی هرگونه که خواستید، این String را پردازش کنید ... ولی یادتون باشه ما به این دلیل از algorithm های متفاوتی مثلا برای search و sort استفاده میکنم، چون در مورد زمان اجرای آنها اطلاعاتی وجود دارد و میدانید به چه صرعتی کار میکند.
همچین چیزی پیچیده تر نیز در Compiler Design وجود دارد، گفته هایی از قبیل Code Optimization، Code Reduction و ... همچنین سرعت اجرا نیز مد نظر است !!! که اگر شما یک برنامه به طول 40,000 خط دادید، 3 سال به طول نینجامه برای گرفتن نتیجه.

تمام این مباحث در طی 40 سال مورد بحث و قلم قرار گرفته ( و هنوز هم جای فکر و تحقیق باقی است) و استفاده از آن اصول (بستگی به بزرگی کار شما دارد) کار را ساده تر میکند.

یک مدل از Parser ها PRedictive parser است که مثال کامل آن همانطوری که گفتم در اینترنت است:
http://en.wikipedia.org/wiki/Recursive_descent_parser

[1485159]

اگر شما یک برنامه به طول 40,000 خط دادید، 3 سال به طول نینجامه برای گرفتن نتیجه.
نه دیگه! اینطوری هم نیست.

[1485159]

سلام
در مورد ذخیره سازی متغیر ها چی پیشنهاد میکنید؟