lab_06.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "lab_06.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyOt60px2ZqDk0Ks9pNQaivw",
      "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_06.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# gram = {}\n",
        "# def add(str):                               \n",
        "#     x = str.split(\"->\")\n",
        "#     y = x[1]\n",
        "#     x.pop()\n",
        "#     z = y.split(\"|\")\n",
        "#     x.append(z)\n",
        "#     gram[x[0]]=x[1]\n",
        "\n",
        "def removeDirectLR(gramA, A):\n",
        "\ttemp = gramA[A]\n",
        "\ttempCr = []\n",
        "\ttempInCr = []\n",
        "\tfor i in temp:\n",
        "\t\tif i[0] == A:\n",
        "      # add the key to dictionaryKeys\n",
        "\t\t\ttempInCr.append(i[1:]+[A+\"'\"])\n",
        "\t\telse:\n",
        "\t\t\ttempCr.append(i+[A+\"'\"])\n",
        "\t #'e' means ϵ (epsalion)\n",
        "\ttempInCr.append([\"e\"]) \n",
        "\tgramA[A] = tempCr\n",
        "\tgramA[A+\"'\"] = tempInCr\n",
        "\treturn gramA\n",
        "\n",
        "#  grammar,grammar2,visited = {},{},[]\n",
        "# while True:\n",
        "# \tn = int(input(\"[1] Add a non terminal. [2] Add a production rule. [3] Check for left recursion\\n\"))\n",
        "# \tif n == 1:\n",
        "# \t\tnonterminal = input(\"Enter a non terminal : \")\n",
        "# \t\tgrammar[nonterminal] = []\n",
        "# \tif n == 2:\n",
        "# \t\ttry :\n",
        "# \t\t\tnonterminal = input(\"Enter the non terminal  : \")\n",
        "# \t\t\tproduction = input(\"Enter the production : \")\n",
        "# \t\t\tgrammar[nonterminal].append(production)\n",
        "# \t\texcept KeyError:print(\"Non Terminal isn't present in the grammar\\n\")\n",
        "# \tif n == 3:break\n",
        "# if present:\n",
        "# \t\ttemp, grammar2[k+\"\\'\"] = [],[]\n",
        "# \t\tfor v in grammar[k]:\n",
        "# \t\t\tif v[0]==k:grammar2[k+\"\\'\"].append(v[1:]+k+\"\\'\") \n",
        "# \t\t\telse:temp.append(v+k+\"\\'\")\n",
        "# \t\tgrammar2[k+\"\\'\"].append(\"E\")\n",
        "# \t\tgrammar[k] = temp\n",
        "# \tvisited.append(k)\n",
        "\n",
        "def checkForIndirect(gramA, a, ai):\n",
        "\tif ai not in gramA:\n",
        "\t\treturn False\n",
        "\tif a == ai:\n",
        "\t\treturn True\n",
        "\tfor i in gramA[ai]:\n",
        "\t\tif i[0] == ai:\n",
        "\t\t\treturn False\n",
        "\t\tif i[0] in gramA:\n",
        "\t\t\treturn checkForIndirect(gramA, a, i[0])\n",
        "\treturn False\n",
        "\n",
        "def rep(gramA, A):\n",
        "\ttemp = gramA[A]\n",
        "\tnewTemp = []\n",
        "\tfor i in temp:\n",
        "\t\tif checkForIndirect(gramA, A, i[0]):\n",
        "\t\t\tt = []\n",
        "\t\t\tfor k in gramA[i[0]]:\n",
        "\t\t\t\tt=[]\n",
        "\t\t\t\tt+=k\n",
        "\t\t\t\tt+=i[1:]\n",
        "\t\t\t\tnewTemp.append(t)\n",
        "\n",
        "\t\telse:\n",
        "\t\t\tnewTemp.append(i)\n",
        "\tgramA[A] = newTemp\n",
        "\treturn gramA\n",
        "\n",
        "def rem(gram):\n",
        "\tc = 1\n",
        "\tconv = {}\n",
        "\tgramA = {}\n",
        "\trevconv = {}\n",
        "\tfor j in gram:\n",
        "\t\tconv[j] = \"A\"+str(c)\n",
        "\t\tgramA[\"A\"+str(c)] = []\n",
        "\t\tc+=1\n",
        "\n",
        "\tfor i in gram:\n",
        "\t\tfor j in gram[i]:\n",
        "\t\t\ttemp = []\n",
        "\t\t\tfor k in j:\n",
        "\t\t\t\tif k in conv:\n",
        "\t\t\t\t\ttemp.append(conv[k])\n",
        "\t\t\t\telse:\n",
        "\t\t\t\t\ttemp.append(k)\n",
        "\t\t\tgramA[conv[i]].append(temp)\n",
        "\n",
        "\tfor i in range(c-1,0,-1):\n",
        "\t\tai = \"A\"+str(i)\n",
        "\t\tfor j in range(0,i):\n",
        "\t\t\taj = gramA[ai][0][0]\n",
        "\t\t\tif ai!=aj :\n",
        "\t\t\t\tif aj in gramA and checkForIndirect(gramA,ai,aj):\n",
        "\t\t\t\t\tgramA = rep(gramA, ai)\n",
        "\n",
        "\tfor i in range(1,c):\n",
        "\t\tai = \"A\"+str(i)\n",
        "\t\tfor j in gramA[ai]:\n",
        "\t\t\tif ai==j[0]:\n",
        "\t\t\t\tgramA = removeDirectLR(gramA, ai)\n",
        "\t\t\t\tbreak\n",
        "\n",
        "# if present:\n",
        "# \t\ttemp, grammar2[k+\"\\'\"] = [],[]\n",
        "# \t\tfor v in grammar[k]:\n",
        "# \t\t\tif v[0]==k:grammar2[k+\"\\'\"].append(v[1:]+k+\"\\'\") \n",
        "# \t\t\telse:temp.append(v+k+\"\\'\")\n",
        "# \t\tgrammar2[k+\"\\'\"].append(\"E\")\n",
        "# \t\tgrammar[k] = temp\n",
        "# \tvisited.append(k)\n",
        "\n",
        "\top = {}\n",
        "\tfor i in gramA:\n",
        "\t\ta = str(i)\n",
        "\t\tfor j in conv:\n",
        "\t\t\ta = a.replace(conv[j],j)\n",
        "\t\trevconv[i] = a\n",
        "\n",
        "\tfor i in gramA:\n",
        "\t\tl = []\n",
        "\t\tfor j in gramA[i]:\n",
        "\t\t\tk = []\n",
        "\t\t\tfor m in j:\n",
        "\t\t\t\tif m in revconv:\n",
        "\t\t\t\t\tk.append(m.replace(m,revconv[m]))\n",
        "\t\t\t\telse:\n",
        "\t\t\t\t\tk.append(m)\n",
        "\t\t\tl.append(k)\n",
        "\t\top[revconv[i]] = l\n",
        "\n",
        "\treturn op\n",
        "# E= T+E|T\n",
        "# T= F*T|F\n",
        "# F= a|b|c\n",
        "gram = {\n",
        "    \"E\":[\"E+T\",\"T\"]\n",
        "}\n",
        "result = rem(gram)\n",
        "\n",
        "for i in result:\n",
        "    print(f'{i}->{result[i]}')\n",
        "\n",
        "    # for trans_item in trans_desc:\n",
        "    #     trans_item = trans_item.split(\",\")\n",
        "\n",
        "    #     i = int(trans_item[0])\n",
        "    #     j = int(trans_item[1])\n",
        "    #     k = int(trans_item[2])\n",
        "        \n",
        "    #     #i,0,j\n",
        "    #     #i,1,k\n",
        " \n",
        "    #     p1 = (i,0)\n",
        "    #     p2 = (i,1)\n",
        "\n",
        "    #     transitionFn[p1] = j\n",
        "    #     transitionFn[p2] = k\n",
        "\n",
        "\n",
        "    # acc_strings = dfa_description.split(\"#\")[1].split(\",\")\n",
        "    # accept_states = []\n",
        "\n",
        "    # for acc_string in acc_strings:\n",
        "    #     accept_states.append(int(acc_string))\n",
        "\n",
        "\n",
        "    # LFT = LFT(accept_states, transitionFn)\n",
        "    # return LFT\n",
        "    # for i in result:\n",
        "    # print(f'{i}->{result[i]}')\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "qm7nn-pvF5cj",
        "outputId": "73ddd42b-f68e-43cc-b71d-cb46a63ddeda"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "E->[['T', \"E'\"]]\n",
            "E'->[['+', 'T', \"E'\"], ['e']]\n"
          ]
        }
      ]
    }
  ]
}