First_Follow_sets.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_rules():\n",
    "    dic = defaultdict()\n",
    "    start_state='E'\n",
    "    dic={       #rules of grammar in LL(1) form\n",
    "        \"E\" : [ [\"T\",\"E1\"] ],\n",
    "        \"T\" : [ [\"F\",\"T1\"] ],\n",
    "        \"F\" : [ [\"id\"], [\"(\",\"E\",\")\"] ],\n",
    "        \"E1\": [ [\"+\",\"T\",\"E1\"], [\"-\",\"T\",\"E1\"], [\"eps\"] ],\n",
    "        \"T1\": [ [\"*\",\"F\",\"T1\"], [\"/\",\"F\",\"T1\"], [\"eps\"], [\"^\",\"F\",\"T1\"] ]\n",
    "    }\n",
    "    return dic,start_state\n",
    "\n",
    "\n",
    "def print_rules(rules):\n",
    "    print(\"\\nRules are:\")\n",
    "    for key,rule in rules.items():\n",
    "        print(key,end=\" => \")\n",
    "        for sub_rule in rule:\n",
    "            for symbol in sub_rule:\n",
    "                print(symbol,end=\" \")\n",
    "            print(' | ',end='')\n",
    "        print()\n",
    "    return\n",
    "        \n",
    "        \n",
    "def isNonTerminal(symbol):\n",
    "    if symbol in rules.keys():#all keys of rules are Non terminals\n",
    "        return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def first(rules,key,firstSet):\n",
    "    for rule in rules[key]:#for every rule of that Non-terminal\n",
    "        symbol=rule[0]\n",
    "        if not isNonTerminal(symbol): #for terminals (not False => True)\n",
    "            firstSet[key].add(symbol)\n",
    "        else:                         # for terminal \n",
    "            firstSet[key]=firstSet[key].union(first(rules,symbol,firstSet))\n",
    "    return firstSet[key]\n",
    "\n",
    "    \n",
    "def get_first_set(rules):#rules is defaultdict\n",
    "    firstSet=defaultdict(set)\n",
    "    for key in rules.keys():\n",
    "        firstSet[key]\n",
    "    for key,rule in rules.items():#for all rules\n",
    "        first(rules,key,firstSet)\n",
    "    return firstSet\n",
    "    \n",
    "\n",
    "def print_FFset(ffset,flag):#both first and follow as FFset\n",
    "    if flag:\n",
    "        print(\"\\nFirst sets are:\")\n",
    "    else:\n",
    "        print(\"\\nFollow sets are:\")\n",
    "    for key,value in ffset.items():\n",
    "        print(key,\"=\",value)\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def follow(rules,firstSet,followSet,non_ter):\n",
    "    # for case; any_non_ter => alpha non_ter beta ( alpha,beta belongsto NonTer or Ter ) \n",
    "    for new_non_ter,rule in rules.items(): #for all productions, 1-1 production\n",
    "        for sub_rule in rule:  #for one production_rules, 1-1 rule\n",
    "            for i in range(len(sub_rule)): #for one rule_symbols, 1-1 symbol\n",
    "                if sub_rule[i]==non_ter:\n",
    "                    if i+1 < len(sub_rule):#checking next symbol beta \n",
    "                        beta=sub_rule[i+1]# when beta is present\n",
    "#                         print(\"Y => alpha X beta as\",new_non_ter,'=>..',non_ter,beta)\n",
    "                        \n",
    "                        if isNonTerminal(beta): #add firstSet(beta) into followSet(non_ter)\n",
    "                            followSet[non_ter]=followSet[non_ter].union(firstSet[beta])\n",
    "                            followSet[non_ter].discard('eps') #trying to remove epsilon, if there is\n",
    "                        else:\n",
    "                            followSet[non_ter].add(beta)\n",
    "                            \n",
    "                        if 'eps' in firstSet[beta] and new_non_ter!=beta :#!= for avoiding infinite loop (for T; P=> +TP)\n",
    "                              followSet[non_ter]=followSet[non_ter].union(follow(rules,firstSet,followSet,new_non_ter))#add firstSet(beta) into followSet(non_ter)\n",
    "                    \n",
    "                    elif i+1 == len(sub_rule) and new_non_ter!=non_ter: # when beta is not there & != for avoiding infinite loop\n",
    "#                         print(\"Y => alpha X as\",new_non_ter,'=>..',non_ter)\n",
    "                        if isNonTerminal(sub_rule[i]):\n",
    "                            followSet[non_ter]=followSet[non_ter].union(follow(rules,firstSet,followSet,new_non_ter))\n",
    "                            \n",
    "    return followSet[non_ter]\n",
    "\n",
    "\n",
    "def get_follow_set(rules,firstSet,start_state):#rules and follow are defaultdicts.\n",
    "    followSet=defaultdict(set)\n",
    "    for non_ter in rules.keys():\n",
    "        if non_ter == start_state: #add terminal symbol\n",
    "            followSet[non_ter].add('$')\n",
    "        else:\n",
    "            followSet[non_ter]\n",
    "    \n",
    "    for non_ter in rules.keys():\n",
    "        follow(rules,firstSet,followSet,non_ter)\n",
    "    return followSet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# def get_parsing_table(firstSet,followSet,rules):\n",
    "#     parsing_table=defaultdict()\n",
    "#     print(\"\\nNon Terminals:\\n\",NON_TERMINALS)\n",
    "    \n",
    "#     terminals=set()\n",
    "#     for nt in NON_TERMINALS:\n",
    "#         terminals=terminals.union(firstSet[nt])\n",
    "#         terminals=terminals.union(followSet[nt])\n",
    "\n",
    "#     terminals.discard('eps')\n",
    "#     print(\"\\nTerminals:\\n\",terminals)\n",
    "        \n",
    "#     table=defaultdict()\n",
    "#     for key,rule in rules.items():\n",
    "#         for sub_rule in rule:\n",
    "#             symbol = sub_rule[0]\n",
    "#             if isNonTerminal(symbol):\n",
    "#                 for ter in firstSet[symbol]-{'eps'}:\n",
    "#                     parsing_table[key,ter]={key:sub_rule}\n",
    "#                     table[key,ter]=key+'-> '+' '.join(i for i in sub_rule)\n",
    "\n",
    "#             elif symbol==\"eps\" or symbol in deepcopy(firstSet[symbol]):\n",
    "#                 for ter in followSet[key]:\n",
    "#                     parsing_table[key,ter] = {key:['eps']}\n",
    "#                     table[key,ter]=key+'-> '+'eps'\n",
    "#             else:\n",
    "#                 parsing_table[key,symbol]={key:sub_rule}\n",
    "#                 table[key,symbol]=key+'-> '+' '.join(i for i in sub_rule)\n",
    "                        \n",
    "#     print(\"\\n\\nTable entries are:\\n\")\n",
    "#     for row,col in table.items():\n",
    "#         print(row,':',col)         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Rules are:\n",
      "E => T E1  | \n",
      "T => F T1  | \n",
      "F => t  | ( E )  | \n",
      "E1 => + T E1  | - T E1  | eps  | \n",
      "T1 => * F T1  | / F T1  | eps  | ^ F T1  | \n",
      "\n",
      "First sets are:\n",
      "E = {'t', '('}\n",
      "T = {'t', '('}\n",
      "F = {'t', '('}\n",
      "E1 = {'eps', '+', '-'}\n",
      "T1 = {'/', '*', '^', 'eps'}\n",
      "\n",
      "Follow sets are:\n",
      "E = {'$', ')'}\n",
      "T = {'$', ')', '+', '-'}\n",
      "F = {'^', '$', ')', '/', '*', '+', '-'}\n",
      "E1 = {'$', ')'}\n",
      "T1 = {'$', '-', '+', ')'}\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "from copy import deepcopy\n",
    "if __name__==\"__main__\":\n",
    "    \n",
    "    rules,start_state=get_rules()\n",
    "    firstSet = get_first_set(rules)\n",
    "    followSet = get_follow_set(rules,deepcopy(firstSet),start_state)\n",
    "    \n",
    "    print_rules(rules);       # print(\"Rules are:\\n\",rules,'\\n')\n",
    "    print_FFset(firstSet,True);   #print(\"\\nFirst sets are:\\n\",firstSet)\n",
    "    print_FFset(followSet,False);  # print(\"\\n\\nFollow sets are:\\n\",followSet)\n",
    "\n",
    "    \n",
    "#     get_parsing_table(deepcopy(firstSet),deepcopy(followSet),rules)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}