{"id":83,"date":"2018-07-19T11:27:32","date_gmt":"2018-07-19T11:27:32","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=83"},"modified":"2018-07-19T11:28:41","modified_gmt":"2018-07-19T11:28:41","slug":"slr-parsing","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/slr-parsing\/","title":{"rendered":"SLR PARSING"},"content":{"raw":"

In this module, we will discuss the parsing action of the SLR parser. The parser uses the SLR parsing table already discussed in the previous module and uses a stack and compares the contents of the stack with the input symbol and manipulates the stack by referring to the parsing table.<\/p>\r\n \r\n\r\n16.1 Parsing algorithm<\/strong>\r\n\r\n \r\n

As in the case of LL(1), Shift-reduce and Operator precedence parser discussed so far, the SLR(1) parser also uses a stack for manipulating the input string and decide on successful or unsuccessful parsing action. The stack is loaded with the initial state symbol 0. As we already discussed in the previous module, the set of items number correspond to the state of the parsing table. The input string is appended with $ symbol. The contents of the stack and the input is shown in figure 16.1<\/p>\r\n\"\"\r\n

of the RHS of the production from the stack. We then observe the state number after popping and let the state be sm -r. The LHS of the production A is pushed onto the stack and the combination of sm-r, A is looked in the goto() section of the SLR parsing table and the corresponding state number is pushed onto the stack. The input pointer stays as it is in the previous iteration<\/p>\r\n\r\n

    \r\n \t
  1. If action<\/em>[s<\/em>m<\/em> ,a<\/em>i<\/em>] = accept, then stop<\/li>\r\n<\/ol>\r\n

    This is a terminating action of the parsing table where the action corresponds to accept and this would be typically reached only if ai corresponds to \u201c$\u201d as it is the only combination in the table that has the accept action.<\/p>\r\n\r\n

      \r\n \t
    1. If action<\/em>[s<\/em>m<\/em> ,a<\/em>i<\/em>] = error, then attempt recovery<\/li>\r\n<\/ol>\r\n

      If the table entry corresponds to an empty entry then we claim it as an error combination and the parser has to go through a error recovery process.<\/p>\r\n \r\n\r\nThe algorithm is given is Algorithm 16.1\r\n\r\n \r\n\r\nSLR_PARSING(SLR_Parsing_table T, Input w$)\r\n\r\n \r\n\r\n{\r\n

        \r\n \t
      • Set input to point to the first symbol of w$<\/li>\r\n \t
      • Repeat forever<\/li>\r\n<\/ul>\r\nLet s be the state on the top of the stack\r\n
          \r\n \t
        1. Let a be the symbol pointed to by ip<\/li>\r\n \t
        2. If action [s, a] = shift s\u2019 then\r\n
            \r\n \t
          1. Push a then s\u2019 on top of the stack<\/li>\r\n<\/ol>\r\n<\/li>\r\n<\/ol>\r\n
              \r\n \t
            1. Move input to the next input symbol<\/li>\r\n<\/ol>\r\n
                \r\n \t
              • Else if action [s, a] = reduce A \u00e0 \u03b2 then\r\n
                  \r\n \t
                1. Pop 2 * | \u03b2 | symbols off the stack<\/li>\r\n<\/ol>\r\n<\/li>\r\n<\/ul>\r\n
                    \r\n \t
                  1. Let s\u2019 be the state now on the top of the stack<\/li>\r\n \t
                  2. Push A then goto [s\u2019, A] on top of the stack<\/li>\r\n \t
                  3. Output the production A \u00e0 \u03b2<\/li>\r\n \t
                  4. Else if action[s, a] = accept then return;<\/li>\r\n \t
                  5. Else error()<\/li>\r\n<\/ol>\r\n}\r\n\r\n \r\n\r\nThe steps from (ii) to (v) correspond to the steps (1) to (4) of the earlier procedure.\r\n\r\n \r\n

                    Example 16.1 Consider the string \u201cid * id +id\u201d to be parsed by the SLR parser. For convenience the SLR parsing table is given in Table 16.1. The input string is appended with $ to indicate end of input. The overall parsing action is given in Table 16.2 where the comments column indicates how parsing action is done.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n\"\"\r\n

                    \r\n

                    If the input has the next symbol as \u201c)\u201d after the last but one step in Table 16.2, we need to compare [1, )]. As we know from the parsing table 16.1, the table entry is blank which means the input is not accepted and the parser cannot continue parsing. For these situations, error recovery mechanisms in terms of panic \/ phrase mode need to be applied. We can also cla im that \u201cEvery SLR grammar is unambiguous, but not<\/strong> every unambiguous grammar is SLR\u201d. This means that the SLR parser can parse only a small class of grammar.<\/p>\r\n\r\n<\/div>\r\n \r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n \r\n\r\n\"\"","rendered":"

                    In this module, we will discuss the parsing action of the SLR parser. The parser uses the SLR parsing table already discussed in the previous module and uses a stack and compares the contents of the stack with the input symbol and manipulates the stack by referring to the parsing table.<\/p>\n

                     <\/p>\n

                    16.1 Parsing algorithm<\/strong><\/p>\n

                     <\/p>\n

                    As in the case of LL(1), Shift-reduce and Operator precedence parser discussed so far, the SLR(1) parser also uses a stack for manipulating the input string and decide on successful or unsuccessful parsing action. The stack is loaded with the initial state symbol 0. As we already discussed in the previous module, the set of items number correspond to the state of the parsing table. The input string is appended with $ symbol. The contents of the stack and the input is shown in figure 16.1<\/p>\n

                    \"\"<\/p>\n

                    of the RHS of the production from the stack. We then observe the state number after popping and let the state be sm -r. The LHS of the production A is pushed onto the stack and the combination of sm-r, A is looked in the goto() section of the SLR parsing table and the corresponding state number is pushed onto the stack. The input pointer stays as it is in the previous iteration<\/p>\n

                      \n
                    1. If action<\/em>[s<\/em>m<\/em> ,a<\/em>i<\/em>] = accept, then stop<\/li>\n<\/ol>\n

                      This is a terminating action of the parsing table where the action corresponds to accept and this would be typically reached only if ai corresponds to \u201c$\u201d as it is the only combination in the table that has the accept action.<\/p>\n

                        \n
                      1. If action<\/em>[s<\/em>m<\/em> ,a<\/em>i<\/em>] = error, then attempt recovery<\/li>\n<\/ol>\n

                        If the table entry corresponds to an empty entry then we claim it as an error combination and the parser has to go through a error recovery process.<\/p>\n

                         <\/p>\n

                        The algorithm is given is Algorithm 16.1<\/p>\n

                         <\/p>\n

                        SLR_PARSING(SLR_Parsing_table T, Input w$)<\/p>\n

                         <\/p>\n

                        {<\/p>\n

                          \n
                        • Set input to point to the first symbol of w$<\/li>\n
                        • Repeat forever<\/li>\n<\/ul>\n

                          Let s be the state on the top of the stack<\/p>\n

                            \n
                          1. Let a be the symbol pointed to by ip<\/li>\n
                          2. If action [s, a] = shift s\u2019 then\n
                              \n
                            1. Push a then s\u2019 on top of the stack<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n
                                \n
                              1. Move input to the next input symbol<\/li>\n<\/ol>\n
                                  \n
                                • Else if action [s, a] = reduce A \u00e0 \u03b2 then\n
                                    \n
                                  1. Pop 2 * | \u03b2 | symbols off the stack<\/li>\n<\/ol>\n<\/li>\n<\/ul>\n
                                      \n
                                    1. Let s\u2019 be the state now on the top of the stack<\/li>\n
                                    2. Push A then goto [s\u2019, A] on top of the stack<\/li>\n
                                    3. Output the production A \u00e0 \u03b2<\/li>\n
                                    4. Else if action[s, a] = accept then return;<\/li>\n
                                    5. Else error()<\/li>\n<\/ol>\n

                                      }<\/p>\n

                                       <\/p>\n

                                      The steps from (ii) to (v) correspond to the steps (1) to (4) of the earlier procedure.<\/p>\n

                                       <\/p>\n

                                      Example 16.1 Consider the string \u201cid * id +id\u201d to be parsed by the SLR parser. For convenience the SLR parsing table is given in Table 16.1. The input string is appended with $ to indicate end of input. The overall parsing action is given in Table 16.2 where the comments column indicates how parsing action is done.<\/p>\n

                                       <\/p>\n

                                      \"\"<\/p>\n

                                      \"\"<\/p>\n

                                      \n

                                      If the input has the next symbol as \u201c)\u201d after the last but one step in Table 16.2, we need to compare [1, )]. As we know from the parsing table 16.1, the table entry is blank which means the input is not accepted and the parser cannot continue parsing. For these situations, error recovery mechanisms in terms of panic \/ phrase mode need to be applied. We can also cla im that \u201cEvery SLR grammar is unambiguous, but not<\/strong> every unambiguous grammar is SLR\u201d. This means that the SLR parser can parse only a small class of grammar.<\/p>\n<\/div>\n

                                       <\/p>\n

                                      \"\"<\/p>\n

                                      \"\"<\/p>\n

                                       <\/p>\n

                                      \"\"<\/p>\n","protected":false},"author":4,"menu_order":16,"template":"","meta":{"_acf_changed":false,"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-83","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\/83","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\/83\/revisions"}],"predecessor-version":[{"id":90,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/83\/revisions\/90"}],"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\/83\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/media?parent=83"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapter-type?post=83"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/contributor?post=83"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/license?post=83"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}