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.
TRAILINGis supposed to be. Please cite the precise definition. – Raphael♦ Sep 24 '12 at 18:32precedence grammars leading and trailing. – Likhit Sep 25 '12 at 12:57