Understanding LEADING and TRAILING operations of an operator precedence grammar

Question Detail: 

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      -- I E   ->  T              -- II T   ->  T   *   F      -- III T   ->  F              -- IV F   ->  (   E   )      -- V F   ->  id             -- VI 

By 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.

Asked By : Likhit

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4716

Answered By : Maverick Snyder

@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.