برنامه ساده سازی گرامر و تبدیل به فرم نرمال چامسکی

موضوع : برنامه ساده سازی گرامر و تبدیل به فرم نرمال چامسکی

درس : نظریه زبان ها و ماشین ها  _ مقطع کارشناسی

دانشگاه : دانشگاه صنعتی سجاد 

استاد : مهندس شکرانی

سال تحصیلی : ترم بهمن 94-1395

نرم افزاز برنامه نویسی شده : Visual Studio 

مستندات : دارد

توضیحات :

شمایی از برنامه:

• وارد کردن گرامر
• ساده سازی گرامر
• گرامر ساده 
• تبدیل به فرم نرمال چامسکی

شرح ظاهر برنامه :

• Step By Step
• Autocomplete
• To Chomsky
• Rest

کمه  Step By Step و  Autocomplete:

پس از وارد کردن گرامر کاربر می‌تواند بصورت قدم به قدم(Step By Step ) و هم بصورت خودکار( Autocomplete) گرامر را ساده کنید. با انتخاب حالت قدم به قدم در هر مرحله برای شما پیامی نمایش داده می‌شود که بیانگر آن است که گرامر ساده نبوده و برنامه در حال ساده سازی آن می‌باشد. پیامی که از سوی برنامه صادر می‌شود بیانگر کاری است که برنامه در آن مرحله انجام می‌دهد. 

دکمه To Chomsky :

برای تبدیل به فرم نرمال چامسکی از یک کتابخانه استفاده شده است. این کتابخانه دو ورودی دارد: 1- لیست قوانین 2- متغییر شروع گرامر و خروجی آن یک لیستی از کلاس Productions  است.

دکمه Rest :

این دکلمه صفحه را پاک کرده و آماده دریافت گرامر بعدی می‌شود.

ساده سازی گرامر شامل سه بخش می‌شود:

• حذف قوانین لاندا
• حذف قوانین یکه
• حذف قوانین غیر مفید

1. حذف متغیر‌های غیر‌قابل دسترس
2. حذف متغیر‌هایی که رشته تولید نمی‌کنند

توضیحات کد برنامه :

برنامه شامل چند تابع اصلی می‌شود که عبارتند از:

1.        F_Simplify:  که کار ساده سازی گرامر را انجام می‌دهد. این تابع در یک حلقه بی‌نهایت قرار می‌گیرد تا گرامر بصورت کامل ساده شود. و دیگر تابع ساده سازی نظیر حذف قوانین لاندا و غیره را فراخوانی میکند.

I.            F_DeleteVariableUseless: حذف متغیر‌های غیر قابل دسترس

II.            F_DeleteVariableUnProductString: حذف  متغیر که رشته تولید نمی کند

III.            F_UserLessProduction: حذف قانون غیر مفید. قوانین که تکراری هستند و یا قوانین نظیرA   → A

IV.            F_LandaProduction: حذف قانون لاندا

V.            F_UnitProduction: حذف قانون یکه

2.        CFG_to_CNF: این تابع گرامر ساده شده را به فرم نرمال چامسکی تبدیل می‌کند

• نکته‌ای که در این برنامه خیلی اهمیت دارد این است که متغیر شروع S  نیست بلکه متغیر است که در ابتدای لیست مرتب شده بر اساس حروف الفبا قرار گیرد. در مثل قبل متغیر شروع A بود.
• متغیر  Is_StepByStep: این متغیر Bool است و بصورت سراسری تعریف شده و کار آن این است که اگر کاربر بر روی دکمه ساده سازی قدم به قدم کلیک کرده باشد مقدار True و اگر بر روی ساده سازی خودکار کلیک کرده باشد مقدار False را می‌گیرد. و در زمان نمایش پیام بررسی می‌شود و اگر مقدار آن  True باشد پیام نمایش داده میشود در غیر این صورت پیام نمایش داده نمیشود.مثل

 if (Is_StepByStep)
 if (MessageBox.Show(StartCurrent + " → " + EndCurrent + "\n حذف قانون که رشته تولید نمی کند ", "", MessageBoxButtons.OKCancel) == DialogResult.Cancel)
 {
     Is_StepByStep = false;
 }

کد بالا ابتدا بررسی می‌کند گه مقدار متغیر Is_StepByStep برابر  True باشد. سپس پیام را برای کابر نمایش می‌دهد و میگوید که اگر کاربر دکمه Cancel کلیک کرد آنگاه مقدار Is_StepByStep را False کرده و دیگر پیامی برای کاربر نمایش داده نمیشود.

• متغیر IsSimplify:  این متغیر نیز Bool است و در تابع ساده سازی(F_Simplify ) تعریف شده است. کار آن این است که مشخص کند گرامر ساده شده است یا خیر. مقدار اولیه آن True به معنی گرامر ساده شده است، و زمانی که یکی از پنج تابع ساده سازی اجرا شوند مقدار آن False میشود و به این معنی است که گرامر ساده شده نیست. اگر هیچ یک از توابع ساده سازی اجرا نشوند متغیر IsSimplify مقدار True خود را حفظ کرده و گرامر ساده شده است.

شرح تابع حذف متغیرهای غیر قابل دسترس ( F_DeleteVariableUseless ):

این تابع با استفاده از ماتریس مجاورت می‌باشد. بدین صورت که یک ماتریس با ابعاد متغیرهای گرامر تولید می‌شود(فرضا اگر سه متغیر داشته باشیم یک ماتریس 3*3 تولید می‌شود) سپس اگر از هر متغیر به متغیر دیگر راهی وجود داشته باشد مقدار داخل ماتریس را برابر یک می‌کنیم.

ما در برنامه توسط کد زیر متغیرهای گرامر را بدست می‌آوریم.

List<string> listVarialbe = new List<string>();
//در این حلقه لیست متغیر ها بدست می آید
for (int i = 0; i < GV1.RowCount - 1; i++)
{
    String StartCurrent = GV1.Rows[i].Cells[0].Value.ToString().Trim();
    if (listVarialbe.IndexOf(StartCurrent) < 0)
        listVarialbe.Add(StartCurrent);
}

که در یک حلقه به اندازه سطرهای DataGridView سلول صفر که متغیر می‌باشد را در StartCurrent قرار می‌دهد. سپس بررسی می‌کند اگر این متغیر در لیست listVarialbe وجود نداشت آن را به لیست اضافه می‌کند. سپس ماتریس به ابعاد تعداد متغیرها تعریف میکنم.

int[,] matrix = new int[listVarialbe.Count, listVarialbe.Count];

و سپس خانه اول ماتریس را برابر یک می‌کنیم. این کار برای این می‌باشد که همیشه متغیر شروع قابل دسترس است.

if (listVarialbe.Count > 0)
    matrix[0, 0] = 1;

مثال:

A → aa | B 				
B → bb | BA 
C → C | ccB
ListVarialbe = {A, B, C }

\[ Matrix 1 = \begin{vmatrix} \mathbf{A} & \mathbf{B} & \mathbf{C} \\ 1 & - & - \\ - & - & - \\ - & - & - \\ \end{vmatrix} \] \[ Matrix 2 = \begin{vmatrix} \mathbf{A} & \mathbf{B} & \mathbf{C} \\ 1 & 1 & - \\ - & - & - \\ - & - & - \\ \end{vmatrix} \] \[ Matrix 3 = \begin{vmatrix} \mathbf{A} & \mathbf{B} & \mathbf{C} \\ 1 & 1 & - \\ 1 & 1 & - \\ - & - & - \\ \end{vmatrix} \] \[ Matrix 4 = \begin{vmatrix} \mathbf{A} & \mathbf{B} & \mathbf{C} \\ 1 & 1 & - \\ 1 & 1 & - \\ - & 1 & 1 \\ \end{vmatrix} \]

اگر ماتریس بدست آمده را بصورت سطری پیمایش کنیم مثل :

•  ستون A ، سطر A 
• ستون A ، سطر B 
• ستون A ، سطر C 

مشاهده میشود که از متغیر A هم به A هم به B راهی وجود دارد. و از متغیر B هم به A و هم به B راهی وجود دارد. ولی به متغیر C راهی وجود ندارد یا به عبارتی هیچ یک از قوانین ما به C نمی‌روند. پس متغیر C غیرقابل دسترس می‌باشد. کد زیر مانند مثال بالا ماتریس را کامل می‌کند. که در یک حلقه به اندازه سطرهای DataGridView تکرار می‌شود. StartCurrent قوانین سمت چپ یا متغیر ها هستند و EndCurrent قوانین سمت راست می‌باشند. سپس قوانین سمت راست را به تابع F_GetVariable فرستاده و لیست متغیرهایی که در قوانین سمت راست وجود دارد را در بصورت یک لیست به عنوان خروجی تابع برای ما ارسال می‌کند. سپس در یک حلقه به تعداد لیست متغیرهایی (listCurrentVariable_End ) که در سمت راست گرامر وجود دارند تکرار می‎شود. سپس اندیکس متغیر را از لیست متغیرهای گرامر(listVarialbe) که در بالا تعریفش کرده بودیم بدست می‌آورد و به این صورت است که میتواند به سطر و ستون ماترس دستریس داشته باشیم مثلا به ترتیب متغیرهای A,B,C دارای اندکس‌های 0،1،2 می‌باشند.

for (int i = 0; i < GV1.RowCount - 1; i++)
{
    String StartCurrent = GV1.Rows[i].Cells[0].Value.ToString();
    String EndCurrent = GV1.Rows[i].Cells[2].Value.ToString();
// مشخص میکنیم از وضعیت شروع به کدام متغیر ها میرویم
    List listCurrentVariable_End = F_GetVariable(EndCurrent);
    foreach (String item in listCurrentVariable_End)
    {
        int indexStartState = listVarialbe.IndexOf(StartCurrent);
        int indexEndState = listVarialbe.IndexOf(item);
//اگر متغیری که در سمت راست است در داخل لیست متغیر های سمت چپ نباشد پس باید آن  قانون حذف شود زیرا آن متغیر وجود ندارد
        if (indexEndState < 0)
        {
            GV1.Rows[i].ErrorText = "این متغیر وجود ندارد";
            if (Is_StepByStep)
                if (MessageBox.Show(item + " متغیر  " + "\n در لیست متغیر های گرامر وجود ندارد پس این قانون حذف می شود", "", MessageBoxButtons.OKCancel) == DialogResult.Cancel)
                    Is_StepByStep = false;
            GV1.Rows.RemoveAt(i--);
            continue;
        }
        matrix[indexStartState, indexEndState] = 1;
    }}

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

for (int colInx = 0; colInx < listVarialbe.Count; colInx++)
{
    bool checkAccess = false;
    for (int rowIdx = 0; rowIdx < listVarialbe.Count; rowIdx++)
        if (matrix[rowIdx, colInx] != 0)
            checkAccess = true;

    if (!checkAccess)
    {
        String UnAccessVariable = listVarialbe[colInx];
        F_DeleteVariable(UnAccessVariable);
    }
}

مثال:

شرح تابع حذف قانون یکه (F_UnitProduction):

در یک حلقه به اندازه سطرهای DataGridView تکرار می‌شود و سپس قوانین سمت راست (cellEnd) و قوانین سمت چپ (cellStart) بدست می‌آید. حال بررسی می‌شود اگر طول قانون سمت راست برابر یک از احتمال این وجود دارد این یک قانون یکه باشد. سپس بررسی می‌شود این یک متغیر است((cellEnd.Equals(cellEnd.ToUpper() که اگر یک رشته را تبدیل به حروف بزرگ کنیم و آن برابر با رشته اولیه باشد این بدین معنا است آن متغیر است مثل A که خود رشته برابر با رشته با حروف بزرگ است) و همچنین بررسی می‌شود که قوانین سمت راست و چپ با هم برابر نباشند، اگر این دو شرط برقرار باشد آنگاه این قانون یک قانون یکه است و باید حذف شود پس شماره سطر جاری را به تابع F_UnitProduction ارسال می‌کنیم تا سطر جاری را حذف کند و قوانین متغیری که می‌خواهد حذف شود را به جای خود متغیر جایگذین کند.

for (int i = 0; i < GV1.RowCount - 1; i++)
{
    String cellEnd = GV1.Rows[i].Cells[2].Value.ToString();
    String cellStart = GV1.Rows[i].Cells[0].Value.ToString();

    ///زمانی طول رشته یک باشد و در سمت راست حروف بزرگ باشد این نشان دهنده وجود قانون یکه است.
    if (cellEnd.Length == 1)
    {
///اگر رشته با رشته ای که تمام حروف آن بزرگ شده برابر باشد
        /// نتیجه میشود که رشته خود قبلا با حروف بزرگ بوده است
        /// پس یک متغیر است
        /// و یک قانون یکه می باشد
        if (cellEnd.Equals(cellEnd.ToUpper()) &&
            !cellStart.Equals(cellEnd))
        {
            F_UnitProduction(i);

            //بدین معنا است که هنوز گرامر ساده نشده است
            IsSimplify = false;
            i--;
        }  
 }
}

ادامه و مثال در مستندات....

شرح تابع حذف قانون لاندا (F_LandaProduction): 

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

private void F_LandaProduction(int rowIndex)
{
String StartState = GV1.Rows[rowIndex].Cells[0].Value.ToString();
String EndState = GV1.Rows[rowIndex].Cells[2].Value.ToString();
GV1.Rows[rowIndex].ErrorText = "یک قانون لاندا است";
if (Is_StepByStep)
    if (MessageBox.Show(StartState + " → " + EndState + "\n یک قانون لاندا است ", "", MessageBoxButtons.OKCancel) == DialogResult.Cancel)
        Is_StepByStep = false;
for (int i = 0; i < GV1.RowCount - 1; i++)
{
    String CurrentStateStart = GV1.Rows[i].Cells[0].Value.ToString();
    String CurrentStateEnd = GV1.Rows[i].Cells[2].Value.ToString();
    if (CurrentStateEnd.IndexOf(StartState) >= 0)
    {
        GV1.Rows[i].ErrorText = " حذف متغیر " + StartState;
        if (Is_StepByStep)
            if (MessageBox.Show(CurrentStateStart + " → " + CurrentStateEnd + "\n" + StartState + " حذف متغیر ", "", MessageBoxButtons.OKCancel) == DialogResult.Cancel)
                Is_StepByStep = false;

        GV1.Rows.Add(CurrentStateStart, " → ", CurrentStateEnd.Replace(StartState, ""));
        GV1.Rows[i].ErrorText = null;

    }
}
if (Is_StepByStep)
    if (MessageBox.Show("حذف قانون لاندا : \n" + StartState + " → " + EndState, "", MessageBoxButtons.OKCancel) == DialogResult.Cancel)
        Is_StepByStep = false;

GV1.Rows.RemoveAt(rowIndex);
}

ادامه و مثال در مستندات....

شرح تابع حذف قانون که رشته تولید نمی‌کند (F_DeleteVariableUnProductString):

در این تابع یک DataGridView جایگزین تولید می‌شود با نام gvTemp. سپس لیستی از متغیرهای گرامر بدست می‌آوریم. بعد از آن با استفاده از کد زیر بجای هر تغیر قوانین خودش را جایگزین میکنیم. مثال

A → aa | B 				
B → bb | BA 
C → C | ccB

ابتدا قوانین B را جایگذین میکنیم

A → aa | bb | BA 				
B → bb | BA 
C → C | ccbb |  ccBA

سپس قوانین A را جایگذین میکنیم

A → aa | bb |BA 				
B → bb | Baa |  Bbb | BBA 
C → C | ccbb |  ccBA

حال مشاهده می‌کنید که هر سه متغیر رشته تولید می‌کنند.

foreach (String item in ListVariable)
    for (int i = 0; i < gvTemp.RowCount - 1; i++)
    {
        String StartState = gvTemp.Rows[i].Cells[0].Value.ToString();
        String EndState = gvTemp.Rows[i].Cells[2].Value.ToString();
        if (F_IsTerminate(EndState))
            for (int j = 0; j < gvTemp.RowCount - 1; j++)
            {
                String EndCurrent = gvTemp.Rows[j].Cells[2].Value.ToString();
                gvTemp.Rows[j].Cells[2].Value = EndCurrent.Replace(StartState, EndState);
            }
    } 

ادامه و مثال در مستندات....