Constituency／Phrase Parsing

is the task of breaking text/sentences into constituents (sub-phrases and words)
- non-terminals in the parse tree are types of phrases
- terminals are the words in the sentence
builds on top of PoS tagging by combining the tags into larger constituents/phrases
constituency parsing with Context-Free Grammar (CFG) or Phrase Structure Grammar (PSG) refers to the task of assigning proper trees to input strings/sentences
- proper here means a tree:
  - that covers all and only elements of the input
  - has an S at the top
- proper doesn’t actually mean that the tree is correct
involves search which involves the making of choices

Constituency Parsing Method	Time Complexity (sentence of length 𝑛)
Parsing Parsing Control & Backtracking	𝑂(𝐶^𝑛) where: 𝐶 is the work at each step
CYK Algorithm	𝑂(𝑛³·\|𝐺\|) where: \|𝐺\| is the number of rules in the given grammar
Bottom-Up Chart Parsing	𝑂(𝐾·𝑛³) where: 𝐾 is the work at each step (𝐾 >> 𝐶)

Constituency Parsing Method

Time Complexity (sentence of length 𝑛)

𝑂(𝐶^𝑛) where:

𝑂(𝑛³·|𝐺|) where:

𝑂(𝐾·𝑛³) where:

／var／log marcus chiu