{"id":164,"date":"2018-07-20T05:34:40","date_gmt":"2018-07-20T05:34:40","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=164"},"modified":"2018-07-20T05:34:46","modified_gmt":"2018-07-20T05:34:46","slug":"top-down-parser-first-follow-parsing-table","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/top-down-parser-first-follow-parsing-table\/","title":{"rendered":"Top Down Parser \u2013 FIRST(), FOLLOW(), Parsing Table"},"content":{"raw":"<p style=\"text-align: justify\">In the previous module, we discussed the pre-processing steps that need to be carried out to convert a grammar to be parsed by a top-down parser. In this module, we will discuss how to compute the functions first () and follow(). Using these functions the LL(1) parsing table is constructed. This parsing table will be subsequently used by the parsing algorithm to verify whether an input string belongs to a grammar or not.<\/p>\r\n&nbsp;\r\n\r\n<strong>10.1 Top-Down Parsing<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The input grammar is to be pre-processed and should be free of left-recursion and need to be left factored. This grammar is considered for computing the two functions FIRST(k) and FOLLOW(k). The \u2018k\u2019 within the parenthesis indicates the number of input symbols to be considered during parsing. So, if we are to consider only \u20181\u2019 input symbol as look ahead, then we need to compute FIRST(1) and FOLLOW(1) and this is required for a LL(1) parser. We have already indicated in the previous module that LL(1) parser is a type of top-down parser that avoids backtracking. The first \u2018L\u2019 indicates that the input is scanned from left to right, the second \u2018L\u2019 denotes that the left derivation is to be applied, and the \u2018(1)\u2019 indicates looking at 1 input symbol at any point of time. This parser predicts what the input string would look like and hence is called predictive parser. This predictive parser avoids backtracking by constructing a parsing table. To construct this LL(1) parsing table, computation of FIRST(1) and FOLLOW(1) are necessary.<\/p>\r\n&nbsp;\r\n\r\nA grammar G is LL(1) if A \u2192 \u03b1 | \u03b2 are two distinct productions of G:\r\n<ul>\r\n \t<li>For no terminal a, both \u03b1 and \u03b2 derive strings beginning with a.<\/li>\r\n \t<li>At most one of \u03b1 and \u03b2 can derive empty string.<\/li>\r\n \t<li>If \u03b2 \u2192 \u03b5, then \u03b1 does not derive any string beginning with a terminal in FOLLOW(A).<\/li>\r\n<\/ul>\r\n<p style=\"text-align: justify\">\u00a0 The interaction of the various modules is shown in figure 10.1. From figure 10.1, a parsing table is to be constructed which requires the functions FIRST() and FOLLOW(). The parsing algorithm considers the current input symbol and the symbol on the top of the stack and looks into the parsing table for an action. Based on the action, the parser pushes\/pops the stack symbol. The output of the parser will be a \u201cYES\u201d or a \u201cNO\u201d indicating success or failure of the parsing action. The parser accepts the string and outputs a \u201cYES\u201d if the stack is empty and the input is completely processed. Any other state of the input or the stack is to be termed as incorrect string for a given grammar.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-165 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-90.png\" alt=\"\" width=\"656\" height=\"793\" \/>\r\n\r\n<img class=\"size-full wp-image-166 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-91.png\" alt=\"\" width=\"659\" height=\"889\" \/>\r\n\r\n<img class=\"size-full wp-image-167 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-92.png\" alt=\"\" width=\"640\" height=\"855\" \/>\r\n\r\n<img class=\"size-full wp-image-168 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-93.png\" alt=\"\" width=\"664\" height=\"779\" \/>\r\n\r\n<img class=\"size-full wp-image-169 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-94.png\" alt=\"\" width=\"683\" height=\"843\" \/>\r\n\r\n<img class=\"size-full wp-image-170 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-95.png\" alt=\"\" width=\"700\" height=\"891\" \/>\r\n\r\n<img class=\"size-full wp-image-171 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-96.png\" alt=\"\" width=\"698\" height=\"835\" \/>","rendered":"<p style=\"text-align: justify\">In the previous module, we discussed the pre-processing steps that need to be carried out to convert a grammar to be parsed by a top-down parser. In this module, we will discuss how to compute the functions first () and follow(). Using these functions the LL(1) parsing table is constructed. This parsing table will be subsequently used by the parsing algorithm to verify whether an input string belongs to a grammar or not.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>10.1 Top-Down Parsing<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The input grammar is to be pre-processed and should be free of left-recursion and need to be left factored. This grammar is considered for computing the two functions FIRST(k) and FOLLOW(k). The \u2018k\u2019 within the parenthesis indicates the number of input symbols to be considered during parsing. So, if we are to consider only \u20181\u2019 input symbol as look ahead, then we need to compute FIRST(1) and FOLLOW(1) and this is required for a LL(1) parser. We have already indicated in the previous module that LL(1) parser is a type of top-down parser that avoids backtracking. The first \u2018L\u2019 indicates that the input is scanned from left to right, the second \u2018L\u2019 denotes that the left derivation is to be applied, and the \u2018(1)\u2019 indicates looking at 1 input symbol at any point of time. This parser predicts what the input string would look like and hence is called predictive parser. This predictive parser avoids backtracking by constructing a parsing table. To construct this LL(1) parsing table, computation of FIRST(1) and FOLLOW(1) are necessary.<\/p>\n<p>&nbsp;<\/p>\n<p>A grammar G is LL(1) if A \u2192 \u03b1 | \u03b2 are two distinct productions of G:<\/p>\n<ul>\n<li>For no terminal a, both \u03b1 and \u03b2 derive strings beginning with a.<\/li>\n<li>At most one of \u03b1 and \u03b2 can derive empty string.<\/li>\n<li>If \u03b2 \u2192 \u03b5, then \u03b1 does not derive any string beginning with a terminal in FOLLOW(A).<\/li>\n<\/ul>\n<p style=\"text-align: justify\">\u00a0 The interaction of the various modules is shown in figure 10.1. From figure 10.1, a parsing table is to be constructed which requires the functions FIRST() and FOLLOW(). The parsing algorithm considers the current input symbol and the symbol on the top of the stack and looks into the parsing table for an action. Based on the action, the parser pushes\/pops the stack symbol. The output of the parser will be a \u201cYES\u201d or a \u201cNO\u201d indicating success or failure of the parsing action. The parser accepts the string and outputs a \u201cYES\u201d if the stack is empty and the input is completely processed. Any other state of the input or the stack is to be termed as incorrect string for a given grammar.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-165 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-90.png\" alt=\"\" width=\"656\" height=\"793\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-90.png 656w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-90-248x300.png 248w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-90-65x79.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-90-225x272.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-90-350x423.png 350w\" sizes=\"auto, (max-width: 656px) 100vw, 656px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-166 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-91.png\" alt=\"\" width=\"659\" height=\"889\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-91.png 659w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-91-222x300.png 222w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-91-65x88.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-91-225x304.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-91-350x472.png 350w\" sizes=\"auto, (max-width: 659px) 100vw, 659px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-167 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-92.png\" alt=\"\" width=\"640\" height=\"855\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-92.png 640w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-92-225x301.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-92-65x87.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-92-350x468.png 350w\" sizes=\"auto, (max-width: 640px) 100vw, 640px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-168 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-93.png\" alt=\"\" width=\"664\" height=\"779\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-93.png 664w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-93-256x300.png 256w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-93-65x76.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-93-225x264.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-93-350x411.png 350w\" sizes=\"auto, (max-width: 664px) 100vw, 664px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-169 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-94.png\" alt=\"\" width=\"683\" height=\"843\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-94.png 683w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-94-243x300.png 243w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-94-65x80.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-94-225x278.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-94-350x432.png 350w\" sizes=\"auto, (max-width: 683px) 100vw, 683px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-170 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-95.png\" alt=\"\" width=\"700\" height=\"891\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-95.png 700w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-95-236x300.png 236w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-95-65x83.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-95-225x286.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-95-350x446.png 350w\" sizes=\"auto, (max-width: 700px) 100vw, 700px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-171 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-96.png\" alt=\"\" width=\"698\" height=\"835\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-96.png 698w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-96-251x300.png 251w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-96-65x78.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-96-225x269.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-96-350x419.png 350w\" sizes=\"auto, (max-width: 698px) 100vw, 698px\" \/><\/p>\n","protected":false},"author":4,"menu_order":10,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-rajeswari-sridhar"],"pb_section_license":""},"chapter-type":[],"contributor":[59],"license":[],"class_list":["post-164","chapter","type-chapter","status-publish","hentry","contributor-dr-rajeswari-sridhar"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/164","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":1,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/164\/revisions"}],"predecessor-version":[{"id":172,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/164\/revisions\/172"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/164\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/media?parent=164"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapter-type?post=164"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/contributor?post=164"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/license?post=164"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}