Masud_Sir/predictive_parser.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://www.geeksforgeeks.org/predictive-parser-in-compiler-design/  <br><br>\n",
    "https://www.tutorialspoint.com/construct-a-predictive-parsing-table-for-the-following-grammar-and-also-check-whether-string-id-plus-id-id-is-accepted-or-not"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Some helper functions\n",
    "def print_iter(Matched,Stack,Input,Action,verbose=True):\n",
    "    if verbose==True:\n",
    "        print(\".\".join(Matched).ljust(30),\" | \",\".\".join(Stack).ljust(25),\" | \",\".\".join(Input).ljust(30),\" | \",Action)\n",
    "#The predictive parsing algorithm\n",
    "def predictive_parsing(sentence,parsingtable,terminals,start_state=\"S\",verbose=True):      #Set verbose to false to not see the stages of the algorithm\n",
    "    status = None\n",
    "    match = []\n",
    "    stack = [start_state,\"$\"]\n",
    "    Inp = sentence.split(\".\")\n",
    "    if verbose==True:\n",
    "        print_iter([\"Matched\"],[\"Stack\"],[\"Input\"],\"Action\")\n",
    "    print_iter(match,stack,Inp,\"Initial\",verbose)\n",
    "    action=[]\n",
    "    while(len(sentence)>0 and status!=False):\n",
    "        top_of_input = Inp[0]\n",
    "        pos = top_of_input\n",
    "        if stack[0] ==\"$\" and pos == \"$\" :\n",
    "            print_iter(match,stack,Inp,\"Accepted\",verbose)\n",
    "            return \"Accepted\"\n",
    "        if stack[0] == pos:\n",
    "            print_iter(match,stack,Inp,\"Pop\",verbose)\n",
    "            match.append(stack[0])\n",
    "            del(stack[0])\n",
    "            del(Inp[0])\n",
    "            continue\n",
    "        if stack[0]==\"epsilon\":\n",
    "            print_iter(match,stack,Inp,\"Poping Epsilon\",verbose)\n",
    "            del(stack[0])\n",
    "            continue\n",
    "        try:\n",
    "            production=parsingtable[stack[0]][pos]\n",
    "            print_iter(match,stack,Inp,stack[0]+\" -> \"+production,verbose)\n",
    "        except:\n",
    "            return \"error for \"+str(stack[0])+\" on \"+str(pos),\"Not Accepted\"\n",
    "\n",
    "        new = production.split(\".\")   \n",
    "        stack=new+stack[1:]\n",
    "    return \"Not Accepted\"\n",
    "\n",
    "if __name__==\"__main__\":\n",
    "    #Example for the working of the predictive parsing :-\n",
    "    #input for the grammar : E->TE1;E1->+TE1|epsilon;T->FT1 ...\n",
    "    parsingtable = {\n",
    "    \"E\" : {\"id\" : \"T.E1\", \"(\" : \"T.E1\"},\n",
    "    \"E1\" : {\"+\":\"+.T.E1\", \")\":\"epsilon\", \"$\" : \"epsilon\"},\n",
    "    \"T\" : {\"id\" : \"F.T1\", \"(\" : \"F.T1\" },\n",
    "    \"T1\" : {\"+\" : \"epsilon\", \"*\" : \"*.F.T1\", \")\" : \"epsilon\", \"$\" : \"epsilon\"},\n",
    "    \"F\":{\"id\":\"id\",\"(\":\"(.E.)\"}\n",
    "    }\n",
    "    terminals = [\"id\",\"(\",\")\",\"+\",\"*\"]\n",
    "    print(predictive_parsing(sentence=\"id.+.(.id.+.id.).$\",parsingtable=parsingtable,terminals=terminals,start_state=\"E\",verbose=True))\n",
    "    #Another Example done in class:-\n",
    "    print(predictive_parsing(sentence=\"c.c.c.c.d.d.$\",parsingtable={\"S\" : {\"c\":\"C.C\",\"d\":\"C.C\"},\"C\":{\"c\":\"c.C\",\"d\":\"d\"}},terminals=[\"c,d\"],start_state=\"S\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def numr(c):\n",
    "    switcher = {\n",
    "        'S': 0,\n",
    "        'A': 1,\n",
    "        'B': 2,\n",
    "        'C': 3,\n",
    "        'a': 0,\n",
    "        'b': 1,\n",
    "        'c': 2,\n",
    "        'd': 3,\n",
    "        '$': 4\n",
    "    }\n",
    "    return switcher.get(c, 2)\n",
    "\n",
    "def main():\n",
    "    table = [[' ' for _ in range(6)] for _ in range(5)]\n",
    "    \n",
    "    prol = [\"S\", \"A\", \"A\", \"B\", \"B\", \"C\", \"C\"]\n",
    "    pror = [\"A\", \"Bb\", \"Cd\", \"aB\", \"@\", \"Cc\", \"@\"]\n",
    "    prod = [\"S->A\", \"A->Bb\", \"A->Cd\", \"B->aB\", \"B->@\", \"C->Cc\", \"C->@\"]\n",
    "    first = [\"abcd\", \"ab\", \"cd\", \"a@\", \"@\", \"c@\", \"@\"]\n",
    "    follow = [\"$\", \"$\", \"$\", \"a$\", \"b$\", \"c$\", \"d$\"]\n",
    "\n",
    "    print(\"\\nThe following is the predictive parsing table for the following grammar:\")\n",
    "    for p in prod:\n",
    "        print(p)\n",
    "\n",
    "    print(\"\\nPredictive parsing table is\")\n",
    "    for i in range(7):\n",
    "        k = min(len(first[i]), 10)  # Use the minimum length\n",
    "        for j in range(k):\n",
    "            if first[i][j] != '@':\n",
    "                table[numr(prol[i][0]) + 1][numr(first[i][j]) + 1] = prod[i]\n",
    "\n",
    "    for i in range(7):\n",
    "        if len(pror[i]) == 1:\n",
    "            if pror[i][0] == '@':\n",
    "                k = len(follow[i])\n",
    "                for j in range(k):\n",
    "                    table[numr(prol[i][0]) + 1][numr(follow[i][j]) + 1] = prod[i]\n",
    "\n",
    "    table[0][0] = \" \"\n",
    "    table[0][1] = \"a\"\n",
    "    table[0][2] = \"b\"\n",
    "    table[0][3] = \"c\"\n",
    "    table[0][4] = \"d\"\n",
    "    table[0][5] = \"$\"\n",
    "    table[1][0] = \"S\"\n",
    "    table[2][0] = \"A\"\n",
    "    table[3][0] = \"B\"\n",
    "    table[4][0] = \"C\"\n",
    "\n",
    "    print(\"\\n\" + \"-\" * 56)\n",
    "    for i in range(5):\n",
    "        for j in range(6):\n",
    "            print(f\"| {table[i][j]:^10}\", end=\"\")\n",
    "            if j == 5:\n",
    "                print(\"|\")\n",
    "                print(\"-\" * 56)\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    main()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Predictive Parser for the given grammar\n",
    "def predictive_parser(input_str):\n",
    "    global input_index, current_token\n",
    "    input_index = 0\n",
    "    current_token = \"\"\n",
    "\n",
    "    # Get the first token\n",
    "    get_next_token()\n",
    "\n",
    "    # Start parsing from the initial non-terminal\n",
    "    if E():\n",
    "        if current_token == '$':\n",
    "            print(\"String accepted by the grammar.\")\n",
    "        else:\n",
    "            print(\"String not fully parsed.\")\n",
    "    else:\n",
    "        print(\"String not accepted by the grammar.\")\n",
    "\n",
    "def get_next_token():\n",
    "    global input_index, current_token\n",
    "    if input_index < len(input_str):\n",
    "        current_token = input_str[input_index]\n",
    "        input_index += 1\n",
    "    else:\n",
    "        current_token = '$'  # End of input marker\n",
    "\n",
    "# Grammar rules\n",
    "def E():\n",
    "    print(\"E -> TE'\")\n",
    "    if T():\n",
    "        if E_prime():\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "def E_prime():\n",
    "    global current_token\n",
    "    if current_token == '+':\n",
    "        print(\"E' -> +TE'\")\n",
    "        get_next_token()\n",
    "        if T():\n",
    "            if E_prime():\n",
    "                return True\n",
    "    else:\n",
    "        print(\"E' -> 0\")\n",
    "    return True\n",
    "\n",
    "def T():\n",
    "    print(\"T -> FT'\")\n",
    "    if F():\n",
    "        if T_prime():\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "def T_prime():\n",
    "    global current_token\n",
    "    if current_token == '*':\n",
    "        print(\"T' -> *FT'\")\n",
    "        get_next_token()\n",
    "        if F():\n",
    "            if T_prime():\n",
    "                return True\n",
    "    else:\n",
    "        print(\"T' -> 0\")\n",
    "    return True\n",
    "\n",
    "def F():\n",
    "    global current_token\n",
    "    if current_token == '(':\n",
    "        print(\"F -> (E)\")\n",
    "        get_next_token()\n",
    "        if E():\n",
    "            if current_token == ')':\n",
    "                get_next_token()\n",
    "                return True\n",
    "    elif current_token.isalpha() or current_token.isdigit():\n",
    "        print(\"F -> id\")\n",
    "        get_next_token()\n",
    "        return True\n",
    "    return False\n",
    "\n",
    "# Example usage\n",
    "input_str = \"id * (id + id)\"\n",
    "predictive_parser(input_str)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# #example for direct left recursion\n",
    "# gram = {\"A\":[\"Aa\",\"Ab\",\"c\",\"d\"]\n",
    "# }\n",
    "#example for indirect left recursion\n",
    "gram = {\n",
    "    \"E\":[\"E+T\",\"T\"],\n",
    "    \"T\":[\"T*F\",\"F\"],\n",
    "    \"F\":[\"(E)\",\"i\"]\n",
    "}\n",
    "\n",
    "def removeDirectLR(gramA, A):\n",
    "    \"\"\"gramA is dictonary\"\"\"\n",
    "    temp = gramA[A]\n",
    "    tempCr = []\n",
    "    tempInCr = []\n",
    "    for i in temp:\n",
    "        if i[0] == A:\n",
    "            #tempInCr.append(i[1:])\n",
    "            tempInCr.append(i[1:]+[A+\"'\"])\n",
    "        else:\n",
    "            #tempCr.append(i)\n",
    "            tempCr.append(i+[A+\"'\"])\n",
    "    tempInCr.append([\"e\"])\n",
    "    gramA[A] = tempCr\n",
    "    gramA[A+\"'\"] = tempInCr\n",
    "    return gramA\n",
    "\n",
    "def checkForIndirect(gramA, a, ai):\n",
    "    if ai not in gramA:\n",
    "        return False \n",
    "    if a == ai:\n",
    "        return True\n",
    "    for i in gramA[ai]:\n",
    "        if i[0] == ai:\n",
    "            return False\n",
    "        if i[0] in gramA:\n",
    "            return checkForIndirect(gramA, a, i[0])\n",
    "    return False\n",
    "\n",
    "def rep(gramA, A):\n",
    "    temp = gramA[A]\n",
    "    newTemp = []\n",
    "    for i in temp:\n",
    "        if checkForIndirect(gramA, A, i[0]):\n",
    "            t = []\n",
    "            for k in gramA[i[0]]:\n",
    "                t=[]\n",
    "                t+=k\n",
    "                t+=i[1:]\n",
    "                newTemp.append(t)\n",
    "\n",
    "        else:\n",
    "            newTemp.append(i)\n",
    "    gramA[A] = newTemp\n",
    "    return gramA\n",
    "\n",
    "def rem(gram):\n",
    "    c = 1\n",
    "    conv = {}\n",
    "    gramA = {}\n",
    "    revconv = {}\n",
    "    for j in gram:\n",
    "        conv[j] = \"A\"+str(c)\n",
    "        gramA[\"A\"+str(c)] = []\n",
    "        c+=1\n",
    "\n",
    "    for i in gram:\n",
    "        for j in gram[i]:\n",
    "            temp = []   \n",
    "            for k in j:\n",
    "                if k in conv:\n",
    "                    temp.append(conv[k])\n",
    "                else:\n",
    "                    temp.append(k)\n",
    "            gramA[conv[i]].append(temp)\n",
    "\n",
    "    #print(gramA)\n",
    "    for i in range(c-1,0,-1):\n",
    "        ai = \"A\"+str(i)\n",
    "        for j in range(0,i):\n",
    "            aj = gramA[ai][0][0]\n",
    "            if ai!=aj :\n",
    "                if aj in gramA and checkForIndirect(gramA,ai,aj):\n",
    "                    gramA = rep(gramA, ai)\n",
    "\n",
    "    for i in range(1,c):\n",
    "        ai = \"A\"+str(i)\n",
    "        for j in gramA[ai]:\n",
    "            if ai==j[0]:\n",
    "                gramA = removeDirectLR(gramA, ai)\n",
    "                break\n",
    "\n",
    "    op = {}\n",
    "    for i in gramA:\n",
    "        a = str(i)\n",
    "        for j in conv:\n",
    "            a = a.replace(conv[j],j)\n",
    "        revconv[i] = a\n",
    "\n",
    "    for i in gramA:\n",
    "        l = []\n",
    "        for j in gramA[i]:\n",
    "            k = []\n",
    "            for m in j:\n",
    "                if m in revconv:\n",
    "                    k.append(m.replace(m,revconv[m]))\n",
    "                else:\n",
    "                    k.append(m)\n",
    "            l.append(k)\n",
    "        op[revconv[i]] = l\n",
    "\n",
    "    return op\n",
    "\n",
    "result = rem(gram)\n",
    "terminals = []\n",
    "for i in result:\n",
    "    for j in result[i]:\n",
    "        for k in j:\n",
    "            if k not in result:\n",
    "                terminals+=[k]\n",
    "terminals = list(set(terminals))\n",
    "#print(terminals)\n",
    "\n",
    "def first(gram, term):\n",
    "    a = []\n",
    "    if term not in gram:\n",
    "        return [term]\n",
    "    for i in gram[term]:\n",
    "        if i[0] not in gram:\n",
    "            a.append(i[0])\n",
    "        elif i[0] in gram:\n",
    "            a += first(gram, i[0])\n",
    "    return a\n",
    "\n",
    "firsts = {}\n",
    "for i in result:\n",
    "    firsts[i] = first(result,i)\n",
    "#   print(f'First({i}):',firsts[i])\n",
    "\n",
    "def follow(gram, term):\n",
    "    a = []\n",
    "    for rule in gram:\n",
    "        for i in gram[rule]:\n",
    "            if term in i:\n",
    "                temp = i\n",
    "                indx = i.index(term)\n",
    "                if indx+1!=len(i):\n",
    "                    if i[-1] in firsts:\n",
    "                        a+=firsts[i[-1]]\n",
    "                    else:\n",
    "                        a+=[i[-1]]\n",
    "                else:\n",
    "                    a+=[\"e\"]\n",
    "                if rule != term and \"e\" in a:\n",
    "                    a+= follow(gram,rule)\n",
    "    return a\n",
    "\n",
    "follows = {}\n",
    "for i in result:\n",
    "    follows[i] = list(set(follow(result,i)))\n",
    "    if \"e\" in follows[i]:\n",
    "        follows[i].pop(follows[i].index(\"e\"))\n",
    "    follows[i]+=[\"$\"]\n",
    "#   print(f'Follow({i}):',follows[i])\n",
    "\n",
    "resMod = {}\n",
    "for i in result:\n",
    "    l = []\n",
    "    for j in result[i]:\n",
    "        temp = \"\"\n",
    "        for k in j:\n",
    "            temp+=k\n",
    "        l.append(temp)\n",
    "    resMod[i] = l\n",
    "\n",
    "# create predictive parsing table\n",
    "tterm = list(terminals)\n",
    "tterm.pop(tterm.index(\"e\"))\n",
    "tterm+=[\"$\"]\n",
    "pptable = {}\n",
    "for i in result:\n",
    "    for j in tterm:\n",
    "        if j in firsts[i]:\n",
    "            pptable[(i,j)]=resMod[i[0]][0]\n",
    "        else:\n",
    "            pptable[(i,j)]=\"\"\n",
    "    if \"e\" in firsts[i]:\n",
    "        for j in tterm:\n",
    "            if j in follows[i]:\n",
    "                pptable[(i,j)]=\"e\"  \n",
    "pptable[(\"F\",\"i\")] = \"i\"\n",
    "toprint = f'{\"\": <10}'\n",
    "for i in tterm:\n",
    "    toprint+= f'|{i: <10}'\n",
    "print(toprint)\n",
    "for i in result:\n",
    "    toprint = f'{i: <10}'\n",
    "    for j in tterm:\n",
    "        if pptable[(i,j)]!=\"\":\n",
    "            toprint+=f'|{i+\"->\"+pptable[(i,j)]: <10}'\n",
    "        else:\n",
    "            toprint+=f'|{pptable[(i,j)]: <10}'\n",
    "    print(f'{\"-\":-<76}')\n",
    "    print(toprint)\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": 2
}