Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

migrated from cstheory.stackexchange.com Sep 24 '12 at 15:27

This question came from our site for theoretical computer scientists and researchers in related fields.

1  
Clearly, the solution does not match what you say TRAILING is supposed to be. Please cite the precise definition. –  Raphael Sep 24 '12 at 18:32
    
@Raphael The problem is that I don't know. The definition I gave is from zeus.cs.pacificu.edu/chadd/cs480s09/Lectures/Lec6.pdf which I came across while trying to answer this question. –  Likhit Sep 25 '12 at 12:55
    
The sad part is this question is already on google's first page for the search term operator precedence grammars leading and trailing. –  Likhit Sep 25 '12 at 12:57
    
This link has a better explanation on leading and trailing. It uses the terms Firststop and Laststop in place of LEADING and TRAILING. As you may see, it increases my confusion. The example taken here makes my LEADING(logic) wrong too. –  Likhit Sep 25 '12 at 13:18
2  
I know "FIRST" and "FOLLOW" but "FOLLOW" does not seem to match either your "definition" or the solution. –  Raphael Sep 25 '12 at 13:56
show 1 more comment

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
add comment

I think this link will be a great help to find leading and trailing for every nonterminal involved in a given grammar. http://www.scribd.com/doc/51358638/16/Operator-Precedence-Relations It made the concept clear to me!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.