chapter_8.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 252,
   "id": "be470370",
   "metadata": {},
   "outputs": [],
   "source": [
    "import nltk\n",
    "import re\n",
    "from nltk.corpus import *\n",
    "from collections import defaultdict, Counter\n",
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f6929ce",
   "metadata": {},
   "source": [
    "__☼ Recall Strunk and White's prohibition against sentence-initial however used to mean \"although\". Do a web search for however used at the start of the sentence. How widely used is this construction?__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "46712ed6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "However , the jury said it believes `` these two offices should be combined to achieve greater efficiency and reduce the cost of administration '' .\n",
      "however , the first belief stood for entire revision with a new third point added to the list .\n",
      "However , this would require a lengthening of the season from thirteen to fourteen weeks .\n",
      "However , Mr. Parichy and his bride will go to Vero Beach on their wedding trip , and will stay in the John G. Beadles' beach house .\n",
      "However , the confession , which was the only evidence against him , was retracted before the trial .\n",
      "However , three of the managers did say that they would agree to attend the proposed meeting if all of the other managers decided to attend .\n",
      "However , compared with March 1960 new car sales of 4,441 , this March was off 23 per cent .\n",
      "However , Peterson , president of Bell & Howell , warned 800 U.S. marketing leaders attending a national conference at the Ambassador , that the future will belong to the industrialist of creative and `` unconventional wisdom '' .\n",
      "However , it's a half-mile walk down a steep hill from our house to the bus , and it's too hard on my legs .\n",
      "However , one can argue that no such control is necessary as long as one pretends that the anti-trust laws are effective and rational .\n",
      "However , the positions of all parties and leaders were constantly shifting .\n",
      "however the President , who would like to woo the former Chinese province away from both Peking and Moscow , would promise Chen nothing more than an abstention by the U.S. if Outer Mongolia's admission comes to a vote .\n",
      "However , in the same three-month period , toll-road bonds , as a group , have bucked this trend .\n",
      "However , Biblical scholars frequently attested to its numerous inaccuracies , as old manuscripts were uncovered and scholarship advanced .\n",
      "However , an initial perusal and comparison of some of the famous passages with the same parts of other versions seems to speak well of the efforts of the British Biblical scholars .\n",
      "However , the East Providence Rescue Squad made its way through to my home in time of desperation .\n",
      "However , there are still several types of calls that necessitate the use of telephone operators .\n",
      "however , several pertinent considerations deserve recognition .\n",
      "However , he states unequivocally `` the scandals in business are far less significant than the scandals in labor '' .\n",
      "However , it seems axiomatic that the government has an obligation `` to exercise its mandate reasonably , equitably and with full regard for the disruptions which it inevitably causes '' .\n",
      "However , last night the tapes were not run at all during the evening hours and all we got on TV were a few snatches which Douglas Edwards and Huntley and Brinkley could squeeze into their programs .\n",
      "However , by comparing the TV snatches , two different radio station re-runs , and the censored Los Angeles Times version , I found that the radio stations had edited out questions ( ABC removed the one regarding Laos ) or even a paragraph out of the middle of the President's answer .\n",
      "However well chosen and cleverly arranged , such memorabilia unfortunately amounted to more of an interruption than an auxiliary to the evening's main business , which ( considering the talent at hand ) should probably have been the gathering of fresh samples of the Chicago style .\n",
      "However , my principal objection in this sort of novel is to the hackneyed treatment of race-drivers , pilots , submariners , atomic researchers , and all the machine-masters of our age as brooding mystics or hysterical fatalists .\n",
      "However , she really does not know how to match the quantity of dollars given away by a quality of leadership that is basically needed .\n",
      "However , Montgomery makes little contribution to leadership theory and practice .\n",
      "However , at the same time Montgomery selects as his hero De Gaulle , who is a militarist dominated by political ambitions .\n",
      "However , even if the latent demand for demythologization is not nearly as widespread as we are claiming , at least among the cultured elements of the population there tends to be an almost complete indifference to the church and its traditional message of sin and grace .\n",
      "However much we may have to criticize liberal theology's constructive formulations , the theology we ourselves must strive to formulate can only go beyond liberalism , not behind it .\n",
      "However , there is a crucial difference between the two histories .\n",
      "However , the wei books were also destroyed in a series of Orthodox Confucian purges which culminated in a final proscription in 605 .\n",
      "However , it is not enough to bring persons to Christian commitment and train them in the meaning of Christian discipleship .\n",
      "However , because this vulnerability is mutual , it is to the advantage of neither side to destroy the opponent's cities , at least so long as the opponent has nuclear weapons with which to effect reprisal .\n",
      "However , the aircraft which we have today are tied to large , `` soft '' airfields .\n",
      "However , there is a minimum of legislative restriction on boating .\n",
      "However , we started with the first row of bars and worked our way back .\n",
      "however , he will have a clearer understanding of what he is doing and the chances are he will be more successful if he understands the few formulas that apply to rodding .\n",
      "However , it is essential that the various mathematical symbols used in the equations be understood so that the mathematical processes can be done properly and in their correct order .\n",
      "However , some formulas are used more than others .\n",
      "However , the displacement of the cylinder can be converted to cubic centimeters .\n",
      "However , the use of tripods is not allowed .\n",
      "However , there is also much to be gained by making use of the abilities of the local people who are available and interested in recreation .\n",
      "However , a narrow strip may be very practical for small developments , or to provide additional stream frontage for a fisherman's trail , or include scenic strips within the park unit .\n",
      "However , in all of Prokofieff's music , young or mature , we find his profile -- his `` signature '' -- his craftsman's attitude .\n",
      "However , first I thoughtfully study my sketch for improvement of color and design along the lines I have described .\n",
      "However , he continued experimenting and lecturing , publishing the results of his experiments in German and Danish periodicals .\n",
      "However , that is not all he has to do .\n",
      "However , after you've seen all the historical piazzas and plazas , the places and forums , the churches and museums , the palaces and castles , and begin to feel at home in the capitals of Europe , you'll want to change your course and follow the by-roads at will , far from the market places .\n",
      "However , whether you arrange to have a European or American model , if you rent a car with the proper seating capacity in relation to the number of people in your party , your transportation expense will average very close to $10.00 per day per passenger .\n",
      "However , readers who accept Freud's findings and believe that he has solved completely the mystery of dreams , should ponder over the following words in his Interpretation Of Dreams , Chapter 1 : :\n",
      "However , the last few years of your life , things seem to be changing .\n",
      "However , this does not mean that a child's teeth or jaws must necessarily resemble those of someone in his family .\n",
      "However that may be , people are known to go to mediums for diverse reasons .\n",
      "However , in the next visit that the researcher made to the medium , he did not receive a personal reading .\n",
      "However , this inaugural feast did its sponsors no good whatever .\n",
      "However , they were hostile to Jewish Orthodoxy , professing to believe in Judaism `` but in a moderate way '' .\n",
      "However , in their junior and senior years , they generally forego their athletic pursuits , presumably in the interest of better academic achievement .\n",
      "However , among the girls , there are some morale-enhancing compensations for not going to college .\n",
      "However , a growing intellectual sophistication and the new certitudes imparted by courses in psychology and anthropology make the students increasingly critical of their somewhat provincial and overprotective parents .\n",
      "However , by cultivating a wine dealer and accepting his advice , one will soon enough ascertain whether he has any knowledge of wines ( as opposed to what he may have been told by salesmen and promoters ) and , better yet , whether he has a taste for wine .\n",
      "However , three distinguished associated graduate schools offer professional curriculums -- the Dartmouth Medical School ( third oldest in the country and founded in 1797 ) , the Thayer School of Engineering , and the Amos Tuck School of Business Administration .\n",
      "However much football has been over-emphasized , the public likes to measure its collegiate favorites by the scoreboard , so , while Yale need never give its record a thought again since outscoring its opponents 694 to 0 in the season of 1888 , Dartmouth had to wait until its championship team of 1925 for national recognition .\n",
      "However , the teacher can only go so far if the attitude of the community and the family is anti-intellectual .\n",
      "however , for slow learners and prospective dropouts these courses ought to begin earlier .\n",
      "However nothing on four legs was supposed to be faster than a lion over a short distance , unless it was a cheetah .\n",
      "However needed this may be , the fundamental problem is not information but active commitment to the total mission of the church of Christ in the world .\n",
      "However , as Erickson has noted , the individual's failure to develop preliminary identities during infancy and childhood need not be irreversibly deterministic with respect to a given area of identity diffusion in his ( or her ) adolescence .\n",
      "However , if the child has been constantly surrounded , during nursery and early school age , by peer groups ; ;\n",
      "However , the chaos on my desk prevented my being in the U.N. gallery .\n",
      "However , it is also a Christian insight to know that unless charity interpenetrates justice it is not likely to be freedom that marches forward .\n",
      "However , in recent decades , for what doubtless are multiple reasons , an unannounced but nonetheless readily observable shift has occurred in both facets of national activity .\n",
      "However , the system is designed , ingeniously and hopefully , so that no one man could initiate a thermonuclear war .\n",
      "However , just as all the buildings have not fallen and flowed back to their original mud , so the values which wanted them and saw that they were built have not all disappeared .\n",
      "However , when he assumed the duties of a conductor , he relinquished his career as a pianist .\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "However , there is always the possibility that chance will make demands the dancers find impossible to execute .\n",
      "However , for convenience we will stick to the idea that information can be classified according to Table 1 .\n",
      "However , it is important to trace the philosophy of the French Revolution to its sources to understand the common democratic origin of individualism and socialism and the influence of the latter on the former .\n",
      "However , the crisis occurs precisely as a weakening of spiritual forces .\n",
      "However , I confess my hope that I will be innocent again , not with a pristine , accidental innocence , but rather with an innocence achieved by the slow cutting away of the flesh to reach the bone .\n",
      "However , it was not of innocence in general that I was speaking , but of perhaps the frailest and surely the least important side of it which is innocence in romantic love .\n",
      "However , in the context of legal and civic policy , these controversies are less than novel .\n",
      "However , the General Court at Boston ordered the purchasers of Shawomet to appear before them to answer the sachems' claim .\n",
      "However , as a practicing historian , he , himself , has left few clues to the amount of professional scholarship that he used when writing history .\n",
      "However , despite the insight of many of his observations , his own conclusions are open to suspicion because of his failure to employ at all times the correct research methods .\n",
      "However , at eighty-five , he had still been busy writing articles , reviewing and speaking , and I had never before known an Englishman who had visited and lectured in three quarters of the United States .\n",
      "However , his subject matter and basic themes have remained surprisingly consistent , and these , together with certain key poetic images , may be traced through all his work , including the new jazz experiments .\n",
      "However , they lend themselves to abuse and inadequate control measures .\n",
      "However , few are taxed , and the owners and location of most boats are unknown to the assessors on the date of assessment of town valuations .\n",
      "However , a word should be mentioned in regard to them as independent units of government .\n",
      "However , only Illinois , Oregon , Louisiana and Rhode Island have a situation in which the sundry units of government vary widely in relation to fiscal uniformity .\n",
      "However , it must be stressed that much depends upon the financial condition of the individual cities and towns involved .\n",
      "However , neither of these two cities is on the desired July 1 to June 30 fiscal year .\n",
      "However , the surface temperature gradient can produce erroneous vapor-pressure measurements for the bulk liquid helium unless precautions are taken to isolate the tube ( which passes through the surface to the vapor pressure bulb ) from the liquid helium surface .\n",
      "However , there is a more profound consideration to this proposed merger than profit and loss .\n",
      "However , as much time as possible should be spent within the shelter to hold radiation exposure to a minimum .\n",
      "However , it determined that neither this factor , nor `` the fact that all concerned in high executive posts in both companies acted honorably and fairly , each in the honest conviction that his actions were in the best interests of his own company and without any design to overreach anyone , including Du Pont's competitors '' , outweighed the Government's claim for relief .\n",
      "However , this Court put to one side without consideration the Government's appeal from the dismissal of its Sherman Act allegations .\n",
      "However , I am recommending that development work on the B-70 air-frame and engines be continued .\n",
      "However , in this case as elsewhere it was necessary to arrive at a single standard to be applied to all situations , representing an averaging of conditions , and thus to fix particular points in time which would be considered the dividing points between daytime and nighttime conditions .\n",
      "However , if their United States income is not subject to the withholding of tax on wages , their returns are due June 15 , 1962 , if they use a calendar year , or the 15th day of the 6th month after the close of their fiscal year .\n",
      "However , the healthy inventory position of the textile industry lends support to the broadly expressed belief that improvement in that industry can be expected by the second half of 1961 .\n",
      "However , its modern one-story layout is designed to increase our production capacity , permit more efficient manufacturing , and substantially reduce current repair and maintenance costs .\n",
      "however , production came to only 5.6 million compared to 6.2 million .\n",
      "however , the anode is still the part receiving the largest heat flux .\n",
      "However , technical difficulties arise by melting at local hot spots .\n",
      "However , they do demonstrate the presence of large normal pressures in the presence of flat shear fields which were forecast by the theory in the first part of the paper .\n",
      "However , there are photographs of suspended drops of cyclohexanol phthalate ( viscosity 155 poises ) suspended in corn syrup of 71 poises in a paper by Mason and Bartok .\n",
      "However , the possible absence of a center of symmetry not only moves the hydrogen atom off Af , but also allows the oxygen atoms to become nonequivalent , with Af at Af and Af at Af ( space group Af ) , where Af represents the oxygens on one side of the Af layers and Af those on the other side .\n",
      "However , any oxygen nonequivalence would shorten either the already extremely short Af interlayer distance of 2.55 A or the non-hydrogen-bonded Af interlayer interactions which are already quite short at 2.58 Aj .\n",
      "However , Af adsorbs water from the atmosphere and this may account for the low chromium analysis and high total weight loss .\n",
      "However , a major factor in binding dirt is the attraction between surfaces that goes under the name of Van der Waal's forces .\n",
      "However , one must expect that vaporization and ejection of material by hypervelocity impacts would cause a deviation from a linear relationship .\n",
      "However , the conversion from mass to size is unreliable , since many photographic meteors give evidence of a fluffy , loosely bound meteorite structure with densities as low as Af .\n",
      "however , in the interest of clarity and conciseness only the results obtained with homozygous Af and homozygous Af cells will be presented here .\n",
      "However , as a field measurement , it is open to question .\n",
      "However , many herpetologists remain skeptical and would prefer a tentative maximum of about 30 feet .\n",
      "However , as so many of the records are not certainly based on newborn snakes , these data must be taken tentatively ; ;\n",
      "However , the dynamics of airflow , from morphologic considerations alone , may conceivably be different in the monkey than in the horse .\n",
      "However , this artery is known to be a nutrient vessel with a distribution primarily to the proximal airways and supportive tissues of the lung .\n",
      "However , the formation of organically bound iodine , mainly mono-iodotyrosine , can be accomplished in cell-free systems .\n",
      "However , the nonspecific staining by the Af in tumor sections was considered bright enough to be confused with the staining of small amounts of WTV antigen .\n",
      "However , if these procedures are applied more often , conditioned emotional responses are temporarily abolished .\n",
      "However , one does not need to know very much .\n",
      "However , since the pencil contains a secant of **zg it actually contains only Af singular lines .\n",
      "However , if there is no additional complex of singular lines , the order of the image regulus of a pencil is precisely Af .\n",
      "However , because of Church laws , lately more stringently enforced , which forbid the marriage of cousins closely related consanguineously , a means of facilitating the goal of in-group relations may be that of recourse to illegitimate unions .\n",
      "However , it cannot be presumed , informal though the structure of the population seems , that there are not well-defined roles within the system .\n",
      "However , the factor of physical isolation is not a static situation .\n",
      "However , the statistical offices of both governments were assigned responsibility for the planning and analysis of these statistics .\n",
      "However , the differences in procedure are fundamental .\n",
      "However , all admitted that the `` hindsight '' was not altogether lost .\n",
      "However , she was able to relax and yield to the moment .\n",
      "However , he turned out to be a complete failure in his new position .\n",
      "However , in this case the district manager was led to see the errors of his ways .\n",
      "However , any such suggestion accounts for only some of the difficulties in hearing tone , or in developing a realistic attitude about tone , but not for the analytic difficulties that occur even when tone is meticulously recorded .\n",
      "However , there was no real question of the justice of creating a strong Poland , both industrially and agriculturally , and one unplagued by large minorities of Germans or Russians .\n",
      "However , the regionally differentiated results , which appear below in tables , are interesting evidence of the problems of developing self-government under even the most favorable circumstances .\n",
      "However , there always is some limit to the numbers who will spend the time and effort to acquire training .\n",
      "However , if Federal funds are used , it would be entirely appropriate to train workers for jobs which could be obtained elsewhere as well as for jobs in the area of chronic unemployment .\n",
      "However , as witnessed by the large corporate bond calendar at present , as well as the record amount of municipal bond issues approved by voters , the over-all demands for capital funds seem likely to remain high , so that any downward pressure on rates from reduced demand should not be great .\n",
      "However , the monetary authorities will continue to be required to pay attention to the consequences of their actions with respect to our international balance of payments position and the outflow of gold , as well as with regard to avoiding the creation of excessive liquidity in the economy , which would delay the effectiveness of monetary policy measures in the next expansion phase of the business cycle .\n",
      "However , to the extent that the monetary authorities , in their effort to ease credit in the next several months , conduct their open market operations in longer-term Government bonds , they will certainly act to accentuate any tendency for long-term interest rates to ease as a result of market forces .\n",
      "However , the impact of a rising rate of household formation this decade should not be exaggerated .\n",
      "However , it is not known to either the union or the public precisely how much of a cost increase is caused by a given change in the basic wage rate , although the companies are presumed to have reliable estimates of this magnitude .\n",
      "However , the sovereign was not Hobbes' absolute monarch but rather the parliamentary sovereign of Austin .\n",
      "However , a similar privilege was not specifically provided in section 168 for a person acquiring emergency facilities .\n",
      "However , when labor disputes arise , its provisions come clearly into play .\n",
      "However , the Attorney General of California , at the request of the Secretary of Labor , sought to have the jurisdiction over the issue removed to the Federal District Court , on grounds that it was predominantly a Federal issue since the validity of the Secretary's Regulation was being challenged .\n",
      "However , the Federal Court held that since the State had accepted the provisions of the Wagner-Peyser Act into its own Code , and presumably therefore also the regulations , it was now a State matter .\n",
      "However , the teacher who understands the influence of emotions on behavior may be highly influential in helping pupils gain confidence , security , and satisfaction .\n",
      "However , as we have seen , in later childhood the child begins to substitute the standards of the peer group for those of parents and teachers .\n",
      "However , there are relatively few such political constituencies , and , as has been pointed out , there is seldom a clear-cut distinction between the educational interests of one social class and those of another .\n",
      "However , when philosophy attempts to stand above the sciences , to dictate the conditions of empirical research , it becomes formal metaphysics ; ;\n",
      "However , modesty and triviality are different qualities .\n",
      "However , the building of freeways and garages cannot continue forever .\n",
      "However , the proposed correlation of the many interrelated properties of crystals will reveal discrepancies in the recorded data and suggest areas for reinvestigation .\n",
      "However , the problem of consumer acceptability remains .\n",
      "However , a major problem here is one of scale of processing ; ;\n",
      "However , in the actual assessment of the cutting force by instrumental methods for any thickness of coating a number of spurious effects occur which must be taken into account and which make the measured value larger than the true cutting force indicated by eqn. ( 1 ) .\n",
      "However , the unavoidable low-duty cycle restricts the effective gain .\n",
      "However , electrostatic focus , important for many applications , has not been realized for these devices .\n",
      "However , the leveling operation can be maintained and controlled remotely with no mechanical or optical contact with the platform .\n",
      "However , skill is required on the part of an operator to level a platform to any degree of accuracy .\n",
      "However , this difficulty is not too serious if it is realized that a surveying team can establish a true north base line with a few days' work .\n",
      "However , a boy's lively eyes might rove .\n",
      "However , the litter remained , augmented by several dozen lunchroom suppers .\n",
      "However , it was virtually impossible to screen the mob outside , even if Bonner had manpower available for the purpose .\n",
      "However likely it was , Pauling said , he couldn't limit himself to it .\n",
      "However , Haney knew it was not a dream .\n",
      "However , we sent a third vessel out , a much smaller and faster one than the first two .\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "However , no diagram of her brain patterns , no early I.Q. tests recorded certain essential facts about Helva that Central must eventually learn .\n",
      "However , when there's a job to be done , I'm a monstrosity of grim determination , I like to think .\n",
      "However while in his cell awaiting trial for theft , Barco , in a fit of apprehension , made an attempt to take his own life .\n",
      "However , such a hotbed of gossip had grown up during the trial , that every precaution had to be taken to keep my visit from being whispered to the world , Society , and even , alas , to my own mother .\n",
      "However one looks at it , therefore , I'd say that your horoscope for this autumn is the reverse of rosy .\n"
     ]
    }
   ],
   "source": [
    "however_sents = [sent for sent in brown.sents() if sent[0].lower() == \"however\"]\n",
    "for sent in however_sents:\n",
    "    print(*sent)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a65e2987",
   "metadata": {},
   "source": [
    "__☼ Consider the sentence _Kim arrived or Dana left and everyone cheered._ Write down the parenthesized forms to show the relative scope of and and or. Generate tree structures corresponding to both of these interpretations.__"
   ]
  },
  {
   "cell_type": "raw",
   "id": "13c671e0",
   "metadata": {},
   "source": [
    "(S\n",
    "  (S (S (NP Kim)(VP arrived)) (CC or) (S (NP Dana) (VP left))))\n",
    "  (CC and)\n",
    "  (S (NP everyone) (VP cheered))))\n",
    "  \n",
    "(S\n",
    "  (S (NP Kim)(VP arrived)) \n",
    "  (CC or) \n",
    "  (S (S (NP Dana) (VP left)) (CC and) (S (NP everyone) (VP cheered))))("
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43d56c7b",
   "metadata": {},
   "source": [
    "__☼ The Tree class implements a variety of other useful methods. See the Tree help documentation for more details, i.e. import the Tree class and then type help(Tree).__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "73174b9a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on class Tree in module nltk.tree:\n",
      "\n",
      "class Tree(builtins.list)\n",
      " |  Tree(node, children=None)\n",
      " |  \n",
      " |  A Tree represents a hierarchical grouping of leaves and subtrees.\n",
      " |  For example, each constituent in a syntax tree is represented by a single Tree.\n",
      " |  \n",
      " |  A tree's children are encoded as a list of leaves and subtrees,\n",
      " |  where a leaf is a basic (non-tree) value; and a subtree is a\n",
      " |  nested Tree.\n",
      " |  \n",
      " |      >>> from nltk.tree import Tree\n",
      " |      >>> print(Tree(1, [2, Tree(3, [4]), 5]))\n",
      " |      (1 2 (3 4) 5)\n",
      " |      >>> vp = Tree('VP', [Tree('V', ['saw']),\n",
      " |      ...                  Tree('NP', ['him'])])\n",
      " |      >>> s = Tree('S', [Tree('NP', ['I']), vp])\n",
      " |      >>> print(s)\n",
      " |      (S (NP I) (VP (V saw) (NP him)))\n",
      " |      >>> print(s[1])\n",
      " |      (VP (V saw) (NP him))\n",
      " |      >>> print(s[1,1])\n",
      " |      (NP him)\n",
      " |      >>> t = Tree.fromstring(\"(S (NP I) (VP (V saw) (NP him)))\")\n",
      " |      >>> s == t\n",
      " |      True\n",
      " |      >>> t[1][1].set_label('X')\n",
      " |      >>> t[1][1].label()\n",
      " |      'X'\n",
      " |      >>> print(t)\n",
      " |      (S (NP I) (VP (V saw) (X him)))\n",
      " |      >>> t[0], t[1,1] = t[1,1], t[0]\n",
      " |      >>> print(t)\n",
      " |      (S (X him) (VP (V saw) (NP I)))\n",
      " |  \n",
      " |  The length of a tree is the number of children it has.\n",
      " |  \n",
      " |      >>> len(t)\n",
      " |      2\n",
      " |  \n",
      " |  The set_label() and label() methods allow individual constituents\n",
      " |  to be labeled.  For example, syntax trees use this label to specify\n",
      " |  phrase tags, such as \"NP\" and \"VP\".\n",
      " |  \n",
      " |  Several Tree methods use \"tree positions\" to specify\n",
      " |  children or descendants of a tree.  Tree positions are defined as\n",
      " |  follows:\n",
      " |  \n",
      " |    - The tree position *i* specifies a Tree's *i*\\ th child.\n",
      " |    - The tree position ``()`` specifies the Tree itself.\n",
      " |    - If *p* is the tree position of descendant *d*, then\n",
      " |      *p+i* specifies the *i*\\ th child of *d*.\n",
      " |  \n",
      " |  I.e., every tree position is either a single index *i*,\n",
      " |  specifying ``tree[i]``; or a sequence *i1, i2, ..., iN*,\n",
      " |  specifying ``tree[i1][i2]...[iN]``.\n",
      " |  \n",
      " |  Construct a new tree.  This constructor can be called in one\n",
      " |  of two ways:\n",
      " |  \n",
      " |  - ``Tree(label, children)`` constructs a new tree with the\n",
      " |      specified label and list of children.\n",
      " |  \n",
      " |  - ``Tree.fromstring(s)`` constructs a new tree by parsing the string ``s``.\n",
      " |  \n",
      " |  Method resolution order:\n",
      " |      Tree\n",
      " |      builtins.list\n",
      " |      builtins.object\n",
      " |  \n",
      " |  Methods defined here:\n",
      " |  \n",
      " |  __add__(self, v)\n",
      " |      Return self+value.\n",
      " |  \n",
      " |  __copy__(self)\n",
      " |  \n",
      " |  __deepcopy__(self, memo)\n",
      " |  \n",
      " |  __delitem__(self, index)\n",
      " |      Delete self[key].\n",
      " |  \n",
      " |  __eq__(self, other)\n",
      " |      Return self==value.\n",
      " |  \n",
      " |  __ge__ lambda self, other\n",
      " |  \n",
      " |  __getitem__(self, index)\n",
      " |      x.__getitem__(y) <==> x[y]\n",
      " |  \n",
      " |  __gt__ lambda self, other\n",
      " |  \n",
      " |  __init__(self, node, children=None)\n",
      " |      Initialize self.  See help(type(self)) for accurate signature.\n",
      " |  \n",
      " |  __le__ lambda self, other\n",
      " |  \n",
      " |  __lt__(self, other)\n",
      " |      Return self<value.\n",
      " |  \n",
      " |  __mul__(self, v)\n",
      " |      Return self*value.\n",
      " |  \n",
      " |  __ne__ lambda self, other\n",
      " |      # @total_ordering doesn't work here, since the class inherits from a builtin class\n",
      " |  \n",
      " |  __radd__(self, v)\n",
      " |  \n",
      " |  __repr__(self)\n",
      " |      Return repr(self).\n",
      " |  \n",
      " |  __rmul__(self, v)\n",
      " |      Return value*self.\n",
      " |  \n",
      " |  __setitem__(self, index, value)\n",
      " |      Set self[key] to value.\n",
      " |  \n",
      " |  __str__(self)\n",
      " |      Return str(self).\n",
      " |  \n",
      " |  chomsky_normal_form(self, factor='right', horzMarkov=None, vertMarkov=0, childChar='|', parentChar='^')\n",
      " |      This method can modify a tree in three ways:\n",
      " |      \n",
      " |        1. Convert a tree into its Chomsky Normal Form (CNF)\n",
      " |           equivalent -- Every subtree has either two non-terminals\n",
      " |           or one terminal as its children.  This process requires\n",
      " |           the creation of more\"artificial\" non-terminal nodes.\n",
      " |        2. Markov (vertical) smoothing of children in new artificial\n",
      " |           nodes\n",
      " |        3. Horizontal (parent) annotation of nodes\n",
      " |      \n",
      " |      :param factor: Right or left factoring method (default = \"right\")\n",
      " |      :type  factor: str = [left|right]\n",
      " |      :param horzMarkov: Markov order for sibling smoothing in artificial nodes (None (default) = include all siblings)\n",
      " |      :type  horzMarkov: int | None\n",
      " |      :param vertMarkov: Markov order for parent smoothing (0 (default) = no vertical annotation)\n",
      " |      :type  vertMarkov: int | None\n",
      " |      :param childChar: A string used in construction of the artificial nodes, separating the head of the\n",
      " |                        original subtree from the child nodes that have yet to be expanded (default = \"|\")\n",
      " |      :type  childChar: str\n",
      " |      :param parentChar: A string used to separate the node representation from its vertical annotation\n",
      " |      :type  parentChar: str\n",
      " |  \n",
      " |  collapse_unary(self, collapsePOS=False, collapseRoot=False, joinChar='+')\n",
      " |      Collapse subtrees with a single child (ie. unary productions)\n",
      " |      into a new non-terminal (Tree node) joined by 'joinChar'.\n",
      " |      This is useful when working with algorithms that do not allow\n",
      " |      unary productions, and completely removing the unary productions\n",
      " |      would require loss of useful information.  The Tree is modified\n",
      " |      directly (since it is passed by reference) and no value is returned.\n",
      " |      \n",
      " |      :param collapsePOS: 'False' (default) will not collapse the parent of leaf nodes (ie.\n",
      " |                          Part-of-Speech tags) since they are always unary productions\n",
      " |      :type  collapsePOS: bool\n",
      " |      :param collapseRoot: 'False' (default) will not modify the root production\n",
      " |                           if it is unary.  For the Penn WSJ treebank corpus, this corresponds\n",
      " |                           to the TOP -> productions.\n",
      " |      :type collapseRoot: bool\n",
      " |      :param joinChar: A string used to connect collapsed node values (default = \"+\")\n",
      " |      :type  joinChar: str\n",
      " |  \n",
      " |  copy(self, deep=False)\n",
      " |      Return a shallow copy of the list.\n",
      " |  \n",
      " |  draw(self)\n",
      " |      Open a new window containing a graphical diagram of this tree.\n",
      " |  \n",
      " |  flatten(self)\n",
      " |      Return a flat version of the tree, with all non-root non-terminals removed.\n",
      " |      \n",
      " |          >>> t = Tree.fromstring(\"(S (NP (D the) (N dog)) (VP (V chased) (NP (D the) (N cat))))\")\n",
      " |          >>> print(t.flatten())\n",
      " |          (S the dog chased the cat)\n",
      " |      \n",
      " |      :return: a tree consisting of this tree's root connected directly to\n",
      " |          its leaves, omitting all intervening non-terminal nodes.\n",
      " |      :rtype: Tree\n",
      " |  \n",
      " |  freeze(self, leaf_freezer=None)\n",
      " |  \n",
      " |  height(self)\n",
      " |      Return the height of the tree.\n",
      " |      \n",
      " |          >>> t = Tree.fromstring(\"(S (NP (D the) (N dog)) (VP (V chased) (NP (D the) (N cat))))\")\n",
      " |          >>> t.height()\n",
      " |          5\n",
      " |          >>> print(t[0,0])\n",
      " |          (D the)\n",
      " |          >>> t[0,0].height()\n",
      " |          2\n",
      " |      \n",
      " |      :return: The height of this tree.  The height of a tree\n",
      " |          containing no children is 1; the height of a tree\n",
      " |          containing only leaves is 2; and the height of any other\n",
      " |          tree is one plus the maximum of its children's\n",
      " |          heights.\n",
      " |      :rtype: int\n",
      " |  \n",
      " |  label(self)\n",
      " |      Return the node label of the tree.\n",
      " |      \n",
      " |          >>> t = Tree.fromstring('(S (NP (D the) (N dog)) (VP (V chased) (NP (D the) (N cat))))')\n",
      " |          >>> t.label()\n",
      " |          'S'\n",
      " |      \n",
      " |      :return: the node label (typically a string)\n",
      " |      :rtype: any\n",
      " |  \n",
      " |  leaf_treeposition(self, index)\n",
      " |      :return: The tree position of the ``index``-th leaf in this\n",
      " |          tree.  I.e., if ``tp=self.leaf_treeposition(i)``, then\n",
      " |          ``self[tp]==self.leaves()[i]``.\n",
      " |      \n",
      " |      :raise IndexError: If this tree contains fewer than ``index+1``\n",
      " |          leaves, or if ``index<0``.\n",
      " |  \n",
      " |  leaves(self)\n",
      " |      Return the leaves of the tree.\n",
      " |      \n",
      " |          >>> t = Tree.fromstring(\"(S (NP (D the) (N dog)) (VP (V chased) (NP (D the) (N cat))))\")\n",
      " |          >>> t.leaves()\n",
      " |          ['the', 'dog', 'chased', 'the', 'cat']\n",
      " |      \n",
      " |      :return: a list containing this tree's leaves.\n",
      " |          The order reflects the order of the\n",
      " |          leaves in the tree's hierarchical structure.\n",
      " |      :rtype: list\n",
      " |  \n",
      " |  pformat(self, margin=70, indent=0, nodesep='', parens='()', quotes=False)\n",
      " |      :return: A pretty-printed string representation of this tree.\n",
      " |      :rtype: str\n",
      " |      :param margin: The right margin at which to do line-wrapping.\n",
      " |      :type margin: int\n",
      " |      :param indent: The indentation level at which printing\n",
      " |          begins.  This number is used to decide how far to indent\n",
      " |          subsequent lines.\n",
      " |      :type indent: int\n",
      " |      :param nodesep: A string that is used to separate the node\n",
      " |          from the children.  E.g., the default value ``':'`` gives\n",
      " |          trees like ``(S: (NP: I) (VP: (V: saw) (NP: it)))``.\n",
      " |  \n",
      " |  pformat_latex_qtree(self)\n",
      " |      Returns a representation of the tree compatible with the\n",
      " |      LaTeX qtree package. This consists of the string ``\\Tree``\n",
      " |      followed by the tree represented in bracketed notation.\n",
      " |      \n",
      " |      For example, the following result was generated from a parse tree of\n",
      " |      the sentence ``The announcement astounded us``::\n",
      " |      \n",
      " |        \\Tree [.I'' [.N'' [.D The ] [.N' [.N announcement ] ] ]\n",
      " |            [.I' [.V'' [.V' [.V astounded ] [.N'' [.N' [.N us ] ] ] ] ] ] ]\n",
      " |      \n",
      " |      See http://www.ling.upenn.edu/advice/latex.html for the LaTeX\n",
      " |      style file for the qtree package.\n",
      " |      \n",
      " |      :return: A latex qtree representation of this tree.\n",
      " |      :rtype: str\n",
      " |  \n",
      " |  pos(self)\n",
      " |      Return a sequence of pos-tagged words extracted from the tree.\n",
      " |      \n",
      " |          >>> t = Tree.fromstring(\"(S (NP (D the) (N dog)) (VP (V chased) (NP (D the) (N cat))))\")\n",
      " |          >>> t.pos()\n",
      " |          [('the', 'D'), ('dog', 'N'), ('chased', 'V'), ('the', 'D'), ('cat', 'N')]\n",
      " |      \n",
      " |      :return: a list of tuples containing leaves and pre-terminals (part-of-speech tags).\n",
      " |          The order reflects the order of the leaves in the tree's hierarchical structure.\n",
      " |      :rtype: list(tuple)\n",
      " |  \n",
      " |  pprint(self, **kwargs)\n",
      " |      Print a string representation of this Tree to 'stream'\n",
      " |  \n",
      " |  pretty_print(self, sentence=None, highlight=(), stream=None, **kwargs)\n",
      " |      Pretty-print this tree as ASCII or Unicode art.\n",
      " |      For explanation of the arguments, see the documentation for\n",
      " |      `nltk.treeprettyprinter.TreePrettyPrinter`.\n",
      " |  \n",
      " |  productions(self)\n",
      " |      Generate the productions that correspond to the non-terminal nodes of the tree.\n",
      " |      For each subtree of the form (P: C1 C2 ... Cn) this produces a production of the\n",
      " |      form P -> C1 C2 ... Cn.\n",
      " |      \n",
      " |          >>> t = Tree.fromstring(\"(S (NP (D the) (N dog)) (VP (V chased) (NP (D the) (N cat))))\")\n",
      " |          >>> t.productions()\n",
      " |          [S -> NP VP, NP -> D N, D -> 'the', N -> 'dog', VP -> V NP, V -> 'chased',\n",
      " |          NP -> D N, D -> 'the', N -> 'cat']\n",
      " |      \n",
      " |      :rtype: list(Production)\n",
      " |  \n",
      " |  set_label(self, label)\n",
      " |      Set the node label of the tree.\n",
      " |      \n",
      " |          >>> t = Tree.fromstring(\"(S (NP (D the) (N dog)) (VP (V chased) (NP (D the) (N cat))))\")\n",
      " |          >>> t.set_label(\"T\")\n",
      " |          >>> print(t)\n",
      " |          (T (NP (D the) (N dog)) (VP (V chased) (NP (D the) (N cat))))\n",
      " |      \n",
      " |      :param label: the node label (typically a string)\n",
      " |      :type label: any\n",
      " |  \n",
      " |  subtrees(self, filter=None)\n",
      " |      Generate all the subtrees of this tree, optionally restricted\n",
      " |      to trees matching the filter function.\n",
      " |      \n",
      " |          >>> t = Tree.fromstring(\"(S (NP (D the) (N dog)) (VP (V chased) (NP (D the) (N cat))))\")\n",
      " |          >>> for s in t.subtrees(lambda t: t.height() == 2):\n",
      " |          ...     print(s)\n",
      " |          (D the)\n",
      " |          (N dog)\n",
      " |          (V chased)\n",
      " |          (D the)\n",
      " |          (N cat)\n",
      " |      \n",
      " |      :type filter: function\n",
      " |      :param filter: the function to filter all local trees\n",
      " |  \n",
      " |  treeposition_spanning_leaves(self, start, end)\n",
      " |      :return: The tree position of the lowest descendant of this\n",
      " |          tree that dominates ``self.leaves()[start:end]``.\n",
      " |      :raise ValueError: if ``end <= start``\n",
      " |  \n",
      " |  treepositions(self, order='preorder')\n",
      " |          >>> t = Tree.fromstring(\"(S (NP (D the) (N dog)) (VP (V chased) (NP (D the) (N cat))))\")\n",
      " |          >>> t.treepositions() # doctest: +ELLIPSIS\n",
      " |          [(), (0,), (0, 0), (0, 0, 0), (0, 1), (0, 1, 0), (1,), (1, 0), (1, 0, 0), ...]\n",
      " |          >>> for pos in t.treepositions('leaves'):\n",
      " |          ...     t[pos] = t[pos][::-1].upper()\n",
      " |          >>> print(t)\n",
      " |          (S (NP (D EHT) (N GOD)) (VP (V DESAHC) (NP (D EHT) (N TAC))))\n",
      " |      \n",
      " |      :param order: One of: ``preorder``, ``postorder``, ``bothorder``,\n",
      " |          ``leaves``.\n",
      " |  \n",
      " |  un_chomsky_normal_form(self, expandUnary=True, childChar='|', parentChar='^', unaryChar='+')\n",
      " |      This method modifies the tree in three ways:\n",
      " |      \n",
      " |        1. Transforms a tree in Chomsky Normal Form back to its\n",
      " |           original structure (branching greater than two)\n",
      " |        2. Removes any parent annotation (if it exists)\n",
      " |        3. (optional) expands unary subtrees (if previously\n",
      " |           collapsed with collapseUnary(...) )\n",
      " |      \n",
      " |      :param expandUnary: Flag to expand unary or not (default = True)\n",
      " |      :type  expandUnary: bool\n",
      " |      :param childChar: A string separating the head node from its children in an artificial node (default = \"|\")\n",
      " |      :type  childChar: str\n",
      " |      :param parentChar: A sting separating the node label from its parent annotation (default = \"^\")\n",
      " |      :type  parentChar: str\n",
      " |      :param unaryChar: A string joining two non-terminals in a unary production (default = \"+\")\n",
      " |      :type  unaryChar: str\n",
      " |  \n",
      " |  ----------------------------------------------------------------------\n",
      " |  Class methods defined here:\n",
      " |  \n",
      " |  convert(tree) from builtins.type\n",
      " |      Convert a tree between different subtypes of Tree.  ``cls`` determines\n",
      " |      which class will be used to encode the new tree.\n",
      " |      \n",
      " |      :type tree: Tree\n",
      " |      :param tree: The tree that should be converted.\n",
      " |      :return: The new Tree.\n",
      " |  \n",
      " |  fromlist(l) from builtins.type\n",
      " |      :type l: list\n",
      " |      :param l: a tree represented as nested lists\n",
      " |      \n",
      " |      :return: A tree corresponding to the list representation ``l``.\n",
      " |      :rtype: Tree\n",
      " |      \n",
      " |      Convert nested lists to a NLTK Tree\n",
      " |  \n",
      " |  fromstring(s, brackets='()', read_node=None, read_leaf=None, node_pattern=None, leaf_pattern=None, remove_empty_top_bracketing=False) from builtins.type\n",
      " |      Read a bracketed tree string and return the resulting tree.\n",
      " |      Trees are represented as nested brackettings, such as::\n",
      " |      \n",
      " |        (S (NP (NNP John)) (VP (V runs)))\n",
      " |      \n",
      " |      :type s: str\n",
      " |      :param s: The string to read\n",
      " |      \n",
      " |      :type brackets: str (length=2)\n",
      " |      :param brackets: The bracket characters used to mark the\n",
      " |          beginning and end of trees and subtrees.\n",
      " |      \n",
      " |      :type read_node: function\n",
      " |      :type read_leaf: function\n",
      " |      :param read_node, read_leaf: If specified, these functions\n",
      " |          are applied to the substrings of ``s`` corresponding to\n",
      " |          nodes and leaves (respectively) to obtain the values for\n",
      " |          those nodes and leaves.  They should have the following\n",
      " |          signature:\n",
      " |      \n",
      " |             read_node(str) -> value\n",
      " |      \n",
      " |          For example, these functions could be used to process nodes\n",
      " |          and leaves whose values should be some type other than\n",
      " |          string (such as ``FeatStruct``).\n",
      " |          Note that by default, node strings and leaf strings are\n",
      " |          delimited by whitespace and brackets; to override this\n",
      " |          default, use the ``node_pattern`` and ``leaf_pattern``\n",
      " |          arguments.\n",
      " |      \n",
      " |      :type node_pattern: str\n",
      " |      :type leaf_pattern: str\n",
      " |      :param node_pattern, leaf_pattern: Regular expression patterns\n",
      " |          used to find node and leaf substrings in ``s``.  By\n",
      " |          default, both nodes patterns are defined to match any\n",
      " |          sequence of non-whitespace non-bracket characters.\n",
      " |      \n",
      " |      :type remove_empty_top_bracketing: bool\n",
      " |      :param remove_empty_top_bracketing: If the resulting tree has\n",
      " |          an empty node label, and is length one, then return its\n",
      " |          single child instead.  This is useful for treebank trees,\n",
      " |          which sometimes contain an extra level of bracketing.\n",
      " |      \n",
      " |      :return: A tree corresponding to the string representation ``s``.\n",
      " |          If this class method is called using a subclass of Tree,\n",
      " |          then it will return a tree of that type.\n",
      " |      :rtype: Tree\n",
      " |  \n",
      " |  ----------------------------------------------------------------------\n",
      " |  Data descriptors defined here:\n",
      " |  \n",
      " |  __dict__\n",
      " |      dictionary for instance variables (if defined)\n",
      " |  \n",
      " |  __weakref__\n",
      " |      list of weak references to the object (if defined)\n",
      " |  \n",
      " |  node\n",
      " |      Outdated method to access the node value; use the label() method instead.\n",
      " |  \n",
      " |  ----------------------------------------------------------------------\n",
      " |  Data and other attributes defined here:\n",
      " |  \n",
      " |  __hash__ = None\n",
      " |  \n",
      " |  ----------------------------------------------------------------------\n",
      " |  Methods inherited from builtins.list:\n",
      " |  \n",
      " |  __contains__(self, key, /)\n",
      " |      Return key in self.\n",
      " |  \n",
      " |  __getattribute__(self, name, /)\n",
      " |      Return getattr(self, name).\n",
      " |  \n",
      " |  __iadd__(self, value, /)\n",
      " |      Implement self+=value.\n",
      " |  \n",
      " |  __imul__(self, value, /)\n",
      " |      Implement self*=value.\n",
      " |  \n",
      " |  __iter__(self, /)\n",
      " |      Implement iter(self).\n",
      " |  \n",
      " |  __len__(self, /)\n",
      " |      Return len(self).\n",
      " |  \n",
      " |  __reversed__(self, /)\n",
      " |      Return a reverse iterator over the list.\n",
      " |  \n",
      " |  __sizeof__(self, /)\n",
      " |      Return the size of the list in memory, in bytes.\n",
      " |  \n",
      " |  append(self, object, /)\n",
      " |      Append object to the end of the list.\n",
      " |  \n",
      " |  clear(self, /)\n",
      " |      Remove all items from list.\n",
      " |  \n",
      " |  count(self, value, /)\n",
      " |      Return number of occurrences of value.\n",
      " |  \n",
      " |  extend(self, iterable, /)\n",
      " |      Extend list by appending elements from the iterable.\n",
      " |  \n",
      " |  index(self, value, start=0, stop=9223372036854775807, /)\n",
      " |      Return first index of value.\n",
      " |      \n",
      " |      Raises ValueError if the value is not present.\n",
      " |  \n",
      " |  insert(self, index, object, /)\n",
      " |      Insert object before index.\n",
      " |  \n",
      " |  pop(self, index=-1, /)\n",
      " |      Remove and return item at index (default last).\n",
      " |      \n",
      " |      Raises IndexError if list is empty or index is out of range.\n",
      " |  \n",
      " |  remove(self, value, /)\n",
      " |      Remove first occurrence of value.\n",
      " |      \n",
      " |      Raises ValueError if the value is not present.\n",
      " |  \n",
      " |  reverse(self, /)\n",
      " |      Reverse *IN PLACE*.\n",
      " |  \n",
      " |  sort(self, /, *, key=None, reverse=False)\n",
      " |      Sort the list in ascending order and return None.\n",
      " |      \n",
      " |      The sort is in-place (i.e. the list itself is modified) and stable (i.e. the\n",
      " |      order of two equal elements is maintained).\n",
      " |      \n",
      " |      If a key function is given, apply it once to each list item and sort them,\n",
      " |      ascending or descending, according to their function values.\n",
      " |      \n",
      " |      The reverse flag can be set to sort in descending order.\n",
      " |  \n",
      " |  ----------------------------------------------------------------------\n",
      " |  Static methods inherited from builtins.list:\n",
      " |  \n",
      " |  __new__(*args, **kwargs) from builtins.type\n",
      " |      Create and return a new object.  See help(type) for accurate signature.\n",
      "\n"
     ]
    }
   ],
   "source": [
    "help(nltk.Tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4309d387",
   "metadata": {},
   "source": [
    "__☼ In this exercise you will manually construct some parse trees.__\n",
    "\n",
    "Write code to produce two trees, one for each reading of the phrase _old men and women_\n",
    "\n",
    "Encode any of the trees presented in this chapter as a labeled bracketing and use nltk.Tree() to check that it is well-formed. Now use draw() to display the tree.\n",
    "\n",
    "As in (a) above, draw a tree for The woman saw a man last Thursday."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "b59844c3",
   "metadata": {},
   "outputs": [],
   "source": [
    "first = nltk.Tree.fromstring(\"(S (NP (JJ old) (N men)) (CC and) (NP (N women)))\")\n",
    "second = nltk.Tree.fromstring(\"(S (NP (JJ old) (NP (N men)) (CC and) (N women)))\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "95dbb52c",
   "metadata": {},
   "outputs": [],
   "source": [
    "first.draw()\n",
    "second.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92ae7aea",
   "metadata": {},
   "source": [
    "__☼ Write a recursive function to traverse a tree and return the depth of the tree, such that a tree with a single node would have depth zero. (Hint: the depth of a subtree is the maximum depth of its children, plus one.)__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "4d0554c0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(S\n",
      "  (NP-SBJ\n",
      "    (NP (NNP Pierre) (NNP Vinken))\n",
      "    (, ,)\n",
      "    (ADJP (NP (CD 61) (NNS years)) (JJ old))\n",
      "    (, ,))\n",
      "  (VP\n",
      "    (MD will)\n",
      "    (VP\n",
      "      (VB join)\n",
      "      (NP (DT the) (NN board))\n",
      "      (PP-CLR (IN as) (NP (DT a) (JJ nonexecutive) (NN director)))\n",
      "      (NP-TMP (NNP Nov.) (CD 29))))\n",
      "  (. .))\n"
     ]
    }
   ],
   "source": [
    "print(treebank.parsed_sents()[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "d33dda96",
   "metadata": {},
   "outputs": [],
   "source": [
    "def traverse_tree(tree):\n",
    "    depth = 0\n",
    "    for subtree in tree:\n",
    "        if len(subtree) == 1:\n",
    "            depth += 1\n",
    "        else:\n",
    "            traverse_tree(subtree)\n",
    "    return depth   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "17d031dc",
   "metadata": {},
   "outputs": [],
   "source": [
    "## WILL COME BACK LATER, I DID NOT GET THE QUESTION"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "918bad2d",
   "metadata": {},
   "source": [
    "__☼ Analyze the A.A. Milne sentence about Piglet, by underlining all of the sentences it contains then replacing these with S (e.g. the first sentence becomes S when:lx` S). Draw a tree structure for this \"compressed\" sentence. What are the main syntactic constructions used for building such a long sentence?__"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eb89a8e1",
   "metadata": {},
   "source": [
    "_In after-years he liked to think_ that _he had been in Very Great Danger during the Terrible Flood, but the only danger \n",
    "he had really been in was the last half-hour of his imprisonment_, when _Owl, who had just flown up, sat on a branch of his \n",
    "tree to comfort him, and told him a very long story_ about _an aunt who had once laid a seagull’s egg by mistake_, and _the story went on and on, rather like this sentence, until Piglet who was listening out of his window without much hope, went to sleep quietly and naturally, slipping slowly out of the window towards the water until he was only hanging on by his toes_, at which moment, luckily, _a sudden loud squawk from Owl, which was really part of the story, being what his aunt said, woke the Piglet up and just gave him time to jerk himself back into safety and say, “How interesting, and did she?”_ when — well, _you can imagine his joy when at last he saw the good ship, Brain of Pooh (Captain, C. Robin; 1st Mate, P. Bear) coming over the sea to rescue him._"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a0422478",
   "metadata": {},
   "source": [
    "__☼ Can the grammar in grammar1 be used to describe sentences that are more than 20 words in length?__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "e0849653",
   "metadata": {},
   "outputs": [],
   "source": [
    "grammar1 = nltk.CFG.fromstring(\"\"\"\n",
    "  S -> NP VP\n",
    "  VP -> V NP | V NP PP\n",
    "  PP -> P NP\n",
    "  V -> \"saw\" | \"ate\" | \"walked\"\n",
    "  NP -> \"John\" | \"Mary\" | \"Bob\" | Det N | Det N PP\n",
    "  Det -> \"a\" | \"an\" | \"the\" | \"my\"\n",
    "  N -> \"man\" | \"dog\" | \"cat\" | \"telescope\" | \"park\" | \"mat\" | \"shop\" | \"pijamas\"\n",
    "  P -> \"in\" | \"on\" | \"by\" | \"with\" | \"behind\" | \"in front of\"\n",
    "  \"\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "484a11c9",
   "metadata": {},
   "outputs": [],
   "source": [
    "# It could be even longer by adding more PPs\n",
    "\n",
    "rd_parser = nltk.RecursiveDescentParser(grammar1)\n",
    "sent = \"a man with a telescope saw the cat in the park on the mat behind the dog by the shop with my pijamas\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "16221b9e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(S\n",
      "  (NP (Det a) (N man) (PP (P with) (NP (Det a) (N telescope))))\n",
      "  (VP\n",
      "    (V saw)\n",
      "    (NP\n",
      "      (Det the)\n",
      "      (N cat)\n",
      "      (PP\n",
      "        (P in)\n",
      "        (NP\n",
      "          (Det the)\n",
      "          (N park)\n",
      "          (PP\n",
      "            (P on)\n",
      "            (NP\n",
      "              (Det the)\n",
      "              (N mat)\n",
      "              (PP\n",
      "                (P behind)\n",
      "                (NP\n",
      "                  (Det the)\n",
      "                  (N dog)\n",
      "                  (PP\n",
      "                    (P by)\n",
      "                    (NP\n",
      "                      (Det the)\n",
      "                      (N shop)\n",
      "                      (PP (P with) (NP (Det my) (N pijamas))))))))))))))\n"
     ]
    }
   ],
   "source": [
    "print(next(rd_parser.parse(sent.split())))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6485327a",
   "metadata": {},
   "source": [
    "__◑ You can modify the grammar in the recursive descent parser demo by selecting Edit Grammar in the Edit menu. Change the second expansion production, namely NP -> Det N PP, to NP -> NP\n",
    "PP. Using the Step button, try to build a parse tree. What happens?__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "e3a775b2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# It fails to parse correctly, infinitely expanding the NP to NP PP\n",
    "nltk.app.rdparser()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8d749bb6",
   "metadata": {},
   "source": [
    "__◑ Extend the grammar in grammar2 with productions that expand prepositions as intransitive, transitive and requiring a PP complement. Based on these productions, use the method of the preceding exercise to draw a tree for the sentence Lee ran away home.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "8352624c",
   "metadata": {},
   "outputs": [],
   "source": [
    "grammar2 = nltk.CFG.fromstring(\"\"\"\n",
    "  S  -> NP VP\n",
    "  NP -> Det Nom | PropN\n",
    "  Nom -> Adj Nom | N\n",
    "  VP -> VI Adj | VT NP | VS S | VT NP PP\n",
    "  PP -> P NP\n",
    "  PropN -> 'Buster' | 'Chatterer' | 'Joe' | 'Lee'\n",
    "  Det -> 'the' | 'a'\n",
    "  N -> 'bear' | 'squirrel' | 'tree' | 'fish' | 'log' | 'dog' | 'cat'\n",
    "  Adj  -> 'angry' | 'frightened' |  'little' | 'tall'\n",
    "  VI -> 'was'\n",
    "  VT -> 'chased'  | 'saw'\n",
    "  VS -> 'said' | 'thought' | 'put'\n",
    "  P -> 'on'\n",
    "  \"\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "id": "e67bd3ee",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(S\n",
      "  (NP (Det the) (Nom (N dog)))\n",
      "  (VP (VT chased) (NP (Det the) (Nom (N cat)))))\n"
     ]
    }
   ],
   "source": [
    "sent_2 = \"the dog chased the cat\"\n",
    "ungram_sent = \"the squirrel was Buster was angry\"\n",
    "parser = nltk.ChartParser(grammar2)\n",
    "for parse in parser.parse(sent_2.split()):\n",
    "    print(parse)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "id": "bc5a58ad",
   "metadata": {},
   "outputs": [],
   "source": [
    "# No parse generated\n",
    "for parse in parser.parse(ungram_sent.split()):\n",
    "    print(parse)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a34c318",
   "metadata": {},
   "source": [
    "__◑ Pick some common verbs and complete the following tasks:__\n",
    "\n",
    "Write a program to find those verbs in the Prepositional Phrase Attachment Corpus nltk.corpus.ppattach. Find any cases where the same verb exhibits two different attachments, but where the first noun, or second noun, or preposition, stay unchanged (as we saw in our discussion of syntactic ambiguity in 2)\n",
    "\n",
    "Devise CFG grammar productions to cover some of these cases."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "b35ff66c",
   "metadata": {},
   "outputs": [],
   "source": [
    "attachments = ppattach.attachments(\"training\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "9d7a5d25",
   "metadata": {},
   "outputs": [],
   "source": [
    "atts = defaultdict(lambda : defaultdict(set))\n",
    "for at in attachments:\n",
    "    atts[at.verb][at.attachment].add((at.noun1, at.prep, at.noun2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "075cc418",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "is {('reporter', 'in', 'bureau'), ('writer', 'in', 'York')}\n",
      "have {('impact', 'on', 'results'), ('impact', 'on', 'market')}\n",
      "had {('access', 'to', 'AZT'), ('effect', 'on', 'market'), ('loss', 'in', 'quarter'), ('change', 'in', 'earnings'), ('sales', 'of', 'million')}\n",
      "keep {('pressure', 'on', 'government'), ('pace', 'with', 'inflation')}\n",
      "make {('payments', 'on', 'debt'), ('payment', 'on', 'million')}\n",
      "reported {('earnings', 'of', 'million'), ('loss', 'for', 'quarter'), ('earnings', 'for', 'companies')}\n",
      "paid {('price', 'for', 'incentives'), ('attention', 'to', 'comments'), ('500,000', 'in', 'fines')}\n",
      "posted {('drop', 'in', 'earnings'), ('gain', 'in', 'profit'), ('drop', 'in', 'profit')}\n",
      "earned {('million', 'on', 'revenue'), ('million', 'on', 'sales')}\n"
     ]
    }
   ],
   "source": [
    "# The list of verbs that can be both \"V\" and \"N\" attachment type, and where the noun1, noun2 and prep are the same\n",
    "for verb, att_dict in atts.items():\n",
    "    if len(att_dict[\"N\"].intersection(att_dict[\"V\"])) > 1:\n",
    "        print(verb, (att_dict[\"N\"].intersection(att_dict[\"V\"])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "31d6cf02",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[PPAttachment(sent='2927', verb='earned', noun1='million', prep='on', noun2='revenue', attachment='V'),\n",
       " PPAttachment(sent='3509', verb='earned', noun1='million', prep='on', noun2='revenue', attachment='V'),\n",
       " PPAttachment(sent='16034', verb='earned', noun1='million', prep='on', noun2='revenue', attachment='V'),\n",
       " PPAttachment(sent='16062', verb='earned', noun1='million', prep='on', noun2='revenue', attachment='V'),\n",
       " PPAttachment(sent='23700', verb='earned', noun1='million', prep='on', noun2='revenue', attachment='N'),\n",
       " PPAttachment(sent='24547', verb='earned', noun1='million', prep='on', noun2='revenue', attachment='V'),\n",
       " PPAttachment(sent='35187', verb='earned', noun1='million', prep='on', noun2='revenue', attachment='V')]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# sanity check\n",
    "[ins for ins in attachments if ins.verb == \"earned\" and ins.noun1 == \"million\" and ins.prep == \"on\" and ins.noun2 == \"revenue\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c079c89c",
   "metadata": {},
   "source": [
    "I would love to see the sentences from above examples of \"earned million on revenue\", but I could not find where to access the sentences"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc85fabd",
   "metadata": {},
   "source": [
    "__◑ Write a program to compare the efficiency of a top-down chart parser compared with a recursive descent parser (4). Use the same grammar and input sentences for both. Compare their performance using the timeit module (see 4.7 for an example of how to do this).__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "id": "2c810cd2",
   "metadata": {},
   "outputs": [],
   "source": [
    "my_sent = \"I thought Joe said Sam believes she saw a black cat on the mat in the park\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "id": "bb69ae70",
   "metadata": {},
   "outputs": [],
   "source": [
    "my_grammar = nltk.CFG.fromstring(\"\"\"\n",
    "  S  -> NP VP\n",
    "  NP -> Det Nom | PropN\n",
    "  Nom -> Adj Nom | N\n",
    "  VP -> V Adj | V NP | V S | V NP PP | VP VP\n",
    "  PP -> P NP\n",
    "  PropN -> 'I' | 'Joe' | 'Sam' | 'she'\n",
    "  Det -> 'the' | 'a'\n",
    "  N -> 'Australia' | 'glasses' | 'cat' | 'mat' | 'park'\n",
    "  Adj  -> 'black' | 'big'\n",
    "  V -> 'said' | 'thought' | 'saw' | 'believes'\n",
    "  P -> 'on' | 'in'\n",
    "\"\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "id": "035ef70b",
   "metadata": {},
   "outputs": [],
   "source": [
    "top_down_chart = nltk.ChartParser(my_grammar)\n",
    "recursive = nltk.RecursiveDescentParser(my_grammar)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "id": "92530285",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10.5 ms ± 1.79 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "top_down_chart.parse(my_sent.split())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "id": "c0a27918",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "16.7 µs ± 7.74 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "recursive.parse(my_sent.split())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a58d08f",
   "metadata": {},
   "source": [
    "__◑ Compare the performance of the top-down, bottom-up, and left-corner parsers using the same grammar and three grammatical test sentences. Use timeit to log the amount of time each parser takes on the same sentence. Write a function that runs all three parsers on all three sentences, and prints a 3-by-3 grid of times, as well as row and column totals. Discuss your findings.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "709408f2",
   "metadata": {},
   "outputs": [],
   "source": [
    "sent1 = \"I thought Joe said Sam believes she saw a black cat on the mat in the park\"\n",
    "sent2 = \"the cat chased the dog\"\n",
    "sent3 = \"I bought an ice-cream in the park\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "7591134a",
   "metadata": {},
   "outputs": [],
   "source": [
    "my_grammar_2 = nltk.CFG.fromstring(\"\"\" \n",
    "  S  -> NP VP | S CC S\n",
    "  NP -> Det Nom | PropN\n",
    "  Nom -> Adj Nom | N\n",
    "  VP -> V Adj | V NP | V S | V NP PP | VP VP\n",
    "  PP -> P NP\n",
    "  PropN -> 'I' | 'Joe' | 'Sam' | 'she'\n",
    "  Det -> 'the' | 'a' | 'an'\n",
    "  N -> 'Australia' | 'glasses' | 'cat' | 'mat' | 'park' | 'ice-cream' | 'dog'\n",
    "  Adj  -> 'black' | 'big'\n",
    "  V -> 'said' | 'thought' | 'saw' | 'believes' | 'love' | 'bought' | 'chased'\n",
    "  P -> 'on' | 'in'\n",
    "  CC -> 'because' | 'and' | 'but'\n",
    "\"\"\")\n",
    "\n",
    "top_down_chart_2 = nltk.ChartParser(my_grammar_2)\n",
    "recursive_2 = nltk.RecursiveDescentParser(my_grammar_2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1bc44542",
   "metadata": {},
   "outputs": [],
   "source": [
    "import timeit\n",
    "\n",
    "matrix_times = [[None for _ in range(3)] for _ in range(2)]\n",
    "for idx, sent in enumerate([sent1, sent2, sent3]):\n",
    "    for idx_p, parser in enumerate([top_down_chart_2, recursive_2]):\n",
    "        matrix_times[idx_p][idx] = timeit.timeit(lambda : parser.parse(sent.split()))\n",
    "print(matrix_times)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9d4eb209",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "95265828",
   "metadata": {},
   "source": [
    "__◑ Read up on \"garden path\" sentences. How might the computational work of a parser relate to the difficulty humans have with processing these sentences? http://en.wikipedia.org/wiki/Garden_path_sentence__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "142897d4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6df03e4b",
   "metadata": {},
   "source": [
    "__◑ To compare multiple trees in a single window, we can use the draw_trees() method. Define some trees and try it out:__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "d3aa6c2b",
   "metadata": {},
   "outputs": [],
   "source": [
    "from nltk.draw.tree import draw_trees\n",
    "draw_trees(treebank.parsed_sents()[0], treebank.parsed_sents()[1], treebank.parsed_sents()[2])  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cba979ff",
   "metadata": {},
   "source": [
    "__◑ Using tree positions, list the subjects of the first 100 sentences in the Penn treebank; to make the results easier to view, limit the extracted subjects to subtrees whose height is 2.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "id": "3899d229",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(NP-SBJ Mr. Vinken)\n",
      "(NP-SBJ *-1)\n",
      "(NP-SBJ *)\n",
      "(NP-SBJ researchers)\n",
      "(NP-SBJ it)\n",
      "(NP-SBJ *T*-1)\n",
      "(NP-SBJ researchers)\n",
      "(NP-SBJ *T*-2)\n",
      "(NP-SBJ the latest results)\n",
      "(NP-SBJ *)\n",
      "(NP-SBJ A Lorillard spokewoman)\n",
      "(NP-SBJ This)\n",
      "(NP-SBJ We)\n",
      "(NP-SBJ anyone)\n",
      "(NP-SBJ asbestos)\n",
      "(NP-SBJ There)\n",
      "(NP-SBJ *T*-3)\n",
      "(NP-SBJ We)\n",
      "(NP-SBJ users)\n",
      "(NP-SBJ Dr. Talcott)\n",
      "(NP-SBJ The Lorillard spokeswoman)\n",
      "(NP-SBJ *)\n",
      "(NP-SBJ the company)\n",
      "(NP-SBJ *T*-4)\n",
      "(NP-SBJ *)\n",
      "(NP-SBJ the researchers)\n",
      "(NP-SBJ The morbidity rate)\n",
      "(NP-SBJ *T*-5)\n",
      "(NP-SBJ Dr. Talcott)\n",
      "(NP-SBJ *-1)\n",
      "(NP-SBJ he)\n",
      "(NP-SBJ *)\n",
      "(NP-SBJ The finding)\n",
      "(NP-SBJ *T*-6)\n",
      "(NP-SBJ the U.S.)\n",
      "(NP-SBJ Dr. Talcott)\n",
      "(NP-SBJ The U.S.)\n",
      "(NP-SBJ *T*-7)\n",
      "(NP-SBJ Dr. Mossman)\n",
      "(NP-SBJ the Environmental Protection Agency)\n",
      "(NP-SBJ *T*-8)\n",
      "(NP-SBJ Workers)\n",
      "(NP-SBJ *)\n",
      "(NP-SBJ Workers)\n",
      "(NP-SBJ *T*-1)\n",
      "(NP-SBJ exhaust fans)\n",
      "(NP-SBJ There)\n",
      "(NP-SBJ *-1)\n",
      "(NP-SBJ these events)\n",
      "(NP-SBJ It)\n",
      "(NP-SBJ *-1)\n",
      "(NP-SBJ portfolio managers)\n",
      "(NP-SBJ Compound yields)\n",
      "(NP-SBJ the current yield)\n",
      "(NP-SBJ *-1)\n",
      "(NP-SBJ they)\n",
      "(NP-SBJ portfolio managers)\n",
      "(NP-SBJ *-9)\n",
      "(NP-SBJ portfolio managers)\n",
      "(NP-SBJ *)\n",
      "(NP-SBJ those managers)\n",
      "(NP-SBJ yields)\n",
      "(NP-SBJ they)\n",
      "(NP-SBJ *-1)\n",
      "(NP-SBJ money-fund yields)\n",
      "(NP-SBJ portfolio managers)\n",
      "(NP-SBJ The top money funds)\n",
      "(NP-SBJ It)\n",
      "(NP-SBJ *T*-9)\n",
      "(NP-SBJ The 30-day simple yield)\n",
      "(NP-SBJ the 30-day compound yield)\n",
      "(NP-SBJ *T*-10)\n",
      "(NP-SBJ *-10)\n",
      "(NP-SBJ He)\n",
      "(NP-SBJ *T*-11)\n",
      "(NP-SBJ W.R. Grace)\n",
      "(NP-SBJ Pacific First Financial Corp.)\n",
      "(NP-SBJ shareholders)\n",
      "(NP-SBJ The thrift holding company)\n",
      "(NP-SBJ *-1)\n",
      "(NP-SBJ McDermott International Inc.)\n",
      "(NP-SBJ its Babcock & Wilcox unit)\n",
      "(NP-SBJ Finmeccanica)\n",
      "(NP-SBJ It)\n",
      "(NP-SBJ The federal government)\n",
      "(NP-SBJ Congress)\n",
      "(NP-SBJ Congress)\n",
      "(NP-SBJ the government)\n",
      "(NP-SBJ *)\n",
      "(NP-SBJ the Treasury)\n",
      "(NP-SBJ *T*-1)\n",
      "(NP-SBJ *)\n",
      "(NP-SBJ *-1)\n",
      "(NP-SBJ *-2)\n",
      "(NP-SBJ The Treasury)\n",
      "(NP-SBJ the U.S.)\n",
      "(NP-SBJ Congress)\n",
      "(NP-SBJ *-12)\n",
      "(NP-SBJ he)\n",
      "(NP-SBJ He)\n",
      "(NP-SBJ it)\n",
      "(NP-SBJ *-1)\n",
      "(NP-SBJ *)\n",
      "(NP-SBJ it)\n",
      "(NP-SBJ a company)\n",
      "(NP-SBJ the executives)\n",
      "(NP-SBJ Champagne and dessert)\n",
      "(NP-SBJ *-1)\n",
      "(NP-SBJ The governor)\n",
      "(NP-SBJ the lieutenant governor)\n",
      "(NP-SBJ the speedway)\n",
      "(NP-SBJ Fortune 500 executives)\n",
      "(NP-SBJ *-1)\n",
      "(NP-SBJ they)\n",
      "(NP-SBJ *-1)\n",
      "(NP-SBJ it)\n",
      "(NP-SBJ *-2)\n",
      "(NP-SBJ they)\n",
      "(NP-SBJ the red-carpet treatment)\n",
      "(NP-SBJ them)\n",
      "(NP-SBJ they)\n",
      "(NP-SBJ South Korea)\n",
      "(NP-SBJ *)\n",
      "(NP-SBJ *)\n",
      "(NP-SBJ imports)\n",
      "(NP-SBJ *T*-12)\n",
      "(NP-SBJ Government officials)\n",
      "(NP-SBJ South Korea)\n",
      "(NP-SBJ Imports)\n",
      "(NP-SBJ *-2)\n",
      "(NP-SBJ it)\n",
      "(NP-SBJ the magazine)\n",
      "(NP-SBJ *T*-13)\n",
      "(NP-SBJ *)\n"
     ]
    }
   ],
   "source": [
    "for tree in treebank.parsed_sents()[:100]:\n",
    "    for subtree in tree.subtrees():\n",
    "        if subtree.label() == (\"NP-SBJ\") and subtree.height() == 3:\n",
    "            print(subtree.flatten())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38968e57",
   "metadata": {},
   "source": [
    "__◑ Inspect the Prepositional Phrase Attachment Corpus and try to suggest some factors that influence PP attachment.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 253,
   "id": "229e40a1",
   "metadata": {},
   "outputs": [],
   "source": [
    "all_n_ins = [(ins.noun1, ins.prep) for ins in attachments if ins.attachment == \"N\"]\n",
    "all_v_ins = [(ins.verb, ins.prep) for ins in attachments if ins.attachment == \"V\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 254,
   "id": "cf407037",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('chairman', 'of') ('director', 'of') ('percentage', 'of') ('asbestos', 'in') ('team', 'of') ('paper', 'for') ('three', 'with') ('finding', 'among') ('one', 'of') ('standard', 'of')\n",
      "('join', 'as') ('using', 'in') ('bring', 'to') ('dumped', 'into') ('mixed', 'in') ('retain', 'for') ('pour', 'into') ('raise', 'to') ('been', 'for') ('registered', 'in')\n"
     ]
    }
   ],
   "source": [
    "print(*all_n_ins[:10])\n",
    "print(*all_v_ins[:10])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 272,
   "id": "8b72690b",
   "metadata": {},
   "outputs": [],
   "source": [
    "my_dict = defaultdict(lambda:list())\n",
    "tuples = []\n",
    "all_attachments_N = []\n",
    "for ins in attachments:\n",
    "    if (ins.noun1, ins.prep) in tuples:\n",
    "        all_attachments_N.append(ins.attachment)\n",
    "    if ins.attachment == \"N\":\n",
    "        my_dict[\"N\"].append((ins.noun1, ins.prep))\n",
    "        tuples.append((ins.noun1, ins.prep))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 273,
   "id": "c9da6662",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'N': 6397, 'V': 1991})"
      ]
     },
     "execution_count": 273,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Counter(all_attachments_N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 274,
   "id": "6fda1aff",
   "metadata": {},
   "outputs": [],
   "source": [
    "my_dict_2 = defaultdict(lambda:list())\n",
    "tuples_2 = []\n",
    "all_attachments_V = []\n",
    "for ins in attachments:\n",
    "    if (ins.verb, ins.prep) in tuples_2:\n",
    "        all_attachments_V.append(ins.attachment)\n",
    "    if ins.attachment == \"V\":\n",
    "        my_dict_2[\"V\"].append((ins.verb, ins.prep))\n",
    "        tuples_2.append((ins.verb, ins.prep))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 275,
   "id": "d8f0b77b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'N': 2349, 'V': 5199})"
      ]
     },
     "execution_count": 275,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Counter(all_attachments_V)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "da5006c0",
   "metadata": {},
   "source": [
    "So, I just tried to show that if we take a list of all N attachments and extract possible attachments for that list's (noun1 and prep), we get the proportion of N (6397) higher than V (1991). In other words, my guess is that N attachments heavily rely on noun1 and prep, while V attachments rely more of verb and prep."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 278,
   "id": "6b999731",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'N': 4966, 'V': 2016})"
      ]
     },
     "execution_count": 278,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Let us try out the same thing with N attachments, but with same (noun2 and prep). \n",
    "# My guess is that the number of V and N attachments in Counter will be more equally distributed\n",
    "# since (noun2 and prep) are not strong predictors of the N type attachment\n",
    "my_dict_3 = defaultdict(lambda:list())\n",
    "tuples_3 = []\n",
    "all_attachments_N2 = []\n",
    "for ins in attachments:\n",
    "    if (ins.noun2, ins.prep) in tuples_3:\n",
    "        all_attachments_N2.append(ins.attachment)\n",
    "    if ins.attachment == \"N\":\n",
    "        my_dict_3[\"N\"].append((ins.noun2, ins.prep))\n",
    "        tuples_3.append((ins.noun2, ins.prep))\n",
    "Counter(all_attachments_N2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3eab6bc5",
   "metadata": {},
   "source": [
    "__◑ In this section we claimed that there are linguistic regularities that cannot be described simply in terms of n-grams. Consider the following sentence, particularly the position of the phrase \"in his turn\". Does this illustrate a problem for an approach based on n-grams?__\n",
    "\n",
    "    What was more, the in his turn somewhat youngish Nikolay Parfenovich also turned out to be the only person in the entire world to acquire a sincere liking to our \"discriminated-against\" public procurator. (Dostoevsky: The Brothers Karamazov)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9004d269",
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad3afc9d",
   "metadata": {},
   "source": [
    "__◑ Write a recursive function that produces a nested bracketing for a tree, leaving out the leaf nodes, and displaying the non-terminal labels after their subtrees. So the above example about Pierre Vinken would produce: [[[NNP NNP]NP , [ADJP [CD NNS]NP JJ]ADJP ,]NP-SBJ MD [VB [DT NN]NP [IN [DT JJ NN]NP]PP-CLR [NNP CD]NP-TMP]VP .]S Consecutive categories should be separated by space.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 249,
   "id": "09ed64fb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bracketing(tree, parents = []):\n",
    "    \n",
    "    parents.append(tree.label())\n",
    "    \n",
    "    l = len(tree) - 1\n",
    "    for child in tree:\n",
    "        if child.height() == 2:\n",
    "            print(child.label(), end = \"\")\n",
    "            if l > 0:\n",
    "                print(\" \", end = \"\")\n",
    "                l -= 1\n",
    "        elif isinstance(child, nltk.Tree):\n",
    "            print(\"[\", end = \"\")\n",
    "            bracketing(child, parents)\n",
    "    print(\"]\" + parents.pop(), end = \" \")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 251,
   "id": "2a4430b7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[NNP NNP]NP , [[CD NNS]NP JJ ]ADJP , ]NP-SBJ [MD [VB [DT NN]NP [IN [DT JJ NN]NP ]PP-CLR [NNP CD]NP-TMP ]VP ]VP . ]S "
     ]
    }
   ],
   "source": [
    "bracketing(treebank.parsed_sents()[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e59b84c",
   "metadata": {},
   "source": [
    "__◑ Download several electronic books from Project Gutenberg. Write a program to scan these texts for any extremely long sentences. What is the longest sentence you can find? What syntactic construction(s) are responsible for such long sentences?__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "66a14143",
   "metadata": {},
   "outputs": [],
   "source": [
    "sents_gutenberg = [sent for file in gutenberg.fileids()[:5] for sent in gutenberg.sents(file)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "3211640e",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15 : 21 And the uttermost cities of the tribe of the children of Judah toward the coast of Edom southward were Kabzeel , and Eder , and Jagur , 15 : 22 And Kinah , and Dimonah , and Adadah , 15 : 23 And Kedesh , and Hazor , and Ithnan , 15 : 24 Ziph , and Telem , and Bealoth , 15 : 25 And Hazor , Hadattah , and Kerioth , and Hezron , which is Hazor , 15 : 26 Amam , and Shema , and Moladah , 15 : 27 And Hazargaddah , and Heshmon , and Bethpalet , 15 : 28 And Hazarshual , and Beersheba , and Bizjothjah , 15 : 29 Baalah , and Iim , and Azem , 15 : 30 And Eltolad , and Chesil , and Hormah , 15 : 31 And Ziklag , and Madmannah , and Sansannah , 15 : 32 And Lebaoth , and Shilhim , and Ain , and Rimmon : all the cities are twenty and nine , with their villages : 15 : 33 And in the valley , Eshtaol , and Zoreah , and Ashnah , 15 : 34 And Zanoah , and Engannim , Tappuah , and Enam , 15 : 35 Jarmuth , and Adullam , Socoh , and Azekah , 15 : 36 And Sharaim , and Adithaim , and Gederah , and Gederothaim ; fourteen cities with their villages : 15 : 37 Zenan , and Hadashah , and Migdalgad , 15 : 38 And Dilean , and Mizpeh , and Joktheel , 15 : 39 Lachish , and Bozkath , and Eglon , 15 : 40 And Cabbon , and Lahmam , and Kithlish , 15 : 41 And Gederoth , Bethdagon , and Naamah , and Makkedah ; sixteen cities with their villages : 15 : 42 Libnah , and Ether , and Ashan , 15 : 43 And Jiphtah , and Ashnah , and Nezib , 15 : 44 And Keilah , and Achzib , and Mareshah ; nine cities with their villages : 15 : 45 Ekron , with her towns and her villages : 15 : 46 From Ekron even unto the sea , all that lay near Ashdod , with their villages : 15 : 47 Ashdod with her towns and her villages , Gaza with her towns and her villages , unto the river of Egypt , and the great sea , and the border thereof : 15 : 48 And in the mountains , Shamir , and Jattir , and Socoh , 15 : 49 And Dannah , and Kirjathsannah , which is Debir , 15 : 50 And Anab , and Eshtemoh , and Anim , 15 : 51 And Goshen , and Holon , and Giloh ; eleven cities with their villages : 15 : 52 Arab , and Dumah , and Eshean , 15 : 53 And Janum , and Bethtappuah , and Aphekah , 15 : 54 And Humtah , and Kirjatharba , which is Hebron , and Zior ; nine cities with their villages : 15 : 55 Maon , Carmel , and Ziph , and Juttah , 15 : 56 And Jezreel , and Jokdeam , and Zanoah , 15 : 57 Cain , Gibeah , and Timnah ; ten cities with their villages : 15 : 58 Halhul , Bethzur , and Gedor , 15 : 59 And Maarath , and Bethanoth , and Eltekon ; six cities with their villages : 15 : 60 Kirjathbaal , which is Kirjathjearim , and Rabbah ; two cities with their villages : 15 : 61 In the wilderness , Betharabah , Middin , and Secacah , 15 : 62 And Nibshan , and the city of Salt , and Engedi ; six cities with their villages .\n"
     ]
    }
   ],
   "source": [
    "print(*sorted(sents_gutenberg, key = lambda x: len(x), reverse = True)[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "ba1ebcac",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['austen-emma.txt',\n",
       " 'austen-persuasion.txt',\n",
       " 'austen-sense.txt',\n",
       " 'bible-kjv.txt',\n",
       " 'blake-poems.txt']"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Well, the sent above seems to be from \"bible-kvj.txt\"\n",
    "gutenberg.fileids()[:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "44966fdd",
   "metadata": {},
   "source": [
    "__◑ Modify the functions init_wfst() and complete_wfst() so that the contents of each cell in the WFST is a set of non-terminal symbols rather than a single non-terminal.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 282,
   "id": "9da7c929",
   "metadata": {},
   "outputs": [],
   "source": [
    "def init_wfst(tokens, grammar):\n",
    "    numtokens = len(tokens)\n",
    "    wfst = [[None for i in range(numtokens+1)] for j in range(numtokens+1)]\n",
    "    for i in range(numtokens):\n",
    "        productions = grammar.productions(rhs=tokens[i])\n",
    "        wfst[i][i+1] = productions[0].lhs()\n",
    "    return wfst\n",
    "\n",
    "def complete_wfst(wfst, tokens, grammar, trace=False):\n",
    "    index = dict((p.rhs(), p.lhs()) for p in grammar.productions())\n",
    "    numtokens = len(tokens)\n",
    "    for span in range(2, numtokens+1):\n",
    "        for start in range(numtokens+1-span):\n",
    "            end = start + span\n",
    "            for mid in range(start+1, end):\n",
    "                nt1, nt2 = wfst[start][mid], wfst[mid][end]\n",
    "                if nt1 and nt2 and (nt1,nt2) in index:\n",
    "                    wfst[start][end] = index[(nt1,nt2)]\n",
    "                    if trace:\n",
    "                        print(\"[%s] %3s [%s] %3s [%s] ==> [%s] %3s [%s]\" % \\\n",
    "                        (start, nt1, mid, nt2, end, start, index[(nt1,nt2)], end))\n",
    "    return wfst\n",
    "\n",
    "def display(wfst, tokens):\n",
    "    print('\\nWFST ' + ' '.join((\"%-4d\" % i) for i in range(1, len(wfst))))\n",
    "    for i in range(len(wfst)-1):\n",
    "        print(\"%d   \" % i, end=\" \")\n",
    "        for j in range(1, len(wfst)):\n",
    "            print(\"%-4s\" % (wfst[i][j] or '.'), end=\" \")\n",
    "        print()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "61dd2f97",
   "metadata": {},
   "source": [
    "__◑ Consider the algorithm in 4.4. Can you explain why parsing context-free grammar is proportional to n3, where n is the length of the input sentence.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "23a2d9d0",
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d141198",
   "metadata": {},
   "source": [
    "__◑ Process each tree of the Treebank corpus sample nltk.corpus.treebank and extract the productions with the help of Tree.productions(). Discard the productions that occur only once. Productions with the same left hand side, and similar right hand sides can be collapsed, resulting in an equivalent but more compact set of rules. Write code to output a compact grammar.__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "id": "b4a2f5f7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_productions(treebank):\n",
    "    \"\"\"\n",
    "    Given parsed sentences from a treebacnk corpus,\n",
    "    the function returns non-terminal productions of the corpus. \n",
    "    If some productions have same LHS and their RHS is similar, then \n",
    "    they are merged. Otherwise, if no other similar RHS was found, that\n",
    "    particular RHS is returned as one of possible non-terminals.\n",
    "    \n",
    "    The similarity of two RHS is determined by looking at the first and the last items of RHS.\n",
    "    If they are the same, RHSes era said to be similar, and the longes of all similar RHSes\n",
    "    is taken when they are merged. \n",
    "    \n",
    "    \"\"\"\n",
    "    prod_dict = defaultdict(int)\n",
    "    prods = set()\n",
    "    prod_lhs_dict = defaultdict(lambda : defaultdict(int))\n",
    "    prod_rhs_dict = defaultdict(lambda : defaultdict(set))\n",
    "    lhs_dict = defaultdict(lambda : list())\n",
    "    \n",
    "    for tree in treebank:\n",
    "        for prod in tree.productions():\n",
    "            if prod.rhs()[0] != str:  # If it is a non-terminal, then get the production. Otehrwise discard\n",
    "                prod_dict[prod] += 1\n",
    "        \n",
    "    for prod, freq in prod_dict.items():\n",
    "        if freq > 1:\n",
    "            prods.add(prod)\n",
    "            \n",
    "    for prod in prods:\n",
    "        LHS = prod.lhs()\n",
    "        if prod.rhs(): RHS = prod.rhs()\n",
    "        RHS_0 = RHS[0]\n",
    "        RHS_last = RHS[-1]\n",
    "        prod_lhs_dict[LHS][(RHS_0, RHS_last)] += 1\n",
    "        prod_rhs_dict[LHS][(RHS_0, RHS_last)].add(RHS)\n",
    "    \n",
    "    for lhs, dict_2 in prod_lhs_dict.items():\n",
    "        for tuples, freq in dict_2.items():\n",
    "            if freq > 1:\n",
    "                lhs_dict[lhs].append(max(prod_rhs_dict[lhs][tuples]))\n",
    "            elif freq == 1:\n",
    "                lhs_dict[lhs] + list((prod_rhs_dict[lhs][tuples]))\n",
    "            \n",
    "    \n",
    "    return lhs_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "id": "6a9cc4ce",
   "metadata": {},
   "outputs": [],
   "source": [
    "prods = get_productions(treebank.parsed_sents())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "id": "7dbf4a0a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "227"
      ]
     },
     "execution_count": 121,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(prods)  # 227 unique LHS values are found"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "id": "54e62356",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(VP,\n",
       " [(VBZ, SBAR, ,, S-ADV),\n",
       "  (VBZ, PP-DIR),\n",
       "  (VB, PRT, PP-CLR),\n",
       "  (VBG, PP-CLR, PP-CLR),\n",
       "  (VBN, S, PP),\n",
       "  (VB, PP-DIR, PP-PRP),\n",
       "  (VBD, PRT, PP-CLR),\n",
       "  (VB, SBAR-ADV),\n",
       "  (VBD, SBAR, PP-TMP),\n",
       "  (VBD, SBAR),\n",
       "  (VBN, PP-DIR, PP-DIR),\n",
       "  (VBP, VP),\n",
       "  (VBZ, S),\n",
       "  (ADVP, VBP, NP),\n",
       "  (VBG, PP),\n",
       "  (VBZ, PP-MNR),\n",
       "  (VBD, S),\n",
       "  (VBG, PP-DIR),\n",
       "  (VBN, PP-PRP),\n",
       "  (VBP, NP-PRD, ,, S-ADV),\n",
       "  (VBN, S, PP-TMP),\n",
       "  (VBD, S-PRP),\n",
       "  (VBP, RB, NP-PRD),\n",
       "  (VBD, SBAR, ,, PP),\n",
       "  (VB, ``, NP-PRD),\n",
       "  (VBD, PP-CLR, ,, ADVP),\n",
       "  (VBG, PP-LOC),\n",
       "  (VB, NP, ADVP-MNR),\n",
       "  (VBP, PP-CLR, PP-CLR),\n",
       "  (VBN, S, ,, S-ADV),\n",
       "  (VBN, S, SBAR-ADV),\n",
       "  (VBZ, NP-PRD, ADVP-TMP),\n",
       "  (VBZ, PP-CLR),\n",
       "  (VB, S, PP-TMP),\n",
       "  (VB, PP-CLR, PP),\n",
       "  (VBG, S-ADV),\n",
       "  (VB, ``, NP),\n",
       "  (VB, SBAR-TMP),\n",
       "  (VBP, PP),\n",
       "  (VBD, VP),\n",
       "  (VBD, ``, ADJP-PRD),\n",
       "  (VBZ, ``, NP),\n",
       "  (VB, PRT, NP, S-PRP),\n",
       "  (VBN, PRT, NP),\n",
       "  (VBD, SBAR, ,, SBAR-ADV),\n",
       "  (VBG, PP-MNR),\n",
       "  (VBG, NP, SBAR-TMP),\n",
       "  (VBN, PP-LOC),\n",
       "  (VBP, NP-PRD, ,, SBAR-ADV),\n",
       "  (VP, CC, VP),\n",
       "  (VBN, PRT, PP-CLR),\n",
       "  (VBD, PP-DIR, PP-DIR),\n",
       "  (MD, ``, VP),\n",
       "  (VBN, ``, ADJP-PRD),\n",
       "  (VB, PRT),\n",
       "  (VBD, SBAR-TMP),\n",
       "  (VBP, PP-MNR),\n",
       "  (VBD, RB, NP-PRD),\n",
       "  (VBD, SBAR, ADVP-TMP),\n",
       "  (VBN, S, SBAR-PRP),\n",
       "  (VBN, NP, PP-CLR, NP-TMP),\n",
       "  (VBN, NP, ADVP),\n",
       "  (VBG, ``, NP),\n",
       "  (VBP, ``, ADJP-PRD),\n",
       "  (VBZ, PP-CLR, PP),\n",
       "  (VBN, VP),\n",
       "  (VBG, NP, ADVP),\n",
       "  (VBZ, RB, PP-PRD),\n",
       "  (VB, NP, ADVP-CLR),\n",
       "  (VBG, VP),\n",
       "  (VBG, PRT, NP, PP-TMP),\n",
       "  (VBN, S-CLR),\n",
       "  (VBP, SBAR-PRP),\n",
       "  (VBD, S, PP-LOC),\n",
       "  (VB, NP, ADVP),\n",
       "  (VB, S, NP-TMP),\n",
       "  (VB, PP-DIR, PP-DIR),\n",
       "  (VBP, PP-LOC),\n",
       "  (VBD, PP-DIR, PP-PRP),\n",
       "  (VB, PP-LOC),\n",
       "  (VBG, NP, ADVP-MNR),\n",
       "  (VBZ, RB, NP-PRD, PP-LOC),\n",
       "  (VBZ, ``, NP-PRD),\n",
       "  (TO, ``, VP),\n",
       "  (ADVP-MNR, VBN, NP, PP-CLR),\n",
       "  (VBZ, ``, VP),\n",
       "  (VBZ, ``, ADJP-PRD),\n",
       "  (VBN, PP-MNR),\n",
       "  (ADVP-MNR, VP, CC, VP, PP),\n",
       "  (VBN, NP, SBAR-TMP),\n",
       "  (ADVP-MNR, VBZ, NP),\n",
       "  (VBZ, S-PRD),\n",
       "  (VBZ, S, ,, SBAR-ADV),\n",
       "  (VB, NP, ADVP-LOC),\n",
       "  (VBZ, NP, NP-TMP),\n",
       "  (VBN, SBAR),\n",
       "  (VBZ, NP-PRD, ADVP-LOC),\n",
       "  (VBD, NP-EXT, S-CLR),\n",
       "  (VBD, SBAR, NP-TMP),\n",
       "  (VBN, S),\n",
       "  (VBZ, SBAR-TMP),\n",
       "  (VBP, PP-CLR, ADVP-TMP),\n",
       "  (VBD, PP-CLR, ,, ADVP-CLR),\n",
       "  (VB, PP-MNR),\n",
       "  (VBN, NP, PP-CLR, ADVP-TMP),\n",
       "  (VBD, PRT, NP),\n",
       "  (VBD, NP, PP-MNR),\n",
       "  (VBZ, RB, ADJP-PRD, S-1),\n",
       "  (VBP, NP, ADVP-LOC),\n",
       "  (VBG, NP-EXT, NP-TMP),\n",
       "  (VBZ, PP-TMP),\n",
       "  (VP, :, NP),\n",
       "  (VBP, PRT, NP),\n",
       "  (VBZ, RB, ADJP-PRD, SBAR-1),\n",
       "  (VB, VP),\n",
       "  (VB, NP, ADVP-TMP),\n",
       "  (VB, S, SBAR-PRP),\n",
       "  (VBD, SBAR, ,, S-ADV),\n",
       "  (VBG, S),\n",
       "  (VBG, S-PRP),\n",
       "  (VBZ, PP-CLR, ,, SBAR-PRP),\n",
       "  (VB, SBAR),\n",
       "  (VBN, NP, ADVP-MNR),\n",
       "  (VB, S)])"
      ]
     },
     "execution_count": 122,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(prods.items())[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "806ae84d",
   "metadata": {},
   "source": [
    "__★ One common way of defining the subject of a sentence S in English is as the noun phrase that is the child of S and the sibling of VP. Write a function that takes the tree for a sentence and returns the subtree corresponding to the subject of the sentence. What should it do if the root node of the tree passed to this function is not S, or it lacks a subject?__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "id": "6cc8ff4f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# If I got the question correctly, here is what is expected from me\n",
    "def subject_finder(tree):\n",
    "    for child in tree:\n",
    "        if child.label().startswith(\"NP-SBJ\"):\n",
    "            print(child)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "id": "31cc03a8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(NP-SBJ\n",
      "  (NP (DT A) (JJ full) (, ,) (JJ four-color) (NN page))\n",
      "  (PP-LOC (IN in) (NP (NNP Newsweek))))\n"
     ]
    }
   ],
   "source": [
    "subject_finder(treebank.parsed_sents()[101])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "429c4dcb",
   "metadata": {},
   "source": [
    "__★ Write a function that takes a grammar (such as the one defined in 3.1) and returns a random sentence generated by the grammar. (Use grammar.start() to find the start symbol of the grammar; grammar.productions(lhs) to get the list of productions from the grammar that have the specified left-hand side; and production.rhs() to get the right-hand side of a production.)__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "id": "fdecef4b",
   "metadata": {},
   "outputs": [],
   "source": [
    "grammar2 = nltk.CFG.fromstring(\"\"\"\n",
    "  S  -> NP VP\n",
    "  NP -> Det Nom | PropN\n",
    "  Nom -> Adj Nom | N\n",
    "  VP -> VI Adj | VT NP | VS S | VT NP PP\n",
    "  PP -> P NP\n",
    "  PropN -> 'Buster' | 'Chatterer' | 'Joe' | 'Lee'\n",
    "  Det -> 'the' | 'a'\n",
    "  N -> 'bear' | 'squirrel' | 'tree' | 'fish' | 'log' | 'dog' | 'cat'\n",
    "  Adj  -> 'angry' | 'frightened' |  'little' | 'tall'\n",
    "  VI -> 'was'\n",
    "  VT -> 'chased'  | 'saw'\n",
    "  VS -> 'said' | 'thought' | 'put'\n",
    "  P -> 'on'\n",
    "  \"\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 212,
   "id": "fc89d027",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def generate_from_grammar(grammar):\n",
    "    \n",
    "    start = grammar.start()\n",
    "    prod_dict = defaultdict(lambda: list())\n",
    "    \n",
    "    for prod in grammar.productions():\n",
    "        prod_dict[prod.lhs()].append(prod.rhs())\n",
    "    \n",
    "    next_rhs = prod_dict[start]\n",
    "    \n",
    "    def get_next(rhs):\n",
    "        phrase = \"\"\n",
    "        for tuples in rhs:\n",
    "            if tuples[0] == nltk.grammar.Nonterminal:  # if RHS is non-terminal\n",
    "                tuple_ = random.choice(rhs)\n",
    "                if len(tuple_) == 1: \n",
    "                    get_next(prod_dict[tuple_[0]])\n",
    "                else:\n",
    "                    for i in tuple_:\n",
    "                        get_next(prod_dict[i])\n",
    "            elif tuples[0] == str:  # if RHS is not a non-terminal, add the word to \"phrase\"\n",
    "                tuple_ = random.choice(rhs)\n",
    "                phrase += tuple_[0]\n",
    "        return phrase\n",
    "    \n",
    "        \n",
    "    return get_next(next_rhs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 224,
   "id": "babce1db",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "''"
      ]
     },
     "execution_count": 224,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "generate_from_grammar(grammar2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "39822ea3",
   "metadata": {},
   "source": [
    "__★ As we saw in 7., it is possible to collapse chunks down to their chunk label. When we do this for sentences involving the word gave, we find patterns such as the following:__\n",
    "\n",
    "    gave NP\n",
    "    gave up NP in NP\n",
    "    gave NP up\n",
    "    gave NP NP\n",
    "    gave NP to NP\n",
    "    \n",
    "Use this method to study the complementation patterns of a verb of interest, and write suitable grammar productions. (This task is sometimes called lexical acquisition.)\n",
    "\n",
    "Identify some English verbs that are near-synonyms, such as the dumped/filled/loaded example from earlier in this chapter. Use the chunking method to study the complementation patterns of these verbs. Create a grammar to cover these cases. Can the verbs be freely substituted for each other, or are their constraints? Discuss your findings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 228,
   "id": "adfe9dc9",
   "metadata": {},
   "outputs": [],
   "source": [
    "conll_train_NP = conll2000.chunked_sents('train.txt')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 247,
   "id": "9470bd22",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(S\n",
      "  (NP This/DT)\n",
      "  (VP has/VBZ increased/VBN)\n",
      "  (NP the/DT risk/NN)\n",
      "  (PP of/IN)\n",
      "  (NP the/DT government/NN)\n",
      "  (VP being/VBG forced/VBN to/TO increase/VB)\n",
      "  (NP base/NN rates/NNS)\n",
      "  (PP to/TO)\n",
      "  (NP 16/CD %/NN)\n",
      "  (PP from/IN)\n",
      "  (NP their/PRP$ current/JJ 15/CD %/NN level/NN)\n",
      "  (VP to/TO defend/VB)\n",
      "  (NP the/DT pound/NN)\n",
      "  ,/,\n",
      "  (NP economists/NNS)\n",
      "  and/CC\n",
      "  (NP foreign/JJ exchange/NN market/NN analysts/NNS)\n",
      "  (VP say/VBP)\n",
      "  ./.)\n"
     ]
    }
   ],
   "source": [
    "print(conll_train_NP[3])"
   ]
  }
 ],
 "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}