{"id":63,"date":"2018-07-19T10:59:04","date_gmt":"2018-07-19T10:59:04","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=63"},"modified":"2018-07-19T11:00:43","modified_gmt":"2018-07-19T11:00:43","slug":"parsing-action-of-operator-precedence-parser-and-precedence-function","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/parsing-action-of-operator-precedence-parser-and-precedence-function\/","title":{"rendered":"PARSING ACTION OF OPERATOR PRECEDENCE PARSER AND PRECEDENCE FUNCTION"},"content":{"raw":"

After learning to construct the operator precedence parsing table, in this module we would learn the operator precedence parsing algorithm with an example and the errors that is encountered by an Operator Precedence parser. The precedence graph and precedence function associated with the operator precedence parser will also be discussed in this module.<\/p>\r\n \r\n\r\n13.1 Ope rator Precedence parsing<\/strong>\r\n\r\n \r\n\r\nWe have seen the first three steps in the Operator precedence parser. Verifying whether a grammar is operator precedence, computing of LEADING, TRAILING and construction of operator precedence parsing table was already done in the previous module. The next step is the Parsing algorithm and is given in algorithm 13.1\r\n\r\n \r\n\r\nAlgorithm 13.1 (Grammar G, input string w, Parsing table T)<\/strong>\r\n\r\n \r\n\r\n{set p to point to the first symbol of w$ ;\r\n\r\n \r\n\r\nrepeat forever<\/strong>\r\n\r\n \r\n\r\nif <\/strong>( $ is on top of the stack and <\/strong>p points to $ ) then return; \/\/ success else <\/strong>{\r\n\r\n \r\n\r\nlet a be the topmost terminal symbol on the stack; let b be the symbol pointed to by p;\r\n\r\n \r\n\r\n1. if ( a <.b or a =\u00b7 b ) then { \/* SHIFT *\/\r\n\r\npush b onto the stack;\r\nadvance p to the next input symbol;\r\n}\r\n\r\n2. else if ( a .\r\n> b ) then \/* REDUCE *\/\r\nrepeat pop stack\r\nuntil ( the top of stack terminal is related by <.\u00a0 to the terminal most\u00a0 recently popped );\r\n3. else error(); \/*ERROR*\/\r\n

\r\n\r\n}\r\n\r\n \r\n\r\n}\r\n\r\n \r\n

The input string \u201cw\u201d is appended with a \u201c$\u201d symbol at the end and is converted to w$. The stack is initialized with the $ symbol to acts as the initial stack symbol. As this parser is a bottom- up parser, the four actions of shift, reduce, error, accepts is handled by this parser also. The parser announces successful parsing and acceptance of a string, if there is a $ that matches the stack and the input. This is given in the beginning of the algorithm. The next step of the<\/p>\r\n\r\n<\/div>\r\n \r\n

algorithm loops until the existence of a string. The stack symbol is compared with the input symbol for precedence relation in the parsing table. If the precedence relation is lesser than or equal to, then the input character is pushed on to the stack and thus making the input pointer advances by one position to the right. If the precedence relation is greater than, then we reduce by popping the stack till the top of stack terminal is related by <. to the terminal most recently popped. If there is no relation defined between the symbols in the stack and input, we announce an error action.<\/p>\r\n \r\n

Example 13.1 Consider the input string id + id * id and let us see how the parsing action is carried out by the Operator precedence parser. For quick reference, the parsing table is given table 13.1 and the parsing action is given in Table 13.2<\/p>\r\n \r\n\r\nTable 13.1 Parsing table<\/strong>\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n13.2 Issues in Operator Precedence parsing.<\/strong>\r\n\r\n \r\n

Operator-Precedence parsing cannot handle the unary minus if the grammar has binary subtraction operator. The best approach to solve this problem is to tackle the unary operator at the lexical phase using one or both of the following approaches:<\/p>\r\n \r\n

    \r\n \t
  • The lexical analyzer can be made to return two different tokens for the unary minus and the binary minus.<\/li>\r\n \t
  • The lexical analyzer will need a lookahead to distinguish the binary minus from the unary minus.<\/li>\r\n<\/ul>\r\nAfter identifying this, we then define the precedence of the all operators in comparison with unary- minus as follows:\r\n
      \r\n \t
    • For any operator q, we set q <. unary- minus<\/li>\r\n \t
    • We then modify the relation,<\/li>\r\n \t
    • o if unary- minus has higher precedence than q, we set unary-minus .> q<\/li>\r\n \t
    • o if unary- minus has lower (or equal) precedence than q , we set unary- minus <. q<\/li>\r\n<\/ul>\r\n \r\n\r\nAfter constructing the precedence table based on the rules discussed in this section, the parsing action is similar to what has been already discussed.\r\n\r\n \r\n\r\n13.3 Precedence Functions<\/strong>\r\n\r\n \r\n

      The operator precedence parsers usually do not store the precedence table with the relations, rather they are implemented in a special way. Operator precedence parsers use precedence functions that map terminal symbols to integers, and so the precedence re lations between the symbols are implemented by numerical comparison. Not every table of precedence relations has precedence functions but in practice for most grammars such functions can be designed.<\/p>\r\n \r\n

      The precedence table is typically stored as a precedence function. The precedence table is coded as two functions f() and g() corresponding to the row and table. The idea behind the precedence functions is to define nodes and edges for all the terminals of a grammar in terms of<\/p>\r\n \r\n

      the functions f() and g(). For symbols \u2018a\u2019 and \u2018b\u2019 we define the functions f(a) and g(b) based on the precedence between the operators \u2018a\u2019 and \u2018b. The following is used as the basis.<\/p>\r\n\r\n

        \r\n \t
      • if a <. b then f(a) < g(b)<\/li>\r\n \t
      • if a =\u00b7 b, then f(a) = g(b)<\/li>\r\n \t
      • if a .> b, then f(a) > g(b)<\/li>\r\n<\/ul>\r\n

        The algorithm for constructing the precedence function is given in Algorithm 13.2 where the input will be the precedence table.<\/p>\r\n \r\n\r\nAlgorithm 13.2<\/strong>\r\n\r\n \r\n\r\nPrecedence_Function(Precedence table T, Precedence Function f)\r\n\r\n \r\n\r\n{\r\n

          \r\n \t
        1. Create symbols fa and gb for each \u2018a\u2019 that is a terminal or $.<\/li>\r\n \t
        2. Partition the created symbols into as many groups as possible, in such a way that if a =. b, then fa and gb are in the same group.<\/li>\r\n \t
        3. Create a directed graph whose nodes are the groups found in the previous step. For any \u2018a\u2019 and \u2018b\u2019, if a <.b , place an edge from the group of gb to the group of fa. If a .> b, place an edge from the group of fa to that of gb.<\/li>\r\n \t
        4. If the graph constructed has a cycle, then no precedence functions exist. If there are no cycle, let f(a) be the length of the longest path beginning at the group of fa ; let g(a) be the length of the longest path beginning at the group of ga.<\/li>\r\n<\/ol>\r\n}\r\n\r\n \r\n

          Algorithm 13.2 lists the steps involved in constructing the precedence graph. After constructing the precedence graph the precedence function computes the length of the longest path for all the terminals.<\/p>\r\n

          Example 13.2 Consider the expression grammar containing the terminals +. *, id and $ whose precedence table is defined in Table 13.1.<\/p>\r\n

          By step 2 of the algorithm, we could define the following functions for f() and g()<\/p>\r\n\r\n

            \r\n \t
          • f+, f*, fi d, f$ are the four functions of \u2018f\u2019<\/li>\r\n \t
          • g+, g*, gi d, g$ are the four function of \u2018g\u2019<\/li>\r\n<\/ul>\r\n

            Since, there is no equal precedence relation in this table, f() and g() for all the terminals will not be in the same group. Using step 3 of the algorithm 13.2 we construct the edges and is given in figure 13.1<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n13.4 Error handling in Operator Precedence Parser<\/strong>\r\n\r\n \r\n

            The operator precedence parser can handle only a small class of grammars. However, it cannot handle the unary minus (the lexical analyzer should handle the unary minus). The issues in Operator precedence parser is it finds difficulty in deciding the language of the grammar. This parser cannot have a relation between the terminal on the top of stack and the next input symbol. A handle is found (reduction step), but there is no production with this handle as RHS.<\/p>\r\n \r\n

            However, to handle the small class of grammar the operator precedence parser has to perform error recovery by one of the following tasks:<\/p>\r\n\r\n

              \r\n \t
            1. As in the LL(1) parser, each empty entry in the precedence table is filled with a pointer to an error routine.<\/li>\r\n \t
            2. Matches what the popped handle resembles which right hand side of the production and tries to recover from that situation. In order to recover, we must modify (insert\/change)<\/li>\r\n<\/ol>\r\n
                \r\n \t
              • Stack or<\/li>\r\n \t
              • Input or<\/li>\r\n \t
              • Both<\/li>\r\n<\/ul>\r\nThe error recovery routines can be grouped into four scenarios as described below:\r\n\r\n \r\n\r\ne1: Scenario: Entire expression is missing: To handle this case, we insert \u201cid\u201d to the input and issue a message - \u2018missing operand\u2019 or \u2018no input\u2019\r\n\r\ne2: Scenario: Expression begins with a right parenthesis: To handle this case, we delete \u2018)\u2019 from the input and issue message - \u2018unbalanced right parenthesis\u2019\r\n\r\ne3: Scenario: Expression has, id or ) is followed by id or (. To handle this situation insert + to the input and issue message - \u2018missing operator\u2019\r\n\r\ne4: Scenario: expression ends with a left parenthesis. To handle this case,\u00a0\u00a0\u00a0\u00a0 pop\u00a0 ( from the stackand issue message: \u2018missing right parenthesis\u2019\r\n\r\n \r\n\r\nThe various scenarios are depicted in Table 13.4\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n\"\"\r\n\r\n \r\n\r\nSummary: <\/strong>This module discussed the parsing action of an Operator Precedence Parser. We also discussed precedence functions and some error recovery strategies of the operator precedence parser.","rendered":"

                After learning to construct the operator precedence parsing table, in this module we would learn the operator precedence parsing algorithm with an example and the errors that is encountered by an Operator Precedence parser. The precedence graph and precedence function associated with the operator precedence parser will also be discussed in this module.<\/p>\n

                 <\/p>\n

                13.1 Ope rator Precedence parsing<\/strong><\/p>\n

                 <\/p>\n

                We have seen the first three steps in the Operator precedence parser. Verifying whether a grammar is operator precedence, computing of LEADING, TRAILING and construction of operator precedence parsing table was already done in the previous module. The next step is the Parsing algorithm and is given in algorithm 13.1<\/p>\n

                 <\/p>\n

                Algorithm 13.1 (Grammar G, input string w, Parsing table T)<\/strong><\/p>\n

                 <\/p>\n

                {set p to point to the first symbol of w$ ;<\/p>\n

                 <\/p>\n

                repeat forever<\/strong><\/p>\n

                 <\/p>\n

                if <\/strong>( $ is on top of the stack and <\/strong>p points to $ ) then return; \/\/ success else <\/strong>{<\/p>\n

                 <\/p>\n

                let a be the topmost terminal symbol on the stack; let b be the symbol pointed to by p;<\/p>\n

                 <\/p>\n

                1. if ( a <.b or a =\u00b7 b ) then { \/* SHIFT *\/<\/p>\n

                push b onto the stack;
                \nadvance p to the next input symbol;
                \n}<\/p>\n

                2. else if ( a .
                \n> b ) then \/* REDUCE *\/
                \nrepeat pop stack
                \nuntil ( the top of stack terminal is related by <.\u00a0 to the terminal most\u00a0 recently popped );
                \n3. else error(); \/*ERROR*\/<\/p>\n

                \n

                }<\/p>\n

                 <\/p>\n

                }<\/p>\n

                 <\/p>\n

                The input string \u201cw\u201d is appended with a \u201c$\u201d symbol at the end and is converted to w$. The stack is initialized with the $ symbol to acts as the initial stack symbol. As this parser is a bottom- up parser, the four actions of shift, reduce, error, accepts is handled by this parser also. The parser announces successful parsing and acceptance of a string, if there is a $ that matches the stack and the input. This is given in the beginning of the algorithm. The next step of the<\/p>\n<\/div>\n

                 <\/p>\n

                algorithm loops until the existence of a string. The stack symbol is compared with the input symbol for precedence relation in the parsing table. If the precedence relation is lesser than or equal to, then the input character is pushed on to the stack and thus making the input pointer advances by one position to the right. If the precedence relation is greater than, then we reduce by popping the stack till the top of stack terminal is related by <. to the terminal most recently popped. If there is no relation defined between the symbols in the stack and input, we announce an error action.<\/p>\n

                 <\/p>\n

                Example 13.1 Consider the input string id + id * id and let us see how the parsing action is carried out by the Operator precedence parser. For quick reference, the parsing table is given table 13.1 and the parsing action is given in Table 13.2<\/p>\n

                 <\/p>\n

                Table 13.1 Parsing table<\/strong><\/p>\n

                \"\"<\/p>\n

                \"\"<\/p>\n

                13.2 Issues in Operator Precedence parsing.<\/strong><\/p>\n

                 <\/p>\n

                Operator-Precedence parsing cannot handle the unary minus if the grammar has binary subtraction operator. The best approach to solve this problem is to tackle the unary operator at the lexical phase using one or both of the following approaches:<\/p>\n

                 <\/p>\n

                  \n
                • The lexical analyzer can be made to return two different tokens for the unary minus and the binary minus.<\/li>\n
                • The lexical analyzer will need a lookahead to distinguish the binary minus from the unary minus.<\/li>\n<\/ul>\n

                  After identifying this, we then define the precedence of the all operators in comparison with unary- minus as follows:<\/p>\n

                    \n
                  • For any operator q, we set q <. unary- minus<\/li>\n
                  • We then modify the relation,<\/li>\n
                  • o if unary- minus has higher precedence than q, we set unary-minus .> q<\/li>\n
                  • o if unary- minus has lower (or equal) precedence than q , we set unary- minus <. q<\/li>\n<\/ul>\n

                     <\/p>\n

                    After constructing the precedence table based on the rules discussed in this section, the parsing action is similar to what has been already discussed.<\/p>\n

                     <\/p>\n

                    13.3 Precedence Functions<\/strong><\/p>\n

                     <\/p>\n

                    The operator precedence parsers usually do not store the precedence table with the relations, rather they are implemented in a special way. Operator precedence parsers use precedence functions that map terminal symbols to integers, and so the precedence re lations between the symbols are implemented by numerical comparison. Not every table of precedence relations has precedence functions but in practice for most grammars such functions can be designed.<\/p>\n

                     <\/p>\n

                    The precedence table is typically stored as a precedence function. The precedence table is coded as two functions f() and g() corresponding to the row and table. The idea behind the precedence functions is to define nodes and edges for all the terminals of a grammar in terms of<\/p>\n

                     <\/p>\n

                    the functions f() and g(). For symbols \u2018a\u2019 and \u2018b\u2019 we define the functions f(a) and g(b) based on the precedence between the operators \u2018a\u2019 and \u2018b. The following is used as the basis.<\/p>\n

                      \n
                    • if a <. b then f(a) < g(b)<\/li>\n
                    • if a =\u00b7 b, then f(a) = g(b)<\/li>\n
                    • if a .> b, then f(a) > g(b)<\/li>\n<\/ul>\n

                      The algorithm for constructing the precedence function is given in Algorithm 13.2 where the input will be the precedence table.<\/p>\n

                       <\/p>\n

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

                       <\/p>\n

                      Precedence_Function(Precedence table T, Precedence Function f)<\/p>\n

                       <\/p>\n

                      {<\/p>\n

                        \n
                      1. Create symbols fa and gb for each \u2018a\u2019 that is a terminal or $.<\/li>\n
                      2. Partition the created symbols into as many groups as possible, in such a way that if a =. b, then fa and gb are in the same group.<\/li>\n
                      3. Create a directed graph whose nodes are the groups found in the previous step. For any \u2018a\u2019 and \u2018b\u2019, if a <.b , place an edge from the group of gb to the group of fa. If a .> b, place an edge from the group of fa to that of gb.<\/li>\n
                      4. If the graph constructed has a cycle, then no precedence functions exist. If there are no cycle, let f(a) be the length of the longest path beginning at the group of fa ; let g(a) be the length of the longest path beginning at the group of ga.<\/li>\n<\/ol>\n

                        }<\/p>\n

                         <\/p>\n

                        Algorithm 13.2 lists the steps involved in constructing the precedence graph. After constructing the precedence graph the precedence function computes the length of the longest path for all the terminals.<\/p>\n

                        Example 13.2 Consider the expression grammar containing the terminals +. *, id and $ whose precedence table is defined in Table 13.1.<\/p>\n

                        By step 2 of the algorithm, we could define the following functions for f() and g()<\/p>\n

                          \n
                        • f+, f*, fi d, f$ are the four functions of \u2018f\u2019<\/li>\n
                        • g+, g*, gi d, g$ are the four function of \u2018g\u2019<\/li>\n<\/ul>\n

                          Since, there is no equal precedence relation in this table, f() and g() for all the terminals will not be in the same group. Using step 3 of the algorithm 13.2 we construct the edges and is given in figure 13.1<\/p>\n

                           <\/p>\n

                          \"\"<\/p>\n

                           <\/p>\n

                          13.4 Error handling in Operator Precedence Parser<\/strong><\/p>\n

                           <\/p>\n

                          The operator precedence parser can handle only a small class of grammars. However, it cannot handle the unary minus (the lexical analyzer should handle the unary minus). The issues in Operator precedence parser is it finds difficulty in deciding the language of the grammar. This parser cannot have a relation between the terminal on the top of stack and the next input symbol. A handle is found (reduction step), but there is no production with this handle as RHS.<\/p>\n

                           <\/p>\n

                          However, to handle the small class of grammar the operator precedence parser has to perform error recovery by one of the following tasks:<\/p>\n

                            \n
                          1. As in the LL(1) parser, each empty entry in the precedence table is filled with a pointer to an error routine.<\/li>\n
                          2. Matches what the popped handle resembles which right hand side of the production and tries to recover from that situation. In order to recover, we must modify (insert\/change)<\/li>\n<\/ol>\n
                              \n
                            • Stack or<\/li>\n
                            • Input or<\/li>\n
                            • Both<\/li>\n<\/ul>\n

                              The error recovery routines can be grouped into four scenarios as described below:<\/p>\n

                               <\/p>\n

                              e1: Scenario: Entire expression is missing: To handle this case, we insert \u201cid\u201d to the input and issue a message – \u2018missing operand\u2019 or \u2018no input\u2019<\/p>\n

                              e2: Scenario: Expression begins with a right parenthesis: To handle this case, we delete \u2018)\u2019 from the input and issue message – \u2018unbalanced right parenthesis\u2019<\/p>\n

                              e3: Scenario: Expression has, id or ) is followed by id or (. To handle this situation insert + to the input and issue message – \u2018missing operator\u2019<\/p>\n

                              e4: Scenario: expression ends with a left parenthesis. To handle this case,\u00a0\u00a0\u00a0\u00a0 pop\u00a0 ( from the stackand issue message: \u2018missing right parenthesis\u2019<\/p>\n

                               <\/p>\n

                              The various scenarios are depicted in Table 13.4<\/p>\n

                              \"\"<\/p>\n

                              \"\"<\/p>\n

                              \"\"<\/p>\n

                               <\/p>\n

                              Summary: <\/strong>This module discussed the parsing action of an Operator Precedence Parser. We also discussed precedence functions and some error recovery strategies of the operator precedence parser.<\/p>\n","protected":false},"author":4,"menu_order":13,"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-63","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\/63","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\/63\/revisions"}],"predecessor-version":[{"id":71,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapters\/63\/revisions\/71"}],"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\/63\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/media?parent=63"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/pressbooks\/v2\/chapter-type?post=63"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/contributor?post=63"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/wp-json\/wp\/v2\/license?post=63"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}