Masud_Sir/top_down_parsing.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "This code uses a recursive function to implement a top-down\n",
    "parser for a given grammar. The grammar is defined as a\n",
    "dictionary, where the keys are the non-terminal symbols\n",
    "and the values are lists of their possible expansions. The\n",
    "input sentence is defined as a list of tokens, and the\n",
    "starting symbol is defined as a variable. The top-down\n",
    "parse function takes in a symbol and an input, and it\n",
    "recursively expands the non-terminal symbols using the\n",
    "grammar. If the entire sentence was successfully parsed,\n",
    "the remaining input should be an empty list\n",
    "\"\"\"\n",
    "\n",
    "# Define the grammar in the form of a dictionary\n",
    "# The keys are the non-terminal symbols, and the values are lists of their possible expansions\n",
    "grammar = {\n",
    "    'S': [['NP', 'VP']],\n",
    "    'NP': [['Det', 'Noun'], ['PN']],\n",
    "    'VP': [['Verb', 'NP'], ['Verb']],\n",
    "    'Det': [['the'], ['a']],\n",
    "    'Noun': [['cat'], ['dog'], ['man'], ['woman']],\n",
    "    'PN': [['John'], ['Mary']],\n",
    "    'Verb': [['chases'], ['likes'], ['hates']]\n",
    "}\n",
    "\n",
    "# Define the input sentence as a list of tokens\n",
    "sentence = ['John', 'hates', 'the', 'woman']\n",
    "\n",
    "# Define the starting symbol\n",
    "start = 'S'\n",
    "\n",
    "# Define the function that implements the recursive top-down parsing\n",
    "def top_down_parse(symbol, input):\n",
    "    # Base case: if the symbol is a terminal, check if it matches the current input token\n",
    "    if symbol in ['the', 'a', 'cat', 'dog', 'man', 'woman', 'John', 'Mary', 'chases', 'likes', 'hates']:\n",
    "        if symbol == input[0]:\n",
    "            return input[1:]\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "    # Recursive case: if the symbol is a non-terminal, expand it using the grammar\n",
    "    elif symbol in grammar:\n",
    "        for expansion in grammar[symbol]:\n",
    "            # Make a copy of the input so that we can backtrack\n",
    "            remaining_input = input.copy()\n",
    "\n",
    "            # Recursively parse the expansion\n",
    "            for sub_symbol in expansion:\n",
    "                remaining_input = top_down_parse(sub_symbol, remaining_input)\n",
    "\n",
    "                # If any of the recursive calls returned None, backtrack\n",
    "                if remaining_input is None:\n",
    "                    break\n",
    "\n",
    "            # If the entire expansion was successfully parsed, return the remaining input\n",
    "            if remaining_input is not None:\n",
    "                return remaining_input\n",
    "\n",
    "    # If the symbol is neither a terminal nor a non-terminal, or if the expansion failed, return None\n",
    "    return None\n",
    "\n",
    "# Call the parsing function with the starting symbol and the input sentence\n",
    "remaining_input = top_down_parse(start, sentence)\n",
    "\n",
    "# If the entire sentence was successfully parsed, the remaining input should be an empty list\n",
    "if not remaining_input:\n",
    "    print(\"Input is valid\")\n",
    "else:\n",
    "    print(\"Error: invalid input\")\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.11.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}