From 29def92f2ddbfca64ba827f116172fe98b2df491 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Tue, 26 Sep 2023 17:43:36 +0100 Subject: Chapter 2 (#4) * Start on Chapter 2. * Start on Chapter 2. * Refactor * Refactor * Initial attempt at peephole opt for add operation * cleanup unused import * Start on graph visualizer * Start on graph visualizer * Rework chapter 2 Add a short discourse on the Types, and provide a Bottom type. Make a final toString; require each Node to specify its special printing via label(). Add a recursing printer called print(); toString is used by default in the debugger and so cannot be recursive. Make the peephole rules based on a proper Type and idealize calls. Big comments about the Type computations. Every node picks up a _print, compute and idealize() call. Rename long arith ops Divide, UnaryMinus, Multiply, Subtract into shorter uniform-length names. Cleans up the parser where he does the precedence op parsing. Rework Parser: - Drop Token class, its all Strings except in the one place we know a number is coming - Embed the Lexer as a field in the Parser, instead of trying to pass it around everywhere in the Parser - StartNode becomes a read-only global, so we don't have to pass it around everywhere in the Parser AND optimizer. - Lexer matches on strings and returns strings. Match and consume *at the moment* instead of carrying around a current token/string and forcing the next-token after consuming the current one. - All parse subexpressions shrink by 1/2 after these changes. * Initial writeup of Chapter 2 * Initial writeup of Chapter 2 * Initial writeup of Chapter 2 * Initial writeup of Chapter 2 * Remove range * progress Chapter 2 Drop integer ranges. Broader lattice pic. Lots of prose changes in the readme. Fixed title in gviz dot generation. Fixed bug with peephole making redundant constants. * Implement compute for all the arithmetic node types Add a flag to switch off peephole so we can see the full graph Add post peephole graph to writeup * Implement compute for all the arithmetic node types Add a flag to switch off peephole so we can see the full graph Add post peephole graph to writeup * Fix bad path to the svg * Update pre-peephole diagram * Add dead code elimination ...and a set_def to proper update graph edges. * Update README.md * Cleanup the GraphVisualizer a bit. Update the graphs. Update the chapter list as chapter 3 deleted, and chapter 4 is now chapter 3. --------- Co-authored-by: Cliff Click --- chapter01/README.md | 2 +- chapter01/docs/01-grammar.md | 1 + chapter01/docs/01-graph.gv | 9 +++ chapter01/docs/01-graph.svg | 43 +++++++++++++ chapter01/docs/02-graph.gv | 9 --- chapter01/docs/02-graph.svg | 43 ------------- .../main/java/com/seaofnodes/simple/Parser.java | 4 +- .../java/com/seaofnodes/simple/Chapter01Test.java | 72 ++++++++++++++++++++++ .../java/com/seaofnodes/simple/ParserTest.java | 72 ---------------------- 9 files changed, 128 insertions(+), 127 deletions(-) create mode 100644 chapter01/docs/01-graph.gv create mode 100644 chapter01/docs/01-graph.svg delete mode 100644 chapter01/docs/02-graph.gv delete mode 100644 chapter01/docs/02-graph.svg create mode 100644 chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java delete mode 100644 chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java (limited to 'chapter01') diff --git a/chapter01/README.md b/chapter01/README.md index f3231d8c..57caa801 100644 --- a/chapter01/README.md +++ b/chapter01/README.md @@ -113,7 +113,7 @@ Here is visualization of the program: return 1; ``` -![Sea of Nodes Visual](./docs/02-graph.svg) +![Sea of Nodes Visual](./docs/01-graph.svg) * Control nodes appear as square boxes * Control edges are in bold red diff --git a/chapter01/docs/01-grammar.md b/chapter01/docs/01-grammar.md index cf947dfc..5d9f3cf7 100644 --- a/chapter01/docs/01-grammar.md +++ b/chapter01/docs/01-grammar.md @@ -21,5 +21,6 @@ primaryExpression INTEGER_LITERAL : [1-9][0-9]* + | [0] ; ``` \ No newline at end of file diff --git a/chapter01/docs/01-graph.gv b/chapter01/docs/01-graph.gv new file mode 100644 index 00000000..40181544 --- /dev/null +++ b/chapter01/docs/01-graph.gv @@ -0,0 +1,9 @@ +digraph chapter01 +{ + start [shape=box, label="Start"]; + constant [label="Constant 1"]; + return [shape=box, label="Return"]; + constant -> return; + edge [color=red]; + start -> return [style=bold]; +} \ No newline at end of file diff --git a/chapter01/docs/01-graph.svg b/chapter01/docs/01-graph.svg new file mode 100644 index 00000000..fbf92d7d --- /dev/null +++ b/chapter01/docs/01-graph.svg @@ -0,0 +1,43 @@ + + + + + + +chapter01 + + + +start + +Start + + + +return + +Return + + + +start->return + + + + + +constant + +Constant 1 + + + +constant->return + + + + + diff --git a/chapter01/docs/02-graph.gv b/chapter01/docs/02-graph.gv deleted file mode 100644 index 40181544..00000000 --- a/chapter01/docs/02-graph.gv +++ /dev/null @@ -1,9 +0,0 @@ -digraph chapter01 -{ - start [shape=box, label="Start"]; - constant [label="Constant 1"]; - return [shape=box, label="Return"]; - constant -> return; - edge [color=red]; - start -> return [style=bold]; -} \ No newline at end of file diff --git a/chapter01/docs/02-graph.svg b/chapter01/docs/02-graph.svg deleted file mode 100644 index fbf92d7d..00000000 --- a/chapter01/docs/02-graph.svg +++ /dev/null @@ -1,43 +0,0 @@ - - - - - - -chapter01 - - - -start - -Start - - - -return - -Return - - - -start->return - - - - - -constant - -Constant 1 - - - -constant->return - - - - - diff --git a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java index 8fb1ebaf..cdfff842 100644 --- a/chapter01/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter01/src/main/java/com/seaofnodes/simple/Parser.java @@ -80,7 +80,7 @@ public class Parser { * Parse integer literal * * 
-     *     integerLiteral: [1-9][0-9]*
+     *     integerLiteral: [1-9][0-9]* | [0]
      *
*/ private ConstantNode parseIntegerLiteral(Lexer lexer) { @@ -245,7 +245,7 @@ public class Parser { private Token parsePuncuation() { int start = _position-1; - while( isPunctuation(nextChar()) ); + if( isPunctuation(nextChar()) ); return Token.newPunct(new String(_input,start,--_position-start)); } diff --git a/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java new file mode 100644 index 00000000..14c22437 --- /dev/null +++ b/chapter01/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -0,0 +1,72 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import org.junit.Test; +import static org.junit.Assert.*; + +public class Chapter01Test { + + @Test + public void testSimpleProgram() { + Parser parser = new Parser(); + StartNode startNode = parser.parse("return 1;"); + assertNotNull(startNode); + assertEquals(2, startNode.nOuts()); + for (int i = 0; i < startNode.nOuts(); i++) { + switch( startNode.out(i) ) { + case ReturnNode ret: + assertEquals(2, ret.nIns()); + assertEquals(startNode, ret.in(0)); + assertTrue(ret.in(1) instanceof ConstantNode); + break; + case ConstantNode con: + assertEquals(1, con._value); + assertEquals(1, con.nIns()); + assertEquals(startNode, con.in(0)); + break; + default: + throw new IllegalStateException(); + } + } + } + + @Test + public void testZero() { + Parser parser = new Parser(); + StartNode start = parser.parse("return 0;"); + for( Node use : start._outputs ) + if( use instanceof ConstantNode con ) + assertEquals(0,con._value); + } + + @Test + public void testBad1() { + try { new Parser().parse("ret"); } + catch( RuntimeException e ) { assertEquals("syntax error, expected return: ret",e.getMessage()); } + } + + @Test + public void testBad2() { + try { new Parser().parse("return 0123;"); } + catch( RuntimeException e ) { assertEquals("syntax error: integer values cannot start with '0'",e.getMessage()); } + } + + @Test + public void testBad3() { + try { new Parser().parse("return --12;"); } + catch( RuntimeException e ) { assertEquals("syntax error, expected integer literal: -",e.getMessage()); } + } + + @Test + public void testBad4() { + try { new Parser().parse("return 100"); } + catch( RuntimeException e ) { assertTrue(e.getMessage().contains("syntax error, expected ; got :")); } + } + + // Negative numbers require unary operator support that is not in scope + @Test + public void testBad5() { + try { new Parser().parse("return -100;"); } + catch( RuntimeException e ) { assertEquals("syntax error, expected integer literal: -", e.getMessage()); } + } +} diff --git a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java b/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java deleted file mode 100644 index 887f63b8..00000000 --- a/chapter01/src/test/java/com/seaofnodes/simple/ParserTest.java +++ /dev/null @@ -1,72 +0,0 @@ -package com.seaofnodes.simple; - -import com.seaofnodes.simple.node.*; -import org.junit.Test; -import static org.junit.Assert.*; - -public class ParserTest { - - @Test - public void testSimpleProgram() { - Parser parser = new Parser(); - StartNode startNode = parser.parse("return 1;"); - assertNotNull(startNode); - assertEquals(2, startNode.nOuts()); - for (int i = 0; i < startNode.nOuts(); i++) { - switch( startNode.out(i) ) { - case ReturnNode ret: - assertEquals(2, ret.nIns()); - assertEquals(startNode, ret.in(0)); - assertTrue(ret.in(1) instanceof ConstantNode); - break; - case ConstantNode con: - assertEquals(1, con._value); - assertEquals(1, con.nIns()); - assertEquals(startNode, con.in(0)); - break; - default: - throw new IllegalStateException(); - } - } - } - - @Test - public void testZero() { - Parser parser = new Parser(); - StartNode start = parser.parse("return 0;"); - for( Node use : start._outputs ) - if( use instanceof ConstantNode con ) - assertEquals(0,con._value); - } - - @Test - public void testBad1() { - try { new Parser().parse("ret"); } - catch( RuntimeException e ) { assertEquals("syntax error, expected return: ret",e.getMessage()); } - } - - @Test - public void testBad2() { - try { new Parser().parse("return 0123;"); } - catch( RuntimeException e ) { assertEquals("syntax error: integer values cannot start with '0'",e.getMessage()); } - } - - @Test - public void testBad3() { - try { new Parser().parse("return --12;"); } - catch( RuntimeException e ) { assertEquals("syntax error, expected integer literal: --",e.getMessage()); } - } - - @Test - public void testBad4() { - try { new Parser().parse("return 100"); } - catch( RuntimeException e ) { assertTrue(e.getMessage().contains("syntax error, expected ; got :")); } - } - - // Negative numbers require unary operator support that is not in scope - @Test - public void testBad5() { - try { new Parser().parse("return -100;"); } - catch( RuntimeException e ) { assertEquals("syntax error, expected integer literal: -", e.getMessage()); } - } -} -- cgit v1.2.3