Types of parsers

Types of Parsers in Artificial Intelligence. Link Parser, Chart Parser, Single Transition Network, Recursive Transition Network, Augmented Transition Network, Definite Clause Grammar

1. TYPES OF PARSERS By, M. Sabiha MCA 2 nd Year

2. What is meant by Parsing? Parsing is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar.

3. TYPES OF PARSERS

4. 1. LINK PARSER Proposed by Davy Temperley and Daniel Sleator in the year 1993. Builds relations between pairs of words. Uses SVO (Subj Verb Obj) language. Rightward links are represented with + Leftward links are represented with – Optional links are contained in curly brackets {…} Undesirable links are contained in any no. of square brackets […] Multiple links are joined either by conjunction (&) or disjunction (or).

5. Link Grammar Rules for SVO Language Link Grammar Rules Interpretation of Rules <Determiner>: Det+; Det connected to word to its right in a sentence <Noun_Sub>: {Det-} & Sub+; Sub connected to word on its right and Det on left (optional) <Noun_Obj>: {Det-} & Obj-; Obj is a last word in a sentence and connected to Det on left (optional) <Verb> : Sub- & {Obj+}; Verb connected to Obj on right (optional) and connected to Sub on left.

6. Example of Link Parser The girl sings a song Here, The:d, girl:n, sings:v, a:d and song:n Then, Link Grammar representation is The(d) girl(n) sings(v) a(d) song(n) | | | | Det- + +Sub- + + Det- + Sub+

7. 2. CHART PARSER Chart parsing is generally credited to Martin Kay. Chart is a data structure which is maintained to keep a record of the positions of the words and new structure derived from the sentence. Keeps the record of rules which are recorded as the active arcs on the chart.

8. Rules of Chart Parsing Rules Rule Number Dictionary Words <S>  <NP><VP> 1 <Det>  a|the|an <NP>  <Det> <Noun> 2 <Noun>  girl|apple|song <NP>  <Det> <Adj> <Noun> 3 <Adj>  cute|smart <NP>  <Adj> <Noun> 4 <Verb>  sings|ate <VP>  <Verb> 5 <VP>  <Verb> <NP> 6

9. Example of Chart Parsing 1 The 2 cute 3 girl 4 sings 5 a 6 song 7

10. 3. SIMPLE TRANSITION NETWORK Convenient for visualizing grammar. Consists of nodes and labeled arcs. The final arc is called as Pop. d np1 vp d np2 pop n1 n2 n3 n4 n5 n6

11. Example of Simple Transition Network A girl is standing at the bus-stop d np1 t vp pp d np2 A girl is standing at the bus-stop Pop

12. 4. RECURSIVE TRANSITION NETWORK Similar to Simple Transition Network. Allows arc labels that refer to other networks rather than word categories. The structural elements of a well-formed sentence may also be well-formed sentences by themselves.

13. Example of Recursive Transition Network Alice jumps and Bob runs Noun Verb S and Alice jumps Bob runs

14. 5. AUGMENTED TRANSITION NETWORK Extension of Recursive Transition Network. Produces the data structure suitable for further processing. Capable of storing semantic details. Internally performs tests and takes actions during arc transitions.

15. Example of Augmented Transition Network John will hit the door (S SUBJ (NP NAME John ) MAIN VERB will ADV hit TENSE FUTURE OBJ (NP DET the HEAD door ))

16. 6. DEFINITE CLAUSE GRAMMAR Developed by Fernando Pereira and David Warren in the year 1980. Extension of Context Free Grammar (CFG). One of the important applications of Prolog . Used to express any natural language grammar in limited sense. Rules are separated by an arrow symbol - - > Left side of the rule contains a part of ordinary Prolog rules. Right side of the rule contains a condition or body of Prolog.

17. Rules of DCG Ordinary Prolog Rule Conditional Prolog Rule Sentence --> Noun Phrase (NP), Verb Phrase (VP) NP --> Det, Noun NP --> Adjective (ADJ), Noun VP --> Verb, NP VP --> Verb, Sentence

18. Example of DCG The cat scares the mouse Det --> The Noun --> cat Verb --> scares Det --> the Noun --> mouse