Scribd
Upload
164 views12 pages

Parsing Algorithms NLP

Parsing in NLP involves analyzing the grammatical structure of sentences to convert plain text into a structured form, which is crucial for machine understanding. There are various types of parsing, including constituency and dependency parsing, and several algorithms such as Top-Down, Bottom-Up, CYK, and Earley's Parser. Parsing is essential for applications like chatbots, machine translation, and voice assistants, making NLP systems more intelligent.

Uploaded by

srinidhiteerdham
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
164 views12 pages

Parsing Algorithms NLP

Parsing in NLP involves analyzing the grammatical structure of sentences to convert plain text into a structured form, which is crucial for machine understanding. There are various types of parsing, including constituency and dependency parsing, and several algorithms such as Top-Down, Bottom-Up, CYK, and Earley's Parser. Parsing is essential for applications like chatbots, machine translation, and voice assistants, making NLP systems more intelligent.

Uploaded by

srinidhiteerdham
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 12

Parsing Algorithms in

NLP
• Presented by Sri Nidhi Teerdham
• 22R91A73B5
Introduction to Parsing

• • Parsing = Analyzing grammatical


structure of sentences
• • Converts plain text into structured
form
• • Essential for machine understanding
Why Parsing is Important
in NLP
• • Identifies relationships between words
• • Aids in semantic understanding
• • Used in:
• - Text-to-speech
• - Machine translation
• - Information extraction
Types of Parsing

• 1. Constituency Parsing (Phrase


structure)
• 2. Dependency Parsing (Relation
between words)
Parsing Algorithms -
Overview
• • Top-Down Parsing
• • Bottom-Up Parsing
• • Shift-Reduce Parsing
• • CYK Algorithm
• • Earley’s Parser
Top-Down Parsing

• • Begins from the start symbol


• • Tries to match input by expanding
rules
• • Recursive in nature
• • Issues: may lead to infinite recursion
Bottom-Up Parsing

• • Starts from input symbols


• • Builds up to the start symbol
• • Example: Shift-Reduce Parsing
Shift-Reduce Parsing

• • Stack-based approach
• • Actions: Shift, Reduce, Accept, Error
• • Used in many practical parsers
CYK Algorithm

• • Works for context-free grammar in


CNF
• • Uses dynamic programming
• • Time Complexity: O(n³)
Earley’s Parser

• • Works for all context-free grammars


• • Handles ambiguity
• • Efficient for natural language
Applications of Parsing

• • Chatbots and Virtual Assistants


• • Machine Translation (e.g., Google
Translate)
• • Grammar correction tools
• • Voice Assistants like Siri, Alexa
Conclusion

• • Parsing is the foundation of language


understanding
• • Different algorithms suit different
needs
• • Important for making NLP systems
smarter

You might also like