1111 Syntax in NLP Parse trees Exhibit the grammatical structure of a sentence Parse trees d me that he had soen "Woukn't the Most view X(s)means that string scan be interpreted as an if quotation marks had be Logical grammars Context-free parsing en placed before Fish,and b "And since I was not informed-as a matter of fact,since I did not know sential step towards meaning: Syntax in NLP Parse trees Exhibit the grammatical structure of a sentence I shoot the wumpus Pronoun Verb Article Noun NP VP NP VP Chapter 22 19 Parse trees Exhibit the grammatical structure of a sentence I shoot the wumpus Pronoun Verb Article Noun NP VP NP VP S Chapter 22 20 Syntax in NLP Most view syntactic structure as an essential step towards meaning; “Mary hit John” 6= “John hit Mary” “And since I was not informed—as a matter of fact, since I did not know that there were excess funds until we, ourselves, in that checkup after the whole thing blew up, and that was, if you’ll remember, that was the incident in which the attorney general came to me and told me that he had seen a memo that indicated that there were no more funds.” Chapter 22 21 Syntax in NLP Most view syntactic structure as an essential step towards meaning; “Mary hit John” 6= “John hit Mary” “And since I was not informed—as a matter of fact, since I did not know that there were excess funds until we, ourselves, in that checkup after the whole thing blew up, and that was, if you’ll remember, that was the incident in which the attorney general came to me and told me that he had seen a memo that indicated that there were no more funds.” “Wouldn’t the sentence ’I want to put a hyphen between the words Fish and And and And and Chips in my Fish-And-Chips sign’ have been clearer if quotation marks had been placed before Fish, and between Fish and and, and and and And, and And and and, and and and And, and And and and, and and and Chips, as well as after Chips?” Chapter 22 22 Context-free parsing Bottom-up parsing works by replacing any substring that matches RHS of a rule with the rule’s LHS Efficient algorithms (e.g., chart parsing, Section 22.3) O(n 3 ) for context-free, run at several thousand words/sec for real grammars Context-free parsing ≡ Boolean matrix multiplication (Lee, 2002) ⇒ unlikely to find faster practical algorithms Chapter 22 23 Logical grammars BNF notation for grammars too restrictive: – difficult to add “side conditions” (number agreement, etc.) – difficult to connect syntax to semantics Idea: express grammar rules as logic X → YZ becomes Y (s1) ∧ Z(s2) ⇒ X(Append(s1, s2)) X → word becomes X([“word”]) X → Y | Z becomes Y (s) ⇒ X(s) Z(s) ⇒ X(s) Here, X(s) means that string s can be interpreted as an X Chapter 22 24