Simple precedence grammar

<h2 id="formal-definition">Formal definition</h2>
<p>G = (<i>N</i>, Σ, <i>P</i>, <i>S</i>) is a simple precedence grammar if all the production rules in <i>P</i> comply with the following constraints:
</p>
<ul><li>There are no <a href="/facts/Erasing_rule/QLxaQNAz">erasing rules</a> (ε-productions)</li>
<li>There are no <a href="/facts/Useless_rules/yu1FFdK4">useless rules</a> (unreachable symbols or unproductive rules)</li>
<li>For each pair of symbols <i>X</i>, <i>Y</i> (<i>X</i>, <i>Y</i> 
  
    
      
        ∈
      
    
    {\displaystyle \in }
  
 (<i>N</i> ∪ Σ)) there is only one <a href="/facts/Wirth%25E2%2580%2593Weber_precedence_relationship/RKws90Nj">Wirth–Weber precedence relation</a>.</li>
<li>G is uniquely inversible</li></ul>
<h2 id="examples">Examples</h2>

S
        →
        a
        S
        S
        b
        
          |
        
        c
      
    
    {\displaystyle S\to aSSb|c}

precedence table

S
              
              
                a
              
              
                b
              
              
                c
              
              
                $
              
            
            
              
                S
              
              
                
                  
                    
                      =
                      ˙
                    
                  
                
              
              
                ⋖
              
              
                
                  
                    
                      =
                      ˙
                    
                  
                
              
              
                ⋖
              
              
            
            
              
                a
              
              
                
                  
                    
                      =
                      ˙
                    
                  
                
              
              
                ⋖
              
              
              
                ⋖
              
              
            
            
              
                b
              
              
              
                ⋗
              
              
              
                ⋗
              
              
                ⋗
              
            
            
              
                c
              
              
              
                ⋗
              
              
                ⋗
              
              
                ⋗
              
              
                ⋗
              
            
            
              
                $
              
              
              
                ⋖
              
              
              
                ⋖
              
              
            
          
        
      
    
    {\displaystyle {\begin{array}{c|ccccc}&S&a&b&c&\$\\\hline S&{\dot {=}}&\lessdot &{\dot {=}}&\lessdot &\\a&{\dot {=}}&\lessdot &&\lessdot &\\b&&\gtrdot &&\gtrdot &\gtrdot \\c&&\gtrdot &\gtrdot &\gtrdot &\gtrdot \\\$&&\lessdot &&\lessdot &\end{array}}}

<h2 id="notes">Notes</h2>

<ul><li>Alfred V. Aho, Jeffrey D. Ullman (1977). <i>Principles of Compiler Design</i>. 1st Edition. Addison–Wesley.</li>
<li>William A. Barrett, John D. Couch (1979). <i>Compiler construction: Theory and Practice</i>. Science Research Associate.</li>
<li>Jean-Paul Tremblay, P. G. Sorenson (1985). <i>The Theory and Practice of Compiler Writing</i>. McGraw–Hill.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.cs.clemson.edu/course/cpsc827/material/Simple%20Precedence/Relations.pdf">"Simple Precedence Relations"</a> at Clemson University</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>The Theory of Parsing, Translation, and Compiling: Compiling, Alfred V. Aho, Jeffrey D. Ullman, Prentice–Hall, 1972. <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Claude Pair (1964). "Arbres, piles et compilation". Revue française de traitement de l'information., in English Trees, stacks and compiling <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Machines, Languages, and Computation, Prentice–Hall, 1978, ISBN 9780135422588, Wirth and Weber [1966] generalized Floyd's precedence grammars, obtaining the simple precedence grammars. <a href="9780135422588" target="_blank">9780135422588</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Simple precedence grammar open-in-new

Simple precedence grammar