{"id":173,"date":"2018-07-20T05:44:59","date_gmt":"2018-07-20T05:44:59","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=173"},"modified":"2018-07-20T05:44:59","modified_gmt":"2018-07-20T05:44:59","slug":"top-down-parser-parsing-tableshift-reduce-parser","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/top-down-parser-parsing-tableshift-reduce-parser\/","title":{"rendered":"Top down parser-parsing table,shift reduce parser"},"content":{"raw":"
\r\n

This module will discuss the algorithm to parse a given string using a LL(1) parser by using the parsing table constructed in the previous module. The errors that could occur in the input string need to be handled which is done by calling appropriate routines. This module will also introduce the preliminary Bottom up parser namely shift-reduce parser.<\/p>\r\n \r\n\r\n11.1 Parsing Algorithm<\/strong>\r\n\r\n \r\n

The primary objective of the non-recursive predictive parser, LL(1) avoids back tracking which is a typical problem in Top-down parsing. The LL (1) parser does this by constructing a parsing table. The parsing table constructed for the expression grammar is given in Table 11.1 for a quick reference. As already discussed, the rows of the parsing table are the non-terminals and the columns correspond to the terminals. The table entries correspond to the productions that match a given non-terminals with its FIRST() list.<\/p>\r\n \r\n\r\nTable 11.1 Parsing table for the Expression grammar\r\n\r\n \r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
 <\/td>\r\nid<\/strong><\/td>\r\n+<\/strong><\/td>\r\n*<\/strong><\/td>\r\n(<\/strong><\/td>\r\n)<\/strong><\/td>\r\n$<\/strong><\/td>\r\n<\/tr>\r\n
E<\/strong><\/td>\r\nE \u00e0 TE\u2019<\/td>\r\n <\/td>\r\n <\/td>\r\nE \u00e0 TE\u2019<\/td>\r\n <\/td>\r\n <\/td>\r\n<\/tr>\r\n
E\u2019<\/strong><\/td>\r\n <\/td>\r\nE\u2019\u00e0 +TE\u2019<\/td>\r\n <\/td>\r\n <\/td>\r\nE\u2019 \u00e0 \u03b5<\/td>\r\nE\u2019 \u00e0 \u03b5<\/td>\r\n<\/tr>\r\n
T<\/strong><\/td>\r\nT \u00e0 FT\u2019<\/td>\r\n <\/td>\r\n <\/td>\r\nT \u00e0 FT\u2019<\/td>\r\n <\/td>\r\n <\/td>\r\n<\/tr>\r\n
T\u2019<\/strong><\/td>\r\n <\/td>\r\nT\u2019 \u00e0 \u03b5<\/td>\r\nT\u2019 \u00e0 *FT\u2019<\/td>\r\n <\/td>\r\nT\u2019 \u00e0 \u03b5<\/td>\r\nT\u2019 \u00e0 \u03b5<\/td>\r\n<\/tr>\r\n
F<\/strong><\/td>\r\nF \u00e0 id<\/td>\r\n <\/td>\r\n <\/td>\r\nF \u00e0 (E)<\/td>\r\n <\/td>\r\n <\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n\r\n \r\n\r\nThe algorithm for parsing is given in 11.1\r\n\r\n \r\n\r\nAlgorithm 11.1\r\n\r\n \r\n\r\nLL(1)_PARSING(Input string s, Start symbol of Grammar, Parsing table)\r\n\r\n \r\n\r\n{\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 push($<\/strong>)\r\n\r\npush(S<\/em>)\r\n\r\na <\/em>:= lookahead<\/em>\r\n\r\n \r\n\r\n2.\u00a0 \u00a0\u00a0repeat<\/strong>\r\n\r\nX <\/em>:= pop()\r\n\r\nif <\/strong>X<\/em> is a terminal or X<\/em> = $ then<\/strong>\r\n\r\nmatch(X<\/em>) \/\/ move to next token, a<\/em> := lookahead<\/em>\r\n\r\nelse if <\/strong>M<\/em>[X<\/em>,a<\/em>] = X<\/em> \u00ae Y<\/em>1Y<\/em>2\u2026Y<\/em>k<\/em> then<\/strong>\r\n\r\npush(Y<\/em>k<\/em>, Y<\/em>k<\/em>-1, \u2026, Y<\/em>2, Y<\/em>1) \/\/ such that Y<\/em>1\u00a0 is on top\u00a0produce output and\/or invoke actions<\/span>\r\n\r\n<\/div>\r\nelse<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 error()\r\n\r\nendif<\/strong>\r\n\r\n \r\n\r\nuntil <\/strong>X<\/em> = $<\/strong>\r\n\r\n \r\n\r\n}<\/strong>\r\n\r\n \r\n

The input string is terminated with a \u201c$\u201d to serve as end-of input indicator. The parsing algorithm uses a stack memory to operate so as to parse the string. This stack memory is pushed initially with a \u201c$\u201d which acts as the initial stack symbol and it is used to indicate success\/ failure parsing action. The start symbol of the grammar is then pushed onto the stack memory, as any derivation of a string belonging to a grammar need to start from the start symbol as already discussed in Module 9. After that the input pointer starts reading the first character of the input symbol. These initialization steps are carried out in Step 1 of the algorithm. Step 2 of the algorithm is a loop which continues till the stack is empty. The input symbol \u2018a\u2019 is compared with the symbol in the stack \u2018X\u2019 and the various actions for the possible combinations are given below.<\/p>\r\n \r\n

    \r\n \t
  • If \u2018X\u2019 is a terminal and if it is \u2018a\u2019, then this character is popped from the stack and the input pointer moves by one position to process the next character.<\/li>\r\n \t
  • If \u2018X\u2019 is a non-terminal, then the parsing table is referred for [X,a] and the corresponding production available in the table entry is retrieved. The input pointer stays in the same position pointing \u2018a\u2019. The stack symbol X is popped and since this will be a LHS non-terminal, the production which is retrieved from the parsing table is pushed onto the stack. The production is read from left to right and this should be available in the stack from top to bottom, thus ensuring the first symbol on the RHS of a production is on the top of the stack.<\/li>\r\n \t
  • If \u2018X\u2019 is a terminal and if it is \u2018$\u2019 and if the input character \u2018a\u2019 is also \u2018$\u2019, then the parser announces successful completion of the parsing action.<\/li>\r\n \t
  • Any other combination of \u2018X\u2019 and \u2019a\u2019 would result in an error action.<\/li>\r\n<\/ul>\r\n \r\n\r\nExample 11.1: Consider the string id + id * id. Let us see how the parsing algorithm, parses this string. The details of it is given in Table 11.2\r\n\r\n \r\n\r\n\"\"\r\n
    \r\n\r\n11.2 Error Recovery in LL(1) Parsers<\/strong>\r\n\r\n \r\n\r\nA LL(1) parser has to recover from errors if an input string doesn\u2019t belong to it. The parser should recover from the error and should continue with the next phase of compilations.\r\n\r\n \r\n\r\n11.2.1 Error Recovery methods<\/strong>\r\n\r\n \r\n

    The parser does not correct the errors. It simply recovers from the errors in one of the many ways available and possible to recover from errors so that the compiler can proceed with the next compilation phase. The following are the various modes a parser uses to recover from errors.<\/p>\r\n \r\n\r\n\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Panic mode<\/em><\/strong>: <\/strong>In this mode of error recovery, the parser discards input until a token in a set of designated synchronizing tokens is found.\r\n\r\n<\/div>\r\n

      \r\n \t
    • Phrase-level recovery: <\/em><\/strong>In this method, the parser performs local correction on the input to repair the error<\/li>\r\n \t
    • Error productions<\/em><\/strong>: <\/strong>Error productions are added to the grammar to identify erroneous constructs<\/li>\r\n \t
    • Global correction<\/em><\/strong>: <\/strong>In this method, a minimal sequence of changes is made to the parsing algorithm to obtain a global least-cost error correction<\/li>\r\n<\/ul>\r\n11.2.2 Error recovery in LL(1) Parsers.<\/strong>\r\n\r\n \r\n\r\nThe LL(1) parsers adopts all the four methods listed above and handles it using the parsing table.\r\n
        \r\n \t
      • Panic Mode: <\/strong>In this mode, the synchronizing actions are added to the undefined entries in the parsing table based on FOLLOW() already computed. This is given in Table 11.3<\/li>\r\n<\/ul>\r\nTable 11.3 Parsing table with synch action to recover from errors for Expression grammar<\/strong>\r\n\r\n \r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
         <\/td>\r\nid<\/strong><\/td>\r\n+<\/strong><\/td>\r\n*<\/strong><\/td>\r\n(<\/strong><\/td>\r\n)<\/strong><\/td>\r\n$<\/strong><\/td>\r\n<\/tr>\r\n
        E<\/td>\r\nE \u00e0 TE\u2019<\/td>\r\n <\/td>\r\n <\/td>\r\nE \u00e0 TE\u2019<\/td>\r\nsynch<\/strong><\/td>\r\nsynch<\/strong><\/td>\r\n<\/tr>\r\n
        E\u2019<\/td>\r\n <\/td>\r\nE\u2019\u00e0 +TE\u2019<\/td>\r\n <\/td>\r\n <\/td>\r\nE\u2019 \u00e0 \u03b5<\/td>\r\nE\u2019 \u00e0 \u03b5<\/td>\r\n<\/tr>\r\n
        T<\/td>\r\nT \u00e0 FT\u2019<\/td>\r\nsynch<\/strong><\/td>\r\n <\/td>\r\nT \u00e0 FT\u2019<\/td>\r\nsynch<\/strong><\/td>\r\nsynch<\/strong><\/td>\r\n<\/tr>\r\n
        T\u2019<\/td>\r\n <\/td>\r\nT\u2019 \u00e0 \u03b5<\/td>\r\nT\u2019 \u00e0 *FT\u2019<\/td>\r\n <\/td>\r\nT\u2019 \u00e0 \u03b5<\/td>\r\nT\u2019 \u00e0 \u03b5<\/td>\r\n<\/tr>\r\n
        F<\/td>\r\nF \u00e0 id<\/td>\r\nsynch<\/strong><\/td>\r\nsynch<\/strong><\/td>\r\nF \u00e0 (E)<\/td>\r\nsynch<\/strong><\/td>\r\nsynch<\/strong><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n\r\n \r\n

        As seen from Table 11.3, the FOLLOW(E) = {$, )}. Therefore, synch actions are added to the intersection of [E, $] and [E, )]. So, when this combination occur in the parsing table and input, the parser enters into the panic mode and start deleting tokens from the input or stack till a valid combination of stack entry and input is available and logs this as error in the error table.<\/p>\r\n \r\n

          \r\n \t
        • Phrase Mode: <\/strong>In this mode, the LL(1) parser, assumes and inserts some missing characters to continue with the parsing action. For example: id id<\/strong> is changed into <\/span>id * id<\/strong> or id + id<\/strong><\/li>\r\n \t
        • Error Production: <\/strong>This is similar to the general parser recovery method. Error production are added to take care of incorrect input combinations<\/li>\r\n<\/ul>\r\nAn ambiguous grammar is not LL(1) and may have multiple entries in the parsing table. In that case, the parsing algorithm can decide to choose to apply any one of the available productions in the table entry.\r\n\r\n \r\n
          \r\n\r\n11.3 Bottom up Parsers<\/strong>\r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\nThe LL(1) parser is not a very powerful parser and cannot handle all types of grammars. We have already seen that LL(1) parser cannot handle ambiguous grammars and some grammars are inherently ambiguous. Bottom up parsers build a derivation by working from the input back toward the start symbol. The parse tree is constructed by looking at the input string and matching the RHS with the LHS of the production and correspondingly substituting it. Thus the parse tree is built from leaves towards the root. Hence, we can say the bottom- up parser builds a derivation tree by applying rightmost derivation in reverse.\r\n\r\n \r\n\r\nBottom-up parsers are powerful than their top-down counterpart and does not require any pre-processing as in the case of LL(1) parsers. There are various types of bottom- up parsers.\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Shift-Reduce Parsing \u2013 Simply constructs the right most derivation tree by replacing RHS of the production with the LHS Non-terminal.\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Operator-precedence parsing \u2013 It is a special type of Bottom \u2013up parser where a grammar has to obey the property of an infix expression.\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 LR parsers \u2013 \u2018L\u2019 stands for the input string being scanned from left to right, \u2018R\u2019 stands for applying rightmost derivation. There are various types of LR parsers\r\n\r\n \r\n\r\n\u2013\u00a0 Simple LR (SLR)\r\n\r\n \r\n\r\n\u2013\u00a0 Canonical LR (CALR)\r\n\r\n \r\n\r\n\u2013\u00a0 Look Ahead LR (LALR)\r\n\r\n \r\n\r\nAs bottom- up parsers match the RHS of production with LHS, a concept called \u2018handle\u2019 is defined. A handle<\/em> is a substring of grammar symbols in a right-sentential form<\/em> that matches a right- hand side of a production. A handle\u2019s reduction to the non-terminal on the LHS represents one step along the reverse of a rightmost derivation. For example, the following are some of the handles of the expression grammar:\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 id\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 E * E\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 (E)\r\n\r\n \r\n\r\nIn this module, we will discuss the simple shift-reduce bottom up parser and other bottom-up parsers are discussed in subsequent modules.\r\n\r\n<\/div>\r\n \r\n\r\n11.4 Shift-Reduce Parsers<\/strong>\r\n\r\n \r\n

          The shift-reduce parser is the simplest of the Bottom up Parsers. It also has a stack memory similar to a LL(1) parser. The input symbol here again is terminated with \u201c$\u201d to indicate end of input. The stack is initialized with the \u201c$\u201d symbol alone in this type of parser.<\/p>\r\n \r\n\r\n11.4.1 Parsing by Shift-Reduce Parsers<\/strong>\r\n\r\n \r\n

          The shift-reduce parser is based on two actions: \u201cshift\u201d and \u201creduce\u201d. The stack memory and the input are considered individually to perform the shift and reduce actions. The \u201cshift\u201d action simply shifts the input symbols until a handle is found into the stack by calling the push() routine. The reduce action, reduces<\/em> the substring to the non-terminal on the LHS of the corresponding production in the stack, by popping the handle and pushing the LHS non-terminals. Thus the shift-reduce parser has 4 actions:<\/p>\r\n \r\n

            \r\n \t
          • Shift <\/em>-\u00a0 the next input symbol is shifted onto the stack<\/li>\r\n \t
          • Reduce <\/em>the handle that is at top of stack<\/li>\r\n \t
          • pop handle<\/li>\r\n \t
          • push appropriate LHS symbol<\/li>\r\n \t
          • Accept <\/em>the input string, stop parsing and report success \u2013 The string is accepted if the input is completely consumed and the stack has the start symbol as its top of stack symbol.<\/li>\r\n \t
          • Error <\/em>recovery routine is called if it was not able to do any of the other 3 actions.<\/li>\r\n<\/ul>\r\n

            Example 11. 2 Consider the following ambiguous expression grammar with productions numbered from 1 to 4. Let us see the parsing action for the string \u201cid+id*id\u201d<\/p>\r\n\r\n

              \r\n \t
            1. S -> E<\/li>\r\n \t
            2. E ->E +<\/strong> E<\/li>\r\n \t
            3. E ->E *<\/strong> E<\/li>\r\n \t
            4. E\u00a0-> id<\/strong><\/li>\r\n<\/ol>\r\nThe parsing action is shown in Table 11.4\r\n\r\n \r\n\r\n\"\"\r\n\r\n11.4.2 Issues in Shift-Reduce parser<\/strong>\r\n\r\n \r\n\r\nThe shift-reduce conflict as explained in Table 11.4 is a typical problem of the Shift-reduce parser. A reduce-reduce conflict may also occur where the parser will not know which production to choose from the list of available productions for a \u201clong\u201d or \u201cshort\u201d handle. These issues are caused by\r\n
                \r\n \t
              • The limitations of the parsing method (even when the grammar is unambiguous)<\/li>\r\n \t
              • Ambiguity of the grammar<\/li>\r\n<\/ul>\r\nThese issues will be resolved by a powerful bottom up Parser and will be dealt with in subsequent modules.\r\n\r\n \r\n\r\nSummary:<\/strong>\r\n\r\n \r\n

                In this module we discussed the parsing action of LL(1) parser. The various error recovery strategies in LL(1) parsers are also discussed. This module introduced one of the simple Bottom up parser namely Shift-reduce parser and discussed the approach to parsing by this parser.<\/p>","rendered":"

                \n

                This module will discuss the algorithm to parse a given string using a LL(1) parser by using the parsing table constructed in the previous module. The errors that could occur in the input string need to be handled which is done by calling appropriate routines. This module will also introduce the preliminary Bottom up parser namely shift-reduce parser.<\/p>\n

                 <\/p>\n

                11.1 Parsing Algorithm<\/strong><\/p>\n

                 <\/p>\n

                The primary objective of the non-recursive predictive parser, LL(1) avoids back tracking which is a typical problem in Top-down parsing. The LL (1) parser does this by constructing a parsing table. The parsing table constructed for the expression grammar is given in Table 11.1 for a quick reference. As already discussed, the rows of the parsing table are the non-terminals and the columns correspond to the terminals. The table entries correspond to the productions that match a given non-terminals with its FIRST() list.<\/p>\n

                 <\/p>\n

                Table 11.1 Parsing table for the Expression grammar<\/p>\n

                 <\/p>\n\n\n\n\n\n\n\n\n
                 <\/td>\nid<\/strong><\/td>\n+<\/strong><\/td>\n*<\/strong><\/td>\n(<\/strong><\/td>\n)<\/strong><\/td>\n$<\/strong><\/td>\n<\/tr>\n
                E<\/strong><\/td>\nE \u00e0 TE\u2019<\/td>\n <\/td>\n <\/td>\nE \u00e0 TE\u2019<\/td>\n <\/td>\n <\/td>\n<\/tr>\n
                E\u2019<\/strong><\/td>\n <\/td>\nE\u2019\u00e0 +TE\u2019<\/td>\n <\/td>\n <\/td>\nE\u2019 \u00e0 \u03b5<\/td>\nE\u2019 \u00e0 \u03b5<\/td>\n<\/tr>\n
                T<\/strong><\/td>\nT \u00e0 FT\u2019<\/td>\n <\/td>\n <\/td>\nT \u00e0 FT\u2019<\/td>\n <\/td>\n <\/td>\n<\/tr>\n
                T\u2019<\/strong><\/td>\n <\/td>\nT\u2019 \u00e0 \u03b5<\/td>\nT\u2019 \u00e0 *FT\u2019<\/td>\n <\/td>\nT\u2019 \u00e0 \u03b5<\/td>\nT\u2019 \u00e0 \u03b5<\/td>\n<\/tr>\n
                F<\/strong><\/td>\nF \u00e0 id<\/td>\n <\/td>\n <\/td>\nF \u00e0 (E)<\/td>\n <\/td>\n <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

                 <\/p>\n

                 <\/p>\n

                The algorithm for parsing is given in 11.1<\/p>\n

                 <\/p>\n

                Algorithm 11.1<\/p>\n

                 <\/p>\n

                LL(1)_PARSING(Input string s, Start symbol of Grammar, Parsing table)<\/p>\n

                 <\/p>\n

                {<\/p>\n

                 <\/p>\n

                1.\u00a0\u00a0\u00a0\u00a0\u00a0 push($<\/strong>)<\/p>\n

                push(S<\/em>)<\/p>\n

                a <\/em>:= lookahead<\/em><\/p>\n

                 <\/p>\n

                2.\u00a0 \u00a0\u00a0repeat<\/strong><\/p>\n

                X <\/em>:= pop()<\/p>\n

                if <\/strong>X<\/em> is a terminal or X<\/em> = $ then<\/strong><\/p>\n

                match(X<\/em>) \/\/ move to next token, a<\/em> := lookahead<\/em><\/p>\n

                else if <\/strong>M<\/em>[X<\/em>,a<\/em>] = X<\/em> \u00ae Y<\/em>1Y<\/em>2\u2026Y<\/em>k<\/em> then<\/strong><\/p>\n

                push(Y<\/em>k<\/em>, Y<\/em>k<\/em>-1, \u2026, Y<\/em>2, Y<\/em>1) \/\/ such that Y<\/em>1\u00a0 is on top\u00a0produce output and\/or invoke actions<\/span><\/p>\n<\/div>\n

                else<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 error()<\/p>\n

                endif<\/strong><\/p>\n

                 <\/p>\n

                until <\/strong>X<\/em> = $<\/strong><\/p>\n

                 <\/p>\n

                }<\/strong><\/p>\n

                 <\/p>\n

                The input string is terminated with a \u201c$\u201d to serve as end-of input indicator. The parsing algorithm uses a stack memory to operate so as to parse the string. This stack memory is pushed initially with a \u201c$\u201d which acts as the initial stack symbol and it is used to indicate success\/ failure parsing action. The start symbol of the grammar is then pushed onto the stack memory, as any derivation of a string belonging to a grammar need to start from the start symbol as already discussed in Module 9. After that the input pointer starts reading the first character of the input symbol. These initialization steps are carried out in Step 1 of the algorithm. Step 2 of the algorithm is a loop which continues till the stack is empty. The input symbol \u2018a\u2019 is compared with the symbol in the stack \u2018X\u2019 and the various actions for the possible combinations are given below.<\/p>\n

                 <\/p>\n

                  \n
                • If \u2018X\u2019 is a terminal and if it is \u2018a\u2019, then this character is popped from the stack and the input pointer moves by one position to process the next character.<\/li>\n
                • If \u2018X\u2019 is a non-terminal, then the parsing table is referred for [X,a] and the corresponding production available in the table entry is retrieved. The input pointer stays in the same position pointing \u2018a\u2019. The stack symbol X is popped and since this will be a LHS non-terminal, the production which is retrieved from the parsing table is pushed onto the stack. The production is read from left to right and this should be available in the stack from top to bottom, thus ensuring the first symbol on the RHS of a production is on the top of the stack.<\/li>\n
                • If \u2018X\u2019 is a terminal and if it is \u2018$\u2019 and if the input character \u2018a\u2019 is also \u2018$\u2019, then the parser announces successful completion of the parsing action.<\/li>\n
                • Any other combination of \u2018X\u2019 and \u2019a\u2019 would result in an error action.<\/li>\n<\/ul>\n

                   <\/p>\n

                  Example 11.1: Consider the string id + id * id. Let us see how the parsing algorithm, parses this string. The details of it is given in Table 11.2<\/p>\n

                   <\/p>\n

                  \"\"<\/p>\n

                  \n

                  11.2 Error Recovery in LL(1) Parsers<\/strong><\/p>\n

                   <\/p>\n

                  A LL(1) parser has to recover from errors if an input string doesn\u2019t belong to it. The parser should recover from the error and should continue with the next phase of compilations.<\/p>\n

                   <\/p>\n

                  11.2.1 Error Recovery methods<\/strong><\/p>\n

                   <\/p>\n

                  The parser does not correct the errors. It simply recovers from the errors in one of the many ways available and possible to recover from errors so that the compiler can proceed with the next compilation phase. The following are the various modes a parser uses to recover from errors.<\/p>\n

                   <\/p>\n

                  \u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Panic mode<\/em><\/strong>: <\/strong>In this mode of error recovery, the parser discards input until a token in a set of designated synchronizing tokens is found.<\/p>\n<\/div>\n

                    \n
                  • Phrase-level recovery: <\/em><\/strong>In this method, the parser performs local correction on the input to repair the error<\/li>\n
                  • Error productions<\/em><\/strong>: <\/strong>Error productions are added to the grammar to identify erroneous constructs<\/li>\n
                  • Global correction<\/em><\/strong>: <\/strong>In this method, a minimal sequence of changes is made to the parsing algorithm to obtain a global least-cost error correction<\/li>\n<\/ul>\n

                    11.2.2 Error recovery in LL(1) Parsers.<\/strong><\/p>\n

                     <\/p>\n

                    The LL(1) parsers adopts all the four methods listed above and handles it using the parsing table.<\/p>\n

                      \n
                    • Panic Mode: <\/strong>In this mode, the synchronizing actions are added to the undefined entries in the parsing table based on FOLLOW() already computed. This is given in Table 11.3<\/li>\n<\/ul>\n

                      Table 11.3 Parsing table with synch action to recover from errors for Expression grammar<\/strong><\/p>\n

                       <\/p>\n\n\n\n\n\n\n\n\n
                       <\/td>\nid<\/strong><\/td>\n+<\/strong><\/td>\n*<\/strong><\/td>\n(<\/strong><\/td>\n)<\/strong><\/td>\n$<\/strong><\/td>\n<\/tr>\n
                      E<\/td>\nE \u00e0 TE\u2019<\/td>\n <\/td>\n <\/td>\nE \u00e0 TE\u2019<\/td>\nsynch<\/strong><\/td>\nsynch<\/strong><\/td>\n<\/tr>\n
                      E\u2019<\/td>\n <\/td>\nE\u2019\u00e0 +TE\u2019<\/td>\n <\/td>\n <\/td>\nE\u2019 \u00e0 \u03b5<\/td>\nE\u2019 \u00e0 \u03b5<\/td>\n<\/tr>\n
                      T<\/td>\nT \u00e0 FT\u2019<\/td>\nsynch<\/strong><\/td>\n <\/td>\nT \u00e0 FT\u2019<\/td>\nsynch<\/strong><\/td>\nsynch<\/strong><\/td>\n<\/tr>\n
                      T\u2019<\/td>\n <\/td>\nT\u2019 \u00e0 \u03b5<\/td>\nT\u2019 \u00e0 *FT\u2019<\/td>\n <\/td>\nT\u2019 \u00e0 \u03b5<\/td>\nT\u2019 \u00e0 \u03b5<\/td>\n<\/tr>\n
                      F<\/td>\nF \u00e0 id<\/td>\nsynch<\/strong><\/td>\nsynch<\/strong><\/td>\nF \u00e0 (E)<\/td>\nsynch<\/strong><\/td>\nsynch<\/strong><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

                       <\/p>\n

                       <\/p>\n

                      As seen from Table 11.3, the FOLLOW(E) = {$, )}. Therefore, synch actions are added to the intersection of [E, $] and [E, )]. So, when this combination occur in the parsing table and input, the parser enters into the panic mode and start deleting tokens from the input or stack till a valid combination of stack entry and input is available and logs this as error in the error table.<\/p>\n

                       <\/p>\n

                        \n
                      • Phrase Mode: <\/strong>In this mode, the LL(1) parser, assumes and inserts some missing characters to continue with the parsing action. For example: id id<\/strong> is changed into <\/span>id * id<\/strong> or id + id<\/strong><\/li>\n
                      • Error Production: <\/strong>This is similar to the general parser recovery method. Error production are added to take care of incorrect input combinations<\/li>\n<\/ul>\n

                        An ambiguous grammar is not LL(1) and may have multiple entries in the parsing table. In that case, the parsing algorithm can decide to choose to apply any one of the available productions in the table entry.<\/p>\n

                         <\/p>\n

                        \n

                        11.3 Bottom up Parsers<\/strong><\/p>\n

                         <\/p>\n

                         <\/p>\n

                         <\/p>\n

                        The LL(1) parser is not a very powerful parser and cannot handle all types of grammars. We have already seen that LL(1) parser cannot handle ambiguous grammars and some grammars are inherently ambiguous. Bottom up parsers build a derivation by working from the input back toward the start symbol. The parse tree is constructed by looking at the input string and matching the RHS with the LHS of the production and correspondingly substituting it. Thus the parse tree is built from leaves towards the root. Hence, we can say the bottom- up parser builds a derivation tree by applying rightmost derivation in reverse.<\/p>\n

                         <\/p>\n

                        Bottom-up parsers are powerful than their top-down counterpart and does not require any pre-processing as in the case of LL(1) parsers. There are various types of bottom- up parsers.<\/p>\n

                         <\/p>\n

                        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Shift-Reduce Parsing \u2013 Simply constructs the right most derivation tree by replacing RHS of the production with the LHS Non-terminal.<\/p>\n

                         <\/p>\n

                        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 Operator-precedence parsing \u2013 It is a special type of Bottom \u2013up parser where a grammar has to obey the property of an infix expression.<\/p>\n

                         <\/p>\n

                        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 LR parsers \u2013 \u2018L\u2019 stands for the input string being scanned from left to right, \u2018R\u2019 stands for applying rightmost derivation. There are various types of LR parsers<\/p>\n

                         <\/p>\n

                        \u2013\u00a0 Simple LR (SLR)<\/p>\n

                         <\/p>\n

                        \u2013\u00a0 Canonical LR (CALR)<\/p>\n

                         <\/p>\n

                        \u2013\u00a0 Look Ahead LR (LALR)<\/p>\n

                         <\/p>\n

                        As bottom- up parsers match the RHS of production with LHS, a concept called \u2018handle\u2019 is defined. A handle<\/em> is a substring of grammar symbols in a right-sentential form<\/em> that matches a right- hand side of a production. A handle\u2019s reduction to the non-terminal on the LHS represents one step along the reverse of a rightmost derivation. For example, the following are some of the handles of the expression grammar:<\/p>\n

                         <\/p>\n

                        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 id<\/p>\n

                         <\/p>\n

                        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 E * E<\/p>\n

                         <\/p>\n

                        \u2022\u00a0\u00a0\u00a0\u00a0\u00a0 (E)<\/p>\n

                         <\/p>\n

                        In this module, we will discuss the simple shift-reduce bottom up parser and other bottom-up parsers are discussed in subsequent modules.<\/p>\n<\/div>\n

                         <\/p>\n

                        11.4 Shift-Reduce Parsers<\/strong><\/p>\n

                         <\/p>\n

                        The shift-reduce parser is the simplest of the Bottom up Parsers. It also has a stack memory similar to a LL(1) parser. The input symbol here again is terminated with \u201c$\u201d to indicate end of input. The stack is initialized with the \u201c$\u201d symbol alone in this type of parser.<\/p>\n

                         <\/p>\n

                        11.4.1 Parsing by Shift-Reduce Parsers<\/strong><\/p>\n

                         <\/p>\n

                        The shift-reduce parser is based on two actions: \u201cshift\u201d and \u201creduce\u201d. The stack memory and the input are considered individually to perform the shift and reduce actions. The \u201cshift\u201d action simply shifts the input symbols until a handle is found into the stack by calling the push() routine. The reduce action, reduces<\/em> the substring to the non-terminal on the LHS of the corresponding production in the stack, by popping the handle and pushing the LHS non-terminals. Thus the shift-reduce parser has 4 actions:<\/p>\n

                         <\/p>\n

                          \n
                        • Shift <\/em>–\u00a0 the next input symbol is shifted onto the stack<\/li>\n
                        • Reduce <\/em>the handle that is at top of stack<\/li>\n
                        • pop handle<\/li>\n
                        • push appropriate LHS symbol<\/li>\n
                        • Accept <\/em>the input string, stop parsing and report success \u2013 The string is accepted if the input is completely consumed and the stack has the start symbol as its top of stack symbol.<\/li>\n
                        • Error <\/em>recovery routine is called if it was not able to do any of the other 3 actions.<\/li>\n<\/ul>\n

                          Example 11. 2 Consider the following ambiguous expression grammar with productions numbered from 1 to 4. Let us see the parsing action for the string \u201cid+id*id\u201d<\/p>\n

                            \n
                          1. S -> E<\/li>\n
                          2. E ->E +<\/strong> E<\/li>\n
                          3. E ->E *<\/strong> E<\/li>\n
                          4. E\u00a0-> id<\/strong><\/li>\n<\/ol>\n

                            The parsing action is shown in Table 11.4<\/p>\n

                             <\/p>\n

                            \"\"<\/p>\n

                            11.4.2 Issues in Shift-Reduce parser<\/strong><\/p>\n

                             <\/p>\n

                            The shift-reduce conflict as explained in Table 11.4 is a typical problem of the Shift-reduce parser. A reduce-reduce conflict may also occur where the parser will not know which production to choose from the list of available productions for a \u201clong\u201d or \u201cshort\u201d handle. These issues are caused by<\/p>\n

                              \n
                            • The limitations of the parsing method (even when the grammar is unambiguous)<\/li>\n
                            • Ambiguity of the grammar<\/li>\n<\/ul>\n

                              These issues will be resolved by a powerful bottom up Parser and will be dealt with in subsequent modules.<\/p>\n

                               <\/p>\n

                              Summary:<\/strong><\/p>\n

                               <\/p>\n

                              In this module we discussed the parsing action of LL(1) parser. The various error recovery strategies in LL(1) parsers are also discussed. This module introduced one of the simple Bottom up parser namely Shift-reduce parser and discussed the approach to parsing by this parser.<\/p>\n","protected":false},"author":4,"menu_order":11,"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-173","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\/173","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\/173\/revisions"}],"predecessor-version":[{"id":176,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/173\/revisions\/176"}],"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\/173\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/media?parent=173"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapter-type?post=173"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/contributor?post=173"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/license?post=173"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}