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