lab_08.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "lab_08.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "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_08.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "from collections import OrderedDict\n",
        "\n",
        "rules = [['S->EFGH'], \n",
        "         ['E->b'], \n",
        "         ['F->x'], \n",
        "         ['G->c'], \n",
        "         ['H->d'], \n",
        "         ['E->yz']]  # Raw grammar\n",
        "\n",
        "firsts = []  # Used as temp storage for firsts if needed\n",
        "\n",
        "# Ordered dictionary to maintain the order of saving in the dictionary\n",
        "# useful when doing the actual first finding in one pass.\n",
        "rules_dict = OrderedDict()  # Dictionary to store all the rules in the grammar\n",
        "firsts_dict = OrderedDict()  # Dictionary to store all the firsts\n",
        "\n",
        "def non_term_appender(firsts, rules):\n",
        "    \"\"\"Adds the non terminals on the left to the firsts_dict\"\"\"\n",
        "    for rule in rules:\n",
        "        if rule[0][0] not in firsts:\n",
        "            firsts.append(rule[0][0])\n",
        "            firsts_dict[rule[0][0]] = []\n",
        "\n",
        "# First terminal value search           \n",
        "number_of_rules = len(rules)\n",
        "rule_count = first_count = 0\n",
        "non_term_appender(firsts, rules)\n",
        "for first in firsts:\n",
        "    rules_dict[first] = rules[rule_count][0][3:]\n",
        "    rule_count += 1\n",
        "\n",
        "for rule in rules:\n",
        "    if rule[0][3].islower():\n",
        "        firsts_dict[rule[0][0]].extend(rule[0][3])\n",
        "# TODO try and re implement one pass, as an else condition in the above loop.\n",
        "for rule in rules:\n",
        "    if rule[0][3].isupper():\n",
        "        firsts_dict[rule[0][0]].extend(firsts_dict[rule[0][3]])\n",
        "print(\"Grammar: \",rules)\n",
        "\n",
        "for k in firsts_dict:\n",
        "    print(\"\\nFirst\", k,end=' --> ')\n",
        "    print(\"%s\" % firsts_dict[k])"
      ],
      "metadata": {
        "id": "aXgHVj8Lre59",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "bd5da5de-585d-42fa-aac2-86b63add0b2f"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Grammar:  [['S->EFGH'], ['E->b'], ['F->x'], ['G->c'], ['H->d'], ['E->yz']]\n",
            "\n",
            "First S --> ['b', 'y']\n",
            "\n",
            "First E --> ['b', 'y']\n",
            "\n",
            "First F --> ['x']\n",
            "\n",
            "First G --> ['c']\n",
            "\n",
            "First H --> ['d']\n"
          ]
        }
      ]
    }
  ]
}