{"id":91,"date":"2018-07-19T11:52:34","date_gmt":"2018-07-19T11:52:34","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=91"},"modified":"2018-07-19T11:52:51","modified_gmt":"2018-07-19T11:52:51","slug":"calr-parsing","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/calr-parsing\/","title":{"rendered":"CALR Parsing"},"content":{"raw":"
\r\n\r\nAfter discussing the SLR parsing and the problems associated with the SLR parsers, this module will discuss the powerful LR parser \u2013 Canonical LR parser. In this module, we will learn to construct LR(1) items which is necessary for constructing the CALR parsing table and using this table parse a given string using the CALR parser.\r\n\r\n \r\n\r\n17.1 Need for CALR parsers<\/strong>\r\n\r\n \r\n

In the SLR parser, there is a problem of shift \/ reduce conflict even if the grammar is unambiguous. This is due to the fact that the SLR parsers uses the FOLLOW() information to perform a reduce action by matching the stack information with input symbol. However the FOLLOW() information alone is not sufficient to decide when to reduce. Hence, powerful parser is required.<\/p>\r\n \r\n\r\nThe issues associated with considering the FOLLOW() information is discussed as follows:\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 In SLR, if there is a production of the form A \u00e0 \u03b1\u25aa , then a reduce action takes place based on FOLLOW(A).\r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 However, there would be situations, where, when state \u2018I\u2019 appears on the top of the stack, the viable prefix \u03b2\u03b1 on the stack is such that \u03b2A cannot be followed by terminal \u2018a\u2019 in a right sentential form. Hence, the reduction A \u00e0 \u03b1 would be invalid on input \u2018a\u2019<\/p>\r\n \r\n

This results in the shift\/reduce conflict. To resolve this conflict, we will consider and check whether it is possible to perform more in the states that allow us to rule out some of the invalid reduction. This is done by introducing more set of items thus resulting in more states in the CALR parsing table. Thus we would be introducing exactly which input symbols to follow a particular non-terminal.<\/p>\r\n \r\n\r\n17.2 CALR Parser<\/strong>\r\n\r\n \r\n\r\nThe steps involved in the CALR parser are as follows:\r\n\r\n \r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Construct LR(1) items \u2013 This is in contrast with the LR(0) items that is constructed for the SLR parser. This also uses Closure() and goto(), but the algorithm for these two functions are different.<\/p>\r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 LR(1) items are used to construct the CALR parsing table involving action, goto.- The parsing table resembles SLR parsing table but has more states and there is little variation in the construction procedure.<\/p>\r\n \r\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Use this table, along with input string and a stack is used to parse the string \u2013 The parsing action is same as the SLR parser\u2019s algorithm.<\/p>\r\n\r\n<\/div>\r\n

\r\n

The CALR parser uses the LR(1) items. The LR(1) items are constructed and this results in increased number of states. The states are increased by accommodating an extra symbol in the items to include a terminal symbol as a second component. Thus A \u00e0[\u03b1 .\u03b2, a] will be the item in the LR(1) items collection, if A \u00e0\u03b1\u03b2 is a production and \u2018a\u2019 is a terminal or the right end marker. If there is no terminal available then the right end marker is $.<\/p>\r\n \r\n\r\n17.2.1. LR(1) item construction<\/strong>\r\n\r\n \r\n

LR(1) items are constructed that has a right end marker in addition to the format of the LR(0) items. The \u20181\u2019 refers to the length of the second component which is the look-ahead of the item. This look-ahead has no effect in A \u00e0[\u03b1 .\u03b2 , a] where \u03b2 is not \u03b5, but will ensure that a conflict does not arise if A \u00e0[\u03b1 . , a] calls for a reduction A \u00e0 \u03b1 if the next input symbol is \u2018a\u2019. This terminal \u2018a\u2019 will be subset of FOLLOW(A). A \u00e0 [\u03b1 .\u03b2 , a] is a valid item for a viable prefix \u03b3 if there is a derivation S => \u03b4Aw => \u03b4\u03b1\u03b2w where \u03b3 = \u03b4\u03b1 and either \u2018a\u2019 is the first symbol of \u2018w\u2019 or \u2018w\u2019 is \u03b5 and \u2018a\u2019 is $.<\/p>\r\n \r\n

LR(1) items construction requires computation of closure() and goto(). The computation of Closure(I) is given in algorithm 17.1. This algorithm is similar to the LR(0)\u2019s closure in considering the augmented grammar to start this, but will accommodate the look-ahead component.<\/p>\r\n \r\n\r\nAlgorithm 17.1\r\n\r\nClosure(I, Augment grammar G\u2019)\r\n\r\n \r\n\r\n{\r\n\r\nrepeat\r\n\r\na.\u00a0\u00a0\u00a0 for each item [A \u00e0 \u03b1\u25aaB\u03b2, a] in I,\r\n\r\neach production B \u00e0 \u03b3 in G\u2019and each terminal b in F IRST(\u03b2a)\r\n\r\nsuch that [B \u00e0 .\u03b3 , b] is not in I do\r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 add [B \u00e0 .\u03b3 , b]\r\n\r\nuntil no more items can be added to I\r\n\r\n \r\n\r\n}\r\n

Step \u2018a\u2019 of the algorithm 17.1 initially starts by adding the initial production of the augmented grammar as an item with the look-ahead as $. After that it considers the non-terminal that appears after the dot. This item is added and its look-ahead is computed by computing the FIRST() of the remaining symbols after this non-terminal including the current look-ahead. So, if\u00a0 \u00a0\u03b2\u00a0 is \u03b5, even than as \u2018a\u2019 is \u2018$\u2019 to start with, the look-ahead will be FIRST($). We keep adding till no more items can be added. Thus the difference between LR(1) and LR(0) is that in considering FIRST(\u03b2a) and adding \u2018a\u2019 as a look-ahead. It is interesting to observe that a single item-set may contain the same items with different look-aheads.\u00a0\u00a0The next algorithm is to compute the goto(I, X) where X is a grammar symbol. This is given in Algorithm 17.2. This algorithm is the same as LR(0)\u2019s goto() but this incorporates the look-ahead symbol.<\/span><\/p>\r\n\r\n<\/div>\r\nAlgorithm 17.2<\/strong>\r\n\r\n \r\n\r\ngoto(I,X)\r\n\r\n \r\n\r\n{\r\n

    \r\n \t
  1. Let J be the set of items [A\u00e0\u03b1X.\u03b2 , a] such that [A\u00e0\u03b1.X\u03b2 , a] is in I;<\/li>\r\n<\/ol>\r\nReturn closure(J)\r\n\r\n}\r\n\r\n \r\n

    Step \u2018a\u2019 of algorithm 17.2, shifts the dot by one position to the right of an item, retaining the look-ahead of the original item. Then after shifting, we compute closure of the shifted item and add that to the set of items. So, if \u03b2 is a non-terminal, we add more items to the current item set with different \/ same look-ahead and if it is a terminal we do not have any more new items to the current item set.<\/p>\r\n \r\n\r\nAfter computing the closure() and goto(), we use these two functions to compute LR(1) items and is given in algorithm 17.3\r\n\r\n \r\n\r\nAlgorithm 17.3<\/strong>\r\n\r\n \r\n\r\nITEMS(Grammar G\u2019)\r\n\r\n \r\n\r\n{C:= closure ( {S\u2019 \u00e0 .S, $}); repeat\r\n\r\nfor each set of items I in C and each grammar symbol X such that goto(I,X) is not empty\r\n\r\n \r\n\r\nand not in C\r\n\r\nadd goto(I, X) to C\r\n\r\n \r\n\r\nuntil no more set of items can be added to C\r\n\r\n}\r\n\r\n \r\n\r\nThis algorithm is same as the LR(0) items construction algorithm, but it considers the items with look-ahead.\r\n\r\n \r\n\r\nExample 17.1 Consider the following grammar and construct the LR(1) items\r\n\r\nS \u00e0 CC\r\n\r\nC \u00e0 cC\r\n\r\nC \u00e0 d\r\n\r\nWe form the Augmented grammar by introducing the new start symbol S\u2019 and form the set of items and is given in table 17.1\r\n\r\n\"\"\r\n

    \r\n\r\nThe LR(1) items can also be represented as a DFA similar to the LR(0) items where the states correspond to the nodes and edges correspond to the grammar symbols.\r\n\r\n<\/div>\r\n \r\n
    \r\n\r\n17.2.2 CALR Parsing Table<\/strong>\r\n\r\n \r\n

    If we could recollect the SLR parsing table requires the knowledge of the FOLLOW() of the non-terminals. This FOLLOW() set is used to populate the SLR parsing table for the reduce action. This is however not required here as the look-ahead which is conveyed by the FOLLOW() in the SLR parsing table, is available along with the item itself in the LR(1) items. The CALR parsing table also has two divisions: action and goto. The action() fields are constituted by the terminals and it has the shift, reduce, accep t and error actions. The goto() fields are constituted by the non-terminals and it contains the state numbers which is the result of the goto(). The procedure for the CALR parsing table construction is given in Algorithm 17.4.<\/p>\r\n \r\n\r\nAlgorithm 17.4\r\n\r\n \r\n\r\nCALR_ParsingTable (Augmented Grammar G\u2019)\r\n\r\n \r\n\r\n{\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 Construct C = {I0 ,I1 ,I2 \u2026 In } the collection of LR(1) items for G\u2019\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 State \u2018i' of the parser is from Ii\r\n\r\ni.\u00a0\u00a0\u00a0\u00a0\u00a0 if [A \u00e0 \u03b1.a\u03b2, b] is in Ii and goto(Ii, a) = Ij set action [i, a] = shift j, where a is a terminal\r\n\r\nii.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 if [ A \u00e0 \u03b1 . , a] is in Ii\u00a0 and A \u2260 S\u2019, then set action[i, a] = reduce by A \u00e0 \u03b1 a.\u00a0 \/\/a conflict here implies the grammar is not CALR grammar\r\n\r\niii.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 if [S\u2019 \u00e0 .S, $] implies an accept action at action[i,$] = accept\r\n\r\niv.\u00a0\u00a0\u00a0\u00a0\u00a0 all other entries are error\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0 If goto(Ii , A) = Ij then goto (i, A) = j\r\n\r\n4.\u00a0\u00a0\u00a0\u00a0\u00a0 All other entries are error\r\n\r\n}\r\n\r\n \r\n

    Step 1 of the algorithm 17.4 calls for the construction of the LR(1) items. Step 2 has four actions which are used to construct the action field of the CALR parsing table. The first one is a shift action which is the same as the SLR table\u2019s shift action. If goto(Ii, a) = Ij then at the intersection of [i, a] we set the action as \u201csj\u201d to indicate \u201cshift j\u201d. Step 2 (ii) of the algorithm is for reduce action where the kernel items are considered. At the table entry of kernel item number and the look-ahead symbol we add the action reduce by the production indicated by the kernel item. The item number that has the initial kernel item is used to indicate the accept action as in the SLR parsing table. All other entries are considered as error in the action field of the CALR parsing table. The goto() field is the same as the SLR table\u2019s goto field. If goto(Ii , A) = Ij then goto (i, A) = j is added to the CALR parsing table.<\/p>\r\n \r\n\r\nExample 17.2\r\n\r\n \r\n\r\nFor the grammar discussed in example 17.1, let us construct the CALR parsing table based on the set of items discussed in Table 17.1. The CALR parsing table is given in Table 17.2\r\n\r\n<\/div>\r\n\"\"\r\n

    \r\n\r\n17.2.3 CALR parsing\r\n\r\n \r\n\r\nCALR parsing action is exactly same as the SLR parsing action but this is done with the help of CALR parsing table. The stack is initialized with the state 0. The stack contains alternately state number and the grammar symbol with the state number on the stack. The input is appended with $. The stack symbol and the input are compared in the table and the stack is manipulated accordingly. The CALR parsing table is given in Algorithm 17.5\r\n\r\n \r\n\r\nAlgortihm 17.5\r\n\r\n \r\n\r\nCALR Parsing Table (Table T, Input w$)\r\n\r\n \r\n\r\n{\r\n\r\n<\/div>\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\n\u2013\u00a0 Let s be the state on the top of the stack\r\n\r\n\u2013\u00a0 Let a be the symbol pointed to by ip\r\n\r\n\u2013\u00a0 If action [s, a] = shift s\u2019 then\r\n
        \r\n \t
      • Push a then s\u2019 on top of the stack<\/li>\r\n \t
      • Move input to the next input symbol<\/li>\r\n<\/ul>\r\n\u2013\u00a0 Else if action [s, a] = reduce A \u00e0 \u03b2 then\r\n
          \r\n \t
        • Pop 2 * | \u03b2 | symbols off the stack<\/li>\r\n<\/ul>\r\n\u2013\u00a0 Let s\u2019 be the state now on the top of the stack\r\n
            \r\n \t
          • Push A then goto [s\u2019, A] on top of the stack<\/li>\r\n \t
          • Output the production A \u00e0 \u03b2<\/li>\r\n<\/ul>\r\n\u2013\u00a0 Else if action[s, a] = accept then return;\r\n\r\n\u2013\u00a0 Else error()\r\n\r\n}\r\n\r\n \r\n\r\nExample 17.3\r\n\r\n \r\n\r\nTable 17.2 could be used to parse the string \u201cccdd\u201d and is explained in table 17.3\r\n\r\n \r\n\r\n\"\"\r\n\r\nExample 17.3\r\n\r\n \r\n\r\nWe considered the pointer variable declaration grammar having the shift \/ reduce conflict in the SLR parsing table. Let us construct the CALR parsing table and verify whether it is a CALR grammar.\r\n
              \r\n \t
            • S\u2019<\/em>\u00e0 S<\/em><\/li>\r\n \t
            • S <\/em>\u00ae L <\/em>= R<\/em><\/li>\r\n \t
            • S<\/em>\u00e0 R<\/em><\/li>\r\n \t
            • L <\/em>\u00ae * R<\/em><\/li>\r\n \t
            • L \u00e0 id<\/li>\r\n \t
            • R <\/em>\u00ae L<\/em><\/li>\r\n<\/ul>\r\n \r\n\r\nThe LR(1) items is given in Table 17.4 and the parsing table is given in Table 17.5\r\n\r\n \r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n\r\n ","rendered":"
              \n

              After discussing the SLR parsing and the problems associated with the SLR parsers, this module will discuss the powerful LR parser \u2013 Canonical LR parser. In this module, we will learn to construct LR(1) items which is necessary for constructing the CALR parsing table and using this table parse a given string using the CALR parser.<\/p>\n

               <\/p>\n

              17.1 Need for CALR parsers<\/strong><\/p>\n

               <\/p>\n

              In the SLR parser, there is a problem of shift \/ reduce conflict even if the grammar is unambiguous. This is due to the fact that the SLR parsers uses the FOLLOW() information to perform a reduce action by matching the stack information with input symbol. However the FOLLOW() information alone is not sufficient to decide when to reduce. Hence, powerful parser is required.<\/p>\n

               <\/p>\n

              The issues associated with considering the FOLLOW() information is discussed as follows:<\/p>\n

               <\/p>\n

              \u2022\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 In SLR, if there is a production of the form A \u00e0 \u03b1\u25aa , then a reduce action takes place based on FOLLOW(A).<\/p>\n

              \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 However, there would be situations, where, when state \u2018I\u2019 appears on the top of the stack, the viable prefix \u03b2\u03b1 on the stack is such that \u03b2A cannot be followed by terminal \u2018a\u2019 in a right sentential form. Hence, the reduction A \u00e0 \u03b1 would be invalid on input \u2018a\u2019<\/p>\n

               <\/p>\n

              This results in the shift\/reduce conflict. To resolve this conflict, we will consider and check whether it is possible to perform more in the states that allow us to rule out some of the invalid reduction. This is done by introducing more set of items thus resulting in more states in the CALR parsing table. Thus we would be introducing exactly which input symbols to follow a particular non-terminal.<\/p>\n

               <\/p>\n

              17.2 CALR Parser<\/strong><\/p>\n

               <\/p>\n

              The steps involved in the CALR parser are as follows:<\/p>\n

               <\/p>\n

              \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Construct LR(1) items \u2013 This is in contrast with the LR(0) items that is constructed for the SLR parser. This also uses Closure() and goto(), but the algorithm for these two functions are different.<\/p>\n

              \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 LR(1) items are used to construct the CALR parsing table involving action, goto.- The parsing table resembles SLR parsing table but has more states and there is little variation in the construction procedure.<\/p>\n

               <\/p>\n

              \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Use this table, along with input string and a stack is used to parse the string \u2013 The parsing action is same as the SLR parser\u2019s algorithm.<\/p>\n<\/div>\n

              \n

              The CALR parser uses the LR(1) items. The LR(1) items are constructed and this results in increased number of states. The states are increased by accommodating an extra symbol in the items to include a terminal symbol as a second component. Thus A \u00e0[\u03b1 .\u03b2, a] will be the item in the LR(1) items collection, if A \u00e0\u03b1\u03b2 is a production and \u2018a\u2019 is a terminal or the right end marker. If there is no terminal available then the right end marker is $.<\/p>\n

               <\/p>\n

              17.2.1. LR(1) item construction<\/strong><\/p>\n

               <\/p>\n

              LR(1) items are constructed that has a right end marker in addition to the format of the LR(0) items. The \u20181\u2019 refers to the length of the second component which is the look-ahead of the item. This look-ahead has no effect in A \u00e0[\u03b1 .\u03b2 , a] where \u03b2 is not \u03b5, but will ensure that a conflict does not arise if A \u00e0[\u03b1 . , a] calls for a reduction A \u00e0 \u03b1 if the next input symbol is \u2018a\u2019. This terminal \u2018a\u2019 will be subset of FOLLOW(A). A \u00e0 [\u03b1 .\u03b2 , a] is a valid item for a viable prefix \u03b3 if there is a derivation S => \u03b4Aw => \u03b4\u03b1\u03b2w where \u03b3 = \u03b4\u03b1 and either \u2018a\u2019 is the first symbol of \u2018w\u2019 or \u2018w\u2019 is \u03b5 and \u2018a\u2019 is $.<\/p>\n

               <\/p>\n

              LR(1) items construction requires computation of closure() and goto(). The computation of Closure(I) is given in algorithm 17.1. This algorithm is similar to the LR(0)\u2019s closure in considering the augmented grammar to start this, but will accommodate the look-ahead component.<\/p>\n

               <\/p>\n

              Algorithm 17.1<\/p>\n

              Closure(I, Augment grammar G\u2019)<\/p>\n

               <\/p>\n

              {<\/p>\n

              repeat<\/p>\n

              a.\u00a0\u00a0\u00a0 for each item [A \u00e0 \u03b1\u25aaB\u03b2, a] in I,<\/p>\n

              each production B \u00e0 \u03b3 in G\u2019and each terminal b in F IRST(\u03b2a)<\/p>\n

              such that [B \u00e0 .\u03b3 , b] is not in I do<\/p>\n

              1.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 add [B \u00e0 .\u03b3 , b]<\/p>\n

              until no more items can be added to I<\/p>\n

               <\/p>\n

              }<\/p>\n

              Step \u2018a\u2019 of the algorithm 17.1 initially starts by adding the initial production of the augmented grammar as an item with the look-ahead as $. After that it considers the non-terminal that appears after the dot. This item is added and its look-ahead is computed by computing the FIRST() of the remaining symbols after this non-terminal including the current look-ahead. So, if\u00a0 \u00a0\u03b2\u00a0 is \u03b5, even than as \u2018a\u2019 is \u2018$\u2019 to start with, the look-ahead will be FIRST($). We keep adding till no more items can be added. Thus the difference between LR(1) and LR(0) is that in considering FIRST(\u03b2a) and adding \u2018a\u2019 as a look-ahead. It is interesting to observe that a single item-set may contain the same items with different look-aheads.\u00a0\u00a0The next algorithm is to compute the goto(I, X) where X is a grammar symbol. This is given in Algorithm 17.2. This algorithm is the same as LR(0)\u2019s goto() but this incorporates the look-ahead symbol.<\/span><\/p>\n<\/div>\n

              Algorithm 17.2<\/strong><\/p>\n

               <\/p>\n

              goto(I,X)<\/p>\n

               <\/p>\n

              {<\/p>\n

                \n
              1. Let J be the set of items [A\u00e0\u03b1X.\u03b2 , a] such that [A\u00e0\u03b1.X\u03b2 , a] is in I;<\/li>\n<\/ol>\n

                Return closure(J)<\/p>\n

                }<\/p>\n

                 <\/p>\n

                Step \u2018a\u2019 of algorithm 17.2, shifts the dot by one position to the right of an item, retaining the look-ahead of the original item. Then after shifting, we compute closure of the shifted item and add that to the set of items. So, if \u03b2 is a non-terminal, we add more items to the current item set with different \/ same look-ahead and if it is a terminal we do not have any more new items to the current item set.<\/p>\n

                 <\/p>\n

                After computing the closure() and goto(), we use these two functions to compute LR(1) items and is given in algorithm 17.3<\/p>\n

                 <\/p>\n

                Algorithm 17.3<\/strong><\/p>\n

                 <\/p>\n

                ITEMS(Grammar G\u2019)<\/p>\n

                 <\/p>\n

                {C:= closure ( {S\u2019 \u00e0 .S, $}); repeat<\/p>\n

                for each set of items I in C and each grammar symbol X such that goto(I,X) is not empty<\/p>\n

                 <\/p>\n

                and not in C<\/p>\n

                add goto(I, X) to C<\/p>\n

                 <\/p>\n

                until no more set of items can be added to C<\/p>\n

                }<\/p>\n

                 <\/p>\n

                This algorithm is same as the LR(0) items construction algorithm, but it considers the items with look-ahead.<\/p>\n

                 <\/p>\n

                Example 17.1 Consider the following grammar and construct the LR(1) items<\/p>\n

                S \u00e0 CC<\/p>\n

                C \u00e0 cC<\/p>\n

                C \u00e0 d<\/p>\n

                We form the Augmented grammar by introducing the new start symbol S\u2019 and form the set of items and is given in table 17.1<\/p>\n

                \"\"<\/p>\n

                \n

                The LR(1) items can also be represented as a DFA similar to the LR(0) items where the states correspond to the nodes and edges correspond to the grammar symbols.<\/p>\n<\/div>\n

                 <\/p>\n

                \n

                17.2.2 CALR Parsing Table<\/strong><\/p>\n

                 <\/p>\n

                If we could recollect the SLR parsing table requires the knowledge of the FOLLOW() of the non-terminals. This FOLLOW() set is used to populate the SLR parsing table for the reduce action. This is however not required here as the look-ahead which is conveyed by the FOLLOW() in the SLR parsing table, is available along with the item itself in the LR(1) items. The CALR parsing table also has two divisions: action and goto. The action() fields are constituted by the terminals and it has the shift, reduce, accep t and error actions. The goto() fields are constituted by the non-terminals and it contains the state numbers which is the result of the goto(). The procedure for the CALR parsing table construction is given in Algorithm 17.4.<\/p>\n

                 <\/p>\n

                Algorithm 17.4<\/p>\n

                 <\/p>\n

                CALR_ParsingTable (Augmented Grammar G\u2019)<\/p>\n

                 <\/p>\n

                {<\/p>\n

                 <\/p>\n

                1.\u00a0\u00a0\u00a0\u00a0\u00a0 Construct C = {I0 ,I1 ,I2 \u2026 In } the collection of LR(1) items for G\u2019<\/p>\n

                2.\u00a0\u00a0\u00a0\u00a0\u00a0 State \u2018i’ of the parser is from Ii<\/p>\n

                i.\u00a0\u00a0\u00a0\u00a0\u00a0 if [A \u00e0 \u03b1.a\u03b2, b] is in Ii and goto(Ii, a) = Ij set action [i, a] = shift j, where a is a terminal<\/p>\n

                ii.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 if [ A \u00e0 \u03b1 . , a] is in Ii\u00a0 and A \u2260 S\u2019, then set action[i, a] = reduce by A \u00e0 \u03b1 a.\u00a0 \/\/a conflict here implies the grammar is not CALR grammar<\/p>\n

                iii.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 if [S\u2019 \u00e0 .S, $] implies an accept action at action[i,$] = accept<\/p>\n

                iv.\u00a0\u00a0\u00a0\u00a0\u00a0 all other entries are error<\/p>\n

                3.\u00a0\u00a0\u00a0\u00a0\u00a0 If goto(Ii , A) = Ij then goto (i, A) = j<\/p>\n

                4.\u00a0\u00a0\u00a0\u00a0\u00a0 All other entries are error<\/p>\n

                }<\/p>\n

                 <\/p>\n

                Step 1 of the algorithm 17.4 calls for the construction of the LR(1) items. Step 2 has four actions which are used to construct the action field of the CALR parsing table. The first one is a shift action which is the same as the SLR table\u2019s shift action. If goto(Ii, a) = Ij then at the intersection of [i, a] we set the action as \u201csj\u201d to indicate \u201cshift j\u201d. Step 2 (ii) of the algorithm is for reduce action where the kernel items are considered. At the table entry of kernel item number and the look-ahead symbol we add the action reduce by the production indicated by the kernel item. The item number that has the initial kernel item is used to indicate the accept action as in the SLR parsing table. All other entries are considered as error in the action field of the CALR parsing table. The goto() field is the same as the SLR table\u2019s goto field. If goto(Ii , A) = Ij then goto (i, A) = j is added to the CALR parsing table.<\/p>\n

                 <\/p>\n

                Example 17.2<\/p>\n

                 <\/p>\n

                For the grammar discussed in example 17.1, let us construct the CALR parsing table based on the set of items discussed in Table 17.1. The CALR parsing table is given in Table 17.2<\/p>\n<\/div>\n

                \"\"<\/p>\n

                \n

                17.2.3 CALR parsing<\/p>\n

                 <\/p>\n

                CALR parsing action is exactly same as the SLR parsing action but this is done with the help of CALR parsing table. The stack is initialized with the state 0. The stack contains alternately state number and the grammar symbol with the state number on the stack. The input is appended with $. The stack symbol and the input are compared in the table and the stack is manipulated accordingly. The CALR parsing table is given in Algorithm 17.5<\/p>\n

                 <\/p>\n

                Algortihm 17.5<\/p>\n

                 <\/p>\n

                CALR Parsing Table (Table T, Input w$)<\/p>\n

                 <\/p>\n

                {<\/p>\n<\/div>\n

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

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

                  \u2013\u00a0 Let a be the symbol pointed to by ip<\/p>\n

                  \u2013\u00a0 If action [s, a] = shift s\u2019 then<\/p>\n

                    \n
                  • Push a then s\u2019 on top of the stack<\/li>\n
                  • Move input to the next input symbol<\/li>\n<\/ul>\n

                    \u2013\u00a0 Else if action [s, a] = reduce A \u00e0 \u03b2 then<\/p>\n

                      \n
                    • Pop 2 * | \u03b2 | symbols off the stack<\/li>\n<\/ul>\n

                      \u2013\u00a0 Let s\u2019 be the state now on the top of the stack<\/p>\n

                        \n
                      • Push A then goto [s\u2019, A] on top of the stack<\/li>\n
                      • Output the production A \u00e0 \u03b2<\/li>\n<\/ul>\n

                        \u2013\u00a0 Else if action[s, a] = accept then return;<\/p>\n

                        \u2013\u00a0 Else error()<\/p>\n

                        }<\/p>\n

                         <\/p>\n

                        Example 17.3<\/p>\n

                         <\/p>\n

                        Table 17.2 could be used to parse the string \u201cccdd\u201d and is explained in table 17.3<\/p>\n

                         <\/p>\n

                        \"\"<\/p>\n

                        Example 17.3<\/p>\n

                         <\/p>\n

                        We considered the pointer variable declaration grammar having the shift \/ reduce conflict in the SLR parsing table. Let us construct the CALR parsing table and verify whether it is a CALR grammar.<\/p>\n

                          \n
                        • S\u2019<\/em>\u00e0 S<\/em><\/li>\n
                        • S <\/em>\u00ae L <\/em>= R<\/em><\/li>\n
                        • S<\/em>\u00e0 R<\/em><\/li>\n
                        • L <\/em>\u00ae * R<\/em><\/li>\n
                        • L \u00e0 id<\/li>\n
                        • R <\/em>\u00ae L<\/em><\/li>\n<\/ul>\n

                           <\/p>\n

                          The LR(1) items is given in Table 17.4 and the parsing table is given in Table 17.5<\/p>\n

                           <\/p>\n

                          \"\"<\/p>\n

                          \"\"<\/p>\n

                           <\/p>\n

                           <\/p>\n

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