Operator-precedence grammar

<h2 id="precedence-relations">Precedence relations</h2>
<p>Operator precedence grammars rely on the following three precedence relations between the terminals:<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p>
<table><tbody><tr><th>Relation</th><th>Meaning</th></tr><tr><td>                    a        ⋖        b              {\displaystyle a\lessdot b}  </td><td>a yields precedence to b</td></tr><tr><td>                    a        ≐        b              {\displaystyle a\doteq b}  </td><td>a has the same precedence as b</td></tr><tr><td>                    a        ⋗        b              {\displaystyle a\gtrdot b}  </td><td>a takes precedence over b</td></tr></tbody></table>
<p>These operator precedence relations allow to delimit the <a href="/facts/Bottom-up_parsing/d1JDdc5h">handles</a> in the <a href="/facts/Formal_grammar/QLxaQNAz">right sentential forms</a>: 
  
    
      
        ⋖
      
    
    {\displaystyle \lessdot }
  
 marks the left end, 
  
    
      
        ≐
      
    
    {\displaystyle \doteq }
  
 appears in the interior of the handle, and 
  
    
      
        ⋗
      
    
    {\displaystyle \gtrdot }
  
 marks the right end. Contrary to other shift-reduce parsers, all nonterminals are considered equal for the purpose of identifying handles.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
The relations do not have the same properties as their un-dotted counterparts;
e. g. 
  
    
      
        a
        ≐
        b
      
    
    {\displaystyle a\doteq b}
  
 does not generally imply 
  
    
      
        b
        ≐
        a
      
    
    {\displaystyle b\doteq a}
  
, and 
  
    
      
        b
        ⋗
        a
      
    
    {\displaystyle b\gtrdot a}
  
 does not follow
from 
  
    
      
        a
        ⋖
        b
      
    
    {\displaystyle a\lessdot b}
  
. Furthermore, 
  
    
      
        a
        ≐
        a
      
    
    {\displaystyle a\doteq a}
  
 does not generally hold, and 
  
    
      
        a
        ⋗
        a
      
    
    {\displaystyle a\gtrdot a}
  
 is possible.
</p><p>Let us assume that between the terminals ai and <i>a</i><i>i</i>+1 there is always exactly one precedence relation. Suppose that $ is the end of the string.
Then for all terminals b we define:  
  
    
      
        $
        ⋖
        b
      
    
    {\displaystyle \$\lessdot b}
  
 and 
  
    
      
        b
        ⋗
        $
      
    
    {\displaystyle b\gtrdot \$}
  
. If we remove all nonterminals and place the correct precedence relation:

⋖
      
    
    {\displaystyle \lessdot }
  
, 
  
    
      
        ≐
      
    
    {\displaystyle \doteq }
  
, 
  
    
      
        ⋗
      
    
    {\displaystyle \gtrdot }
  
 between the remaining terminals, there remain strings that can be analyzed by an easily developed <a href="/facts/Bottom-up_parser/d1JDdc5h">bottom-up parser</a>.
</p>
<h3>Example</h3>
<p>For example, the following operator precedence relations can
be introduced for simple expressions:<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p>

i
                  d
                
              
              
                +
              
              
                ∗
              
              
                $
              
            
            
              
                
                  i
                  d
                
              
              
              
                ⋗
              
              
                ⋗
              
              
                ⋗
              
            
            
              
                +
              
              
                ⋖
              
              
                ⋗
              
              
                ⋖
              
              
                ⋗
              
            
            
              
                ∗
              
              
                ⋖
              
              
                ⋗
              
              
                ⋗
              
              
                ⋗
              
            
            
              
                $
              
              
                ⋖
              
              
                ⋖
              
              
                ⋖
              
              
            
          
        
      
    
    {\displaystyle {\begin{array}{c|cccc}&\mathrm {id} &+&*&\$\\\hline \mathrm {id} &&\gtrdot &\gtrdot &\gtrdot \\+&\lessdot &\gtrdot &\lessdot &\gtrdot \\*&\lessdot &\gtrdot &\gtrdot &\gtrdot \\\$&\lessdot &\lessdot &\lessdot &\end{array}}}

<p>They follow from the following facts:<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>
<ul><li>+ has lower precedence than * (hence 
  
    
      
        +
        ⋖
        ∗
      
    
    {\displaystyle +\lessdot *}
  
 and 
  
    
      
        ∗
        ⋗
        +
      
    
    {\displaystyle *\gtrdot +}
  
).</li>
<li>Both + and * are <a href="/facts/Left-associative/HcEdArws">left-associative</a> (hence 
  
    
      
        +
        ⋗
        +
      
    
    {\displaystyle +\gtrdot +}
  
 and 
  
    
      
        ∗
        ⋗
        ∗
      
    
    {\displaystyle *\gtrdot *}
  
).</li></ul>
<p>The input string<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a>
</p>

i
            d
          
          
            1
          
        
        +
        
          
            i
            d
          
          
            2
          
        
        ∗
        
          
            i
            d
          
          
            3
          
        
      
    
    {\displaystyle \mathrm {id} _{1}+\mathrm {id} _{2}*\mathrm {id} _{3}}

<p>after adding end markers and inserting precedence relations becomes
</p>

$
        ⋖
        
          
            i
            d
          
          
            1
          
        
        ⋗
        +
        ⋖
        
          
            i
            d
          
          
            2
          
        
        ⋗
        ∗
        ⋖
        
          
            i
            d
          
          
            3
          
        
        ⋗
        $
      
    
    {\displaystyle \$\lessdot \mathrm {id} _{1}\gtrdot +\lessdot \mathrm {id} _{2}\gtrdot *\lessdot \mathrm {id} _{3}\gtrdot \$}

<h2 id="operator-precedence-parsing">Operator precedence parsing</h2>
<p>Having precedence relations allows to identify handles as follows:<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a>
</p>
<ul><li>scan the string from left until seeing 
  
    
      
        ⋗
      
    
    {\displaystyle \gtrdot }
  
</li>
<li>scan backwards (from right to left) over any 
  
    
      
        ≐
      
    
    {\displaystyle \doteq }
  
 until seeing 
  
    
      
        ⋖
      
    
    {\displaystyle \lessdot }
  
</li>
<li>everything between the two relations 
  
    
      
        ⋖
      
    
    {\displaystyle \lessdot }
  
 and 
  
    
      
        ⋗
      
    
    {\displaystyle \gtrdot }
  
, including any intervening or surrounding nonterminals, forms the handle</li></ul>
<p>It is generally not necessary to scan the entire <a href="/facts/Formal_grammar/QLxaQNAz">sentential form</a> to find the handle.
</p>
<h2 id="operator-precedence-parsing-algorithm">Operator precedence parsing algorithm</h2>
<p>The algorithm below is from Aho et al.:<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a>
</p>
If $ is on the top of the stack and ip points to $ then return
else
    Let a be the top terminal on the stack, and b the symbol pointed to by ip
    if <i>a</i> 
  
    
      
        ⋖
      
    
    {\displaystyle \lessdot }
  
 <i>b</i> or <i>a</i> 
  
    
      
        ≐
      
    
    {\displaystyle \doteq }
  
 <i>b</i> then
        push <i>b</i> onto the stack
        advance ip to the next input symbol
    else if <i>a</i> 
  
    
      
        ⋗
      
    
    {\displaystyle \gtrdot }
  
 <i>b</i> then
        repeat
            pop the stack
        until the top stack terminal is related by 
  
    
      
        ⋖
      
    
    {\displaystyle \lessdot }
  
 to the terminal most recently popped
    else error()
end

<h2 id="precedence-functions">Precedence functions</h2>
<p>An operator precedence parser usually does not store the precedence table with the relations, which can get rather large. Instead, precedence functions <i>f</i> and <i>g</i> are defined.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a>
They map terminal symbols to integers, and so the precedence relations between the symbols are implemented by numerical comparison:
⁠
  
    
      
        f
        (
        a
        )
        <
        g
        (
        b
        )
      
    
    {\displaystyle f(a)<g(b)}
  
⁠ must hold if 
  
    
      
        a
        ⋖
        b
      
    
    {\displaystyle a\lessdot b}
  
 holds, etc.
</p><p>Not every table of precedence relations has precedence functions, but in practice for most grammars such functions can be designed.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a>
</p>
<h3>Algorithm for constructing precedence functions</h3>
<p>The below algorithm is from Aho et al.:<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a>
</p>
<ol><li>Create symbols fa and ga for each grammar terminal a and for the end of string symbol;</li>
<li>Partition the created symbols in groups so that fa and gb are in the same group if 
  
    
      
        a
        ≐
        b
      
    
    {\displaystyle a\doteq b}
  
 (there can be symbols in the same group even if their terminals are not connected by this relation);</li>
<li>Create a <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">directed graph</a> whose nodes are the groups. For each pair ⁠
  
    
      
        (
        a
        ,
        b
        )
      
    
    {\displaystyle (a,b)}
  
⁠ of terminals do: place an edge from the group of gb to the group of fa if 
  
    
      
        a
        ⋖
        b
      
    
    {\displaystyle a\lessdot b}
  
, otherwise if 
  
    
      
        a
        ⋗
        b
      
    
    {\displaystyle a\gtrdot b}
  
 place an edge from the group of fa to that of gb;</li>
<li>If the constructed graph has a cycle then no precedence functions exist. When there are no cycles, let ⁠
  
    
      
        f
        (
        a
        )
      
    
    {\displaystyle f(a)}
  
⁠ be the length of the <a href="/facts/Longest_path/W17hlDKs">longest path</a> from the group of fa and let ⁠
  
    
      
        g
        (
        a
        )
      
    
    {\displaystyle g(a)}
  
⁠ be the length of the longest path from the group of ga.</li></ol>
<h3>Example</h3>
<p>Consider the following table (repeated from above):<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a>
</p>

<p>Using the algorithm leads to the following graph:
</p>
    gid
      \
 fid   f*
    \  /
     g*
    /
  f+  
   | \
   |  g+
   |  |
  g$  f$

<p>from which we extract the following precedence functions from the maximum heights in the <a href="/facts/Directed_acyclic_graph/k6zq1os9">directed acyclic graph</a>:
</p>
<table><tbody><tr><th></th><th>id</th><th>+</th><th>*</th><th>$</th></tr><tr><th><i>f</i></th><td>4</td><td>2</td><td>4</td><td>0</td></tr><tr><th><i>g</i></th><td>5</td><td>1</td><td>3</td><td>0</td></tr></tbody></table>
<h2 id="operator-precedence-languages">Operator-precedence languages</h2>
<p>The class of languages described by operator-precedence grammars, i.e., operator-precedence languages, is strictly contained in the class of <a href="/facts/Deterministic_context-free_language/XDlUnBJ8">deterministic context-free languages</a>, and strictly contains <a href="/facts/Visibly_pushdown_language/a7t4wPmA">visibly pushdown languages</a>.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a>
</p><p>Operator-precedence languages enjoy many closure properties: union, intersection, complementation,<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> concatenation,<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> and they are the largest known class closed under all these operations and for which the emptiness problem is decidable. Another peculiar feature of operator-precedence languages is their local parsability,<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> that enables efficient parallel parsing.
</p><p>There are also characterizations based on an equivalent form of automata and monadic second-order logic.<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a>
</p>
<h2 id="notes">Notes</h2>

<ul><li>Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1988). <i>Compilers — Principles, Techniques, and Tools</i>. Addison-Wesley.</li>
<li>Crespi Reghizzi, Stefano; Mandrioli, Dino (2012). <a href="https://doi.org/10.1016%2Fj.jcss.2011.12.006">"Operator precedence and the visibly pushdown property"</a>. <i>Journal of Computer and System Sciences</i>. 78 (6): 1837–1867. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.jcss.2011.12.006">10.1016/j.jcss.2011.12.006</a>.</li>
<li>Crespi Reghizzi, Stefano; Mandrioli, Dino; Martin, David F. (1978). <a href="https://doi.org/10.1016%2FS0019-9958%2878%2990474-6">"Algebraic Properties of Operator Precedence Languages"</a>. <i>Information and Control</i>. 37 (2): 115–133. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0019-9958%2878%2990474-6">10.1016/S0019-9958(78)90474-6</a>.</li>
<li>Barenghi, Alessandro; Crespi Reghizzi, Stefano; Mandrioli, Dino; Panella, Federica; Pradella, Matteo (2015). <a href="https://doi.org/10.1016%2Fj.scico.2015.09.002">"Parallel parsing made practical"</a>. <i>Science of Computer Programming</i>. 112 (3): 245–249. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.scico.2015.09.002">10.1016/j.scico.2015.09.002</a>. <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/11311%2F971391">11311/971391</a>.</li>
<li>Lonati, Violetta; Mandrioli, Dino; Panella, Federica; Pradella, Matteo (2015). "Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization". <i>SIAM Journal on Computing</i>. 44 (4): 1026–1088. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F140978818">10.1137/140978818</a>. <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/2434%2F352809">2434/352809</a>.</li></ul>
<h2 id="further-reading">Further reading</h2>
<ul><li><a href="/facts/Robert_W._Floyd/sTFRb3TH">Floyd, R. W.</a> (July 1963). <a href="https://doi.org/10.1145%2F321172.321179">"Syntactic Analysis and Operator Precedence"</a>. <i>Journal of the ACM</i>. 10 (3): 316–333. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F321172.321179">10.1145/321172.321179</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:19785090">19785090</a>.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li>Nikolay Nikolaev: <a href="http://homepages.gold.ac.uk/nikolaev/cis324.htm">IS53011A Language Design and Implementation</a>, Course notes for CIS 324, 2010.</li></ul>

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

<ol>
<li id="fn:1"><p>Aho, Sethi & Ullman 1988, p. 203 - Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1988). Compilers — Principles, Techniques, and Tools. Addison-Wesley. <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Aho, Sethi & Ullman 1988, pp. 203–204 - Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1988). Compilers — Principles, Techniques, and Tools. Addison-Wesley. <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Aho, Sethi & Ullman 1988, pp. 205–206 - Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1988). Compilers — Principles, Techniques, and Tools. Addison-Wesley. <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Aho, Sethi & Ullman 1988, p. 205 - Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1988). Compilers — Principles, Techniques, and Tools. Addison-Wesley. <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Aho, Sethi & Ullman 1988, p. 204 - Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1988). Compilers — Principles, Techniques, and Tools. Addison-Wesley. <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Aho, Sethi & Ullman 1988, p. 205 - Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1988). Compilers — Principles, Techniques, and Tools. Addison-Wesley. <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>Aho, Sethi & Ullman 1988, p. 205 - Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1988). Compilers — Principles, Techniques, and Tools. Addison-Wesley. <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>Aho, Sethi & Ullman 1988, p. 206 - Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1988). Compilers — Principles, Techniques, and Tools. Addison-Wesley. <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
<li id="fn:9"><p>Aho, Sethi & Ullman 1988, pp. 208–209 - Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1988). Compilers — Principles, Techniques, and Tools. Addison-Wesley. <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li>
<li id="fn:10"><p>Aho, Sethi & Ullman 1988, p. 209 - Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1988). Compilers — Principles, Techniques, and Tools. Addison-Wesley. <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li>
<li id="fn:11"><p>Aho, Sethi & Ullman 1988, pp. 209–210 - Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1988). Compilers — Principles, Techniques, and Tools. Addison-Wesley. <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li>
<li id="fn:12"><p>Aho, Sethi & Ullman 1988, p. 210 - Aho, Alfred V.; Sethi, Ravi; Ullman, Jeffrey D. (1988). Compilers — Principles, Techniques, and Tools. Addison-Wesley. <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li>
<li id="fn:13"><p>Crespi Reghizzi & Mandrioli 2012 - Crespi Reghizzi, Stefano; Mandrioli, Dino (2012). "Operator precedence and the visibly pushdown property". Journal of Computer and System Sciences. 78 (6): 1837–1867. doi:10.1016/j.jcss.2011.12.006. <a href="https://doi.org/10.1016%2Fj.jcss.2011.12.006" target="_blank">https://doi.org/10.1016%2Fj.jcss.2011.12.006</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li>
<li id="fn:14"><p>Crespi Reghizzi, Mandrioli & Martin 1978 - Crespi Reghizzi, Stefano; Mandrioli, Dino; Martin, David F. (1978). "Algebraic Properties of Operator Precedence Languages". Information and Control. 37 (2): 115–133. doi:10.1016/S0019-9958(78)90474-6. <a href="https://doi.org/10.1016%2FS0019-9958%2878%2990474-6" target="_blank">https://doi.org/10.1016%2FS0019-9958%2878%2990474-6</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li>
<li id="fn:15"><p>Crespi Reghizzi & Mandrioli 2012 - Crespi Reghizzi, Stefano; Mandrioli, Dino (2012). "Operator precedence and the visibly pushdown property". Journal of Computer and System Sciences. 78 (6): 1837–1867. doi:10.1016/j.jcss.2011.12.006. <a href="https://doi.org/10.1016%2Fj.jcss.2011.12.006" target="_blank">https://doi.org/10.1016%2Fj.jcss.2011.12.006</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li>
<li id="fn:16"><p>Barenghi et al. 2015 - Barenghi, Alessandro; Crespi Reghizzi, Stefano; Mandrioli, Dino; Panella, Federica; Pradella, Matteo (2015). "Parallel parsing made practical". Science of Computer Programming. 112 (3): 245–249. doi:10.1016/j.scico.2015.09.002. hdl:11311/971391. <a href="https://doi.org/10.1016%2Fj.scico.2015.09.002" target="_blank">https://doi.org/10.1016%2Fj.scico.2015.09.002</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li>
<li id="fn:17"><p>Lonati et al. 2015 - Lonati, Violetta; Mandrioli, Dino; Panella, Federica; Pradella, Matteo (2015). "Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization". SIAM Journal on Computing. 44 (4): 1026–1088. doi:10.1137/140978818. hdl:2434/352809. <a href="https://doi.org/10.1137%2F140978818" target="_blank">https://doi.org/10.1137%2F140978818</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li>
</ol>

Operator-precedence grammar open-in-new

Operator-precedence grammar