diff options
Added the parser generators slides to the contents
1 files changed, 334 insertions, 0 deletions
| -rw-r--r-- | website/content/slides/04_parser_generators/parser.html | 334 |
diff --git a/website/content/slides/04_parser_generators/parser.html b/website/content/slides/04_parser_generators/parser.html new file mode 100644 index 0000000..724b703 --- /dev/null +++ b/website/content/slides/04_parser_generators/parser.html @@ -0,0 +1,334 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> +<html xmlns="http://www.w3.org/1999/xhtml" xmlns:bison="http://www.gnu.org/software/bison/"> + <head> + <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> + <title>parser.y - GNU Bison XML Automaton Report</title> + <style type="text/css"> + body { + font-family: "Nimbus Sans L", Arial, sans-serif; + font-size: 9pt; + } + a:link { + color: #1f00ff; + text-decoration: none; + } + a:visited { + color: #1f00ff; + text-decoration: none; + } + a:hover { + color: red; + } + #menu a { + text-decoration: underline; + } + .i { + font-style: italic; + } + .pre { + font-family: monospace; + white-space: pre; + } + ol.decimal { + list-style-type: decimal; + } + ol.lower-alpha { + list-style-type: lower-alpha; + } + .point { + color: #cc0000; + } + #footer { + margin-top: 3.5em; + font-size: 7pt; + } + </style> + </head> + <body><h1>GNU Bison XML Automaton Report</h1><p> + input grammar: <span class="i">parser.y</span></p> + +<h3>Table of Contents</h3><ul id="menu"><li><a href="#reductions">Reductions</a><ul class="lower-alpha"><li><a href="#nonterminals_useless_in_grammar">Nonterminals useless in grammar</a></li><li><a href="#terminals_unused_in_grammar">Terminals unused in grammar</a></li><li><a href="#rules_useless_in_grammar">Rules useless in grammar</a></li></ul></li><li><a href="#conflicts">Conflicts</a></li><li><a href="#grammar">Grammar</a><ul class="lower-alpha"><li><a href="#grammar">Itemset</a></li><li><a href="#terminals">Terminal symbols</a></li><li><a href="#nonterminals">Nonterminal symbols</a></li></ul></li><li><a href="#automaton">Automaton</a></li></ul><h2><a name="reductions" id="reductions"></a> Reductions</h2><h3><a name="nonterminals_useless_in_grammar" id="nonterminals_useless_in_grammar"></a> Nonterminals useless in grammar</h3> + +<h3><a name="terminals_unused_in_grammar" id="terminals_unused_in_grammar"></a> Terminals unused in grammar</h3> + +<h3><a name="rules_useless_in_grammar" id="rules_useless_in_grammar"></a> Rules useless in grammar</h3> +<h2><a name="conflicts" id="conflicts"></a> Conflicts</h2> + +<h2><a name="grammar" id="grammar"></a> Grammar</h2> +<p class="pre"> +<a name="rule_0" id="rule_0"></a> 0 <span class="i">$accept</span> → <span class="i">input</span> <b>$end</b> + +<a name="rule_1" id="rule_1"></a> 1 <span class="i">input</span> → %empty +<a name="rule_2" id="rule_2"></a> 2 | <span class="i">expr</span> + +<a name="rule_3" id="rule_3"></a> 3 <span class="i">expr</span> → <b>NUMBER</b> +<a name="rule_4" id="rule_4"></a> 4 | <b>'('</b> <span class="i">expr</span> <b>')'</b> +<a name="rule_5" id="rule_5"></a> 5 | <span class="i">expr</span> <b>PLUS</b> <span class="i">expr</span> +<a name="rule_6" id="rule_6"></a> 6 | <span class="i">expr</span> <b>MINUS</b> <span class="i">expr</span> +<a name="rule_7" id="rule_7"></a> 7 | <span class="i">expr</span> <b>MULT</b> <span class="i">expr</span> +<a name="rule_8" id="rule_8"></a> 8 | <span class="i">expr</span> <b>DIV</b> <span class="i">expr</span> +</p> + +<h3><a name="terminals" id="terminals"></a> Terminals, with rules where they appear</h3> + +<p class="pre"><b>$end</b> (0) <a href="#rule_0">0</a> +<b>'('</b> (40) <a href="#rule_4">4</a> +<b>')'</b> (41) <a href="#rule_4">4</a> +<b>error</b> (256) +<b>NUMBER</b> (258) <a href="#rule_3">3</a> +<b>PLUS</b> (259) <a href="#rule_5">5</a> +<b>MINUS</b> (260) <a href="#rule_6">6</a> +<b>MULT</b> (261) <a href="#rule_7">7</a> +<b>DIV</b> (262) <a href="#rule_8">8</a> +</p> + +<h3><a name="nonterminals" id="nonterminals"></a> Nonterminals, with rules where they appear</h3> + +<p class="pre"><b>$accept</b> (10) + on left: <a href="#rule_0">0</a> +<b>input</b> (11) + on left: <a href="#rule_1">1</a> <a href="#rule_2">2</a> + on right: <a href="#rule_0">0</a> +<b>expr</b> (12) + on left: <a href="#rule_3">3</a> <a href="#rule_4">4</a> <a href="#rule_5">5</a> <a href="#rule_6">6</a> <a href="#rule_7">7</a> <a href="#rule_8">8</a> + on right: <a href="#rule_2">2</a> <a href="#rule_4">4</a> <a href="#rule_5">5</a> <a href="#rule_6">6</a> <a href="#rule_7">7</a> <a href="#rule_8">8</a> +</p><h2><a name="automaton" id="automaton"></a> Automaton</h2> + +<h3><a name="state_0" id="state_0"></a>state 0</h3> + +<p class="pre"> <a href="#rule_0"> 0</a> <span class="i">$accept</span> → <span class="point">.</span> <span class="i">input</span> <b>$end</b> + <a href="#rule_1"> 1</a> <span class="i">input</span> → <span class="point">.</span> %empty [$end] + <a href="#rule_2"> 2</a> | <span class="point">.</span> <span class="i">expr</span> + <a href="#rule_3"> 3</a> <span class="i">expr</span> → <span class="point">.</span> <b>NUMBER</b> + <a href="#rule_4"> 4</a> | <span class="point">.</span> <b>'('</b> <span class="i">expr</span> <b>')'</b> + <a href="#rule_5"> 5</a> | <span class="point">.</span> <span class="i">expr</span> <b>PLUS</b> <span class="i">expr</span> + <a href="#rule_6"> 6</a> | <span class="point">.</span> <span class="i">expr</span> <b>MINUS</b> <span class="i">expr</span> + <a href="#rule_7"> 7</a> | <span class="point">.</span> <span class="i">expr</span> <b>MULT</b> <span class="i">expr</span> + <a href="#rule_8"> 8</a> | <span class="point">.</span> <span class="i">expr</span> <b>DIV</b> <span class="i">expr</span> + + NUMBER <a href="#state_1">shift, and go to state 1</a> + '(' <a href="#state_2">shift, and go to state 2</a> + + $default <a href="#rule_1">reduce using rule 1</a> (input) + + input <a href="#state_3">go to state 3</a> + expr <a href="#state_4">go to state 4</a> +</p> + +<h3><a name="state_1" id="state_1"></a>state 1</h3> + +<p class="pre"> <a href="#rule_3"> 3</a> <span class="i">expr</span> → <b>NUMBER</b> <span class="point">.</span> + + $default <a href="#rule_3">reduce using rule 3</a> (expr) +</p> + +<h3><a name="state_2" id="state_2"></a>state 2</h3> + +<p class="pre"> <a href="#rule_3"> 3</a> <span class="i">expr</span> → <span class="point">.</span> <b>NUMBER</b> + <a href="#rule_4"> 4</a> | <span class="point">.</span> <b>'('</b> <span class="i">expr</span> <b>')'</b> + <a href="#rule_4"> 4</a> | <b>'('</b> <span class="point">.</span> <span class="i">expr</span> <b>')'</b> + <a href="#rule_5"> 5</a> | <span class="point">.</span> <span class="i">expr</span> <b>PLUS</b> <span class="i">expr</span> + <a href="#rule_6"> 6</a> | <span class="point">.</span> <span class="i">expr</span> <b>MINUS</b> <span class="i">expr</span> + <a href="#rule_7"> 7</a> | <span class="point">.</span> <span class="i">expr</span> <b>MULT</b> <span class="i">expr</span> + <a href="#rule_8"> 8</a> | <span class="point">.</span> <span class="i">expr</span> <b>DIV</b> <span class="i">expr</span> + + NUMBER <a href="#state_1">shift, and go to state 1</a> + '(' <a href="#state_2">shift, and go to state 2</a> + + expr <a href="#state_5">go to state 5</a> +</p> + +<h3><a name="state_3" id="state_3"></a>state 3</h3> + +<p class="pre"> <a href="#rule_0"> 0</a> <span class="i">$accept</span> → <span class="i">input</span> <span class="point">.</span> <b>$end</b> + + $end <a href="#state_6">shift, and go to state 6</a> +</p> + +<h3><a name="state_4" id="state_4"></a>state 4</h3> + +<p class="pre"> <a href="#rule_2"> 2</a> <span class="i">input</span> → <span class="i">expr</span> <span class="point">.</span> [$end] + <a href="#rule_5"> 5</a> <span class="i">expr</span> → <span class="i">expr</span> <span class="point">.</span> <b>PLUS</b> <span class="i">expr</span> + <a href="#rule_6"> 6</a> | <span class="i">expr</span> <span class="point">.</span> <b>MINUS</b> <span class="i">expr</span> + <a href="#rule_7"> 7</a> | <span class="i">expr</span> <span class="point">.</span> <b>MULT</b> <span class="i">expr</span> + <a href="#rule_8"> 8</a> | <span class="i">expr</span> <span class="point">.</span> <b>DIV</b> <span class="i">expr</span> + + PLUS <a href="#state_7">shift, and go to state 7</a> + MINUS <a href="#state_8">shift, and go to state 8</a> + MULT <a href="#state_9">shift, and go to state 9</a> + DIV <a href="#state_10">shift, and go to state 10</a> + + $default <a href="#rule_2">reduce using rule 2</a> (input) +</p> + +<h3><a name="state_5" id="state_5"></a>state 5</h3> + +<p class="pre"> <a href="#rule_4"> 4</a> <span class="i">expr</span> → <b>'('</b> <span class="i">expr</span> <span class="point">.</span> <b>')'</b> + <a href="#rule_5"> 5</a> | <span class="i">expr</span> <span class="point">.</span> <b>PLUS</b> <span class="i">expr</span> + <a href="#rule_6"> 6</a> | <span class="i">expr</span> <span class="point">.</span> <b>MINUS</b> <span class="i">expr</span> + <a href="#rule_7"> 7</a> | <span class="i">expr</span> <span class="point">.</span> <b>MULT</b> <span class="i">expr</span> + <a href="#rule_8"> 8</a> | <span class="i">expr</span> <span class="point">.</span> <b>DIV</b> <span class="i">expr</span> + + PLUS <a href="#state_7">shift, and go to state 7</a> + MINUS <a href="#state_8">shift, and go to state 8</a> + MULT <a href="#state_9">shift, and go to state 9</a> + DIV <a href="#state_10">shift, and go to state 10</a> + ')' <a href="#state_11">shift, and go to state 11</a> +</p> + +<h3><a name="state_6" id="state_6"></a>state 6</h3> + +<p class="pre"> <a href="#rule_0"> 0</a> <span class="i">$accept</span> → <span class="i">input</span> <b>$end</b> <span class="point">.</span> + + $default accept +</p> + +<h3><a name="state_7" id="state_7"></a>state 7</h3> + +<p class="pre"> <a href="#rule_3"> 3</a> <span class="i">expr</span> → <span class="point">.</span> <b>NUMBER</b> + <a href="#rule_4"> 4</a> | <span class="point">.</span> <b>'('</b> <span class="i">expr</span> <b>')'</b> + <a href="#rule_5"> 5</a> | <span class="point">.</span> <span class="i">expr</span> <b>PLUS</b> <span class="i">expr</span> + <a href="#rule_5"> 5</a> | <span class="i">expr</span> <b>PLUS</b> <span class="point">.</span> <span class="i">expr</span> + <a href="#rule_6"> 6</a> | <span class="point">.</span> <span class="i">expr</span> <b>MINUS</b> <span class="i">expr</span> + <a href="#rule_7"> 7</a> | <span class="point">.</span> <span class="i">expr</span> <b>MULT</b> <span class="i">expr</span> + <a href="#rule_8"> 8</a> | <span class="point">.</span> <span class="i">expr</span> <b>DIV</b> <span class="i">expr</span> + + NUMBER <a href="#state_1">shift, and go to state 1</a> + '(' <a href="#state_2">shift, and go to state 2</a> + + expr <a href="#state_12">go to state 12</a> +</p> + +<h3><a name="state_8" id="state_8"></a>state 8</h3> + +<p class="pre"> <a href="#rule_3"> 3</a> <span class="i">expr</span> → <span class="point">.</span> <b>NUMBER</b> + <a href="#rule_4"> 4</a> | <span class="point">.</span> <b>'('</b> <span class="i">expr</span> <b>')'</b> + <a href="#rule_5"> 5</a> | <span class="point">.</span> <span class="i">expr</span> <b>PLUS</b> <span class="i">expr</span> + <a href="#rule_6"> 6</a> | <span class="point">.</span> <span class="i">expr</span> <b>MINUS</b> <span class="i">expr</span> + <a href="#rule_6"> 6</a> | <span class="i">expr</span> <b>MINUS</b> <span class="point">.</span> <span class="i">expr</span> + <a href="#rule_7"> 7</a> | <span class="point">.</span> <span class="i">expr</span> <b>MULT</b> <span class="i">expr</span> + <a href="#rule_8"> 8</a> | <span class="point">.</span> <span class="i">expr</span> <b>DIV</b> <span class="i">expr</span> + + NUMBER <a href="#state_1">shift, and go to state 1</a> + '(' <a href="#state_2">shift, and go to state 2</a> + + expr <a href="#state_13">go to state 13</a> +</p> + +<h3><a name="state_9" id="state_9"></a>state 9</h3> + +<p class="pre"> <a href="#rule_3"> 3</a> <span class="i">expr</span> → <span class="point">.</span> <b>NUMBER</b> + <a href="#rule_4"> 4</a> | <span class="point">.</span> <b>'('</b> <span class="i">expr</span> <b>')'</b> + <a href="#rule_5"> 5</a> | <span class="point">.</span> <span class="i">expr</span> <b>PLUS</b> <span class="i">expr</span> + <a href="#rule_6"> 6</a> | <span class="point">.</span> <span class="i">expr</span> <b>MINUS</b> <span class="i">expr</span> + <a href="#rule_7"> 7</a> | <span class="point">.</span> <span class="i">expr</span> <b>MULT</b> <span class="i">expr</span> + <a href="#rule_7"> 7</a> | <span class="i">expr</span> <b>MULT</b> <span class="point">.</span> <span class="i">expr</span> + <a href="#rule_8"> 8</a> | <span class="point">.</span> <span class="i">expr</span> <b>DIV</b> <span class="i">expr</span> + + NUMBER <a href="#state_1">shift, and go to state 1</a> + '(' <a href="#state_2">shift, and go to state 2</a> + + expr <a href="#state_14">go to state 14</a> +</p> + +<h3><a name="state_10" id="state_10"></a>state 10</h3> + +<p class="pre"> <a href="#rule_3"> 3</a> <span class="i">expr</span> → <span class="point">.</span> <b>NUMBER</b> + <a href="#rule_4"> 4</a> | <span class="point">.</span> <b>'('</b> <span class="i">expr</span> <b>')'</b> + <a href="#rule_5"> 5</a> | <span class="point">.</span> <span class="i">expr</span> <b>PLUS</b> <span class="i">expr</span> + <a href="#rule_6"> 6</a> | <span class="point">.</span> <span class="i">expr</span> <b>MINUS</b> <span class="i">expr</span> + <a href="#rule_7"> 7</a> | <span class="point">.</span> <span class="i">expr</span> <b>MULT</b> <span class="i">expr</span> + <a href="#rule_8"> 8</a> | <span class="point">.</span> <span class="i">expr</span> <b>DIV</b> <span class="i">expr</span> + <a href="#rule_8"> 8</a> | <span class="i">expr</span> <b>DIV</b> <span class="point">.</span> <span class="i">expr</span> + + NUMBER <a href="#state_1">shift, and go to state 1</a> + '(' <a href="#state_2">shift, and go to state 2</a> + + expr <a href="#state_15">go to state 15</a> +</p> + +<h3><a name="state_11" id="state_11"></a>state 11</h3> + +<p class="pre"> <a href="#rule_4"> 4</a> <span class="i">expr</span> → <b>'('</b> <span class="i">expr</span> <b>')'</b> <span class="point">.</span> + + $default <a href="#rule_4">reduce using rule 4</a> (expr) +</p> + +<h3><a name="state_12" id="state_12"></a>state 12</h3> + +<p class="pre"> <a href="#rule_5"> 5</a> <span class="i">expr</span> → <span class="i">expr</span> <span class="point">.</span> <b>PLUS</b> <span class="i">expr</span> + <a href="#rule_5"> 5</a> | <span class="i">expr</span> <b>PLUS</b> <span class="i">expr</span> <span class="point">.</span> [$end, PLUS, MINUS, ')'] + <a href="#rule_6"> 6</a> | <span class="i">expr</span> <span class="point">.</span> <b>MINUS</b> <span class="i">expr</span> + <a href="#rule_7"> 7</a> | <span class="i">expr</span> <span class="point">.</span> <b>MULT</b> <span class="i">expr</span> + <a href="#rule_8"> 8</a> | <span class="i">expr</span> <span class="point">.</span> <b>DIV</b> <span class="i">expr</span> + + MULT <a href="#state_9">shift, and go to state 9</a> + DIV <a href="#state_10">shift, and go to state 10</a> + + $default <a href="#rule_5">reduce using rule 5</a> (expr) + + Conflict between <a href="#rule_5">rule 5</a> and token PLUS resolved as reduce (%left PLUS). + Conflict between <a href="#rule_5">rule 5</a> and token MINUS resolved as reduce (%left MINUS). + Conflict between <a href="#rule_5">rule 5</a> and token MULT resolved as shift (PLUS < MULT). + Conflict between <a href="#rule_5">rule 5</a> and token DIV resolved as shift (PLUS < DIV). +</p> + +<h3><a name="state_13" id="state_13"></a>state 13</h3> + +<p class="pre"> <a href="#rule_5"> 5</a> <span class="i">expr</span> → <span class="i">expr</span> <span class="point">.</span> <b>PLUS</b> <span class="i">expr</span> + <a href="#rule_6"> 6</a> | <span class="i">expr</span> <span class="point">.</span> <b>MINUS</b> <span class="i">expr</span> + <a href="#rule_6"> 6</a> | <span class="i">expr</span> <b>MINUS</b> <span class="i">expr</span> <span class="point">.</span> [$end, PLUS, MINUS, ')'] + <a href="#rule_7"> 7</a> | <span class="i">expr</span> <span class="point">.</span> <b>MULT</b> <span class="i">expr</span> + <a href="#rule_8"> 8</a> | <span class="i">expr</span> <span class="point">.</span> <b>DIV</b> <span class="i">expr</span> + + MULT <a href="#state_9">shift, and go to state 9</a> + DIV <a href="#state_10">shift, and go to state 10</a> + + $default <a href="#rule_6">reduce using rule 6</a> (expr) + + Conflict between <a href="#rule_6">rule 6</a> and token PLUS resolved as reduce (%left PLUS). + Conflict between <a href="#rule_6">rule 6</a> and token MINUS resolved as reduce (%left MINUS). + Conflict between <a href="#rule_6">rule 6</a> and token MULT resolved as shift (MINUS < MULT). + Conflict between <a href="#rule_6">rule 6</a> and token DIV resolved as shift (MINUS < DIV). +</p> + +<h3><a name="state_14" id="state_14"></a>state 14</h3> + +<p class="pre"> <a href="#rule_5"> 5</a> <span class="i">expr</span> → <span class="i">expr</span> <span class="point">.</span> <b>PLUS</b> <span class="i">expr</span> + <a href="#rule_6"> 6</a> | <span class="i">expr</span> <span class="point">.</span> <b>MINUS</b> <span class="i">expr</span> + <a href="#rule_7"> 7</a> | <span class="i">expr</span> <span class="point">.</span> <b>MULT</b> <span class="i">expr</span> + <a href="#rule_7"> 7</a> | <span class="i">expr</span> <b>MULT</b> <span class="i">expr</span> <span class="point">.</span> [$end, PLUS, MINUS, MULT, DIV, ')'] + <a href="#rule_8"> 8</a> | <span class="i">expr</span> <span class="point">.</span> <b>DIV</b> <span class="i">expr</span> + + $default <a href="#rule_7">reduce using rule 7</a> (expr) + + Conflict between <a href="#rule_7">rule 7</a> and token PLUS resolved as reduce (PLUS < MULT). + Conflict between <a href="#rule_7">rule 7</a> and token MINUS resolved as reduce (MINUS < MULT). + Conflict between <a href="#rule_7">rule 7</a> and token MULT resolved as reduce (%left MULT). + Conflict between <a href="#rule_7">rule 7</a> and token DIV resolved as reduce (%left DIV). +</p> + +<h3><a name="state_15" id="state_15"></a>state 15</h3> + +<p class="pre"> <a href="#rule_5"> 5</a> <span class="i">expr</span> → <span class="i">expr</span> <span class="point">.</span> <b>PLUS</b> <span class="i">expr</span> + <a href="#rule_6"> 6</a> | <span class="i">expr</span> <span class="point">.</span> <b>MINUS</b> <span class="i">expr</span> + <a href="#rule_7"> 7</a> | <span class="i">expr</span> <span class="point">.</span> <b>MULT</b> <span class="i">expr</span> + <a href="#rule_8"> 8</a> | <span class="i">expr</span> <span class="point">.</span> <b>DIV</b> <span class="i">expr</span> + <a href="#rule_8"> 8</a> | <span class="i">expr</span> <b>DIV</b> <span class="i">expr</span> <span class="point">.</span> [$end, PLUS, MINUS, MULT, DIV, ')'] + + $default <a href="#rule_8">reduce using rule 8</a> (expr) + + Conflict between <a href="#rule_8">rule 8</a> and token PLUS resolved as reduce (PLUS < DIV). + Conflict between <a href="#rule_8">rule 8</a> and token MINUS resolved as reduce (MINUS < DIV). + Conflict between <a href="#rule_8">rule 8</a> and token MULT resolved as reduce (%left MULT). + Conflict between <a href="#rule_8">rule 8</a> and token DIV resolved as reduce (%left DIV). +</p> + +<div id="footer"><hr />This document was generated using + <a href="http://www.gnu.org/software/bison/" title="GNU Bison"> + GNU Bison 3.0.4</a> + XML Automaton Report.<br /> + Verbatim copying and distribution of this entire page is + permitted in any medium, provided this notice is preserved.</div></body> +</html> |
