CD_Mini_Project_Final.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "e5VR7EMvxQBn"
      },
      "source": [
        "## Problem Statement"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9WoYSbW9xXrh"
      },
      "source": [
        "Q9. Design compiler for the following hypothetical languages"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 254,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "4JKM61Ypw88G",
        "outputId": "875cb80a-1a18-4f15-c180-e383c1cbcb3a"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Overwriting question.txt\n"
          ]
        }
      ],
      "source": [
        "%%writefile question.txt\n",
        "int main()\n",
        "begin\n",
        " int n;\n",
        " do\n",
        "  expr=expr+expr;\n",
        "  n=exp;\n",
        " while(exp)\n",
        " return(n)\n",
        "end"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "03KtITARxT9o"
      },
      "source": [
        "## Lexical Analyzer"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 255,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "fZ8jsstcvxsS",
        "outputId": "09a7d02a-b230-440d-cfa4-0666c2f300fd"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "------------------------ LEXICAL ANALYZER - TOKENIZER -----------------------\n",
            "At line 1\n",
            "Content: int main()\n",
            "\n",
            "Tokens found: \n",
            "+----------+-----------+\n",
            "| Lexeme   | Token     |\n",
            "+==========+===========+\n",
            "| int      | Keyword   |\n",
            "+----------+-----------+\n",
            "| main     | Keyword   |\n",
            "+----------+-----------+\n",
            "| (        | Delimiter |\n",
            "+----------+-----------+\n",
            "| )        | Delimiter |\n",
            "+----------+-----------+\n",
            "\n",
            "----------------------------------------------------\n",
            "At line 2\n",
            "Content: begin\n",
            "\n",
            "Tokens found: \n",
            "+----------+---------+\n",
            "| Lexeme   | Token   |\n",
            "+==========+=========+\n",
            "| begin    | Keyword |\n",
            "+----------+---------+\n",
            "\n",
            "----------------------------------------------------\n",
            "At line 3\n",
            "Content:  int n;\n",
            "\n",
            "Tokens found: \n",
            "+----------+------------+\n",
            "| Lexeme   | Token      |\n",
            "+==========+============+\n",
            "| int      | Keyword    |\n",
            "+----------+------------+\n",
            "| n        | Identifier |\n",
            "+----------+------------+\n",
            "| ;        | Delimiter  |\n",
            "+----------+------------+\n",
            "\n",
            "----------------------------------------------------\n",
            "At line 4\n",
            "Content:  do\n",
            "\n",
            "Tokens found: \n",
            "+----------+---------+\n",
            "| Lexeme   | Token   |\n",
            "+==========+=========+\n",
            "| do       | Keyword |\n",
            "+----------+---------+\n",
            "\n",
            "----------------------------------------------------\n",
            "At line 5\n",
            "Content:   expr=expr+expr;\n",
            "\n",
            "Tokens found: \n",
            "+----------+---------------------+\n",
            "| Lexeme   | Token               |\n",
            "+==========+=====================+\n",
            "| expr     | Identifier          |\n",
            "+----------+---------------------+\n",
            "| =        | Assignment Operator |\n",
            "+----------+---------------------+\n",
            "| expr     | Identifier          |\n",
            "+----------+---------------------+\n",
            "| +        | Arithmetic Operator |\n",
            "+----------+---------------------+\n",
            "| expr     | Identifier          |\n",
            "+----------+---------------------+\n",
            "| ;        | Delimiter           |\n",
            "+----------+---------------------+\n",
            "\n",
            "----------------------------------------------------\n",
            "At line 6\n",
            "Content:   n=exp;\n",
            "\n",
            "Tokens found: \n",
            "+----------+---------------------+\n",
            "| Lexeme   | Token               |\n",
            "+==========+=====================+\n",
            "| n        | Identifier          |\n",
            "+----------+---------------------+\n",
            "| =        | Assignment Operator |\n",
            "+----------+---------------------+\n",
            "| exp      | Identifier          |\n",
            "+----------+---------------------+\n",
            "| ;        | Delimiter           |\n",
            "+----------+---------------------+\n",
            "\n",
            "----------------------------------------------------\n",
            "At line 7\n",
            "Content:  while(exp)\n",
            "\n",
            "Tokens found: \n",
            "+----------+------------+\n",
            "| Lexeme   | Token      |\n",
            "+==========+============+\n",
            "| while    | Keyword    |\n",
            "+----------+------------+\n",
            "| (        | Delimiter  |\n",
            "+----------+------------+\n",
            "| exp      | Identifier |\n",
            "+----------+------------+\n",
            "| )        | Delimiter  |\n",
            "+----------+------------+\n",
            "\n",
            "----------------------------------------------------\n",
            "At line 8\n",
            "Content:  return(n)\n",
            "\n",
            "Tokens found: \n",
            "+----------+------------+\n",
            "| Lexeme   | Token      |\n",
            "+==========+============+\n",
            "| return   | Keyword    |\n",
            "+----------+------------+\n",
            "| (        | Delimiter  |\n",
            "+----------+------------+\n",
            "| n        | Identifier |\n",
            "+----------+------------+\n",
            "| )        | Delimiter  |\n",
            "+----------+------------+\n",
            "\n",
            "----------------------------------------------------\n",
            "At line 9\n",
            "Content: end\n",
            "\n",
            "Tokens found: \n",
            "+----------+---------+\n",
            "| Lexeme   | Token   |\n",
            "+==========+=========+\n",
            "| end      | Keyword |\n",
            "+----------+---------+\n",
            "\n",
            "----------------------------------------------------\n",
            "At line 10\n",
            "Content: \n",
            "\n",
            "Tokens found: \n",
            "+----------+---------+\n",
            "| Lexeme   | Token   |\n",
            "+==========+=========+\n",
            "+----------+---------+\n",
            "\n",
            "----------------------------------------------------\n",
            "\n",
            "Global Token Table: \n",
            "+------------+----------+---------------------+-----------+\n",
            "|   Token No | Lexeme   | Token               |   Line No |\n",
            "+============+==========+=====================+===========+\n",
            "|          1 | int      | Keyword             |         1 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|          2 | main     | Keyword             |         1 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|          3 | (        | Delimiter           |         1 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|          4 | )        | Delimiter           |         1 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|          5 | begin    | Keyword             |         2 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|          6 | int      | Keyword             |         3 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|          7 | n        | Identifier          |         3 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|          8 | ;        | Delimiter           |         3 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|          9 | do       | Keyword             |         4 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|         10 | expr     | Identifier          |         5 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|         11 | =        | Assignment Operator |         5 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|         12 | expr     | Identifier          |         5 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|         13 | +        | Arithmetic Operator |         5 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|         14 | expr     | Identifier          |         5 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|         15 | ;        | Delimiter           |         5 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|         16 | n        | Identifier          |         6 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|         17 | =        | Assignment Operator |         6 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|         18 | exp      | Identifier          |         6 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|         19 | ;        | Delimiter           |         6 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|         20 | while    | Keyword             |         7 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|         21 | (        | Delimiter           |         7 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|         22 | exp      | Identifier          |         7 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|         23 | )        | Delimiter           |         7 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|         24 | return   | Keyword             |         8 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|         25 | (        | Delimiter           |         8 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|         26 | n        | Identifier          |         8 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|         27 | )        | Delimiter           |         8 |\n",
            "+------------+----------+---------------------+-----------+\n",
            "|         28 | end      | Keyword             |         9 |\n",
            "+------------+----------+---------------------+-----------+\n"
          ]
        }
      ],
      "source": [
        "import re\n",
        "from tabulate import tabulate\n",
        "\n",
        "delimiters=[\" \",\"+\",\"-\",\"*\",\"/\",\"=\",\";\",\"(\",\")\",\"[\",\"]\",\"{\",\"}\",\"<\",\">\",\"!\",\"&\",\"|\",\"^\",\"%\",\"~\",\"?\",\".\",\",\",\"'\",\"\\\"\"]\n",
        "keywords=['int','main','begin','end','do','while','return']\n",
        "\n",
        "kwd_dict={\n",
        "    \"int\":\"t\",\n",
        "    \"main\":\"m()\",\n",
        "    \"begin\":\"b\",\n",
        "    \"end\":\"d\",\n",
        "    \"do\":\"do\",\n",
        "    \"while\":\"w\",\n",
        "    \"return\":\"r\",\n",
        "    \"+\":\"o\",\n",
        "    \"-\":\"o\",\n",
        "    \"*\":\"o\",\n",
        "    \"/\":\"o\",\n",
        "    \"=\":\"a\",\n",
        "    \"expr\":\"e\",\n",
        "    \"exp\":\"e\",\n",
        "    \"n\":\"id\"\n",
        "}\n",
        "\n",
        "def isKeyword(token):\n",
        "    if token in keywords:\n",
        "        return True\n",
        "    return False\n",
        "\n",
        "def isDelimiter(ch):\n",
        "    if ch in delimiters:\n",
        "        return True\n",
        "    return False\n",
        "\n",
        "print(\"------------------------ LEXICAL ANALYZER - TOKENIZER -----------------------\")\n",
        "tokentable_global=[]\n",
        "tokentable_global.append([\"Token No\",\"Lexeme\",\"Token\",\"Line No\"])\n",
        "txt=open(\"question.txt\",\"r\")\n",
        "tokens=txt.read()\n",
        "count=0\n",
        "tkncount=0\n",
        "delimit_flag=0\n",
        "program = tokens.split(\"\\n\")\n",
        "\n",
        "for line in program:\n",
        "    err=0\n",
        "    prevct=tkncount\n",
        "    count = count + 1\n",
        "    tokentable_local=[]\n",
        "    print(f\"At line {count}\\nContent: {line}\\n\")\n",
        "\n",
        "    tokens=line\n",
        "    tokens=re.findall(r\"[A-Za-z0-9_]+|[0-9]+|[(){}]|\\S\", tokens)\n",
        "\n",
        "    print(\"Tokens found: \")\n",
        "    tokentable=[]\n",
        "    tokentable.append([\"Lexeme\",\"Token\"])\n",
        "    for token in tokens:\n",
        "        if isDelimiter(token):\n",
        "            if token in [\"{\",\"}\",\"(\",\")\",\";\",\",\"]:\n",
        "                tkncount+=1\n",
        "                tokentable.append([token,\"Delimiter\"])\n",
        "                tokentable_local.append([tkncount,token,\"Delimiter\",count])\n",
        "                \n",
        "            elif token in [\"+\",\"-\",\"*\",\"/\",\"=\"]:\n",
        "              if token in [\"+\",\"-\",\"*\",\"/\"]:\n",
        "                tkncount+=1\n",
        "                tokentable.append([token,\"Arithmetic Operator\"])\n",
        "                tokentable_local.append([tkncount,token,\"Arithmetic Operator\",count])\n",
        "                \n",
        "              elif token in [\"=\"]:\n",
        "                tkncount+=1\n",
        "                tokentable.append([token,\"Assignment Operator\"])\n",
        "                tokentable_local.append([tkncount,token,\"Assignment Operator\",count])\n",
        "                \n",
        "            else:\n",
        "                tokentable.append([token,\"Invalid Character [Error]\"])\n",
        "                print(\"Error Recovery: Line Ignored\")\n",
        "                err=1\n",
        "                break\n",
        "            continue\n",
        "        else:\n",
        "\n",
        "            if isKeyword(token):\n",
        "                tkncount+=1\n",
        "                tokentable.append([token,\"Keyword\"])\n",
        "                tokentable_local.append([tkncount,token,\"Keyword\",count])\n",
        "                \n",
        "            else:\n",
        "                if token.isnumeric():\n",
        "                    tkncount+=1\n",
        "                    tokentable.append([token,\"Number\"])\n",
        "                    tokentable_local.append([tkncount,token,\"Number\",count])\n",
        "                    \n",
        "                else:        \n",
        "                    if re.match(\"^[a-zA-Z][a-zA-Z0-9_]*\", token) is not None:\n",
        "                        tkncount+=1\n",
        "                        tokentable.append([token,\"Identifier\"])\n",
        "                        tokentable_local.append([tkncount,token,\"Identifier\",count])\n",
        "\n",
        "                    else:\n",
        "                        tokentable.append([token,\"Invalid Character [Error]\"])\n",
        "                        print(\"Error Recovery: Line Ignored\")\n",
        "                        err=1\n",
        "                        break\n",
        "    delimit_flag=0                    \n",
        "    if err != 1:\n",
        "      for entry in tokentable_local:\n",
        "        tokentable_global.append(entry)\n",
        "    else:\n",
        "      tkncount=prevct\n",
        "\n",
        "    print(tabulate(tokentable, headers=\"firstrow\", tablefmt=\"grid\"))\n",
        "    print(\"\\n----------------------------------------------------\")\n",
        "\n",
        "print(\"\\nGlobal Token Table: \")\n",
        "print(tabulate(tokentable_global, headers=\"firstrow\", tablefmt=\"grid\"))\n",
        "\n",
        "# For the parser tool\n",
        "mth_flag=0\n",
        "with open('tokens.txt', 'w') as f:\n",
        "    str_to_load=\"\"\n",
        "    for token in tokentable_global[1:]:\n",
        "        if mth_flag > 0:\n",
        "            mth_flag-=1\n",
        "            continue\n",
        "        sym=kwd_dict.get(token[1]) if kwd_dict.get(token[1]) is not None else token[1]\n",
        "        str_to_load+=str(sym)+\" \"\n",
        "        if token[1] == \"main\":\n",
        "            mth_flag=2\n",
        "    f.write(f\"{str_to_load}\\n\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3b1B1YNY2h7X"
      },
      "source": [
        "## Parser"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Defining functions for the parser"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 256,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rAdmq2nY_C6I",
        "outputId": "dc51aa9b-48ae-46a5-946c-39e6ae4b7a49"
      },
      "outputs": [],
      "source": [
        "import re\n",
        "from tabulate import tabulate\n",
        "\n",
        "def removeLeftRecursion(rulesDiction):\n",
        "    store = {}\n",
        "    for lhs in rulesDiction:\n",
        "        alphaRules = []\n",
        "        betaRules = []\n",
        "        allrhs = rulesDiction[lhs]\n",
        "        for subrhs in allrhs:\n",
        "            if subrhs[0] == lhs:\n",
        "                alphaRules.append(subrhs[1:])\n",
        "            else:\n",
        "                betaRules.append(subrhs)\n",
        "        if len(alphaRules) != 0:\n",
        "            lhs_ = lhs + \"'\"\n",
        "            while (lhs_ in rulesDiction.keys()) \\\n",
        "                    or (lhs_ in store.keys()):\n",
        "                lhs_ += \"'\"\n",
        "            for b in range(0, len(betaRules)):\n",
        "                betaRules[b].append(lhs_)\n",
        "            rulesDiction[lhs] = betaRules\n",
        "            for a in range(0, len(alphaRules)):\n",
        "                alphaRules[a].append(lhs_)\n",
        "            alphaRules.append(['#'])\n",
        "            store[lhs_] = alphaRules\n",
        "    for left in store:\n",
        "        rulesDiction[left] = store[left]\n",
        "    return rulesDiction\n",
        "\n",
        "\n",
        "def LeftFactoring(rulesDiction):\n",
        "    newDict = {}\n",
        "    for lhs in rulesDiction:\n",
        "        allrhs = rulesDiction[lhs]\n",
        "        temp = dict()\n",
        "        for subrhs in allrhs:\n",
        "            if subrhs[0] not in list(temp.keys()):\n",
        "                temp[subrhs[0]] = [subrhs]\n",
        "            else:\n",
        "                temp[subrhs[0]].append(subrhs)\n",
        "        new_rule = []\n",
        "        tempo_dict = {}\n",
        "        for term_key in temp:\n",
        "            allStartingWithTermKey = temp[term_key]\n",
        "            if len(allStartingWithTermKey) > 1:\n",
        "                lhs_ = lhs + \"'\"\n",
        "                while (lhs_ in rulesDiction.keys()) \\\n",
        "                        or (lhs_ in tempo_dict.keys()):\n",
        "                    lhs_ += \"'\"\n",
        "                new_rule.append([term_key, lhs_])\n",
        "                ex_rules = []\n",
        "                for g in temp[term_key]:\n",
        "                    ex_rules.append(g[1:])\n",
        "                tempo_dict[lhs_] = ex_rules\n",
        "            else:\n",
        "                new_rule.append(allStartingWithTermKey[0])\n",
        "        newDict[lhs] = new_rule\n",
        "        for key in tempo_dict:\n",
        "            newDict[key] = tempo_dict[key]\n",
        "    return newDict\n",
        "\n",
        "\n",
        "def first(rule):\n",
        "    global rules, nonterm_userdef, \\\n",
        "        term_userdef, diction, firsts\n",
        "    if len(rule)!= 0 and (rule is not None):\n",
        "        if rule[0] in term_userdef:\n",
        "            return rule[0]\n",
        "        elif rule[0] == '#':\n",
        "            return '#'\n",
        "\n",
        "    if len(rule)!= 0:\n",
        "        if rule[0] in list(diction.keys()):\n",
        "            fres = []\n",
        "            rhs_rules = diction[rule[0]]\n",
        "            for itr in rhs_rules:\n",
        "                indivRes = first(itr)\n",
        "                if type(indivRes) is list:\n",
        "                    for i in indivRes:\n",
        "                        fres.append(i)\n",
        "                else:\n",
        "                    fres.append(indivRes)\n",
        "\n",
        "            if '#' not in fres:\n",
        "                return fres\n",
        "            else:\n",
        "                newList = []\n",
        "                fres.remove('#')\n",
        "                if len(rule) > 1:\n",
        "                    ansNew = first(rule[1:])\n",
        "                    if ansNew != None:\n",
        "                        if type(ansNew) is list:\n",
        "                            newList = fres + ansNew\n",
        "                        else:\n",
        "                            newList = fres + [ansNew]\n",
        "                    else:\n",
        "                        newList = fres\n",
        "                    return newList\n",
        "                fres.append('#')\n",
        "                return fres\n",
        "\n",
        "\n",
        "def follow(nt):\n",
        "    global start_symbol, rules, nonterm_userdef,term_userdef, diction, firsts, follows\n",
        "\n",
        "    solset = set()\n",
        "    if nt == start_symbol:\n",
        "        solset.add('$')\n",
        "\n",
        "    for curNT in diction:\n",
        "        rhs = diction[curNT]\n",
        "        for subrule in rhs:\n",
        "            if nt in subrule:\n",
        "                while nt in subrule:\n",
        "                    index_nt = subrule.index(nt)\n",
        "                    subrule = subrule[index_nt + 1:]\n",
        "                    if len(subrule) != 0:\n",
        "                        res = first(subrule)\n",
        "                        if '#' in res:\n",
        "                            newList = []\n",
        "                            res.remove('#')\n",
        "                            ansNew = follow(curNT)\n",
        "                            if ansNew != None:\n",
        "                                if type(ansNew) is list:\n",
        "                                    newList = res + ansNew\n",
        "                                else:\n",
        "                                    newList = res + [ansNew]\n",
        "                            else:\n",
        "                                newList = res\n",
        "                            res = newList\n",
        "                    else:\n",
        "                        if nt != curNT:\n",
        "                            res = follow(curNT)\n",
        "\n",
        "                    if res is not None:\n",
        "                        if type(res) is list:\n",
        "                            for g in res:\n",
        "                                solset.add(g)\n",
        "                        else:\n",
        "                            solset.add(res)\n",
        "    return list(solset)\n",
        "\n",
        "\n",
        "def computeAllFirsts():\n",
        "    global rules, nonterm_userdef, term_userdef, diction, firsts\n",
        "    for rule in rules:\n",
        "        k = rule.split(\"->\")\n",
        "        k[0] = k[0].strip()\n",
        "        k[1] = k[1].strip()\n",
        "        rhs = k[1]\n",
        "        multirhs = rhs.split('|')\n",
        "        for i in range(len(multirhs)):\n",
        "            multirhs[i] = multirhs[i].strip()\n",
        "            multirhs[i] = multirhs[i].split()\n",
        "        diction[k[0]] = multirhs\n",
        "\n",
        "    print(f\"\\nRules: \\n\")\n",
        "    for y in diction:\n",
        "        print(f\"{y}->{diction[y]}\")\n",
        "\n",
        "    diction = removeLeftRecursion(diction)\n",
        "\n",
        "    diction = LeftFactoring(diction)\n",
        "\n",
        "    for y in list(diction.keys()):\n",
        "        t = set()\n",
        "        for sub in diction.get(y):\n",
        "            res = first(sub)\n",
        "            if res != None:\n",
        "                if type(res) is list:\n",
        "                    for u in res:\n",
        "                        t.add(u)\n",
        "                else:\n",
        "                    t.add(res)\n",
        "\n",
        "        firsts[y] = t\n",
        "\n",
        "    print(\"\\nCalculated firsts: \")\n",
        "    key_list = list(firsts.keys())\n",
        "    index = 0\n",
        "    for gg in firsts:\n",
        "        print(f\"first({key_list[index]}) \"\n",
        "              f\"=> {firsts.get(gg)}\")\n",
        "        index += 1\n",
        "\n",
        "def computeAllFollows():\n",
        "    global start_symbol, rules, nonterm_userdef,\\\n",
        "        term_userdef, diction, firsts, follows\n",
        "    for NT in diction:\n",
        "        solset = set()\n",
        "        sol = follow(NT)\n",
        "        if sol is not None:\n",
        "            for g in sol:\n",
        "                solset.add(g)\n",
        "        follows[NT] = solset\n",
        "\n",
        "    print(\"\\nCalculated follows: \")\n",
        "    key_list = list(follows.keys())\n",
        "    index = 0\n",
        "    for gg in follows:\n",
        "        print(f\"follow({key_list[index]})\"\n",
        "              f\" => {follows[gg]}\")\n",
        "        index += 1\n",
        "\n",
        "\n",
        "def createParseTable():\n",
        "    import copy\n",
        "    global diction, firsts, follows, term_userdef\n",
        "    \n",
        "    print(\"\\nFirsts and Follow Result table\\n\")\n",
        "\n",
        "    mx_len_first = 0\n",
        "    mx_len_fol = 0\n",
        "    for u in diction:\n",
        "        k1 = len(str(firsts[u]))\n",
        "        k2 = len(str(follows[u]))\n",
        "        if k1 > mx_len_first:\n",
        "            mx_len_first = k1\n",
        "        if k2 > mx_len_fol:\n",
        "            mx_len_fol = k2\n",
        "\n",
        "    firstfollow_table=[]\n",
        "    firstfollow_table.append([\"Non-Terminal\",\"First\",\"Follow\"])\n",
        "    \n",
        "    for u in diction:\n",
        "        firstfollow_table.append([u,str(firsts[u]),str(follows[u])])\n",
        "        \n",
        "    print(tabulate(firstfollow_table, headers=\"firstrow\", tablefmt=\"grid\"))\n",
        "\n",
        "    ntlist = list(diction.keys())\n",
        "    terminals = copy.deepcopy(term_userdef)\n",
        "    terminals.append('$')\n",
        "\n",
        "    mat = []\n",
        "    for x in diction:\n",
        "        row = []\n",
        "        for y in terminals:\n",
        "            row.append('')\n",
        "        mat.append(row)\n",
        "\n",
        "    grammar_is_LL = True\n",
        "\n",
        "    for lhs in diction:\n",
        "        rhs = diction[lhs]\n",
        "        for y in rhs:\n",
        "            res = first(y)\n",
        "            if '#' in res:\n",
        "                if type(res) == str:\n",
        "                    firstFollow = []\n",
        "                    fol_op = follows[lhs]\n",
        "                    if fol_op is str:\n",
        "                        firstFollow.append(fol_op)\n",
        "                    else:\n",
        "                        for u in fol_op:\n",
        "                            firstFollow.append(u)\n",
        "                    res = firstFollow\n",
        "                else:\n",
        "                    res.remove('#')\n",
        "                    res = list(res) +\\\n",
        "                        list(follows[lhs])\n",
        "            ttemp = []\n",
        "            if type(res) is str:\n",
        "                ttemp.append(res)\n",
        "                res = copy.deepcopy(ttemp)\n",
        "            for c in res:\n",
        "                xnt = ntlist.index(lhs)\n",
        "                yt = terminals.index(c)\n",
        "                if mat[xnt][yt] == '':\n",
        "                    mat[xnt][yt] = mat[xnt][yt] \\\n",
        "                        + f\"{lhs}->{' '.join(y)}\"\n",
        "                else:\n",
        "                    if f\"{lhs}->{y}\" in mat[xnt][yt]:\n",
        "                        continue\n",
        "                    else:\n",
        "                        grammar_is_LL = False\n",
        "                        mat[xnt][yt] = mat[xnt][yt] \\\n",
        "                            + f\",{lhs}->{' '.join(y)}\"\n",
        "\n",
        "    parse_table=[]\n",
        "    print(\"\\nGenerated parsing table:\\n\")\n",
        "    \n",
        "    frmt = \"{:>15}\" * len(terminals)\n",
        "    parse_table.append([\"\"]+terminals)\n",
        "    \n",
        "    for i in range(len(mat)):\n",
        "        parse_table.append([ntlist[i]]+mat[i])\n",
        "\n",
        "    print(tabulate(parse_table, headers=\"firstrow\", tablefmt=\"grid\"))\n",
        "    \n",
        "    return (mat, grammar_is_LL, terminals)\n",
        "\n",
        "\n",
        "def validateStringUsingStackBuffer(parsing_table, grammarll1,\n",
        "                                   table_term_list, input_string,\n",
        "                                   term_userdef, start_symbol):\n",
        "\n",
        "\n",
        "    print(f\"\\nValidating program:\\nOutput from Lexer: \\n{input_string}\\n\")\n",
        "\n",
        "    if grammarll1 == False:\n",
        "        return f\"\\nInput String = \" \\\n",
        "            f\"\\\"{input_string}\\\"\\n\" \\\n",
        "            f\"Grammar is not LL(1)\"\n",
        "\n",
        "    stack = [start_symbol, '$']\n",
        "    buffer = []\n",
        "\n",
        "    input_string = input_string.split()\n",
        "    input_string.reverse()\n",
        "    buffer = ['$'] + input_string\n",
        "\n",
        "    eval_table=[]\n",
        "    eval_table.append([\"Input\",\"Stack\",\"Action\"])\n",
        "\n",
        "    print(\"Evaluating Program Code: \")\n",
        "\n",
        "    err=0\n",
        "    while True:\n",
        "        if stack == ['$'] and buffer == ['$']:\n",
        "            eval_table.append([' '.join(buffer),\n",
        "                               ' '.join(stack),\n",
        "                               \"Valid\"])\n",
        "            print(tabulate(eval_table, headers=\"firstrow\", tablefmt=\"grid\"))  \n",
        "            return \"\\nValid String!\"\n",
        "        elif stack[0] not in term_userdef:\n",
        "            x = list(diction.keys()).index(stack[0])\n",
        "            y = table_term_list.index(buffer[-1])\n",
        "            if parsing_table[x][y] != '':\n",
        "                entry = parsing_table[x][y]\n",
        "                eval_table.append([' '.join(buffer),\n",
        "                                   ' '.join(stack),\n",
        "                                    f\"T[{stack[0]}][{buffer[-1]}] = {entry}\"])\n",
        "            \n",
        "                lhs_rhs = entry.split(\"->\")\n",
        "                lhs_rhs[1] = lhs_rhs[1].replace('#', '').strip()\n",
        "                entryrhs = lhs_rhs[1].split()\n",
        "                stack = entryrhs + stack[1:]\n",
        "            else:\n",
        "                # Panic mode recovery\n",
        "                eval_table.append([' '.join(buffer),\n",
        "                                   ' '.join(stack),\n",
        "                              f\"\\nNo rule at \" \\\n",
        "                    f\"Table[{stack[0]}][{buffer[-1]}]. [Skipped]\"])\n",
        "                stack = stack[1:]\n",
        "                \n",
        "        else:\n",
        "            if stack[0] == buffer[-1]:\n",
        "                eval_table.append([' '.join(buffer),\n",
        "                                   ' '.join(stack),\n",
        "                              f\"Matched:{stack[0]}\"])\n",
        "                \n",
        "                buffer = buffer[:-1]\n",
        "                stack = stack[1:]\n",
        "            else:\n",
        "                # Panic mode recovery\n",
        "                eval_table.append([' '.join(buffer),\n",
        "                                   ' '.join(stack),\n",
        "                              f\"Unmatched terminal symbol [Skipped]\"])\n",
        "                if err==0:\n",
        "                    err+=1\n",
        "                    stack = stack[1:]\n",
        "                else:\n",
        "                    err-=1\n",
        "                    buffer = buffer[:-1]               \n",
        "    \n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Main function"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 257,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "\n",
            "Rules: \n",
            "\n",
            "S->[['A', 'B']]\n",
            "A->[['t', 'm()']]\n",
            "B->[['b', 'M', 'W', 'r', '(', 'id', ')', 'd']]\n",
            "M->[['t', 'id', ';'], ['#']]\n",
            "E1->[['e', 'a', 'e', 'o', 'e', ';'], ['#']]\n",
            "E2->[['id', 'a', 'e', ';'], ['#']]\n",
            "W->[['do', 'E1', 'E2', 'w', '(', 'e', ')'], ['#']]\n",
            "\n",
            "Calculated firsts: \n",
            "first(S) => {'t'}\n",
            "first(A) => {'t'}\n",
            "first(B) => {'b'}\n",
            "first(M) => {'t', '#'}\n",
            "first(E1) => {'e', '#'}\n",
            "first(E2) => {'id', '#'}\n",
            "first(W) => {'do', '#'}\n",
            "\n",
            "Calculated follows: \n",
            "follow(S) => {'$'}\n",
            "follow(A) => {'b'}\n",
            "follow(B) => {'$'}\n",
            "follow(M) => {'do', 'r'}\n",
            "follow(E1) => {'id', 'w'}\n",
            "follow(E2) => {'w'}\n",
            "follow(W) => {'r'}\n",
            "\n",
            "Firsts and Follow Result table\n",
            "\n",
            "+----------------+-------------+-------------+\n",
            "| Non-Terminal   | First       | Follow      |\n",
            "+================+=============+=============+\n",
            "| S              | {'t'}       | {'$'}       |\n",
            "+----------------+-------------+-------------+\n",
            "| A              | {'t'}       | {'b'}       |\n",
            "+----------------+-------------+-------------+\n",
            "| B              | {'b'}       | {'$'}       |\n",
            "+----------------+-------------+-------------+\n",
            "| M              | {'t', '#'}  | {'do', 'r'} |\n",
            "+----------------+-------------+-------------+\n",
            "| E1             | {'e', '#'}  | {'id', 'w'} |\n",
            "+----------------+-------------+-------------+\n",
            "| E2             | {'id', '#'} | {'w'}       |\n",
            "+----------------+-------------+-------------+\n",
            "| W              | {'do', '#'} | {'r'}       |\n",
            "+----------------+-------------+-------------+\n",
            "\n",
            "Generated parsing table:\n",
            "\n",
            "+----+-----------+-------+---------------------+-----+------+-----------------+-----+-----+--------------+-----+---------------------+-------+-----+-----+-----+\n",
            "|    | t         | m()   | b                   | d   | r    | e               | o   | ;   | id           | a   | do                  | w     | (   | )   | $   |\n",
            "+====+===========+=======+=====================+=====+======+=================+=====+=====+==============+=====+=====================+=======+=====+=====+=====+\n",
            "| S  | S->A B    |       |                     |     |      |                 |     |     |              |     |                     |       |     |     |     |\n",
            "+----+-----------+-------+---------------------+-----+------+-----------------+-----+-----+--------------+-----+---------------------+-------+-----+-----+-----+\n",
            "| A  | A->t m()  |       |                     |     |      |                 |     |     |              |     |                     |       |     |     |     |\n",
            "+----+-----------+-------+---------------------+-----+------+-----------------+-----+-----+--------------+-----+---------------------+-------+-----+-----+-----+\n",
            "| B  |           |       | B->b M W r ( id ) d |     |      |                 |     |     |              |     |                     |       |     |     |     |\n",
            "+----+-----------+-------+---------------------+-----+------+-----------------+-----+-----+--------------+-----+---------------------+-------+-----+-----+-----+\n",
            "| M  | M->t id ; |       |                     |     | M-># |                 |     |     |              |     | M->#                |       |     |     |     |\n",
            "+----+-----------+-------+---------------------+-----+------+-----------------+-----+-----+--------------+-----+---------------------+-------+-----+-----+-----+\n",
            "| E1 |           |       |                     |     |      | E1->e a e o e ; |     |     | E1->#        |     |                     | E1-># |     |     |     |\n",
            "+----+-----------+-------+---------------------+-----+------+-----------------+-----+-----+--------------+-----+---------------------+-------+-----+-----+-----+\n",
            "| E2 |           |       |                     |     |      |                 |     |     | E2->id a e ; |     |                     | E2-># |     |     |     |\n",
            "+----+-----------+-------+---------------------+-----+------+-----------------+-----+-----+--------------+-----+---------------------+-------+-----+-----+-----+\n",
            "| W  |           |       |                     |     | W-># |                 |     |     |              |     | W->do E1 E2 w ( e ) |       |     |     |     |\n",
            "+----+-----------+-------+---------------------+-----+------+-----------------+-----+-----+--------------+-----+---------------------+-------+-----+-----+-----+\n",
            "\n",
            "Validating program:\n",
            "Output from Lexer: \n",
            "t m() b t id ; do e a e o e ; id a e ; w ( e ) r ( id ) d \n",
            "\n",
            "Evaluating Program Code: \n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| Input                                                       | Stack                               | Action                         |\n",
            "+=============================================================+=====================================+================================+\n",
            "| $ d ) id ( r ) e ( w ; e a id ; e o e a e do ; id t b m() t | S $                                 | T[S][t] = S->A B               |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id ; e o e a e do ; id t b m() t | A B $                               | T[A][t] = A->t m()             |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id ; e o e a e do ; id t b m() t | t m() B $                           | Matched:t                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id ; e o e a e do ; id t b m()   | m() B $                             | Matched:m()                    |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id ; e o e a e do ; id t b       | B $                                 | T[B][b] = B->b M W r ( id ) d  |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id ; e o e a e do ; id t b       | b M W r ( id ) d $                  | Matched:b                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id ; e o e a e do ; id t         | M W r ( id ) d $                    | T[M][t] = M->t id ;            |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id ; e o e a e do ; id t         | t id ; W r ( id ) d $               | Matched:t                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id ; e o e a e do ; id           | id ; W r ( id ) d $                 | Matched:id                     |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id ; e o e a e do ;              | ; W r ( id ) d $                    | Matched:;                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id ; e o e a e do                | W r ( id ) d $                      | T[W][do] = W->do E1 E2 w ( e ) |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id ; e o e a e do                | do E1 E2 w ( e ) r ( id ) d $       | Matched:do                     |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id ; e o e a e                   | E1 E2 w ( e ) r ( id ) d $          | T[E1][e] = E1->e a e o e ;     |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id ; e o e a e                   | e a e o e ; E2 w ( e ) r ( id ) d $ | Matched:e                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id ; e o e a                     | a e o e ; E2 w ( e ) r ( id ) d $   | Matched:a                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id ; e o e                       | e o e ; E2 w ( e ) r ( id ) d $     | Matched:e                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id ; e o                         | o e ; E2 w ( e ) r ( id ) d $       | Matched:o                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id ; e                           | e ; E2 w ( e ) r ( id ) d $         | Matched:e                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id ;                             | ; E2 w ( e ) r ( id ) d $           | Matched:;                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id                               | E2 w ( e ) r ( id ) d $             | T[E2][id] = E2->id a e ;       |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a id                               | id a e ; w ( e ) r ( id ) d $       | Matched:id                     |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e a                                  | a e ; w ( e ) r ( id ) d $          | Matched:a                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ; e                                    | e ; w ( e ) r ( id ) d $            | Matched:e                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w ;                                      | ; w ( e ) r ( id ) d $              | Matched:;                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e ( w                                        | w ( e ) r ( id ) d $                | Matched:w                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e (                                          | ( e ) r ( id ) d $                  | Matched:(                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r ) e                                            | e ) r ( id ) d $                    | Matched:e                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r )                                              | ) r ( id ) d $                      | Matched:)                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id ( r                                                | r ( id ) d $                        | Matched:r                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id (                                                  | ( id ) d $                          | Matched:(                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d ) id                                                    | id ) d $                            | Matched:id                     |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d )                                                       | ) d $                               | Matched:)                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $ d                                                         | d $                                 | Matched:d                      |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "| $                                                           | $                                   | Valid                          |\n",
            "+-------------------------------------------------------------+-------------------------------------+--------------------------------+\n",
            "\n",
            "Valid String!\n"
          ]
        }
      ],
      "source": [
        "sample_input_string = \"\"\n",
        "\n",
        "rules=[\"S -> A B\",\n",
        "       \"A -> t m()\",\n",
        "       \"B -> b M W r ( id ) d\",\n",
        "       \"M -> t id ; | #\",\n",
        "       \"E1 -> e a e o e ; | #\",\n",
        "       \"E2 -> id a e ; | #\",\n",
        "       \"W -> do E1 E2 w ( e ) | #\"]\n",
        "\n",
        "nonterm_userdef=['S','A','B','M','E1','E2','W']\n",
        "term_userdef=['t','m()','b','d','r','e','o',';','id','a','do','w','(',')']\n",
        "\n",
        "sample_input_string=str_to_load\n",
        "\n",
        "#Sending output to parser from a file (generated by lexer)\n",
        "#inps = ''\n",
        "#with open('tokens.txt', 'r+') as f:\n",
        "#    for line in f.readlines():\n",
        "#        inps += line\n",
        "#sample_input_string = inps\n",
        "\n",
        "diction = {}\n",
        "firsts = {}\n",
        "follows = {}\n",
        "\n",
        "computeAllFirsts()\n",
        "\n",
        "start_symbol = list(diction.keys())[0]\n",
        "\n",
        "computeAllFollows()\n",
        "\n",
        "(parsing_table, result, tabTerm) = createParseTable()\n",
        "\n",
        "if sample_input_string != None:\n",
        "    validity = validateStringUsingStackBuffer(parsing_table, result,\n",
        "                                              tabTerm, sample_input_string,\n",
        "                                              term_userdef, start_symbol)\n",
        "    print(validity)\n",
        "\n",
        "else:\n",
        "    print(\"\\nNo input string detected\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## End of notebook"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "<i>For Compiler Design - 19CS702</i>"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "provenance": []
    },
    "gpuClass": "standard",
    "kernelspec": {
      "display_name": "Python 3.8.3 ('base')",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.8.3"
    },
    "orig_nbformat": 4,
    "vscode": {
      "interpreter": {
        "hash": "a97d73cf4d3c620710d0675ddbf59f5c73663c170048a80b2327a12cc135e5e1"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}