UMass Amherst CMPSCI 591N - Chart Parsing (43 pages)

Previewing pages 1, 2, 3, 20, 21, 22, 41, 42, 43 of 43 page document View the full content.
View Full Document

Chart Parsing



Previewing pages 1, 2, 3, 20, 21, 22, 41, 42, 43 of actual document.

View the full content.
View Full Document
View Full Document

Chart Parsing

75 views

Lecture Notes


Pages:
43
School:
University of Massachusetts Amherst
Course:
Cmpsci 591n - Computational Linguistics

Unformatted text preview:

Chart Parsing Lecture 6 Computational Linguistics CMPSCI 591N Spring 2006 University of Massachusetts Amherst Andrew McCallum Including slides from Jason Eisner Andrew McCallum UMass Amherst Today s Main Points Hand back In class Exercise 2 Motivations and applications of Parsing Dynamic Programming for Parsing CYK Some hands on practice Discuss Programming Assignment 3 Implement CYK and build a grammar Andrew McCallum UMass Amherst Programming languages printf charset s re opcode t p 1 charset not assert p p pend for c 0 c 256 c if c 8 p p 1 c 8 1 c 8 Are we starting a range if last 1 c inrange putchar inrange 1 Have we broken a range else if last 1 c inrange putchar last inrange 0 if inrange putchar c last c Easy to parse Designed that way Andrew McCallum UMass Amherst Natural languages printf charset s re opcode t p 1 charset not assert p p pend for c 0 c 256 c if c 8 p p1 c 8 1 c 8 Are we starting a range if last 1 c inrange putchar inrange 1 Have we broken a range else if last 1 c inrange putchar last inrange 0 if inrange putchar c last c No to indicate scope precedence Lots of overloading arity varies Grammar isn t known in advance Context free grammar not best formalism Andrew McCallum UMass Amherst The parsing problem correct test trees test sentences P A R S E R Grammar Andrew McCallum UMass Amherst s c o r e r accuracy Applications of parsing 1 2 Machine translation English Alshawi 1996 Wu 1997 tree operations Speech synthesis from parses Chinese Prevost 1996 The government plans to raise income tax The government plans to raise income tax the imagination Speech recognition using parsing Chelba et al 1998 Put the file in the folder Put the file and the folder Andrew McCallum UMass Amherst Applications of parsing 2 2 Grammar checking Microsoft Indexing for information retrieval Woods 1997 washing a car with a hose Information extraction vehicle maintenance Hobbs 1996 Miller et al 2000 Database NY Times archive pattern Andrew McCallum UMass Amherst Parsing



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Chart Parsing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Chart Parsing and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?