Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Simple precedence parser
open-in-new
<h2 id="implementation">Implementation</h2> <ul><li>Compute the <a href="/facts/Wirth%25E2%2580%2593Weber_precedence_relationship/RKws90Nj">Wirth–Weber precedence relationship</a> table for a grammar with initial symbol S.</li> <li>Initialize a stack with the starting marker $.</li> <li>Append an ending marker $ to the string being parsed (Input).</li> <li>Until Stack equals "$ S" and Input equals "$" <ul><li>Search the table for the relationship between Top(stack) and NextToken(Input)</li> <li>if the relationship is ⋖ or ≐ <ul><li>Shift:</li> <li>Push(Stack, relationship)</li> <li>Push(Stack, NextToken(Input))</li> <li>RemoveNextToken(Input)</li></ul></li> <li>if the relationship is ⋗ <ul><li>Reduce:</li> <li>SearchProductionToReduce(Stack)</li> <li>Remove the Pivot from the Stack</li> <li>Search the table for the relationship between the nonterminal from the production and first symbol in the stack (Starting from top)</li> <li>Push(Stack, relationship)</li> <li>Push(Stack, Non terminal)</li></ul></li></ul></li></ul> <p>SearchProductionToReduce (Stack) </p> <ul><li>Find the topmost ⋖ in the stack; this and all the symbols above it are the Pivot.</li> <li>Find the production of the grammar which has the Pivot as its right side.</li></ul> <h2 id="example">Example</h2> <p>Given following language, which can parse arithmetic expressions with the multiplication and addition operations: </p> E --> E + T' | T' T' --> T T --> T * F | F F --> ( E' ) | num E' --> E <p>num is a terminal, and the <a href="/facts/Lexer_(computer_science)/T1JYWpIf">lexer</a> parse any integer as num; E represents an arithmetic expression, T is a term and F is a factor. </p><p>and the Parsing table: </p> <table><tbody><tr><th></th><th>E</th><th>E'</th><th>T</th><th>T'</th><th>F</th><th>+</th><th>*</th><th>(</th><th>)</th><th>num</th><th>$</th></tr><tr><th>E</th><td></td><td></td><td></td><td></td><td></td><td>≐</td><td></td><td></td><td>⋗</td><td></td><td></td></tr><tr><th>E'</th><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>≐</td><td></td><td></td></tr><tr><th>T</th><td></td><td></td><td></td><td></td><td></td><td>⋗</td><td>≐</td><td></td><td>⋗</td><td></td><td>⋗</td></tr><tr><th>T'</th><td></td><td></td><td></td><td></td><td></td><td>⋗</td><td></td><td></td><td>⋗</td><td></td><td>⋗</td></tr><tr><th>F</th><td></td><td></td><td></td><td></td><td></td><td>⋗</td><td>⋗</td><td></td><td>⋗</td><td></td><td>⋗</td></tr><tr><th>+</th><td></td><td></td><td>⋖</td><td>≐</td><td>⋖</td><td></td><td></td><td>⋖</td><td></td><td>⋖</td><td></td></tr><tr><th>*</th><td></td><td></td><td></td><td></td><td>≐</td><td></td><td></td><td>⋖</td><td></td><td>⋖</td><td></td></tr><tr><th>(</th><td>⋖</td><td>≐</td><td>⋖</td><td>⋖</td><td>⋖</td><td></td><td></td><td>⋖</td><td></td><td>⋖</td><td></td></tr><tr><th>)</th><td></td><td></td><td></td><td></td><td></td><td>⋗</td><td>⋗</td><td></td><td>⋗</td><td></td><td>⋗</td></tr><tr><th>num</th><td></td><td></td><td></td><td></td><td></td><td>⋗</td><td>⋗</td><td></td><td>⋗</td><td></td><td>⋗</td></tr><tr><th>$</th><td>⋖</td><td></td><td>⋖</td><td>⋖</td><td>⋖</td><td></td><td></td><td>⋖</td><td></td><td>⋖</td><td></td></tr></tbody></table> <table><tbody><tr><th scope="col"> STACK</th><th scope="col"> PRECEDENCE</th><th scope="col"> INPUT</th><th scope="col"> ACTION</th></tr><tr><td> $</td><td> ⋖</td><td> 2 * ( 1 + 3 )$</td><td> SHIFT</td></tr><tr><td> $ ⋖ 2</td><td> ⋗</td><td> * ( 1 + 3 )$</td><td> REDUCE (F -> num)</td></tr><tr><td> $ ⋖ F</td><td> ⋗</td><td> * ( 1 + 3 )$</td><td> REDUCE (T -> F)</td></tr><tr><td> $ ⋖ T</td><td> ≐</td><td> * ( 1 + 3 )$</td><td> SHIFT</td></tr><tr><td> $ ⋖ T ≐ *</td><td> ⋖</td><td> ( 1 + 3 )$</td><td> SHIFT</td></tr><tr><td> $ ⋖ T ≐ * ⋖ (</td><td> ⋖</td><td> 1 + 3 )$</td><td> SHIFT</td></tr><tr><td> $ ⋖ T ≐ * ⋖ ( ⋖ 1</td><td> ⋗</td><td> + 3 )$</td><td> REDUCE 4× (F -> num) (T -> F) (T' -> T) (E ->T ')</td></tr><tr><td> $ ⋖ T ≐ * ⋖ ( ⋖ E</td><td> ≐</td><td> + 3 )$</td><td> SHIFT</td></tr><tr><td> $ ⋖ T ≐ * ⋖ ( ⋖ E ≐ +</td><td> ⋖</td><td> 3 )$</td><td> SHIFT</td></tr><tr><td> $ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + < 3</td><td> ⋗</td><td> )$</td><td> REDUCE 3× (F -> num) (T -> F) (T' -> T)</td></tr><tr><td> $ ⋖ T ≐ * ⋖ ( ⋖ E ≐ + ≐ T</td><td> ⋗</td><td> )$</td><td> REDUCE 2× (E -> E + T) (E' -> E)</td></tr><tr><td> $ ⋖ T ≐ * ⋖ ( ≐ E'</td><td> ≐</td><td> )$</td><td> SHIFT</td></tr><tr><td> $ ⋖ T ≐ * ⋖ ( ≐ E' ≐ )</td><td> ⋗</td><td> $</td><td> REDUCE (F -> ( E' ))</td></tr><tr><td> $ ⋖ T ≐ * ≐ F</td><td> ⋗</td><td> $</td><td> REDUCE (T -> T * F)</td></tr><tr><td> $ ⋖ T</td><td> ⋗</td><td> $</td><td> REDUCE 2× (T' -> T) (E -> T')</td></tr><tr><td> $ ⋖ E</td><td></td><td> $</td><td> ACCEPT</td></tr></tbody></table> <ul><li>Alfred V. Aho, Jeffrey D. Ullman (1977). <i><a href="/facts/Principles_of_Compiler_Design/1PVNPhbM">Principles of Compiler Design</a></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>