I want to understand what the LEADING and TRAILING of non-terminal in an operator precedence grammar physically mean.I am confused by the various definitions I have read on them. I understand that the LEADING of a non-terminal is the first terminal which can be present in it's derivation. On the other hand, the TRAILING of a non-terminal is the last terminal which can be present in it's derivation. In the following example: E   ->  E   +   T      -- IE   ->  T              -- IIT   ->  T   *   F      -- IIIT   ->  F              -- IVF   ->  (   E   )      -- VF   ->  id             -- VIBy my understanding,LEADING(E) = { +, *, (, id }LEADING(T) = { *, (, id }LEADING(F) = { (, id }This turns out fine, but my problem is in the TRAILING.TRAILING(F) = { id, ) }TRAILING(T) = TRAILING(F) = { id, ) }          -- (1)TRAILING(E) = TRAILING(T) = { id, ) }          -- (2)Reason for (2) is that according to productions I and II, the last terminal of the derivation of E will be last terminals in the derivation of T.Hence, TRAILING(E) = TRAILING(T).Similarly, TRAILING(T) = TRAILING(F).Unfortunately the solution to this problem states:TRAILING(F) = { id, ) }TRAILING(T) = TRAILING(F) `union` { * } = { *, id, ) }TRAILING(E) = TRAILING(T) `union` { + } = { +, *, id, ) }I don't see how * or + can be the last terminals in the derivation of E. Any derivation of E will always end with either an id or ). Similarly, case for T.
Understanding LEADING and TRAILING operations of an operator precedence grammar
terminology;formal grammars;parsing
@Raphael : Definition of trailing : Any terminal which is present at the last of a right sentential form (and not the sentence) which is derived from a non-terminal is the trailing of that non-terminal.Trailing($E$) : $E \rightarrow E + T$  --In this the trailing is '$+$'$ \rightarrow E + T * F$ [using $T \rightarrow T*F$] -- Here trailing is '$*$'$\rightarrow E + T * ( E )$ [using $F \rightarrow ( E )$] -- Here trailing is '$)$'(from $E + T * F$) $\rightarrow E + T * id$ [using $F \rightarrow id$] -- Here trailing is '$id$'Hence trailing($E$) = $\{+,*,),id\}$So the lesson here is that you must use the right sentential forms also and not just the sentence to find out the trailing.Note : $E \rightarrow E + T \rightarrow E + T * F \rightarrow E + F * id \rightarrow T + id * id \rightarrow F + id * id$ are all right sentential forms of $E$ as they have at least one non-terminal.However $id + id * id$ is a sentence because it has no non-terminals and you must not use just the sentence to find out the trailing.