Top Down Parser : Earley Parser

• The Earley parser is a type of algorithm used for parsing sentences based on a context-
free grammars (CFGs).

• Three Phases (States):

• Prediction: For any non-terminal symbol that appears at a position in the input, the
algorithm predicts what rules might match.

• Scanning: The parser checks the input string and matches the next symbol (if it’s a
terminal symbol).

• Completion: Once a rule is fully matched, the parser moves backward, recognizing that
part of the sentence and allowing higher-level rules to continue parsing.
 How the Earley Parser Works:
• For a given input sentence and grammar:

[Link]: The parser starts by initializing the first set, based on the
starting non-terminal symbol of the grammar.

[Link] Loop: The algorithm iterates over each input token, applying the three

phases: prediction, scanning, and completion.

[Link]: Once all input tokens are processed, the parser checks whether
the start symbol has been fully matched.
 Example
• S → NP VP (Rule 1) Sentence: " dog chases the cat."
• NP → Det N |N (Rule 2)
• VP → V NP (Rule 3)
• Det → 'the’ (Rule 4)
• N → 'dog’ |’cat’ (Rule 5)
• V → 'chase’ (Rule 6)
 S: " dog chases the cat."
Operation Types Production Rules Completion Status

Initialization 0
S-> .NP VP S → NP VP (Rule 1)
Predict NP-> .Det N 0 NP → Det N |N (Rule 2)
VP → V NP (Rule 3)
NP->. N
Det → 'the’ (Rule 4)
N → 'dog’ | ‘cat’ (Rule 5)
Scan : dog 1 (First word scanned)
NP-> N. V → 'chases’ (Rule 6)
Complete S-> NP . VP 1
Predict VP-> . V NP 1

Scan: chases VP-> V . NP 2 (Second word is scanned)

 S: " dog chases the cat."
Operation Types Production Rules Completion Status

Predict 2
NP-> . Det N
NP-> N. S → NP VP (Rule 1)
3 (Third word is scanned) NP → Det N |N (Rule 2)
Scan : the NP-> Det . N
VP → V NP (Rule 3)
NP-> Det . N Det → 'the’ (Rule 4)
N → 'dog’ | ‘cat’ (Rule 5)
Scan : cat NP-> Det N . 4 (Fourth word is V → 'chases’ (Rule 6)
scanned)

Complete S-> NP VP . 4
Example 2: " book that flight"
• S-> NP VP
• S-> VP
• NP-> DET NOM
• NOM-> Noun
• NOM-> Noun NOM
• VP-> Verb
• VP-> Verb NP
• DET-> that | this | a | the
• Noun -> book | flight | meal | man
• Verb-> book | include | read
 Operation Types Production Rules Completion Status book that flight
Initialization 0
S-> .NP VP S-> NP VP
S-> VP
S-> . VP NP-> DET NOM
NOM-> Noun
Predict VP-> . Verb 0
NOM-> Noun NOM
VP-> Verb
VP-> . Verb NP VP-> Verb NP
DET-> that | this | a | the
Scan : book VP-> Verb . NP 1 (First word scanned) Noun -> book | flight | meal | man
Verb-> book | include | read
Complete S-> Verb . NP 1
Predict NP-> . Det NOM 1

Scan: that NP-> Det . NOM 2 (Second word is scanned)

 Operation Types Production Rules Completion Status book that flight
Predict NOM->. Noun S-> NP VP
NOM-> .Noun NOM S-> VP
NP-> DET NOM
Scan : flight 3(Third word is scanned)
NOM-> Noun . NOM-> Noun
NOM-> Noun NOM
Complete S-> VP . 3 VP-> Verb
VP-> Verb NP
DET-> that | this | a | the
Noun -> book | flight | meal | man
Verb-> book | include | read
 PREDICTIVE PARSER
• A predictive parser in Natural Language Processing (NLP) is a type of parser
used to analyze the structure of a sentence based on its syntax, predicting the
next symbol or word in a given sentence.

• It is typically associated with top-down parsing, where the parser begins with
the highest level (start symbol) of the grammar and attempts to generate the
input string by predicting what comes next.
Symbols
terminals
Predictive Parser Table
the a cat dog chases sees $
S

NP

VP

Det

V
Predictive Parser Table
 Parsing Procedure
Step Stack Input Action
 Probabilistic Context Free Grammar(PCFG)
• A Probabilistic Context-Free Grammar (PCFG) parser is an extension of a
traditional Context-Free Grammar (CFG) used in Natural Language Processing
(NLP) to analyze the syntactic structure of sentences.

• It assigns probabilities to the production rules, which helps resolve

ambiguities by choosing the most likely parse for a sentence.
 Components of a PCFG:
[Link]-terminal symbols (N): Represent abstract grammatical categories like
noun phrases (NP), verb phrases (VP), and sentences (S).

[Link] symbols (T): Represent the actual words in a language.

[Link] rules (P): Rules that define how non-terminal symbols can be
replaced by other non-terminals or terminals (e.g., S → NP VP).

[Link] symbol (S): The non-terminal symbol from which parsing starts.

[Link] (θ): Each production rule is assigned a probability that indicates

how likely it is for that rule to be used in generating or parsing a sentence.
Example P(S → NP VP) = 1.0
• S → NP VP P(NP → Det N) = 0.9
• NP → Det N P(VP → V NP) = 0.8
• VP → V NP P(N → 'dog') = 0.6
• Det → 'the' P(N → 'cat') = 0.4
• N → 'dog' | 'cat' P(Det → 'the') = 1.0
• V → 'chased' P(V → 'chased') =
1.0
 Ex: “the dog chased the cat” P(S → NP VP) = 1.0
P(NP → Det N) = 0.9
• S → NP VP
P(VP → V NP) = 0.8
• NP → Det N S 1.0 P(N → 'dog') = 0.6
• VP → V NP P(N → 'cat') = 0.4
• Det → 'the' P(Det → 'the') = 1.0
0.9 NP 0.8 VP
• N → 'dog' | 'cat' P(V → 'chased') = 1.0
• V → 'chased'

1.0 Det 0.6 N V 1.0 NP 0.9

Det 1.0
N 0.4

the dog chased

the cat
S= 1.0* 0.6 * 1.0 * 1.0 * 0.4 * 0.9 * 0.9 * 0.8 * 1.0 = 0.15
Ex2: PCFG PARSER
“ Book book ”
Highest Probability : 0.0056
Bottom Up Parser: Shift Reduce Parser
• A Shift-Reduce Parser is a bottom-up parsing technique used in
Natural Language Processing (NLP) to analyze the structure of
sentences, particularly in dependency and constituency parsing.