{"id":58,"date":"2018-07-19T10:48:11","date_gmt":"2018-07-19T10:48:11","guid":{"rendered":"http:\/\/csp10.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=58"},"modified":"2018-07-19T10:48:29","modified_gmt":"2018-07-19T10:48:29","slug":"leading-trailing-and-operator-precedence-table","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp10\/chapter\/leading-trailing-and-operator-precedence-table\/","title":{"rendered":"LEADING, TRAILING and Operator Precedence Table"},"content":{"raw":"
\r\n

In this module, we will learn to construct the next type of Bottom up parser, which is the operator precedence parser. The functions Leading and Trailing are computed to construct the Operator precedence parsing table. This module discusses the constructio n of Operator precedence parsing table using the functions leading and trailing.<\/p>\r\n \r\n\r\n12.1 Ope rator Precedence Grammar<\/strong>\r\n\r\n \r\n\r\nThe class of grammar parsed by the Operator precedence parser is the Operator Precedence Grammar. This is a small, but an important class of grammar. An operator precedence parser can be a powerful shift-reduce parser for this small class of operator precedence grammar. A grammar has to satisfy the following conditions for it to be parsed by an operator precedence parser:\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 No e-productions are permitted thus ensuring that the RHS of all production should be a combination of terminals and non-terminals.\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 The RHS of all productions should be in such a way that no two non-terminals should be adjacent\r\n\r\n \r\n\r\nConsider the following examples:\r\n\r\n \r\n

1.\u00a0\u00a0\u00a0\u00a0\u00a0 Grammar G1 is defined with the productions, E\u00aeAB, A \u00e0 a, B \u00e0b. This grammar has the non-terminals A and B adjacent to each other and hence is not an operator precedence grammar.<\/p>\r\n

2.\u00a0\u00a0 Grammar G2 is defined with productions, E\u00aeEOE, E \u00e0 id, O \u00e0 + | * | \/ . This grammar is also not operator precedence grammar as E, O, E are non-terminals and they are adjacent to each other.<\/p>\r\n

3.\u00a0\u00a0\u00a0\u00a0\u00a0 Grammar G3, is a modified version of G2 with productions, E\u00aeE+E | E*E | E\/E | id which is a operator precedence grammar as it does not have \u03b5 productions and has no two non-terminals adjacent to each other in the RHS of the productions.<\/p>\r\n \r\n\r\n12.2 Ope rator precedence parser rules<\/strong>\r\n\r\n \r\n

Let G be an \u220a-free operator grammar (No \u220a-Production).For each terminal symbols a and b, the following conditions need to be satisfied. We define three symbols to define the precedence relations between two terminals \u2018a\u2019 and \u2018b\u2019 namely, the \u2250 , <., .> to indicate same, lesser and greater precedence respectively. The same, lesser and greater precedence between any two terminals is defined based on the following rules:<\/p>\r\n \r\n

1.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 The first rule is for the same precedence relation between two terminals \u2018a\u2019 and \u2018b\u2019. We say, a\u2250 b, if \u2203 a production in RHS of the form \u03b1a\u03b2b\u03b3, where \u03b2 is either \u220a or a single non-Terminal. Consider the grammar with a production, S\u00e0iCtSeS. It can be observed\u00a0that this grammar is an operator precedence grammar. The symbols for \u03b1 can be \u03b5, C, S for three situations. Thus for the scenario where \u03b1 is \u03b5, we have \u2018a\u2019 is \u2018i' and \u2018b\u2019 is \u2018t\u2019. Thus we have the relation, <\/span>i \u2250 t. Considering an alternate situation, where \u03b1 is \u2018C\u2019, we have \u2018a\u2019 as \u2018t\u2019 and \u2018b\u2019 as \u2018e\u2019 which yields the precedence relation t \u2250 e. When \u03b1 is S, we don\u2019t have a symbol for \u03b2 and thus only these two precedence relations could be derived.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n

2.\u00a0\u00a0\u00a0\u00a0\u00a0 The second rule is to design the lesser than relation between two terminals \u2018a\u2019 and \u2018b\u2019.<\/p>\r\n \r\n

We say, a <. b if for some non-terminal A \u2203 a production in RHS of the form A\u00e0 \u03b1aA\u03b2, and A\u21d2+ \u03b3b\u03b4 where \u03b3 is either \u220a or a single non-terminal. Consider the productions, S\u00e0iCtS and C \u21d2+ b and where \u03b2 has \u2018b\u03b4\u2019 and hence, we deduce i <. b as non-terminal C derives \u2018b\u2019<\/p>\r\n \r\n

3.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 The third rule is to design the greater than relation between two terminals \u2018a\u2019 and \u2018b\u2019 and is to look at the derivation from the right of the RHS of the production. We say, a .> b if for some non-terminal A \u2203 a production in RHS of the form A\u00e0 \u03b1Ab\u03b2, and A\u21d2+ \u03b3a\u03b4 where \u03b4 is either \u220a or a single non-terminal. Thus, for the production, S\u00e0iCtS and C \u21d2+ b the relation derived will be b .> t.<\/p>\r\n \r\n\r\nExample 12.1 Consider the following ambiguous expression grammar.\r\n\r\n \r\n\r\nE\u00e0E+E | E*E | (E) | id\r\n

This grammar is not a Operator precedence Grammar since by rule no. 3 we have + <. + &\u00a0\u00a0 + .> + as the grammar is ambiguous. However, we have the unambiguous expression grammar and is given below. This grammar has clear definition of the precedence relation. E\u00e0E+T | T, T\u00e0T*F | F, F\u00e0(E) | id<\/p>\r\n \r\n\r\n12.3 Ope rator precedence parsing<\/strong>\r\n\r\n \r\n

The operator precedence parser is based on the precedence rules that are defined between the terminals of a grammar. In operator-precedence parsing, we define three disjoint precedence relations between certain pairs of terminals.<\/p>\r\n \r\n\r\n\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 a <. b implies \u2018b\u2019 has higher precedence than \u2018a\u2019\r\n\r\n\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 a =\u00b7 b implies \u2018b\u2019 has same precedence as \u2018a\u2019\r\n\r\n\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 a .> b implies \u2018b\u2019 has lower precedence than \u2018a\u2019\r\n\r\n \r\n

The challenge lies in the determination of correct precedence relations between terminals which are used for constructing the Operator precedence parsing table. For now let us assume the existence of the operator precedence parsing table. The determination of precedence relations are based on the traditional notions of associativity and precedence of operators. In the expression grammar, the precedence relations could be identified between all pairs of operators based on associativity and precedence and unary minus alone cause\u2019s problem.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\nThe intention of the precedence relations is to find the handle of a right-sentential form. The following conventions are used\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 <.\u00a0 with marking the left end,\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 =\u00b7 appearing in the interior of the handle, and\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 .> marking the right hand.\r\n\r\n \r\n

The input string is prefixed and suffixed with \u201c$\u201d which would look like, \u201c $a1a2...an$ \u201c and then we insert the precedence relation between the pairs of terminals (the precedence relation holds between the terminals in that pair).<\/p>\r\n \r\n\r\nExample 11.2 Consider the following ambiguous grammar with productions E \u00ae E+E | E*E | id\r\n\r\n \r\n\r\nLet us assume the precedence table as given in Table 12.1. The next section of this module will deal with the construction of this precedence table.\r\n\r\n \r\n\r\nTable 12.1 Precedence table for ambiguous expression grammar<\/strong>\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<\/tr>\r\n
id<\/strong><\/td>\r\n<\/td>\r\n.<\/strong>><\/strong><\/td>\r\n.<\/strong>><\/strong><\/td>\r\n.<\/strong>><\/strong><\/td>\r\n<\/tr>\r\n
+<\/strong><\/td>\r\n<<\/strong>.<\/strong><\/td>\r\n.<\/strong>><\/strong><\/td>\r\n<<\/strong>.<\/strong><\/td>\r\n.<\/strong>><\/strong><\/td>\r\n<\/tr>\r\n
*<\/strong><\/td>\r\n<<\/strong>.<\/strong><\/td>\r\n.<\/strong>><\/strong><\/td>\r\n.<\/strong>><\/strong><\/td>\r\n.<\/strong>><\/strong><\/td>\r\n<\/tr>\r\n
$<\/strong><\/td>\r\n<<\/strong>.<\/strong><\/td>\r\n<<\/strong>.<\/strong><\/td>\r\n<<\/strong>.<\/strong><\/td>\r\n<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n \r\n\r\n \r\n\r\nThen the input string id+id*id with the precedence relations inserted will look like \u201c$ <<\/strong>.<\/strong> id <\/strong>.<\/strong>> + <<\/strong>.<\/strong> id <\/strong>.<\/strong>> * <<\/strong>.<\/strong> id <\/strong>.<\/strong>> $\u201d<\/strong>\r\n\r\n \r\n

The precedence relation is inserted between two terminals, by considering the first terminal in the row and the second terminal in the column. Thus, \u201c$\u201d and \u201cid\u201d has <<\/strong>..<\/strong> Thus, the next pair is \u201cid\u201d and \u201c+\u201d which has a .<\/strong>><\/strong> relation and is also inserted<\/p>\r\n \r\n\r\nThe operator precedence parsing algorithm is a two step process. The stack is looked and scanned for the following\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 Scan the string from left end until the first .> is encountered.\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 Then scan backwards (to the left) over any =\u00b7 until a <.\u00a0 is encountered.\r\n\r\n \r\n

This algorithm also uses a stack where the initial stack contents are the modified input string with precedence added. The handle contains everything to left of the first .> and to the right of the <. is encountered. The parsing action by the operator precedence parser is given in Table 12.2<\/p>\r\n\"\"\r\n\r\n<\/div>\r\n

\r\n\r\nAfter discussing the overview of the operator precedence parsers, we will discuss each step of the operator precedence parser in detail. Steps involved in the construction of the parser are as follows.\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 Ensure the Grammar satisfies the pre-requisite\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 Compute the functions Leading and Trailing\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0 Using the computed leading and trailing, construct the Operator precedence parsing table\r\n\r\n4.\u00a0\u00a0\u00a0\u00a0\u00a0 Parse the string based on the algorithm\r\n\r\n \r\n\r\nIn this module, we will discuss the computation of Leading and Trailing followed by the construction of the parsing table.\r\n\r\n \r\n\r\n12.3 LEADING and TRAILING computation<\/strong>\r\n\r\n \r\n

LEADING is defined for every non-terminal. It is defined for each non-terminal such that, terminals that can be the first terminal in a string derived from that non-terminal. Similarly, TRAILING for each non-terminal are those terminals that can be the last terminal in a string derived from that NT. Formally, the functions LEADING and TRAILING are defined as follows:\u00a0 \u00a0 \u00a0LEADING(A) = { a| A \u21d2+ \u03b3a\u03b4, where \u03b3 is \u220a or a single non-terminal., where => indicates derivation, + indicates in one or more steps, A is a non-terminal. Thus LEADING(A) can be interpreted as looking for the first terminal from the left, in the RHS of a production by applying all possible derivations for a production<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

TRAILING(A) = { a| A \u21d2+ \u03b3a\u03b4, where \u03b4 is \u220a or a single non-terminal., where => indicates derivation, + indicates in one or more steps, A is a non-terminal. Thus TRAILING(A) can be interpreted as looking for the first terminal from the right, in the RHS of a production by applying all possible derivations for a production.<\/p>\r\n \r\n\r\nThe algorithm for finding LEADING(A) where A is a non-terminal is given in Algorithm 12.1\r\n\r\n \r\n\r\nAlgorithm 12.1<\/strong>\r\n\r\n \r\n\r\nLEADING(A)\r\n\r\n \r\n\r\n{\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 \u2018a\u2019 is in Leading(A) if A \u00e0 \u03b3a\u03b4 where \u03b3 is \u03b5 or any Non-Terminal\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 If\u2019 \u2018a\u2019 is in Leading(B) and A \u00e0 B\u03b1, then a in Leading(A)\r\n\r\n \r\n\r\n}\r\n\r\n \r\n

Step 1 of algorithm 12.1, indicates how to add the first terminal occurring in the RHS of every production directly. Step 2 of the algorithm indicates to add the first terminal, through another non-terminal B to be included indirectly to the LEADING() of every non-terminal.<\/p>\r\n \r\n\r\nSimilarly the algorithm to find TRAILING (A) is given in algorithm 12.2\r\n\r\n \r\n\r\nAlgorithm 12.2<\/strong>\r\n\r\n \r\n\r\nTRAILING (A)\r\n\r\n \r\n\r\n{\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 a is in Trailing(A) if A \u00e0 \u03b3a\u03b4 where \u03b4 is \u03b5 or any Non-Terminal\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0 If a is in Trailing(B) and A \u00e0 \u03b1B, then a in Trailing(A)\r\n\r\n \r\n\r\n}\r\n\r\n \r\n

Algorithm 12.2 is similar to algorithm 12.1 and the only difference being, the symbol is looked from right to left as against left to right in algorithm 12.1. Step 1 of the algorithm 12.2, indicates looking for the first terminal occurring in the RHS of a production from right side and thus adds the direct first symbol. The second step looks for adding the indirect first symbol from the right of the RHS of the production.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\nExample 12.2 Consider the unambiguous version of the expression grammar.\r\n\r\n1.\u00a0\u00a0\u00a0\u00a0\u00a0 E \u00e0 E + T\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 E \u00e0 T\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 T \u00e0 T * F\r\n\r\n4.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 T \u00e0 F\r\n\r\n5.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 F \u00e0 (E)\r\n\r\n6.\u00a0\u00a0\u00a0\u00a0\u00a0 F \u00e0 id\r\n\r\n \r\n

Let us consider the productions of F from productions 5, 6. From production 6, there is only one symbol in the RHS and that is a terminal. So, \u201cid\u201d will be in the LEADING(F). From production 5, the first symbol itself is a terminal \u201c(\u201c and hence that will be added to LEADING(F) as well. Further additions to LEADING(F) is not possible as the first symbol in the RHS of the productions involving F is a terminal. Thus<\/p>\r\n \r\n\r\nLEADING (F) = {( , id}\r\n\r\n \r\n

Let us consider the production of T as defined in production 3, 4. From production 3, the first symbol on the RHS is a non-terminal and the first terminal is \u201c*\u201d and thus \u201c*\u201d will be in LEADING(T). Then from production 4, there is only one symbol in the RHS and that is a non-terminal. So, the LEADING of the RHS non-terminal will be there in the LHS non-terminal also. Thus, LEADING(T) will include LEADING(F) in addition to \u201c*\u201d.<\/p>\r\n \r\n\r\nLEADING (T) = { *, (, id }\r\n\r\n \r\n

A similar analogy as explained for non-terminal T is applied to define the LEADING(E). Thus LEADING(E) will include LEADING(T) from production 2 and \u201c+\u201d from production 1. Thus<\/p>\r\n \r\n\r\nLEADING (E) = { + , * , ( , id}\r\n\r\n \r\n

Let us consider computation of TRAILING () where it is similar to LEADING() but the productions are scanned from right to left. Let us again start from F. From production 6, \u201cid\u201d will be in TRAILING(F) as it is the only symbol in the RHS. In addition, from production 5, \u201c)\u201d will be in the TRAILING(F) and will not have any more symbols as the first symbol from the right is a terminal in both productions.<\/p>\r\n \r\n\r\nTRAILING (F) = {), id}\r\n\r\n \r\n

Similarly from productions 3, 4, the TRAILING(T) would include \u201c*\u201d and TRAILING(F) from the two productions respectively. Thus,<\/p>\r\n \r\n\r\nTRAILING (T) = { *, ), id}\r\n\r\n \r\n

Similarly from productions 1,2, the TRAILING(E) would include \u201c+\u201d and TRAILING(T) from these two productions. Thus,<\/p>\r\n\r\n<\/div>\r\n \r\n

\r\n\r\nTRAILIN G (E) = { +, *, ), id}\r\n\r\n \r\n\r\n12.4 Ope rator precedence parsing table construction<\/strong>\r\n\r\n \r\n

After computing the two functions LEADING() and TRAILING(), the operator precedence table is constructed between all the terminals in the grammar including the \u201c$\u201d symbol. The algorithm for computing this parsing table is given in Algorithm 12.3<\/p>\r\n \r\n\r\nAlgorithm 12.3<\/strong>\r\n\r\n \r\n\r\nPARSINGTABLE(Grammar G, LEADING(), TRAILING() )\r\n\r\n \r\n\r\n{\r\n\r\n \r\n\r\nFor each production A \u00e0X1X2X3 ...Xn\r\n\r\n \r\n\r\nfor i = 1 to n-1\r\n\r\n \r\n\r\n1.\u00a0\u00a0\u00a0 if Xi and Xi+1\u00a0 are terminals\r\n\r\nset Xi =\u00b7 Xi+1\r\n\r\n2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 if i \u2264 n-2 and Xi and Xi+2 are terminals and Xi+1 is a non-terminal set Xi =\u00b7 Xi+2\r\n\r\n3.\u00a0\u00a0\u00a0\u00a0\u00a0 if Xi is a terminal and Xi+1 is a non-terminal then for all \u2018a\u2019 in Leading(Xi+1) set Xi <<\/strong>.<\/strong> a<\/strong>\r\n\r\n4.\u00a0\u00a0\u00a0\u00a0\u00a0 if Xi is a non-terminal and Xi+1 is a terminal then for all \u2018a\u2019 in Trailing(Xi ) set a .<\/strong>><\/strong> Xi+1\r\n\r\n}\r\n\r\n \r\n\r\nExample 12.3\r\n\r\n \r\n

Consider the unambiguous expression grammar involving as given in example 12.2. Step 1 is not to be encountered in the expression grammar where two terminals occur adjacent to each other. Step 2 of the algorithm looks for a Non-terminal between a pair of terminals and the RHS should have only three symbols, then we go for the same precedence. Using this step, the terminals \u201c(\u201c and \u201c)\u201d of the 5th production of the Expression grammar gets the same precedence and is given in Table 12.3. Since, it is the only production obeying this rule, the same precedence situation will not arise for any other pair of terminals.<\/p>\r\n \r\n

Consider step 3 of the algorithm, where we are looking for a terminal followed by a non-terminal. Productions 1, 3, 5 will fall in this category. We are looking at \u201c+\u201d and \u201cT\u201d in<\/p>\r\n\r\n<\/div>\r\n

production 1. LEADING(T) = {*, (, id}. So we set + <<\/strong>.<\/strong> {*, (, id} and this is shown in row 1 of Table 12.3. Similarly, from production 3, we set * <<\/strong>.<\/strong> { (, id} and is given in row 2 of the table 12.3. So, is the case from production 5 we set ( <<\/strong>.<\/strong> {+, *, (, id}<\/p>\r\n \r\n

Consider step 4 of the algorithm, where we are looking for a terminal preceded by a non-terminal. Similarly productions 1, 3, 5 will be used for this step of the algorithm also. Consider production 1 so we set, TRAILING(E) .<\/strong>><\/strong> Xi+1 . Therefore, { ), id} .<\/strong>><\/strong> + and is shown in row 5, row 3 of the algorithm. Similarly, {*, ), id} .<\/strong>><\/strong> *. From production 5, {+, *, ), id} .<\/strong>><\/strong> ). This parsing table is later used by the operator precedence parser.<\/p>\r\n\"\"\r\n

Summary<\/strong>: This module detailed on the pre-requisite for a grammar to be parsed using operator precedence parser with a brief note on the operator precedence parsing algorithm. This module also dealt with computing Leading, trailing and using which the operator parsing table is also constructed.<\/p>\r\n ","rendered":"

\n

In this module, we will learn to construct the next type of Bottom up parser, which is the operator precedence parser. The functions Leading and Trailing are computed to construct the Operator precedence parsing table. This module discusses the constructio n of Operator precedence parsing table using the functions leading and trailing.<\/p>\n

 <\/p>\n

12.1 Ope rator Precedence Grammar<\/strong><\/p>\n

 <\/p>\n

The class of grammar parsed by the Operator precedence parser is the Operator Precedence Grammar. This is a small, but an important class of grammar. An operator precedence parser can be a powerful shift-reduce parser for this small class of operator precedence grammar. A grammar has to satisfy the following conditions for it to be parsed by an operator precedence parser:<\/p>\n

 <\/p>\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 No e-productions are permitted thus ensuring that the RHS of all production should be a combination of terminals and non-terminals.<\/p>\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 The RHS of all productions should be in such a way that no two non-terminals should be adjacent<\/p>\n

 <\/p>\n

Consider the following examples:<\/p>\n

 <\/p>\n

1.\u00a0\u00a0\u00a0\u00a0\u00a0 Grammar G1 is defined with the productions, E\u00aeAB, A \u00e0 a, B \u00e0b. This grammar has the non-terminals A and B adjacent to each other and hence is not an operator precedence grammar.<\/p>\n

2.\u00a0\u00a0 Grammar G2 is defined with productions, E\u00aeEOE, E \u00e0 id, O \u00e0 + | * | \/ . This grammar is also not operator precedence grammar as E, O, E are non-terminals and they are adjacent to each other.<\/p>\n

3.\u00a0\u00a0\u00a0\u00a0\u00a0 Grammar G3, is a modified version of G2 with productions, E\u00aeE+E | E*E | E\/E | id which is a operator precedence grammar as it does not have \u03b5 productions and has no two non-terminals adjacent to each other in the RHS of the productions.<\/p>\n

 <\/p>\n

12.2 Ope rator precedence parser rules<\/strong><\/p>\n

 <\/p>\n

Let G be an \u220a-free operator grammar (No \u220a-Production).For each terminal symbols a and b, the following conditions need to be satisfied. We define three symbols to define the precedence relations between two terminals \u2018a\u2019 and \u2018b\u2019 namely, the \u2250 , <., .> to indicate same, lesser and greater precedence respectively. The same, lesser and greater precedence between any two terminals is defined based on the following rules:<\/p>\n

 <\/p>\n

1.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 The first rule is for the same precedence relation between two terminals \u2018a\u2019 and \u2018b\u2019. We say, a\u2250 b, if \u2203 a production in RHS of the form \u03b1a\u03b2b\u03b3, where \u03b2 is either \u220a or a single non-Terminal. Consider the grammar with a production, S\u00e0iCtSeS. It can be observed\u00a0that this grammar is an operator precedence grammar. The symbols for \u03b1 can be \u03b5, C, S for three situations. Thus for the scenario where \u03b1 is \u03b5, we have \u2018a\u2019 is \u2018i’ and \u2018b\u2019 is \u2018t\u2019. Thus we have the relation, <\/span>i \u2250 t. Considering an alternate situation, where \u03b1 is \u2018C\u2019, we have \u2018a\u2019 as \u2018t\u2019 and \u2018b\u2019 as \u2018e\u2019 which yields the precedence relation t \u2250 e. When \u03b1 is S, we don\u2019t have a symbol for \u03b2 and thus only these two precedence relations could be derived.<\/span><\/p>\n<\/div>\n

\n

2.\u00a0\u00a0\u00a0\u00a0\u00a0 The second rule is to design the lesser than relation between two terminals \u2018a\u2019 and \u2018b\u2019.<\/p>\n

 <\/p>\n

We say, a <. b if for some non-terminal A \u2203 a production in RHS of the form A\u00e0 \u03b1aA\u03b2, and A\u21d2+ \u03b3b\u03b4 where \u03b3 is either \u220a or a single non-terminal. Consider the productions, S\u00e0iCtS and C \u21d2+ b and where \u03b2 has \u2018b\u03b4\u2019 and hence, we deduce i <. b as non-terminal C derives \u2018b\u2019<\/p>\n

 <\/p>\n

3.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 The third rule is to design the greater than relation between two terminals \u2018a\u2019 and \u2018b\u2019 and is to look at the derivation from the right of the RHS of the production. We say, a .> b if for some non-terminal A \u2203 a production in RHS of the form A\u00e0 \u03b1Ab\u03b2, and A\u21d2+ \u03b3a\u03b4 where \u03b4 is either \u220a or a single non-terminal. Thus, for the production, S\u00e0iCtS and C \u21d2+ b the relation derived will be b .> t.<\/p>\n

 <\/p>\n

Example 12.1 Consider the following ambiguous expression grammar.<\/p>\n

 <\/p>\n

E\u00e0E+E | E*E | (E) | id<\/p>\n

This grammar is not a Operator precedence Grammar since by rule no. 3 we have + <. + &\u00a0\u00a0 + .> + as the grammar is ambiguous. However, we have the unambiguous expression grammar and is given below. This grammar has clear definition of the precedence relation. E\u00e0E+T | T, T\u00e0T*F | F, F\u00e0(E) | id<\/p>\n

 <\/p>\n

12.3 Ope rator precedence parsing<\/strong><\/p>\n

 <\/p>\n

The operator precedence parser is based on the precedence rules that are defined between the terminals of a grammar. In operator-precedence parsing, we define three disjoint precedence relations between certain pairs of terminals.<\/p>\n

 <\/p>\n

\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 a <. b implies \u2018b\u2019 has higher precedence than \u2018a\u2019<\/p>\n

\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 a =\u00b7 b implies \u2018b\u2019 has same precedence as \u2018a\u2019<\/p>\n

\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 a .> b implies \u2018b\u2019 has lower precedence than \u2018a\u2019<\/p>\n

 <\/p>\n

The challenge lies in the determination of correct precedence relations between terminals which are used for constructing the Operator precedence parsing table. For now let us assume the existence of the operator precedence parsing table. The determination of precedence relations are based on the traditional notions of associativity and precedence of operators. In the expression grammar, the precedence relations could be identified between all pairs of operators based on associativity and precedence and unary minus alone cause\u2019s problem.<\/p>\n<\/div>\n

\n

The intention of the precedence relations is to find the handle of a right-sentential form. The following conventions are used<\/p>\n

 <\/p>\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 <.\u00a0 with marking the left end,<\/p>\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 =\u00b7 appearing in the interior of the handle, and<\/p>\n

\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 .> marking the right hand.<\/p>\n

 <\/p>\n

The input string is prefixed and suffixed with \u201c$\u201d which would look like, \u201c $a1a2…an$ \u201c and then we insert the precedence relation between the pairs of terminals (the precedence relation holds between the terminals in that pair).<\/p>\n

 <\/p>\n

Example 11.2 Consider the following ambiguous grammar with productions E \u00ae E+E | E*E | id<\/p>\n

 <\/p>\n

Let us assume the precedence table as given in Table 12.1. The next section of this module will deal with the construction of this precedence table.<\/p>\n

 <\/p>\n

Table 12.1 Precedence table for ambiguous expression grammar<\/strong><\/p>\n

 <\/p>\n\n\n\n\n\n\n\n
<\/td>\nId<\/strong><\/td>\n+<\/strong><\/td>\n*<\/strong><\/td>\n$<\/strong><\/td>\n<\/tr>\n
id<\/strong><\/td>\n<\/td>\n.<\/strong>><\/strong><\/td>\n.<\/strong>><\/strong><\/td>\n.<\/strong>><\/strong><\/td>\n<\/tr>\n
+<\/strong><\/td>\n<<\/strong>.<\/strong><\/td>\n.<\/strong>><\/strong><\/td>\n<<\/strong>.<\/strong><\/td>\n.<\/strong>><\/strong><\/td>\n<\/tr>\n
*<\/strong><\/td>\n<<\/strong>.<\/strong><\/td>\n.<\/strong>><\/strong><\/td>\n.<\/strong>><\/strong><\/td>\n.<\/strong>><\/strong><\/td>\n<\/tr>\n
$<\/strong><\/td>\n<<\/strong>.<\/strong><\/td>\n<<\/strong>.<\/strong><\/td>\n<<\/strong>.<\/strong><\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

 <\/p>\n

 <\/p>\n

Then the input string id+id*id with the precedence relations inserted will look like \u201c$ <<\/strong>.<\/strong> id <\/strong>.<\/strong>> + <<\/strong>.<\/strong> id <\/strong>.<\/strong>> * <<\/strong>.<\/strong> id <\/strong>.<\/strong>> $\u201d<\/strong><\/p>\n

 <\/p>\n

The precedence relation is inserted between two terminals, by considering the first terminal in the row and the second terminal in the column. Thus, \u201c$\u201d and \u201cid\u201d has <<\/strong>..<\/strong> Thus, the next pair is \u201cid\u201d and \u201c+\u201d which has a .<\/strong>><\/strong> relation and is also inserted<\/p>\n

 <\/p>\n

The operator precedence parsing algorithm is a two step process. The stack is looked and scanned for the following<\/p>\n

 <\/p>\n

1.\u00a0\u00a0\u00a0\u00a0\u00a0 Scan the string from left end until the first .> is encountered.<\/p>\n

2.\u00a0\u00a0\u00a0\u00a0\u00a0 Then scan backwards (to the left) over any =\u00b7 until a <.\u00a0 is encountered.<\/p>\n

 <\/p>\n

This algorithm also uses a stack where the initial stack contents are the modified input string with precedence added. The handle contains everything to left of the first .> and to the right of the <. is encountered. The parsing action by the operator precedence parser is given in Table 12.2<\/p>\n

\"\"<\/p>\n<\/div>\n

\n

After discussing the overview of the operator precedence parsers, we will discuss each step of the operator precedence parser in detail. Steps involved in the construction of the parser are as follows.<\/p>\n

 <\/p>\n

1.\u00a0\u00a0\u00a0\u00a0\u00a0 Ensure the Grammar satisfies the pre-requisite<\/p>\n

2.\u00a0\u00a0\u00a0\u00a0\u00a0 Compute the functions Leading and Trailing<\/p>\n

3.\u00a0\u00a0\u00a0\u00a0\u00a0 Using the computed leading and trailing, construct the Operator precedence parsing table<\/p>\n

4.\u00a0\u00a0\u00a0\u00a0\u00a0 Parse the string based on the algorithm<\/p>\n

 <\/p>\n

In this module, we will discuss the computation of Leading and Trailing followed by the construction of the parsing table.<\/p>\n

 <\/p>\n

12.3 LEADING and TRAILING computation<\/strong><\/p>\n

 <\/p>\n

LEADING is defined for every non-terminal. It is defined for each non-terminal such that, terminals that can be the first terminal in a string derived from that non-terminal. Similarly, TRAILING for each non-terminal are those terminals that can be the last terminal in a string derived from that NT. Formally, the functions LEADING and TRAILING are defined as follows:\u00a0 \u00a0 \u00a0LEADING(A) = { a| A \u21d2+ \u03b3a\u03b4, where \u03b3 is \u220a or a single non-terminal., where => indicates derivation, + indicates in one or more steps, A is a non-terminal. Thus LEADING(A) can be interpreted as looking for the first terminal from the left, in the RHS of a production by applying all possible derivations for a production<\/span><\/p>\n<\/div>\n

\n

 <\/p>\n

TRAILING(A) = { a| A \u21d2+ \u03b3a\u03b4, where \u03b4 is \u220a or a single non-terminal., where => indicates derivation, + indicates in one or more steps, A is a non-terminal. Thus TRAILING(A) can be interpreted as looking for the first terminal from the right, in the RHS of a production by applying all possible derivations for a production.<\/p>\n

 <\/p>\n

The algorithm for finding LEADING(A) where A is a non-terminal is given in Algorithm 12.1<\/p>\n

 <\/p>\n

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

 <\/p>\n

LEADING(A)<\/p>\n

 <\/p>\n

{<\/p>\n

 <\/p>\n

1.\u00a0\u00a0\u00a0\u00a0\u00a0 \u2018a\u2019 is in Leading(A) if A \u00e0 \u03b3a\u03b4 where \u03b3 is \u03b5 or any Non-Terminal<\/p>\n

2.\u00a0\u00a0\u00a0\u00a0\u00a0 If\u2019 \u2018a\u2019 is in Leading(B) and A \u00e0 B\u03b1, then a in Leading(A)<\/p>\n

 <\/p>\n

}<\/p>\n

 <\/p>\n

Step 1 of algorithm 12.1, indicates how to add the first terminal occurring in the RHS of every production directly. Step 2 of the algorithm indicates to add the first terminal, through another non-terminal B to be included indirectly to the LEADING() of every non-terminal.<\/p>\n

 <\/p>\n

Similarly the algorithm to find TRAILING (A) is given in algorithm 12.2<\/p>\n

 <\/p>\n

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

 <\/p>\n

TRAILING (A)<\/p>\n

 <\/p>\n

{<\/p>\n

 <\/p>\n

1.\u00a0\u00a0\u00a0\u00a0\u00a0 a is in Trailing(A) if A \u00e0 \u03b3a\u03b4 where \u03b4 is \u03b5 or any Non-Terminal<\/p>\n

2.\u00a0\u00a0\u00a0\u00a0\u00a0 If a is in Trailing(B) and A \u00e0 \u03b1B, then a in Trailing(A)<\/p>\n

 <\/p>\n

}<\/p>\n

 <\/p>\n

Algorithm 12.2 is similar to algorithm 12.1 and the only difference being, the symbol is looked from right to left as against left to right in algorithm 12.1. Step 1 of the algorithm 12.2, indicates looking for the first terminal occurring in the RHS of a production from right side and thus adds the direct first symbol. The second step looks for adding the indirect first symbol from the right of the RHS of the production.<\/p>\n<\/div>\n

\n

Example 12.2 Consider the unambiguous version of the expression grammar.<\/p>\n

1.\u00a0\u00a0\u00a0\u00a0\u00a0 E \u00e0 E + T<\/p>\n

2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 E \u00e0 T<\/p>\n

3.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 T \u00e0 T * F<\/p>\n

4.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 T \u00e0 F<\/p>\n

5.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 F \u00e0 (E)<\/p>\n

6.\u00a0\u00a0\u00a0\u00a0\u00a0 F \u00e0 id<\/p>\n

 <\/p>\n

Let us consider the productions of F from productions 5, 6. From production 6, there is only one symbol in the RHS and that is a terminal. So, \u201cid\u201d will be in the LEADING(F). From production 5, the first symbol itself is a terminal \u201c(\u201c and hence that will be added to LEADING(F) as well. Further additions to LEADING(F) is not possible as the first symbol in the RHS of the productions involving F is a terminal. Thus<\/p>\n

 <\/p>\n

LEADING (F) = {( , id}<\/p>\n

 <\/p>\n

Let us consider the production of T as defined in production 3, 4. From production 3, the first symbol on the RHS is a non-terminal and the first terminal is \u201c*\u201d and thus \u201c*\u201d will be in LEADING(T). Then from production 4, there is only one symbol in the RHS and that is a non-terminal. So, the LEADING of the RHS non-terminal will be there in the LHS non-terminal also. Thus, LEADING(T) will include LEADING(F) in addition to \u201c*\u201d.<\/p>\n

 <\/p>\n

LEADING (T) = { *, (, id }<\/p>\n

 <\/p>\n

A similar analogy as explained for non-terminal T is applied to define the LEADING(E). Thus LEADING(E) will include LEADING(T) from production 2 and \u201c+\u201d from production 1. Thus<\/p>\n

 <\/p>\n

LEADING (E) = { + , * , ( , id}<\/p>\n

 <\/p>\n

Let us consider computation of TRAILING () where it is similar to LEADING() but the productions are scanned from right to left. Let us again start from F. From production 6, \u201cid\u201d will be in TRAILING(F) as it is the only symbol in the RHS. In addition, from production 5, \u201c)\u201d will be in the TRAILING(F) and will not have any more symbols as the first symbol from the right is a terminal in both productions.<\/p>\n

 <\/p>\n

TRAILING (F) = {), id}<\/p>\n

 <\/p>\n

Similarly from productions 3, 4, the TRAILING(T) would include \u201c*\u201d and TRAILING(F) from the two productions respectively. Thus,<\/p>\n

 <\/p>\n

TRAILING (T) = { *, ), id}<\/p>\n

 <\/p>\n

Similarly from productions 1,2, the TRAILING(E) would include \u201c+\u201d and TRAILING(T) from these two productions. Thus,<\/p>\n<\/div>\n

 <\/p>\n

\n

TRAILIN G (E) = { +, *, ), id}<\/p>\n

 <\/p>\n

12.4 Ope rator precedence parsing table construction<\/strong><\/p>\n

 <\/p>\n

After computing the two functions LEADING() and TRAILING(), the operator precedence table is constructed between all the terminals in the grammar including the \u201c$\u201d symbol. The algorithm for computing this parsing table is given in Algorithm 12.3<\/p>\n

 <\/p>\n

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

 <\/p>\n

PARSINGTABLE(Grammar G, LEADING(), TRAILING() )<\/p>\n

 <\/p>\n

{<\/p>\n

 <\/p>\n

For each production A \u00e0X1X2X3 …Xn<\/p>\n

 <\/p>\n

for i = 1 to n-1<\/p>\n

 <\/p>\n

1.\u00a0\u00a0\u00a0 if Xi and Xi+1\u00a0 are terminals<\/p>\n

set Xi =\u00b7 Xi+1<\/p>\n

2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 if i \u2264 n-2 and Xi and Xi+2 are terminals and Xi+1 is a non-terminal set Xi =\u00b7 Xi+2<\/p>\n

3.\u00a0\u00a0\u00a0\u00a0\u00a0 if Xi is a terminal and Xi+1 is a non-terminal then for all \u2018a\u2019 in Leading(Xi+1) set Xi <<\/strong>.<\/strong> a<\/strong><\/p>\n

4.\u00a0\u00a0\u00a0\u00a0\u00a0 if Xi is a non-terminal and Xi+1 is a terminal then for all \u2018a\u2019 in Trailing(Xi ) set a .<\/strong>><\/strong> Xi+1<\/p>\n

}<\/p>\n

 <\/p>\n

Example 12.3<\/p>\n

 <\/p>\n

Consider the unambiguous expression grammar involving as given in example 12.2. Step 1 is not to be encountered in the expression grammar where two terminals occur adjacent to each other. Step 2 of the algorithm looks for a Non-terminal between a pair of terminals and the RHS should have only three symbols, then we go for the same precedence. Using this step, the terminals \u201c(\u201c and \u201c)\u201d of the 5th production of the Expression grammar gets the same precedence and is given in Table 12.3. Since, it is the only production obeying this rule, the same precedence situation will not arise for any other pair of terminals.<\/p>\n

 <\/p>\n

Consider step 3 of the algorithm, where we are looking for a terminal followed by a non-terminal. Productions 1, 3, 5 will fall in this category. We are looking at \u201c+\u201d and \u201cT\u201d in<\/p>\n<\/div>\n

production 1. LEADING(T) = {*, (, id}. So we set + <<\/strong>.<\/strong> {*, (, id} and this is shown in row 1 of Table 12.3. Similarly, from production 3, we set * <<\/strong>.<\/strong> { (, id} and is given in row 2 of the table 12.3. So, is the case from production 5 we set ( <<\/strong>.<\/strong> {+, *, (, id}<\/p>\n

 <\/p>\n

Consider step 4 of the algorithm, where we are looking for a terminal preceded by a non-terminal. Similarly productions 1, 3, 5 will be used for this step of the algorithm also. Consider production 1 so we set, TRAILING(E) .<\/strong>><\/strong> Xi+1 . Therefore, { ), id} .<\/strong>><\/strong> + and is shown in row 5, row 3 of the algorithm. Similarly, {*, ), id} .<\/strong>><\/strong> *. From production 5, {+, *, ), id} .<\/strong>><\/strong> ). This parsing table is later used by the operator precedence parser.<\/p>\n

\"\"<\/p>\n

Summary<\/strong>: This module detailed on the pre-requisite for a grammar to be parsed using operator precedence parser with a brief note on the operator precedence parsing algorithm. This module also dealt with computing Leading, trailing and using which the operator parsing table is also constructed.<\/p>\n

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