{"id":99,"date":"2018-07-19T11:58:39","date_gmt":"2018-07-19T11:58:39","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=99"},"modified":"2018-07-19T11:58:56","modified_gmt":"2018-07-19T11:58:56","slug":"lalr-parsing","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/lalr-parsing\/","title":{"rendered":"LALR parsing"},"content":{"raw":"After understanding the most powerful CALR parser, in this module we will learn to construct the LALR parser. The CALR parser has a large set of items and hence the LALR parser is designed that has lesser number of items but with reduction in the number of conflicts which is a problem of SLR parser. This module will discuss the construction of LR(1) items necessary for LALR parsing, LALR parsing table followed by parsing a string using the LALR parser.\r\n\r\n&nbsp;\r\n\r\n<strong>18.1 Need for LALR parser<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Though the CALR parser is powerful enough in avoiding the conflicts of the SLR parser, it suffers from a large set of LR(1) items. This increases the number of entries in the CALR parsing table and thus increases the time complexity of computation and parsing. Increase in the number of items is reduced in LALR parsing table by combining the items that have the same core items but different look-ahead. Thus this is less powerful than CALR parser but avoids shift\/reduce conflicts as shifts do not use look-ahead. As we are combining the items with different look-ahead into one, the LALR parser may introduce reduce-reduce conflicts, but not much of a problem for grammars of programming languages.<\/p>\r\n&nbsp;\r\n\r\n18.2 LR(1) items\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The algorithm for LR(1) items for the LALR parser is computed by first constructing the LR(1) items as in the case of the CALR parser and then combining the items that have the same item-set but differing look-ahead into one item. The algorithm for the CALR\u2019s LR(1) items construction is discussed in module 17. Combining the items alone is discussed by means of an example.<\/p>\r\n&nbsp;\r\n\r\nExample 18.1\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Let us construct the LR(1) items for the grammar given below to construct the LALR parsing table.<\/p>\r\nS \u00e0 CC\r\n\r\nC \u00e0 cC\r\n\r\nC \u00e0 d\r\n<p style=\"text-align: justify\">The augmented grammar is given below and the CALR\u2019s LR(1) items are repeated here for a quick reference in Table 18.1<\/p>\r\n\r\n<ul>\r\n \t<li>S\u2019 \u00e0 S<\/li>\r\n \t<li>S \u00e0 CC<\/li>\r\n \t<li>C \u00e0 cC<\/li>\r\n \t<li>C \u00e0 d<\/li>\r\n<\/ul>\r\n<img class=\"size-full wp-image-100 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-49.png\" alt=\"\" width=\"695\" height=\"828\" \/>\r\n\r\n<img class=\"size-full wp-image-101 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-50.png\" alt=\"\" width=\"647\" height=\"856\" \/>\r\n\r\n<img class=\"size-full wp-image-102 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-51.png\" alt=\"\" width=\"654\" height=\"799\" \/>\r\n\r\n<img class=\"size-full wp-image-103 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-52.png\" alt=\"\" width=\"675\" height=\"861\" \/>\r\n\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-104 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-53.png\" alt=\"\" width=\"658\" height=\"457\" \/>\r\n\r\n&nbsp;\r\n<div>\r\n\r\n18.4 Conflicts in LL and LR Parsers\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">LL\u00a0 parsing tables are computed using FIRST\/FOLLOW where the rows correspond to the non-terminals and the columns correspond to the terminals. To construct the parsing table the grammar need to be pre-processed to remove left recursion and need to be left factored and generate a modified grammar. This modified grammar is used to construct the FIRST and FOLLOW which are used to construct the parsing table.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">LR parsing tables are computed using Closure and Goto, where the actions correspond to the shift, reduce, accept and error situation. The three types of LR parsers are SLR, CALR and LALR and all of them constructs a parsing table where the rows correspond to the states which are the result of LR() items and the columns corresponds to the terminals and non-terminals.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">This parsing table is fundamental and is very important for the parsing action. An incorrect parsing table will result in an ambiguous parsing. A grammar is said to be LL(1) if its LL(1) parse table has no conflicts, SLR if its SLR parse table has no conflicts, LALR(1) if its LALR(1) parse table has no conflicts and CALR(1) if its CALR(1) parse table has no conflicts. The conflicts can be shift \/ reduce conflict or a reduce\/ reduce conflict.<\/p>\r\n\r\n<\/div>\r\n&nbsp;\r\n\r\nConflicts in LL and LR parsers\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Conflicts are resolved depending on whether operators \/ symbols involved are left\/right associative or precedence. The following is the manner in which the parsers resolve the conflicts.<\/p>\r\n\r\n<ul>\r\n \t<li>For Left-associative operators the conflict is resolved in favor of reduce action.<\/li>\r\n \t<li>For Right-associative operators the conflict is resolved in favor of shift action.<\/li>\r\n \t<li>If the stack has a higher precedent operator the conflict is in favor of reduce action.<\/li>\r\n \t<li>If the stack has a lower precedent operator the conflict is in favor of shift action.<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\n<strong>18.5 Error Detection and Recovery<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Canonical LR parser uses full LR (1) parse table and will never make a single reduction before recognizing the error when a syntax error occurs on the input. SLR and LALR may still reduce when a syntax error occurs on the input, but will never shift the erroneous input symbol. An error is detected if the symbol on top of the stack and the input symbol do not have a LR parsing table entry. The parsers recover from errors so that the compilation can be carried forward and will not make it as a permanent change. The errors are recovered in one of the following ways:<\/p>\r\n&nbsp;\r\n<ul>\r\n \t<li style=\"text-align: justify\">Panic mode: In this mode of error recovery, the stack symbols are popped until a state with a goto on a non-terminal <em>A<\/em> is found, where <em>A<\/em> represents a non-terminal of the grammar. From the input, the symbols are discarded until we find a symbol in the input that matches with the FOLLOW set of <em>A.<\/em><\/li>\r\n \t<li style=\"text-align: justify\">Phrase-level recovery: We implement individual error routines and call appropriate routines which will pop the stack \/ discard the input or both and log this information in an error log and recovers from error so that parsing could continue.<\/li>\r\n \t<li style=\"text-align: justify\">Error productions: New error productions are added to the grammar. In the event of an incorrect state and table entry match, the symbols in the stack are popped until state has error production and this is pushed onto the stack. After that the input symbols are discarded till a parsing action could continue.<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\n<strong>Summary<\/strong>:\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In this module we discussed the construction of LR(1) items for the LALR parser which is a modified LR(1) items after constructing it for the CALR parser. Using the modified LR(1) items the LALR parsing table is constructed and is used to parser a given string. We also discussed the LALR parsing action along with error recovery in LR parsers.<\/p>","rendered":"<p>After understanding the most powerful CALR parser, in this module we will learn to construct the LALR parser. The CALR parser has a large set of items and hence the LALR parser is designed that has lesser number of items but with reduction in the number of conflicts which is a problem of SLR parser. This module will discuss the construction of LR(1) items necessary for LALR parsing, LALR parsing table followed by parsing a string using the LALR parser.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>18.1 Need for LALR parser<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Though the CALR parser is powerful enough in avoiding the conflicts of the SLR parser, it suffers from a large set of LR(1) items. This increases the number of entries in the CALR parsing table and thus increases the time complexity of computation and parsing. Increase in the number of items is reduced in LALR parsing table by combining the items that have the same core items but different look-ahead. Thus this is less powerful than CALR parser but avoids shift\/reduce conflicts as shifts do not use look-ahead. As we are combining the items with different look-ahead into one, the LALR parser may introduce reduce-reduce conflicts, but not much of a problem for grammars of programming languages.<\/p>\n<p>&nbsp;<\/p>\n<p>18.2 LR(1) items<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The algorithm for LR(1) items for the LALR parser is computed by first constructing the LR(1) items as in the case of the CALR parser and then combining the items that have the same item-set but differing look-ahead into one item. The algorithm for the CALR\u2019s LR(1) items construction is discussed in module 17. Combining the items alone is discussed by means of an example.<\/p>\n<p>&nbsp;<\/p>\n<p>Example 18.1<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Let us construct the LR(1) items for the grammar given below to construct the LALR parsing table.<\/p>\n<p>S \u00e0 CC<\/p>\n<p>C \u00e0 cC<\/p>\n<p>C \u00e0 d<\/p>\n<p style=\"text-align: justify\">The augmented grammar is given below and the CALR\u2019s LR(1) items are repeated here for a quick reference in Table 18.1<\/p>\n<ul>\n<li>S\u2019 \u00e0 S<\/li>\n<li>S \u00e0 CC<\/li>\n<li>C \u00e0 cC<\/li>\n<li>C \u00e0 d<\/li>\n<\/ul>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-100 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-49.png\" alt=\"\" width=\"695\" height=\"828\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-49.png 695w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-49-252x300.png 252w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-49-65x77.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-49-225x268.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-49-350x417.png 350w\" sizes=\"auto, (max-width: 695px) 100vw, 695px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-101 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-50.png\" alt=\"\" width=\"647\" height=\"856\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-50.png 647w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-50-227x300.png 227w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-50-65x86.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-50-225x298.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-50-350x463.png 350w\" sizes=\"auto, (max-width: 647px) 100vw, 647px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-102 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-51.png\" alt=\"\" width=\"654\" height=\"799\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-51.png 654w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-51-246x300.png 246w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-51-65x79.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-51-225x275.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-51-350x428.png 350w\" sizes=\"auto, (max-width: 654px) 100vw, 654px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-103 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-52.png\" alt=\"\" width=\"675\" height=\"861\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-52.png 675w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-52-235x300.png 235w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-52-65x83.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-52-225x287.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-52-350x446.png 350w\" sizes=\"auto, (max-width: 675px) 100vw, 675px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-104 aligncenter\" src=\"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-53.png\" alt=\"\" width=\"658\" height=\"457\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-53.png 658w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-53-300x208.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-53-65x45.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-53-225x156.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-content\/uploads\/sites\/50\/2018\/07\/Untitled-53-350x243.png 350w\" sizes=\"auto, (max-width: 658px) 100vw, 658px\" \/><\/p>\n<p>&nbsp;<\/p>\n<div>\n<p>18.4 Conflicts in LL and LR Parsers<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">LL\u00a0 parsing tables are computed using FIRST\/FOLLOW where the rows correspond to the non-terminals and the columns correspond to the terminals. To construct the parsing table the grammar need to be pre-processed to remove left recursion and need to be left factored and generate a modified grammar. This modified grammar is used to construct the FIRST and FOLLOW which are used to construct the parsing table.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">LR parsing tables are computed using Closure and Goto, where the actions correspond to the shift, reduce, accept and error situation. The three types of LR parsers are SLR, CALR and LALR and all of them constructs a parsing table where the rows correspond to the states which are the result of LR() items and the columns corresponds to the terminals and non-terminals.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">This parsing table is fundamental and is very important for the parsing action. An incorrect parsing table will result in an ambiguous parsing. A grammar is said to be LL(1) if its LL(1) parse table has no conflicts, SLR if its SLR parse table has no conflicts, LALR(1) if its LALR(1) parse table has no conflicts and CALR(1) if its CALR(1) parse table has no conflicts. The conflicts can be shift \/ reduce conflict or a reduce\/ reduce conflict.<\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<p>Conflicts in LL and LR parsers<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Conflicts are resolved depending on whether operators \/ symbols involved are left\/right associative or precedence. The following is the manner in which the parsers resolve the conflicts.<\/p>\n<ul>\n<li>For Left-associative operators the conflict is resolved in favor of reduce action.<\/li>\n<li>For Right-associative operators the conflict is resolved in favor of shift action.<\/li>\n<li>If the stack has a higher precedent operator the conflict is in favor of reduce action.<\/li>\n<li>If the stack has a lower precedent operator the conflict is in favor of shift action.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p><strong>18.5 Error Detection and Recovery<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Canonical LR parser uses full LR (1) parse table and will never make a single reduction before recognizing the error when a syntax error occurs on the input. SLR and LALR may still reduce when a syntax error occurs on the input, but will never shift the erroneous input symbol. An error is detected if the symbol on top of the stack and the input symbol do not have a LR parsing table entry. The parsers recover from errors so that the compilation can be carried forward and will not make it as a permanent change. The errors are recovered in one of the following ways:<\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li style=\"text-align: justify\">Panic mode: In this mode of error recovery, the stack symbols are popped until a state with a goto on a non-terminal <em>A<\/em> is found, where <em>A<\/em> represents a non-terminal of the grammar. From the input, the symbols are discarded until we find a symbol in the input that matches with the FOLLOW set of <em>A.<\/em><\/li>\n<li style=\"text-align: justify\">Phrase-level recovery: We implement individual error routines and call appropriate routines which will pop the stack \/ discard the input or both and log this information in an error log and recovers from error so that parsing could continue.<\/li>\n<li style=\"text-align: justify\">Error productions: New error productions are added to the grammar. In the event of an incorrect state and table entry match, the symbols in the stack are popped until state has error production and this is pushed onto the stack. After that the input symbols are discarded till a parsing action could continue.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p><strong>Summary<\/strong>:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In this module we discussed the construction of LR(1) items for the LALR parser which is a modified LR(1) items after constructing it for the CALR parser. Using the modified LR(1) items the LALR parsing table is constructed and is used to parser a given string. We also discussed the LALR parsing action along with error recovery in LR parsers.<\/p>\n","protected":false},"author":4,"menu_order":18,"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-99","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\/99","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\/99\/revisions"}],"predecessor-version":[{"id":105,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/99\/revisions\/105"}],"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\/99\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/media?parent=99"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapter-type?post=99"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/contributor?post=99"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/license?post=99"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}