Introduction to Syntactic Analysis after John Bryant Form What Is Natural Language Written Sound Motion Sign Language Bridged to Meaning Factual meaning what the form literally asserts Pragmatic meaning what the speaker wanted the hearer to know In Some Context Shared world knowledge Common situation What is Syntax The Way Words Are Put Together For example Determiners come before Nouns in English Constituency How words group together to behave as a single unit Grammatical Relations E g What word functions as the subject of the sentence Subcategorization and dependency How particular words constrain the sentence Why Are We Interested In It Beyond the scientific interest in the structure of language syntax is important because it tells us along with the words what the sentence means Syntactic modification is indicative of semantic modification Modeling Syntax The standard approach for modeling syntax is to treat natural language as a formal language Using Formal Languages for Describing Syntax Problematic Different ways of specifying formal languages have different levels of expressive power Much care must be taken to choose a mechanism that is expressive enough but not too expressive But Necessary Knowledge of a process like language must be formalized for computational methods to be effective Which type of formal language is the right one What Is a Formal Language A possibly infinite set of strings String here means a sequence of words or symbols Mary had a little lamb could be a string in some set Defined by a set of rules The rules are a compact way of representing which strings belong to the set They provide a strict mathematical definition of which strings are in the set and which are not They are called the grammar of the language Allowing these rules to be more complex lets us define more complex sets of strings More Precisely A finite set of terminals Terminals are the atomic symbols in our language the words A finite set of nonterminals A nonterminal is a special symbol that refers to a chunk of terminals and nonterminals a k a a constituent Nonterminals are the syntactic categories of the language A set of rules For defining how the symbols can be grouped ordered A designated start symbol This is the symbol from which rule application must originate An Example Language Terminals b Nonterminals S A designated start symbol S A set of rules S bS S b The rules are read S goes to bS or S goes to b Can be interpreted in both directions either as saying S can be rewritten into a bS or that bS can be reduced to an S This language generates all strings containing at least one b that only have b s Things We Can Do With a Formal Language Determine if a particular string is in the language By trying to derive it Deriving a string just means finding a mapping via the grammar rules between the start symbol and the string It is also called parsing Generating all the strings in the language Trying every possible rule combination from the start symbol allows us to check that we only allow the good strings Compare it to other formal languages Different ways of defining the rules leads to different amounts of Deriving the string bbb going top down 1 S bS 2 S b S is the designated start symbol S 2 1 bS b Using rule 2 here is the wrong move because there are no more nonterminals to rewrite and we have not derived bbb 2 bb So instead we use rule 1 which at least gives us a nonterminal to expand 1 bbS 2 bbb Using rule 2 here is right because we will have matched the desired string and don t have anymore nonterminals to deal with Top Down Parsing as Search The initial state is the designated start symbol The states are combinations of terminals and nonterminals derivable from S The operators are the grammar rules Any chunk of a state that matches the left hand side of a rule can be replaced by the right hand side of that rule The goal state is the input string without Deriving the string bbb going bottom up 1 S bS 2 S b SSS SSS SS SSS SSb SbS Sbb SSb SSS SS SS SSS SS bSS Sb bSb SbS SSS SS bSS SS S bS bbS bbb tart with the input string and try to find the start symbol Bottom Up Parsing as Search The initial state is the input string The states are combinations of terminals and nonterminals The operators are the grammar rules Any chunk of the state that matches the right hand side of a grammar rule can be replaced by the left hand side of that rule The Goal state is the designated start symbol Parsing as Search Using search appears to have drawbacks Repeated states infinite search trees Exponential with respect to the desired string Ambiguity Is the derivation we found the right one Actual Natural Language Parsers Keep a table of states a chart so as not to repeat them The chart allows the parser to keep track of multiple derivations which makes it possible to deal with ambiguity With the chart we also don t get caught in infinite loops The chart makes parsing polynomial Even with ambiguous grammars More on the Rules They can schematically be represented as Where and are ordered lists of terminals and nonterminals Constraining the number of terminals and and constrains the expressive power of the rules i e the more complex we let and be the more complex our languages can get nonterminals in Context Free Grammar Is a type of grammar that constrains the rules such that can only be a single nonterminal can be any number of terminals and nonterminals Some flavor of Context Free Grammar is usually used to recognize English syntax A Tiny NL CFG Using context free grammar rules we can make a tiny natural language grammar The Lexicon Noun soul pipe fiddlers bowl ProperNoun King Cole Verb was called plays play Adjective old merry three Article a the Possessive his Conjunction and Preposition for Pronoun he The Lexicon is the list of words that we support organized by part of speech These words are the terminal symbols The Syntax Rules S NP VP S Conjunction S NP Adjective ProperNoun Possessive Adjective Noun Article Adjective Noun Pronoun VP Verb NP Verb PP The means any number of PP Preposition NP NP VP and PP stand for Noun Phrase Verb Phrase and Prepositional phrase They are the constituents in our grammar as well as some of the constituents of actual What s a Constituent Consider the noun phrase A sequence of words surrounding a noun referring to something The screaming monkey The laptop on the table How do we know these words form a constituent Noun phrases can all appear before a suitable verb The