LL(1)_parsingTable_Parser.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {},
   "outputs": [],
   "source": [
    "#for printing terminals, non_terminals and their entries in Parsing_table\n",
    "def print_(table):\n",
    "    ffs.print_rules(rules);       \n",
    "    ffs.print_FFset(firstSet,True);   \n",
    "    ffs.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 ffs.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": 155,
   "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": 164,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Rules are:\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",
      "First sets are:\n",
      "E = {'id', '('}\n",
      "T = {'id', '('}\n",
      "F = {'id', '('}\n",
      "E1 = {'eps', '+', '-'}\n",
      "T1 = {'/', '*', 'eps', '^'}\n",
      "\n",
      "Follow sets are:\n",
      "E = {')', '$'}\n",
      "T = {')', '-', '+', '$'}\n",
      "F = {'/', '+', ')', '^', '-', '*', '$'}\n",
      "E1 = {')', '$'}\n",
      "T1 = {')', '$', '+', '-'}\n",
      "\n",
      "Non Terminals:\n",
      " dict_keys(['E', 'T', 'F', 'E1', 'T1'])\n",
      "\n",
      "Terminals:\n",
      " {'+', '/', 'id', '(', ')', '^', '-', '*', '$'}\n",
      "\n",
      "\n",
      "Table entries are:\n",
      "\n",
      "('E', 'id') : E-> T E1\n",
      "('E', '(') : E-> T E1\n",
      "('T', 'id') : T-> F T1\n",
      "('T', '(') : T-> F T1\n",
      "('F', 'id') : F-> id\n",
      "('F', '(') : F-> ( E )\n",
      "('E1', '+') : E1-> + T E1\n",
      "('E1', '-') : E1-> - T E1\n",
      "('E1', ')') : E1-> eps\n",
      "('E1', '$') : E1-> eps\n",
      "('T1', '*') : T1-> * F T1\n",
      "('T1', '/') : T1-> / F T1\n",
      "('T1', ')') : T1-> eps\n",
      "('T1', '+') : T1-> eps\n",
      "('T1', '$') : T1-> eps\n",
      "('T1', '-') : T1-> eps\n",
      "('T1', '^') : T1-> ^ F T1\n",
      "\n",
      "Enter expression for prasing\n",
      "id + id $\n",
      "\n",
      "your expression is ['id', '+', 'id', '$']\n",
      "\n",
      "Expression accepted\n"
     ]
    }
   ],
   "source": [
    "import First_Follow_sets as ffs  \n",
    "from collections import defaultdict\n",
    "from copy import deepcopy\n",
    "if __name__==\"__main__\":\n",
    "    \n",
    "    rules,start_state=ffs.get_rules()\n",
    "    firstSet = ffs.get_first_set(rules)\n",
    "    followSet = ffs.get_follow_set(rules,deepcopy(firstSet),start_state)\n",
    "    parsing_table = get_parsing_table(deepcopy(firstSet),deepcopy(followSet),rules)\n",
    "    parser(parsing_table,start_state)\n",
    "#     print(parsing_table)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter expression for prasing\n",
      "id + id - id \n",
      "\n",
      "Please add '$' at the end of expression. Try again\n"
     ]
    }
   ],
   "source": [
    "parser(parsing_table,start_state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter expression for prasing\n",
      "id + id id * id $\n",
      "\n",
      "your expression is ['id', '+', 'id', 'id', '*', 'id', '$']\n",
      "\n",
      "Error, the expression is wrong. Try again\n"
     ]
    }
   ],
   "source": [
    "parser(parsing_table,start_state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 161,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter expression for prasing\n",
      "id + id ^ / * id + id $\n",
      "\n",
      "your expression is ['id', '+', 'id', '^', '/', '*', 'id', '+', 'id', '$']\n",
      "\n",
      "Error, the expression is wrong. Try again\n"
     ]
    }
   ],
   "source": [
    "parser(parsing_table,start_state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 162,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter expression for prasing\n",
      "id + id id * id ^ id $\n",
      "\n",
      "your expression is ['id', '+', 'id', 'id', '*', 'id', '^', 'id', '$']\n",
      "\n",
      "Error, the expression is wrong. Try again\n"
     ]
    }
   ],
   "source": [
    "parser(parsing_table,start_state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter expression for prasing\n",
      "id + id / id * id ^ id - id + id / id * id $\n",
      "\n",
      "your expression is ['id', '+', 'id', '/', 'id', '*', 'id', '^', 'id', '-', 'id', '+', 'id', '/', 'id', '*', 'id', '$']\n",
      "\n",
      "Expression accepted\n"
     ]
    }
   ],
   "source": [
    "parser(parsing_table,start_state)"
   ]
  },
  {
   "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
}