Parsing

1.上下无关文法与上下有关文法

Starting unit:

$\underset{\text{非终结符}}{S}V\ O$

transition rule:

$\begin{array}{l} S\rightarrow \text{人|天}\\ V\rightarrow \text{吃|下}\\ O\rightarrow \text{雨|饭|肉}\\ \end{array}$

上下文文无关语法
- 不考虑前后依赖关系

$sent\rightarrow SVO\rightarrow\text{天}VO\rightarrow\text{天吃}O\rightarrow\text{天吃肉}$

上下文有关语法
- 考虑前后依赖关系

$\begin{array}{l} S\rightarrow \text{人|天}\\ \text{人V}\rightarrow \text{人吃}\\ \text{天V}\rightarrow \text{天下}\\ \text{下O}\rightarrow \text{下雨}\\ \text{吃O}\rightarrow \text{吃饭|吃肉}\\ \end{array}$

上下文无关文法以及上下文有关文法都具有歧义，即不同语料表达的意思不一定相同

2. Parsing

2.1 Def

Suntactic Structure: Constitunency = phrase structure grammar = context - free grammars
传统认为，句子构成应该是：从最简单的单词出发，然后不同的词组成短语，再将短语组成大的短语。
- (the, cuddly, cat, by, the, door)(the cuddly cat|by the door)(the cuddly cat by the door)

$\begin{array}{l} \text{Lexicon:}\\ N\rightarrow \text{dog}\\ N\rightarrow \text{cat}\\ Det\rightarrow \text{a}\\ Det\rightarrow \text{the}\\ P\rightarrow \text{in|on|by}\\ V\rightarrow \text{talk|walk|...}\\ \end{array}$

Gramma:

$\begin{array}{l} \text{NP}\rightarrow\text{Det N}\\ \text{NP}\rightarrow\text{Det $(Adj)^*$ N (PP)}\\ PP\rightarrow\text{P NP}\\ VP\rightarrow\text{V PP}\\ sent\rightarrow\text{NP VP}\\ \end{array}$

2.2 PP Attachment Ambiguities Multiply

Look in the large crate in the kitchen by the door
- PP存在修饰歧义

$\text{Look in } \underset{NP}{\underbrace{\text{the large crate}}} \underset{PP}{\underbrace{\text{ in the kitchen}}} \underset{PP}{\underbrace{\text{ by the door}}}$

通常我们把一个句子的核心词称为head，修饰部分为modification

Prepositional Phrase Attachment Ambiguity
- San Jose cops kill man with knife

不同的是，中文由于语法习惯不一样不存在相同的歧义。

A key parsing decision is how we ‘attach’ various constituents
PPs , adverbial or participial phrases, infinitives, coordinations

2.3 Coordination Scope Ambiguity

定语修饰范围出现错误
Shuttle veteran and longtime NASA executive Fred Gregory appointed to board
- [Shuttle veteran] and [longtime NASA executive Fred Gregory ]appointed to board
- [Shuttle veteran and longtime NASA executive] Fred Gregory appointed to board
Doctor:No heart, cognitive issues
- Doctor:No [heart, cognitive issues]
- Doctor:[No heart], [cognitive issues]

2.4 Adjectival/Adverbial Modifier Ambiguity

Students get first hand job experience
- Students get [first hand] [job experience]
- Students get [first [hand job] experience]

2.5 Verb Phrase (VP) attachment ambiguity

Multilated body washes up on Rio beach to be used for Olympics beach volleyball
- Multilated body washes up on Rio beach to be used for Olympics beach volleyball
- Multilated body washes up on Rio beach to be used for Olympics beach volleyball

3. Dependency Grammar and Dependency Structure

3.1 Def

Dependency syntax postulates that syntactic structure consists of relations between lexical items, normally binary asymmetric relations (“arrows”) called dependencies
- 研究紧挨着的两个词的关系，并且会给边打上相关的标签
The arrows arecommonly typed with the name of grammatical relations (subject,prepositional object,apposition, etc.)
- An arrow connects a head(governor, superior,regent) with a dependent(modifier, inferior,subordinate)
- Usually, dependencies form a tree (a connected,acyclic, single-root graph)
处于支配地位的成分称为支配者head,governor,regent，而处于被支配地位的成分称为从属者 modifier,subordinate,dependency
值得一提的是，我们都会在句子解析结构加上根节点以保证树状结构

3.2 Dependency Relations

3.3 Dependency Grammar and Dependency Structure

ROOT

What are the sources of information for dependency parsing?

Bilexical affinities 同词性之间的依赖关系
- The dependency [discussion issues] is plausible
Dependency distance 依赖距离
- Most dependencies are between nearby words
Intervening material
- Dependencies rarely span intervening verbs or punctuation
- 依赖关系很少跨越中间的动词或标点符号
Valency of heads
- How many dependents on which side are usual for a head?

A sentence is parsed by choosing for each word what other word (including ROOT) it is a dependent of
Usually some constraints:
- Only one word is a dependent of ROOT (single headed)
- Don’t want cycles (acyclic)
This makes the dependencies a tree
Final issue is whether arrows can cross (be non-projective) or not
- 是否允许交叉将使得建树的方法和结果有所不同

3.4 Methods of Dependency Parsing

3.4.1 Greedy transition based parsing

A simple form of greedy discriminative dependency parser
The parser does a sequence of bottom up actions
- Roughly like “shift” or “reduce” in a shift-reduce parser, but the “reduce” actions are specialized to create dependencies with head on left or right
The parser has:
- a stack , written with top to the right
  - which starts with the ROOT symbol
  - 用一个栈存放代操作的字符，后进先出
- a buffer , written with top to the left
  - which starts with the input sentence
  - 用一个队列存放剩余需要操作的句子，先进先出
- a set of dependency
  - which starts off empty
  - 有一个集合存放所有弧的关系
- a set of actions
  - 用一个集合存放所有操作

Basic Transition based Dependency Parser

Arc standard Transition based Parser

(there are other transition schemes …) Analysis of “I ate fish“

Example

Left-Arc
Precondition: ROOT
- 意思是当所在的stack中相邻的两个symbol的左依赖关系没有在集合里时，可以进行操作
- 操作时，我们比较栈顶和队首的两个词，如果存在Left Arc，那么我们只pop掉栈顶的词
Right-Arc
- 操作时，我们比较栈顶和队首的两个词，如果存在right Arc，我们就pop掉队首并且push进栈顶
- 这里我理解是，Right arc的两个词都有可能产生新的依赖关系，最具标志性的就是ROOT连接句子的第一个修饰的词
Reduce
Precondition:
- 意思是当队列为空，且所在的stack中相邻的两个symbol的左依赖关系有在集合里时，那么直接pop栈顶
Shift
- 当栈顶和队首不存在任何依赖关系时，且队列不为空时，直接将队首的词加入栈顶