According to this post https://stackoverflow.com/questions/28397767/computing-leading-and-trailing-sets-for-context-free-grammar while constructing operator precendence parser we have to create tabel with operator. Actually i dont understand the rules which tells how to build such table. For example take last production term -> '(' expr ')' do we use rule terminal nonterminal because of ( expr or do we use rule nonterminal terminal because of expr ) or do we use rule terminal nonterminal terminal shoudl we divide production or treat as whole? Then is there any other rule applicable in example from link then terminal nonterminal terminal ?


1 Answer 1


I think that answer is clear (although of course I would do, because I wrote it).

What it says is:

if you find

$$nonterminal\; TERMINAL$$

in any production, then you add the precedence relations $TRAIL \gtrdot TERMINAL$ for every $TRAIL$ in $Trailing(nonterminal)$. Similarly, every occurrence of

$$TERMINAL\; nonterminal$$

generates the relationships $TERMINAL \lessdot LEAD$ for every $LEAD$ in $Leading(nonterminal)$.

So in $'(' expr ')'$, you have both an instance of $TERMINAL\; nonterminal$ and an instance of $nonterminal\; TERMINAL$, and you need to deal with both of them independently.

  • $\begingroup$ Do we have $ operator in such gramma or we ignore it? $\endgroup$
    – whd
    May 31, 2016 at 18:45
  • $\begingroup$ Do you mean the convention of augmenting grammars with an end-of-input symbol? If so, that is usually done in order to finish the parse. Since the only use of $ in the grammar will be in the augmented production S' -> S $, we can conclude that every terminal T which has a relation with $ has the relation T ⋗ $. In practice, it's easy to just add that relation to every terminal. $\endgroup$
    – rici
    May 31, 2016 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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