Masud_Sir/constructing_LL(1)_parsing_Alternative.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#for printing terminals, non_terminals and their entries in Parsing_table\n",
    "def print_(table):\n",
    "    print_rules(rules);       \n",
    "    print_FFset(firstSet,True);   \n",
    "    print_FFset(followSet,False); \n",
    "    terminals=set()\n",
    "    for nt in rules.keys():\n",
    "        terminals=terminals.union(firstSet[nt])\n",
    "        terminals=terminals.union(followSet[nt])\n",
    "    terminals.discard('eps')\n",
    "    print(\"\\nNon Terminals:\\n\",rules.keys())  \n",
    "    print(\"\\nTerminals:\\n\",terminals)                   \n",
    "    print(\"\\n\\nTable entries are:\\n\")\n",
    "    for row,col in table.items():\n",
    "        print(row,':',col)    \n",
    "    print()\n",
    "    return\n",
    "\n",
    "\n",
    "def get_parsing_table(firstSet,followSet,rules):\n",
    "    parsing_table=defaultdict()\n",
    "    table=defaultdict()   #just for printing in good way (can be done by parsing_table too)\n",
    "    for key,rule in rules.items():\n",
    "        for sub_rule in rule:\n",
    "            symbol = sub_rule[0]\n",
    "            if isNonTerminal(symbol,rules): \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",
    "    print_(table)  #for printing terminals, non_terminals and their entries in Parsing_table\n",
    "    return parsing_table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parser(p_table,start_state):\n",
    "    expr = list(map(str,input(\"Enter expression for prasing(Plz enter space between 2 entry)\\n\").split())) \n",
    "    if expr[-1] != '$':\n",
    "        print(\"\\nPlease add '$' at the end of expression. Try again\")\n",
    "        return\n",
    "    print(\"\\nyour expression is\",expr)\n",
    "    stack=['$'];stack.append(start_state)\n",
    "    inp=0\n",
    "    while(stack and expr[inp]):\n",
    "        popped = stack.pop()\n",
    "        while (popped=='eps'):  #when popped is epsilon then again pop\n",
    "            popped = stack.pop()\n",
    "        if popped != expr[inp]:\n",
    "            if p_table.get((popped,expr[inp])): #for checking, this entry is in table or not ?\n",
    "                rule = p_table.get((popped,expr[inp])).get(popped)  # 2D dict table is again 1D dict with that rule\n",
    "                for x in range(len(rule)):   \n",
    "                    stack.append(rule[-x-1])     # minus for reversing \n",
    "            else:\n",
    "                print(\"\\nError, the expression is wrong. Try again\")\n",
    "                return\n",
    "        else:\n",
    "            inp+=1\n",
    "        if stack[0]==expr[inp]:\n",
    "            flag=True\n",
    "            break\n",
    "            \n",
    "    if flag:\n",
    "        print(\"\\nExpression accepted\")\n",
    "    else:\n",
    "        print(\"\\nExpression rejected, it can't be generated from this grammar\")\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "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,rules):\n",
    "    if symbol in rules.keys():#all keys of rules are Non terminals\n",
    "        return True\n",
    "    return False\n",
    "\n",
    "\n",
    "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,rules): #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\n",
    "\n",
    "\n",
    "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,rules): #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],rules):\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\n",
    "\n",
    "\n",
    "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",
    "    parsing_table = get_parsing_table(deepcopy(firstSet),deepcopy(followSet),rules)\n",
    "    parser(parsing_table,start_state)\n",
    "    # print_(parsing_table)\n",
    "    \n"
   ]
  }
 ],
 "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.11.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}