دریافت گرامر و کنترل شرط

[abasfar]

سلام
دوستان نظریه زبانها و ماشینها یادتان هست
من میخوام گرامری را از کاربر گرفته و سپس را رشته را نیز بگیرم و کنترل رشته را انجام دهم
لطفا کمک کنید

[maktoom]

سلام
اگه منظورتون پیاده سازیشون با یه زبونی مثه سی و... اینطوری باید انجام بشه:
بعد از رسم درست ماشینتون هرکدوم از وضعیتها رو شماره گذاری کنید. بعد یه سوئیچ بذارید و به تعداد لازم کیس.
البته یه تابع شکست هم می خواید بعنوان وضعیت بن بست. که در هر وضعیت ورودی اشتباه بود به شکست بره.

[abasfar]

ممنون از جواب شما
بله منظورم پیاده سازیش است
اما زیاد متوجه نشدم میشه یکمی بحث را بازتر و توضیحات بیشتری بدهید

[maktoom]

شما در ماشینی که دارید یکسری وضعیت دارید و در هر وضعیت با دیدن یک ورودی به وضعیت دیگه میرید. البته اگه ماشین پشته ای باشه پردازش های اضافی دیگه ای هم خواهید داشت.
اما اگه گرامر مستقل از متن برای یه گرامر می خواد کار ساده تره. یعنی به ازای دیدن ورودی خاص رفتن به وضعیت دیگر یا خودش.
برای اینکار باید ماشینتون یا گرامرتون و قوانینش مشخص باشه.
یعنی باید معلوم باشه چه پردازشی در ازای دیدن ورودی باید انجام بگیره. بعبارت دیگه باید وضعیت بعدی به ازای دیدن یک ورودی در هر وضعیت معلوم باشه.
خب حالا امکان داره رشته یه رشته نامعتبر باشه. یعنی در وضعیتی به ازای ورودی اون رشته در این ماشین پذیرش نمیشه. پس باید وضعیتی به نام وضعیت شکست تعریف کنیم تا در صورت پذیرش نبودن گرمر در آتاماتا
با دیدن اون ورودی خاص در اون وضعیت به وضعیت شکستمون بره.
خب پس ما یه تابع اصلی داریم و یه تابع شکست.
برای چنین ماشینهایی کار بمراتب آسونتر از مثلا مباحث درس کامپایلرهاست که برای ثابتهای عددی باید چنتا ماشین رسم کنیم. اینجا ما فقط بایه ماشین سروکار داریم و
باید اونو پیمایش کنیم.
پس کاری که می کنیم بر اساس ماشین و یا گرامری که داریم و از روی اون ماشین یعنی دیاگرام رو رسم می کنیم و وضعیت ها رو شماره گذاری می کنیم.
خب حالا یه سری وضعیت برای کیسها داریم و یه سری خروجی از وضعیتها بعنوان شروط داخل کیسها و همچنین یه سری وضعیت ورودی داریم برای
تعیین اینکه اگه خروجی وضعیت قبلی فلان چیز بود بره به کدوم کیس. یعنی باید یه متغیر بگیرید برای تست روی سوئیچ و این حلقه سوئیچ رو بندازید داخل یه حلقه با شرط تست شماره وضعیت.
تا معلوم باشه در هر وضعیت چه اتفاقی باید بیافته.
یعنی بره به کدوم کیس و یا اینکه کلا بره به تابع شکست و اعلام پذیرش نشدن رشته بکنه.

[abasfar]

شما در ماشینی که دارید یکسری وضعیت دارید و در هر وضعیت با دیدن یک ورودی به وضعیت دیگه میرید. البته اگه ماشین پشته ای باشه پردازش های اضافی دیگه ای هم خواهید داشت.
اما اگه گرامر مستقل از متن برای یه گرامر می خواد کار ساده تره. یعنی به ازای دیدن ورودی خاص رفتن به وضعیت دیگر یا خودش.
برای اینکار باید ماشینتون یا گرامرتون و قوانینش مشخص باشه.
یعنی باید معلوم باشه چه پردازشی در ازای دیدن ورودی باید انجام بگیره. بعبارت دیگه باید وضعیت بعدی به ازای دیدن یک ورودی در هر وضعیت معلوم باشه.
خب حالا امکان داره رشته یه رشته نامعتبر باشه. یعنی در وضعیتی به ازای ورودی اون رشته در این ماشین پذیرش نمیشه. پس باید وضعیتی به نام وضعیت شکست تعریف کنیم تا در صورت پذیرش نبودن گرمر در آتاماتا
با دیدن اون ورودی خاص در اون وضعیت به وضعیت شکستمون بره.
خب پس ما یه تابع اصلی داریم و یه تابع شکست.
برای چنین ماشینهایی کار بمراتب آسونتر از مثلا مباحث درس کامپایلرهاست که برای ثابتهای عددی باید چنتا ماشین رسم کنیم. اینجا ما فقط بایه ماشین سروکار داریم و
باید اونو پیمایش کنیم.
پس کاری که می کنیم بر اساس ماشین و یا گرامری که داریم و از روی اون ماشین یعنی دیاگرام رو رسم می کنیم و وضعیت ها رو شماره گذاری می کنیم.
خب حالا یه سری وضعیت برای کیسها داریم و یه سری خروجی از وضعیتها بعنوان شروط داخل کیسها و همچنین یه سری وضعیت ورودی داریم برای
تعیین اینکه اگه خروجی وضعیت قبلی فلان چیز بود بره به کدوم کیس. یعنی باید یه متغیر بگیرید برای تست روی سوئیچ و این حلقه سوئیچ رو بندازید داخل یه حلقه با شرط تست شماره وضعیت.
تا معلوم باشه در هر وضعیت چه اتفاقی باید بیافته.
یعنی بره به کدوم کیس و یا اینکه کلا بره به تابع شکست و اعلام پذیرش نشدن رشته بکنه.

ممنون
حالا میشه یک شبه کدی چیزی هم لطف نمایید ممنون میشم

[maktoom]

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

[mostafa_shaeri_tj]

برای اینکار بایستی از الگوریتم CYK استفاده کنی. شبیه به ضرب ماتریس هاست.

این لینک ممکنه بدردت بخوره (http://barnamenevis.org/showthread.php?203274-%D8%A8%D8%B1%D9%86%D8%A7%D9%85%D9%87-%D8%AA%D8%B4%D8%AE%DB%8C%D8%B5-%D8%B9%D8%B6%D9%88%DB%8C%D8%AA-%DB%8C%DA%A9-%D8%AC%D9%85%D9%84%D9%87-%D8%AF%D8%B1-%DB%8C%DA%A9-%D8%B2%D8%A8%D8%A7%D9%86-%D9%85%D8%B3%D8%AA%D9%82%D9%84-%D8%A7%D8%B2-%D9%85%D8%AA%D9%86)