lab_07.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "lab_07.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyODaXdiYSXJk7bHGsfyBVVc",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/Shakilgithub20/Compiler-Construction-Lab/blob/main/lab_07.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "DXMoJFyhr-L8",
        "outputId": "0fc055e6-bc48-4e1c-a2dd-25c2ff4cf28a"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Enter the grammar: S->αβ|αγ\n",
            "S-> αS'\n",
            "S'-> β|γ\n"
          ]
        }
      ],
      "source": [
        "length=1000\n",
        "grammer=input('Enter the grammar: ')\n",
        "lhs=grammer[0]\n",
        "f=grammer[3:]\n",
        "rhs=f.split('|')\n",
        "\n",
        "grammar={lhs:rhs}\n",
        "\n",
        "def minimum_matched_string(a, b,len_a,len_b):\n",
        "    if len_a == 0 or len_b == 0:\n",
        "       return 0;\n",
        "    elif a[len_a-1] == b[len_b-1]:\n",
        "        return 1 + minimum_matched_string(a, b, len_a-1, len_b-1);\n",
        "    else:\n",
        "       return max(minimum_matched_string(a, b, len_a, len_b-1), minimum_matched_string(a, b, len_a-1, len_b));\n",
        "\n",
        "for key in grammar.copy():\n",
        "    item=grammar[key]\n",
        "    for i in range(0, len(item)-1):\n",
        "        for j in range(i, len(item)):\n",
        "            if i!=j:\n",
        "                # print(item[i], item[j], len(item[i]), len(item[j]))\n",
        "                l=minimum_matched_string(item[i],item[j],len(item[i]),len(item[j]))\n",
        "                if l>0:\n",
        "                    if length > l:\n",
        "                        length = l\n",
        "\n",
        "exp2=[]\n",
        "if length>0:\n",
        "     common_val=grammar[key][0][:length]\n",
        "     for i in range(len(grammar[key])):\n",
        "         if common_val in grammar[key][i]:\n",
        "             grammar[key][i]=grammar[key][i][length:]\n",
        "             exp2.append(grammar[key][i])\n",
        "             grammar[key][i]=''\n",
        "\n",
        "exp1=grammar[key]\n",
        "for i in range(len(exp1)):\n",
        "    if '' in exp1:\n",
        "        exp1.remove('')\n",
        "\n",
        "\n",
        "exp1.append(common_val+\"S'\")\t\n",
        "\n",
        "for i in exp2:\n",
        "    if i=='':\n",
        "        ind=exp2.index(i)\n",
        "        exp2[ind]='ε'\n",
        "        \n",
        "\n",
        "fi='S-> '\n",
        "fii='''S'-> '''\n",
        "\n",
        "for i in exp1:\n",
        "    fi+=i+'|'\n",
        "    \n",
        "for i in exp2:\n",
        "    fii+=i+'|'\n",
        "\n",
        "fi=fi[:-1]\n",
        "fii=fii[:-1]\n",
        "\n",
        "print(fi)\n",
        "print(fii)"
      ]
    }
  ]
}