Last active
November 13, 2022 18:33
-
-
Save bobbicodes/7727f4100cb16fa354588f8c748fc7cb to your computer and use it in GitHub Desktop.
Transcript: Mark Engelberg - Instaparse
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| [[{"text": "good morning I'm mark Engelbert welcome", "start": 0.03, "duration": 4.88}, {"text": "to closure West it's exciting to be here", "start": 2.28, "duration": 6.06}, {"text": "it's the first talk of the first morning", "start": 4.91, "duration": 5.71}, {"text": "and I feel like I should be hijacking", "start": 8.34, "duration": 4.29}, {"text": "this time slot to give a keynote and set", "start": 10.62, "duration": 4.13}, {"text": "the future of closures something but", "start": 12.63, "duration": 6.409}, {"text": "we're here to talk about insta parse", "start": 14.75, "duration": 4.289}, {"text": "let's begin with a little warm-up it's", "start": 19.91, "duration": 4.51}, {"text": "the morning get to get the brains going", "start": 22.65, "duration": 8.039}, {"text": "so what's this any it's a map it's a map", "start": 24.42, "duration": 9.6}, {"text": "its closure data right this is the Eden", "start": 30.689, "duration": 5.911}, {"text": "format we all know and love and one of", "start": 34.02, "duration": 4.35}, {"text": "the beautiful things about closer for", "start": 36.6, "duration": 3.36}, {"text": "those of you who are here trying out", "start": 38.37, "duration": 5.13}, {"text": "closure you know relatively recently one", "start": 39.96, "duration": 4.829}, {"text": "of the things in my opinion that is the", "start": 43.5, "duration": 2.82}, {"text": "most exciting thing about closure it", "start": 44.789, "duration": 4.321}, {"text": "gives us these great lightweight ways to", "start": 46.32, "duration": 6.21}, {"text": "express data to model our data and it", "start": 49.11, "duration": 6.629}, {"text": "gives us a huge toolkit for manipulating", "start": 52.53, "duration": 6.09}, {"text": "that data so once we can get things in", "start": 55.739, "duration": 5.061}, {"text": "this form we're really really happy", "start": 58.62, "duration": 7.98}, {"text": "now what's this yeah it's just a string", "start": 60.8, "duration": 8.02}, {"text": "it's got the same information in there", "start": 66.6, "duration": 3.66}, {"text": "but we can't really do anything with it", "start": 68.82, "duration": 4.32}, {"text": "yet right the good news is that built", "start": 70.26, "duration": 4.5}, {"text": "right into closure in the closure", "start": 73.14, "duration": 3.96}, {"text": "edan namespace is the read string", "start": 74.76, "duration": 4.44}, {"text": "function and if we apply the function to", "start": 77.1, "duration": 5.519}, {"text": "this string we get back that map that we", "start": 79.2, "duration": 5.37}, {"text": "can actually work with and that's also", "start": 82.619, "duration": 3.451}, {"text": "another really wonderful thing about", "start": 84.57, "duration": 4.14}, {"text": "closure is how easy it is to write out", "start": 86.07, "duration": 4.77}, {"text": "and read back in this kind of data we", "start": 88.71, "duration": 7.159}, {"text": "like working with okay how about this", "start": 90.84, "duration": 5.029}, {"text": "anyone recognize this yeah this is a", "start": 96.229, "duration": 7.6}, {"text": "JSON that's been read in as a string and", "start": 100.729, "duration": 5.82}, {"text": "we can't really work with it just yet", "start": 103.829, "duration": 5.82}, {"text": "but we have this function in the closure", "start": 106.549, "duration": 7.0}, {"text": "data Jason's namespace read stir that", "start": 109.649, "duration": 6.15}, {"text": "lets us read this in and get that", "start": 113.549, "duration": 6.091}, {"text": "closure map we want to work with how", "start": 115.799, "duration": 7.041}, {"text": "about this this one's a little trickier", "start": 119.64, "duration": 5.7}, {"text": "yeah exactly this is what you get if you", "start": 122.84, "duration": 7.479}, {"text": "slurp in a CSV file now we have a way to", "start": 125.34, "duration": 7.02}, {"text": "read in CSV files but notice you don't", "start": 130.319, "duration": 2.791}, {"text": "get a", "start": 132.36, "duration": 2.88}, {"text": "exactly what you want because it reads", "start": 133.11, "duration": 4.26}, {"text": "in that first row which was meant to be", "start": 135.24, "duration": 4.23}, {"text": "header information sort of as its own", "start": 137.37, "duration": 4.59}, {"text": "row so maybe this isn't exactly what you", "start": 139.47, "duration": 5.58}, {"text": "want but it's at least a good start", "start": 141.96, "duration": 5.49}, {"text": "right once we get this into our closure", "start": 145.05, "duration": 5.91}, {"text": "format we have ways of working with it", "start": 147.45, "duration": 6.48}, {"text": "massaging it into the map format we're", "start": 150.96, "duration": 6.75}, {"text": "looking for and this everyone knows this", "start": 153.93, "duration": 9.93}, {"text": "right so this is XML read in as a string", "start": 157.71, "duration": 9.9}, {"text": "and again we have a way to bring it into", "start": 163.86, "duration": 6.27}, {"text": "closure and work with it what we get", "start": 167.61, "duration": 4.62}, {"text": "back is some sort of generic tree", "start": 170.13, "duration": 4.77}, {"text": "structure that then we can work with and", "start": 172.23, "duration": 6.03}, {"text": "further refine it into what we want now", "start": 174.9, "duration": 6.059}, {"text": "the good news is that most of the time", "start": 178.26, "duration": 4.229}, {"text": "we're working with one of these standard", "start": 180.959, "duration": 3.631}, {"text": "formats we're working with Eden", "start": 182.489, "duration": 6.841}, {"text": "hopefully or possibly JSON CSV XML you", "start": 184.59, "duration": 6.84}, {"text": "know I mean what at least 90 percent of", "start": 189.33, "duration": 4.17}, {"text": "the time but these are not the only", "start": 191.43, "duration": 4.49}, {"text": "things you're gonna encounter", "start": 193.5, "duration": 4.56}, {"text": "what if someone gives you a file that", "start": 195.92, "duration": 5.95}, {"text": "looks like this I mean who would who on", "start": 198.06, "duration": 5.82}, {"text": "earth would represent a map this way", "start": 201.87, "duration": 4.92}, {"text": "that that's kind of a dig I guess but", "start": 203.88, "duration": 4.62}, {"text": "the I mean this is this is how Scala", "start": 206.79, "duration": 3.75}, {"text": "represents maps and and the point is", "start": 208.5, "duration": 3.989}, {"text": "that different communities represent", "start": 210.54, "duration": 5.699}, {"text": "their Maps differently or what if", "start": 212.489, "duration": 7.321}, {"text": "someone hands you a bunch of cave data", "start": 216.239, "duration": 6.75}, {"text": "in some kind of unusual exotic format", "start": 219.81, "duration": 5.07}, {"text": "that you know kind of looks almost like", "start": 222.989, "duration": 4.321}, {"text": "JSON if you look at it funny but it's", "start": 224.88, "duration": 6.96}, {"text": "not quite JSON or what if you want to", "start": 227.31, "duration": 7.29}, {"text": "work with you know like a Python config", "start": 231.84, "duration": 7.32}, {"text": "file or what if you want to make your", "start": 234.6, "duration": 7.23}, {"text": "own programming language or your own DSL", "start": 239.16, "duration": 4.44}, {"text": "for something all of these are things", "start": 241.83, "duration": 5.58}, {"text": "that you want to as quickly as possible", "start": 243.6, "duration": 6.21}, {"text": "get them into your closure Eden format", "start": 247.41, "duration": 4.23}, {"text": "so that you can work with them and do", "start": 249.81, "duration": 6.6}, {"text": "things with them and those last three", "start": 251.64, "duration": 6.689}, {"text": "examples by the way are all problems", "start": 256.41, "duration": 4.56}, {"text": "that were solved by actual users in the", "start": 258.329, "duration": 4.681}, {"text": "closure community with the insta parse", "start": 260.97, "duration": 4.98}, {"text": "library so now is the opportunity to", "start": 263.01, "duration": 3.51}, {"text": "kind of say", "start": 265.95, "duration": 2.48}, {"text": "way and start talking about insta parse", "start": 266.52, "duration": 4.41}, {"text": "but first I want to outline a couple key", "start": 268.43, "duration": 5.199}, {"text": "concepts so for the purposes of this", "start": 270.93, "duration": 6.769}, {"text": "talk I'm defining a parser to be a", "start": 273.629, "duration": 6.931}, {"text": "function that takes a string as an input", "start": 277.699, "duration": 7.18}, {"text": "and produces closure data as an output", "start": 280.56, "duration": 6.69}, {"text": "so all those things we saw before the", "start": 284.879, "duration": 5.341}, {"text": "you know the read XML Strunk ssin the", "start": 287.25, "duration": 5.099}, {"text": "read CSV function those are all examples", "start": 290.22, "duration": 7.14}, {"text": "of parsers and the idea is we want to be", "start": 292.349, "duration": 7.47}, {"text": "able to create parsers for these other", "start": 297.36, "duration": 7.41}, {"text": "kinds of formats well to understand how", "start": 299.819, "duration": 6.871}, {"text": "to create a parser first we need to ask", "start": 304.77, "duration": 3.84}, {"text": "the question how do we describe the", "start": 306.69, "duration": 5.969}, {"text": "structure of data well we can take a cue", "start": 308.61, "duration": 7.04}, {"text": "from automata theory in computer science", "start": 312.659, "duration": 5.401}, {"text": "automata theory describes two very", "start": 315.65, "duration": 5.859}, {"text": "important classes of data there's the", "start": 318.06, "duration": 5.07}, {"text": "kind of data that can be represented", "start": 321.509, "duration": 3.84}, {"text": "with regular expressions and those", "start": 323.13, "duration": 4.74}, {"text": "happen to correspond to data that can be", "start": 325.349, "duration": 5.97}, {"text": "processed with a state machine and then", "start": 327.87, "duration": 6.72}, {"text": "we also have this wonderful this", "start": 331.319, "duration": 5.511}, {"text": "wonderful language for expressing", "start": 334.59, "duration": 5.1}, {"text": "context-free grammars which is another", "start": 336.83, "duration": 5.199}, {"text": "class of which describes another class", "start": 339.69, "duration": 4.379}, {"text": "of data that can be processed with", "start": 342.029, "duration": 5.75}, {"text": "something called a pushdown automaton", "start": 344.069, "duration": 3.71}, {"text": "now the good news is that we have great", "start": 348.139, "duration": 5.77}, {"text": "support for regular expressions built in", "start": 351.81, "duration": 5.699}, {"text": "just about every modern language however", "start": 353.909, "duration": 6.87}, {"text": "there's many kinds of data that cannot", "start": 357.509, "duration": 5.16}, {"text": "be expressed well with a regular", "start": 360.779, "duration": 4.741}, {"text": "expression but can be expressed with a", "start": 362.669, "duration": 5.011}, {"text": "context-free grammar and unfortunately", "start": 365.52, "duration": 4.11}, {"text": "we don't have very good support in our", "start": 367.68, "duration": 4.829}, {"text": "languages for context-free grammars at", "start": 369.63, "duration": 4.649}, {"text": "least not that same kind of rich support", "start": 372.509, "duration": 4.951}, {"text": "that we have for regular expressions and", "start": 374.279, "duration": 6.5}, {"text": "I think that's kind of a shame because", "start": 377.46, "duration": 6.81}, {"text": "when a context-free grammar describes", "start": 380.779, "duration": 6.551}, {"text": "your data it automatically is also", "start": 384.27, "duration": 6.75}, {"text": "describing a tree structure that is in", "start": 387.33, "duration": 6.089}, {"text": "that data and that's called the", "start": 391.02, "duration": 4.56}, {"text": "derivation tree I literally walked over", "start": 393.419, "duration": 5.37}, {"text": "to my shelf for this slide and I pulled", "start": 395.58, "duration": 4.56}, {"text": "off the automaton", "start": 398.789, "duration": 3.931}, {"text": "book off the shelf flipped it open and", "start": 400.14, "duration": 4.74}, {"text": "open it up to the first context-free", "start": 402.72, "duration": 6.27}, {"text": "grammar I saw and copied it down and", "start": 404.88, "duration": 6.33}, {"text": "then in the book there is a picture of", "start": 408.99, "duration": 4.8}, {"text": "the derivation tree for that grammar for", "start": 411.21, "duration": 5.88}, {"text": "that particular string a a VBA a so you", "start": 413.79, "duration": 6.96}, {"text": "the how many of you have never seen a", "start": 417.09, "duration": 6.45}, {"text": "context-free grammar before it's okay so", "start": 420.75, "duration": 5.25}, {"text": "you know not not everybody's seen it but", "start": 423.54, "duration": 4.65}, {"text": "the basic idea is it's a series of rules", "start": 426.0, "duration": 5.22}, {"text": "and usually the implication is that the", "start": 428.19, "duration": 5.49}, {"text": "first rule is kind of your starting", "start": 431.22, "duration": 5.1}, {"text": "point so we have this label s and the", "start": 433.68, "duration": 4.35}, {"text": "first thing is a rule saying you know s", "start": 436.32, "duration": 4.59}, {"text": "is a and then the description on the", "start": 438.03, "duration": 5.76}, {"text": "other side and the vertical bar means or", "start": 440.91, "duration": 5.25}, {"text": "and the other things well I'll get into", "start": 443.79, "duration": 4.68}, {"text": "that a little bit so we've got two rules", "start": 446.16, "duration": 6.06}, {"text": "here and we see the tree structure of", "start": 448.47, "duration": 5.7}, {"text": "how you can sort of prove that this", "start": 452.22, "duration": 6.9}, {"text": "grammar fits that string now that", "start": 454.17, "duration": 7.32}, {"text": "example was just this kind of arbitrary", "start": 459.12, "duration": 6.03}, {"text": "you know a textbook example of a a B ba", "start": 461.49, "duration": 5.13}, {"text": "now that's not the kind of data we", "start": 465.15, "duration": 3.06}, {"text": "really work with right so I want to at", "start": 466.62, "duration": 3.12}, {"text": "least convince you that grammars are", "start": 468.21, "duration": 3.69}, {"text": "used in the real world to describe", "start": 469.74, "duration": 5.25}, {"text": "actual data this is from a specification", "start": 471.9, "duration": 5.85}, {"text": "for email addresses I mean who knew that", "start": 474.99, "duration": 4.62}, {"text": "email addresses were that complicated", "start": 477.75, "duration": 4.77}, {"text": "right but it took a couple people yes", "start": 479.61, "duration": 5.16}, {"text": "really annoying to validate it email", "start": 482.52, "duration": 4.35}, {"text": "addresses because it turns out that the", "start": 484.77, "duration": 4.59}, {"text": "universe of allowed email addresses is", "start": 486.87, "duration": 4.32}, {"text": "much broader than what you would think", "start": 489.36, "duration": 5.04}, {"text": "and to capture all those nuances really", "start": 491.19, "duration": 4.77}, {"text": "requires you know it's not something", "start": 494.4, "duration": 3.12}, {"text": "that can be described adequately with", "start": 495.96, "duration": 3.51}, {"text": "just regular expressions you need a", "start": 497.52, "duration": 5.9}, {"text": "context-free grammar to describe that", "start": 499.47, "duration": 3.95}, {"text": "okay so now we're ready to get into what", "start": 503.66, "duration": 7.81}, {"text": "is insta parse specifically and I like", "start": 507.0, "duration": 8.31}, {"text": "to think of insta parse as a really", "start": 511.47, "duration": 6.3}, {"text": "lightweight tool for converting", "start": 515.31, "duration": 6.21}, {"text": "context-free grammars into an executable", "start": 517.77, "duration": 5.94}, {"text": "parser one of these functions that will", "start": 521.52, "duration": 5.58}, {"text": "let you convert a string into a tree", "start": 523.71, "duration": 4.86}, {"text": "structure that you can work with in", "start": 527.1, "duration": 3.71}, {"text": "closure", "start": 528.57, "duration": 2.24}, {"text": "so going back to that example that I", "start": 531.009, "duration": 5.32}, {"text": "pulled from the automaton book on my", "start": 533.69, "duration": 7.98}, {"text": "shelf on the upper right corner you can", "start": 536.329, "duration": 9.18}, {"text": "see what I did is I actually just typed", "start": 541.67, "duration": 6.659}, {"text": "the context-free grammar into insta", "start": 545.509, "duration": 5.101}, {"text": "parse fed it to this function in the", "start": 548.329, "duration": 4.801}, {"text": "insta parse neck core namespace which I", "start": 550.61, "duration": 5.52}, {"text": "have aliased here is insta so there's a", "start": 553.13, "duration": 4.709}, {"text": "function they're called parser that", "start": 556.13, "duration": 4.439}, {"text": "takes grammars and returns a parser so I", "start": 557.839, "duration": 5.511}, {"text": "wrote down the context-free grammar", "start": 560.569, "duration": 5.161}, {"text": "passed it to the parser function and got", "start": 563.35, "duration": 5.59}, {"text": "back a function which I named automata", "start": 565.73, "duration": 6.299}, {"text": "book parser and you can see when I apply", "start": 568.94, "duration": 5.879}, {"text": "automata book parser to that exact same", "start": 572.029, "duration": 4.321}, {"text": "string that was in the example in the", "start": 574.819, "duration": 4.08}, {"text": "book I get back some sort of closure", "start": 576.35, "duration": 6.179}, {"text": "tree structure if you have trouble", "start": 578.899, "duration": 4.711}, {"text": "visualizing it from there there's", "start": 582.529, "duration": 2.881}, {"text": "actually a function built in insta parse", "start": 583.61, "duration": 5.25}, {"text": "Club visualize and it produces the tree", "start": 585.41, "duration": 5.97}, {"text": "that's in the lower left corner showing", "start": 588.86, "duration": 3.839}, {"text": "you what the tree actually looks like", "start": 591.38, "duration": 3.809}, {"text": "and it's got some extra information in", "start": 592.699, "duration": 4.62}, {"text": "there but you can see that the tree", "start": 595.189, "duration": 3.96}, {"text": "structure that it produces is exactly", "start": 597.319, "duration": 3.301}, {"text": "the same as the one that was shown in", "start": 599.149, "duration": 3.451}, {"text": "the textbook that's pretty nice to be", "start": 600.62, "duration": 4.74}, {"text": "able to just put this in and get", "start": 602.6, "duration": 3.9}, {"text": "something out that you can work with", "start": 605.36, "duration": 6.959}, {"text": "like this is great now my first version", "start": 606.5, "duration": 7.92}, {"text": "of this talk I have to admit was like", "start": 612.319, "duration": 4.26}, {"text": "twice as long as it needed to be and I", "start": 614.42, "duration": 3.96}, {"text": "was planning to spend a lot of time", "start": 616.579, "duration": 4.141}, {"text": "giving sort of a tour of the features of", "start": 618.38, "duration": 4.68}, {"text": "insta parse but I realized when I had to", "start": 620.72, "duration": 4.619}, {"text": "sort of pare things down to a reasonable", "start": 623.06, "duration": 5.519}, {"text": "length of time that there's already a", "start": 625.339, "duration": 6.151}, {"text": "really detailed tutorial about insta", "start": 628.579, "duration": 5.791}, {"text": "parse on github on the github site and", "start": 631.49, "duration": 6.69}, {"text": "so I'm not gonna make this about you", "start": 634.37, "duration": 5.159}, {"text": "know just showing you all the features", "start": 638.18, "duration": 3.93}, {"text": "of insta parse this is talk is going to", "start": 639.529, "duration": 3.601}, {"text": "be a little more about the", "start": 642.11, "duration": 3.51}, {"text": "implementation events to parse but I do", "start": 643.13, "duration": 5.129}, {"text": "feel like there's at least a few key", "start": 645.62, "duration": 6.93}, {"text": "features you need to know about so these", "start": 648.259, "duration": 6.39}, {"text": "are the three features that I think", "start": 652.55, "duration": 6.259}, {"text": "really helped make instapass a", "start": 654.649, "duration": 7.0}, {"text": "particularly nice lightweight tool for", "start": 658.809, "duration": 6.53}, {"text": "working with context-free grammars so", "start": 661.649, "duration": 7.92}, {"text": "first there are three ways to describe a", "start": 665.339, "duration": 8.67}, {"text": "grammar in insta parse most libraries", "start": 669.569, "duration": 7.911}, {"text": "especially in the closure ecosystem", "start": 674.009, "duration": 6.091}, {"text": "allow you to create a grammar using kind", "start": 677.48, "duration": 4.359}, {"text": "of a combination of functions and data", "start": 680.1, "duration": 3.149}, {"text": "that's often called the Combinator", "start": 681.839, "duration": 4.74}, {"text": "approach insta parse lets you do that", "start": 683.249, "duration": 5.64}, {"text": "but on top of that you can also just", "start": 686.579, "duration": 5.01}, {"text": "enter in these two syntaxes that are", "start": 688.889, "duration": 4.89}, {"text": "very popular for describing context-free", "start": 691.589, "duration": 5.04}, {"text": "grammars ebn f syntax and a B and F", "start": 693.779, "duration": 4.771}, {"text": "syntax and I really think that's gone a", "start": 696.629, "duration": 5.4}, {"text": "long way towards making insta parse feel", "start": 698.55, "duration": 5.009}, {"text": "like I said kind of as lightweight as", "start": 702.029, "duration": 3.391}, {"text": "regular expressions although I guess", "start": 703.559, "duration": 3.03}, {"text": "some people would argue how lightweight", "start": 705.42, "duration": 3.63}, {"text": "our regular expressions but it at least", "start": 706.589, "duration": 4.53}, {"text": "is is like gives you that feel that you", "start": 709.05, "duration": 3.449}, {"text": "can kind of enter in this notation", "start": 711.119, "duration": 5.52}, {"text": "that's very familiar also insta parse", "start": 712.499, "duration": 8.46}, {"text": "can produce the two most popular formats", "start": 716.639, "duration": 7.89}, {"text": "for expressing trees enclosure and when", "start": 720.959, "duration": 5.0}, {"text": "it produces these trees that", "start": 724.529, "duration": 3.961}, {"text": "automatically labels the nodes of the", "start": 725.959, "duration": 5.05}, {"text": "tree with the rules from your grammar", "start": 728.49, "duration": 6.599}, {"text": "the rule names from the grammar finally", "start": 731.009, "duration": 6.091}, {"text": "and I think this might be one of the", "start": 735.089, "duration": 4.68}, {"text": "most important features of insta parse", "start": 737.1, "duration": 5.0}, {"text": "is it lets you work with any", "start": 739.769, "duration": 5.07}, {"text": "context-free grammar and that actually", "start": 742.1, "duration": 6.489}, {"text": "turns out to be relatively unusual most", "start": 744.839, "duration": 7.141}, {"text": "parser libraries can only handle a", "start": 748.589, "duration": 5.97}, {"text": "certain subset of context-free grammars", "start": 751.98, "duration": 4.62}, {"text": "and it requires a fair amount of", "start": 754.559, "duration": 5.4}, {"text": "specialist knowledge to figure out how", "start": 756.6, "duration": 6.839}, {"text": "to take your grammar and turn it into", "start": 759.959, "duration": 5.25}, {"text": "something that this particular library", "start": 763.439, "duration": 7.74}, {"text": "can process insta parse is relatively", "start": 765.209, "duration": 8.94}, {"text": "rare in in that you can really put in", "start": 771.179, "duration": 4.95}, {"text": "any context-free grammar and it just", "start": 774.149, "duration": 8.24}, {"text": "works so", "start": 776.129, "duration": 6.26}, {"text": "one of the things I really want to", "start": 782.41, "duration": 4.59}, {"text": "address here in this talk is how does", "start": 783.67, "duration": 5.19}, {"text": "that sort of magic happen what is it", "start": 787.0, "duration": 4.14}, {"text": "that insta parse does that these other", "start": 788.86, "duration": 5.07}, {"text": "libraries aren't doing that lets it", "start": 791.14, "duration": 4.74}, {"text": "handle any grammar and I'm going to", "start": 793.93, "duration": 5.31}, {"text": "focus specifically on something called a", "start": 795.88, "duration": 5.25}, {"text": "left recursive grammar because that's", "start": 799.24, "duration": 3.45}, {"text": "something that other languages don't", "start": 801.13, "duration": 2.79}, {"text": "handle well", "start": 802.69, "duration": 3.78}, {"text": "first I need to explain to you for those", "start": 803.92, "duration": 4.26}, {"text": "of you who aren't quite as familiar with", "start": 806.47, "duration": 4.73}, {"text": "grammars the two main concepts in", "start": 808.18, "duration": 5.97}, {"text": "grammars is this notion of alternation", "start": 811.2, "duration": 6.64}, {"text": "so when you see that vertical bar that's", "start": 814.15, "duration": 5.79}, {"text": "telling you you know that's sort of", "start": 817.84, "duration": 4.95}, {"text": "defining that's like the word or so I'm", "start": 819.94, "duration": 5.64}, {"text": "looking for the letter A or the letter B", "start": 822.79, "duration": 6.9}, {"text": "that's alternation concatenation when no", "start": 825.58, "duration": 6.06}, {"text": "symbol appears is saying I'm looking for", "start": 829.69, "duration": 4.74}, {"text": "the letter A followed by the letter B", "start": 831.64, "duration": 7.35}, {"text": "and those two concepts are really the", "start": 834.43, "duration": 6.15}, {"text": "main ingredients in grammars there's a", "start": 838.99, "duration": 2.54}, {"text": "few other things but they can", "start": 840.58, "duration": 6.18}, {"text": "technically be built out of those so the", "start": 841.53, "duration": 7.21}, {"text": "grammar that I'm gonna focus on here to", "start": 846.76, "duration": 3.9}, {"text": "sort of show you how insta parse does it", "start": 848.74, "duration": 5.16}, {"text": "where other parser libraries would kind", "start": 850.66, "duration": 6.45}, {"text": "of break down is this left recursive", "start": 853.9, "duration": 4.56}, {"text": "grammar this is probably the simplest", "start": 857.11, "duration": 3.93}, {"text": "possible one it's the rule S is the", "start": 858.46, "duration": 5.43}, {"text": "letter A or the rule s followed by the", "start": 861.04, "duration": 3.51}, {"text": "letter A", "start": 863.89, "duration": 3.65}, {"text": "it's called left recursion because the S", "start": 864.55, "duration": 6.15}, {"text": "occurs on the left side of its", "start": 867.54, "duration": 7.18}, {"text": "concatenation just to give you an idea", "start": 870.7, "duration": 5.52}, {"text": "of how it's supposed to work and how", "start": 874.72, "duration": 3.24}, {"text": "insta parse handles it on the upper", "start": 876.22, "duration": 4.89}, {"text": "right I have entered that grammar and", "start": 877.96, "duration": 4.95}, {"text": "insta parse and we can see that if you", "start": 881.11, "duration": 5.96}, {"text": "feed the string AAA to that parser it", "start": 882.91, "duration": 7.05}, {"text": "successfully generates the proper tree", "start": 887.07, "duration": 5.32}, {"text": "structure which I've shown both in the", "start": 889.96, "duration": 5.04}, {"text": "closure code and the actual kind of", "start": 892.39, "duration": 4.47}, {"text": "visualized tree of what you get out of", "start": 895.0, "duration": 4.1}, {"text": "that", "start": 896.86, "duration": 2.24}, {"text": "now most libraries use a technique", "start": 899.49, "duration": 5.47}, {"text": "called recursive descent recursive", "start": 902.62, "duration": 5.16}, {"text": "descent sort of used these parsing rules", "start": 904.96, "duration": 6.5}, {"text": "as a bunch of mutually recursive", "start": 907.78, "duration": 6.14}, {"text": "components that call each other as they", "start": 911.46, "duration": 6.67}, {"text": "attempt to resolve the parse the problem", "start": 913.92, "duration": 6.07}, {"text": "is a recursive descent does not handle", "start": 918.13, "duration": 4.46}, {"text": "these left recursive grammars here's", "start": 919.99, "duration": 5.76}, {"text": "kind of at a high level why it doesn't", "start": 922.59, "duration": 5.53}, {"text": "work you can imagine stepping through", "start": 925.75, "duration": 4.86}, {"text": "the process like tracing through what a", "start": 928.12, "duration": 4.59}, {"text": "recursive descent parser would do with", "start": 930.61, "duration": 5.28}, {"text": "the string AAA it says okay well first I", "start": 932.71, "duration": 5.19}, {"text": "got to call this you know my overall", "start": 935.89, "duration": 4.56}, {"text": "rule is the rule s and I want to start", "start": 937.9, "duration": 4.17}, {"text": "from the very beginning of the string", "start": 940.45, "duration": 5.54}, {"text": "index zero and I want to do this parse", "start": 942.07, "duration": 8.85}, {"text": "well the rule s expands to a or s a so I", "start": 945.99, "duration": 7.18}, {"text": "got to do that parse starting from the", "start": 950.92, "duration": 4.17}, {"text": "beginning of the string well this is an", "start": 953.17, "duration": 4.11}, {"text": "or so I have to try both possibilities", "start": 955.09, "duration": 4.59}, {"text": "so first I'm gonna try the a parser", "start": 957.28, "duration": 5.52}, {"text": "starting at index zero and that works it", "start": 959.68, "duration": 4.95}, {"text": "succeeds there is an a at the beginning", "start": 962.8, "duration": 3.69}, {"text": "of the string but that's not enough to", "start": 964.63, "duration": 3.96}, {"text": "consume the whole string we need to keep", "start": 966.49, "duration": 4.92}, {"text": "going explore the other scenario the", "start": 968.59, "duration": 5.9}, {"text": "other scenario is s followed by a and", "start": 971.41, "duration": 5.55}, {"text": "well if you have a concatenation like", "start": 974.49, "duration": 5.14}, {"text": "that the first step is to try s starting", "start": 976.96, "duration": 3.93}, {"text": "from the beginning of the string and now", "start": 979.63, "duration": 4.13}, {"text": "we're caught in an infinite loop right", "start": 980.89, "duration": 6.42}, {"text": "so what I want to do now is kind of talk", "start": 983.76, "duration": 6.19}, {"text": "about how insta parse handles this and I", "start": 987.31, "duration": 3.75}, {"text": "know some of you in the audience", "start": 989.95, "duration": 4.52}, {"text": "probably you know have no interest in", "start": 991.06, "duration": 6.45}, {"text": "knowing all the details of how a parser", "start": 994.47, "duration": 4.66}, {"text": "library is implemented and that's fine", "start": 997.51, "duration": 3.89}, {"text": "but I hope you'll bear with me because I", "start": 999.13, "duration": 5.22}, {"text": "really think there's some big ideas here", "start": 1001.4, "duration": 4.63}, {"text": "in the implementation of insta parse", "start": 1004.35, "duration": 4.59}, {"text": "that could actually be applied to other", "start": 1006.03, "duration": 5.64}, {"text": "programming paradigms so stay with me", "start": 1008.94, "duration": 4.47}, {"text": "I'm going to sort of describe it at a", "start": 1011.67, "duration": 3.48}, {"text": "high level and I think you'll come out", "start": 1013.41, "duration": 6.2}, {"text": "of it with some interesting ideas so the", "start": 1015.15, "duration": 7.439}, {"text": "engine that drives insta parse is", "start": 1019.61, "duration": 6.729}, {"text": "something called the gll algorithm and", "start": 1022.589, "duration": 5.37}, {"text": "even though it's not described this way", "start": 1026.339, "duration": 4.86}, {"text": "in the literature I tend to think of", "start": 1027.959, "duration": 4.801}, {"text": "this algorithm", "start": 1031.199, "duration": 5.221}, {"text": "as well as a dataflow network really I", "start": 1032.76, "duration": 6.81}, {"text": "think of it as a bunch of nodes that", "start": 1036.42, "duration": 6.9}, {"text": "each represent a parser component trying", "start": 1039.57, "duration": 5.94}, {"text": "to parse the string from a certain point", "start": 1043.32, "duration": 6.12}, {"text": "and other components are listening for", "start": 1045.51, "duration": 6.51}, {"text": "those results and waiting for those", "start": 1049.44, "duration": 5.03}, {"text": "results to be transmitted to them and", "start": 1052.02, "duration": 5.54}, {"text": "that's how I think of it as a network", "start": 1054.47, "duration": 5.62}, {"text": "now as I mentioned there's these two big", "start": 1057.56, "duration": 4.84}, {"text": "concepts alternation and concatenation", "start": 1060.09, "duration": 3.78}, {"text": "so let's sort of look at how that would", "start": 1062.4, "duration": 4.77}, {"text": "work in this dataflow network sense so", "start": 1063.87, "duration": 5.73}, {"text": "if you have a parser a or B that's our", "start": 1067.17, "duration": 5.01}, {"text": "alternation pattern basically it's gonna", "start": 1069.6, "duration": 5.1}, {"text": "set up and say okay I want to start off", "start": 1072.18, "duration": 5.31}, {"text": "the parser a and I want to start off the", "start": 1074.7, "duration": 4.86}, {"text": "parser B and I'm gonna listen for the", "start": 1077.49, "duration": 4.2}, {"text": "results when you find some results come", "start": 1079.56, "duration": 3.54}, {"text": "report that back to me", "start": 1081.69, "duration": 2.97}, {"text": "so that's the alternation they're pretty", "start": 1083.1, "duration": 5.37}, {"text": "straightforward now the concatenation", "start": 1084.66, "duration": 6.72}, {"text": "patterns a little trickier and the idea", "start": 1088.47, "duration": 5.31}, {"text": "this isn't quite right but the idea is", "start": 1091.38, "duration": 4.29}, {"text": "that if you're looking for a followed by", "start": 1093.78, "duration": 5.16}, {"text": "B you start off a node that says okay I", "start": 1095.67, "duration": 6.63}, {"text": "want to do parser a starting from the", "start": 1098.94, "duration": 4.59}, {"text": "beginning of the string starting from", "start": 1102.3, "duration": 4.68}, {"text": "index 0 when you get a result hand that", "start": 1103.53, "duration": 6.36}, {"text": "off to the guy who follows that which is", "start": 1106.98, "duration": 5.22}, {"text": "parser B so I'm going to start looking", "start": 1109.89, "duration": 4.68}, {"text": "for parser B starting at the next index", "start": 1112.2, "duration": 5.91}, {"text": "index 1 and when he succeeds then notify", "start": 1114.57, "duration": 5.34}, {"text": "me back then you've successfully found", "start": 1118.11, "duration": 4.71}, {"text": "an a followed by a B now the reason why", "start": 1119.91, "duration": 8.34}, {"text": "this doesn't quite work is because in", "start": 1122.82, "duration": 7.32}, {"text": "this particular example we know that the", "start": 1128.25, "duration": 4.65}, {"text": "letter A is always one character long so", "start": 1130.14, "duration": 4.74}, {"text": "we know that this B parser is always", "start": 1132.9, "duration": 4.35}, {"text": "going to start looking one character", "start": 1134.88, "duration": 3.48}, {"text": "later but in general we don't", "start": 1137.25, "duration": 3.63}, {"text": "necessarily know how long the first", "start": 1138.36, "duration": 4.77}, {"text": "parse result will be so we have to use", "start": 1140.88, "duration": 4.02}, {"text": "something I call the cat listener", "start": 1143.13, "duration": 5.01}, {"text": "pattern so the cat listener pattern", "start": 1144.9, "duration": 4.8}, {"text": "basically says we need to create this", "start": 1148.14, "duration": 4.11}, {"text": "object that is going to listen for that", "start": 1149.7, "duration": 5.1}, {"text": "first thing to complete that a parser", "start": 1152.25, "duration": 4.68}, {"text": "needs to complete and I'm going to be", "start": 1154.8, "duration": 5.82}, {"text": "listening for that and when a is done I", "start": 1156.93, "duration": 8.55}, {"text": "look at how much he consumed and then", "start": 1160.62, "duration": 7.47}, {"text": "I'm gonna kick off the beat parser", "start": 1165.48, "duration": 4.77}, {"text": "starting from that index and reporting", "start": 1168.09, "duration": 4.62}, {"text": "back to the main guy the one who started", "start": 1170.25, "duration": 5.429}, {"text": "it all so just to understand my notation", "start": 1172.71, "duration": 5.31}, {"text": "here and the cat listener I used that", "start": 1175.679, "duration": 4.141}, {"text": "triangle just to kind of denote that the", "start": 1178.02, "duration": 4.17}, {"text": "cat listener knows that when he gets a", "start": 1179.82, "duration": 4.44}, {"text": "result that a is done but the beast", "start": 1182.19, "duration": 3.45}, {"text": "still needs to be processed you can", "start": 1184.26, "duration": 2.46}, {"text": "almost think of it kind of like a", "start": 1185.64, "duration": 5.22}, {"text": "continuation the the dotted line the", "start": 1186.72, "duration": 6.27}, {"text": "dashed line is something that no values", "start": 1190.86, "duration": 4.08}, {"text": "actually travel along that's just there", "start": 1192.99, "duration": 3.6}, {"text": "to show the cat listener knows who", "start": 1194.94, "duration": 5.489}, {"text": "initially created him and when he moves", "start": 1196.59, "duration": 6.48}, {"text": "on to do that second when he starts the", "start": 1200.429, "duration": 5.461}, {"text": "node to do the second parse he knows who", "start": 1203.07, "duration": 4.17}, {"text": "need that result needs to get", "start": 1205.89, "duration": 5.19}, {"text": "transmitted back to okay now these", "start": 1207.24, "duration": 6.24}, {"text": "individual nodes in the network how do", "start": 1211.08, "duration": 4.56}, {"text": "we program those what kind of model are", "start": 1213.48, "duration": 4.05}, {"text": "they're using and it's almost like the", "start": 1215.64, "duration": 3.93}, {"text": "publisher subscriber model but with a", "start": 1217.53, "duration": 4.889}, {"text": "slight twist so usually when we think of", "start": 1219.57, "duration": 5.82}, {"text": "the pub/sub model for data flow we", "start": 1222.419, "duration": 4.681}, {"text": "imagine it a lot like a magazine", "start": 1225.39, "duration": 5.46}, {"text": "subscription so if I subscribe to a", "start": 1227.1, "duration": 5.88}, {"text": "magazine I expect them to send me all", "start": 1230.85, "duration": 5.459}, {"text": "the issues from this point forward so", "start": 1232.98, "duration": 4.89}, {"text": "the kind of model we're gonna use though", "start": 1236.309, "duration": 3.391}, {"text": "is a little bit different the idea is", "start": 1237.87, "duration": 3.51}, {"text": "that when I subscribe to this magazine", "start": 1239.7, "duration": 3.75}, {"text": "I'm basically saying send me all your", "start": 1241.38, "duration": 5.1}, {"text": "back issues and then start sending me", "start": 1243.45, "duration": 5.28}, {"text": "the new stuff also and it turns out that", "start": 1246.48, "duration": 4.68}, {"text": "this is the kind of node we need for", "start": 1248.73, "duration": 4.319}, {"text": "this particular network and it's", "start": 1251.16, "duration": 2.91}, {"text": "something you might want to think about", "start": 1253.049, "duration": 3.361}, {"text": "using in your own programs when you see", "start": 1254.07, "duration": 5.55}, {"text": "how it's useful here programming that is", "start": 1256.41, "duration": 5.37}, {"text": "quite easy the each of these nodes", "start": 1259.62, "duration": 5.22}, {"text": "basically just tracks who is listening", "start": 1261.78, "duration": 5.04}, {"text": "who needs to know these results and what", "start": 1264.84, "duration": 3.959}, {"text": "results that's found so far for this", "start": 1266.82, "duration": 4.859}, {"text": "parser component at this particular", "start": 1268.799, "duration": 5.37}, {"text": "point in the string and when a new", "start": 1271.679, "duration": 4.441}, {"text": "result comes in well that's really", "start": 1274.169, "duration": 4.111}, {"text": "obvious we just forward that information", "start": 1276.12, "duration": 4.71}, {"text": "to all the listeners but we also have to", "start": 1278.28, "duration": 4.86}, {"text": "keep track of it so that if a new", "start": 1280.83, "duration": 4.469}, {"text": "listener comes in we can send to that", "start": 1283.14, "duration": 7.44}, {"text": "new listener all the old results okay so", "start": 1285.299, "duration": 7.531}, {"text": "now we're ready to actually get in and", "start": 1290.58, "duration": 4.86}, {"text": "do kind of this high-level you know", "start": 1292.83, "duration": 5.339}, {"text": "understanding how insta parse would", "start": 1295.44, "duration": 3.81}, {"text": "handle that particular", "start": 1298.169, "duration": 3.661}, {"text": "left recursive grammar with the input a", "start": 1299.25, "duration": 5.91}, {"text": "a so we start off with something that I", "start": 1301.83, "duration": 5.58}, {"text": "call the top listener it's job is to", "start": 1305.16, "duration": 5.22}, {"text": "start off the parsing process listen for", "start": 1307.41, "duration": 6.12}, {"text": "full results and when it hears full", "start": 1310.38, "duration": 5.4}, {"text": "results transmit that back to the user", "start": 1313.53, "duration": 6.57}, {"text": "so it start it says ok that top level", "start": 1315.78, "duration": 6.48}, {"text": "rule is s so I'm going to start off the", "start": 1320.1, "duration": 7.5}, {"text": "rule s starting from index zero and I'm", "start": 1322.26, "duration": 7.59}, {"text": "listening for results and that little", "start": 1327.6, "duration": 5.07}, {"text": "notation there as indicating right here", "start": 1329.85, "duration": 5.82}, {"text": "is indicating that only complete parses", "start": 1332.67, "duration": 5.28}, {"text": "need to be transmitted up to the top", "start": 1335.67, "duration": 9.33}, {"text": "listener now the s parser expands to a", "start": 1337.95, "duration": 9.9}, {"text": "or s a so it creates that parser and", "start": 1345.0, "duration": 4.68}, {"text": "it's going to listen to it now I talked", "start": 1347.85, "duration": 3.69}, {"text": "about how insta parse automatically", "start": 1349.68, "duration": 4.38}, {"text": "labels all the nodes in the tree with", "start": 1351.54, "duration": 5.94}, {"text": "the rule name so when values flow from", "start": 1354.06, "duration": 5.07}, {"text": "here to here they have to get labeled", "start": 1357.48, "duration": 5.55}, {"text": "with that s label now this is the", "start": 1359.13, "duration": 6.09}, {"text": "alternation pattern right we have an A", "start": 1363.03, "duration": 5.55}, {"text": "or s a so we spin off to other parse", "start": 1365.22, "duration": 5.82}, {"text": "nodes a and s a starting from the", "start": 1368.58, "duration": 3.75}, {"text": "beginning of the string and I'm", "start": 1371.04, "duration": 4.23}, {"text": "listening to both those results now this", "start": 1372.33, "duration": 4.94}, {"text": "is effectively happening asynchronously", "start": 1375.27, "duration": 4.68}, {"text": "and that's the key you know one of the", "start": 1377.27, "duration": 4.9}, {"text": "key differences here is usually in", "start": 1379.95, "duration": 6.84}, {"text": "recursive descent style strategy we're", "start": 1382.17, "duration": 6.3}, {"text": "calling one of the things in the", "start": 1386.79, "duration": 4.11}, {"text": "alternation and it's a blocking call we", "start": 1388.47, "duration": 4.11}, {"text": "wait for the result and we get that", "start": 1390.9, "duration": 3.9}, {"text": "result then we try the other possibility", "start": 1392.58, "duration": 3.84}, {"text": "but we're spinning both of these things", "start": 1394.8, "duration": 4.68}, {"text": "off asynchronously and just waiting and", "start": 1396.42, "duration": 4.35}, {"text": "listening for the results so we don't", "start": 1399.48, "duration": 2.52}, {"text": "know which order these things are going", "start": 1400.77, "duration": 3.15}, {"text": "to be processed for the moment I'm going", "start": 1402.0, "duration": 6.18}, {"text": "to explore the rightmost node that's the", "start": 1403.92, "duration": 6.54}, {"text": "concatenation pattern right s followed", "start": 1408.18, "duration": 4.92}, {"text": "by a so we have to do that cat listener", "start": 1410.46, "duration": 4.74}, {"text": "thing I talked about earlier so we", "start": 1413.1, "duration": 3.84}, {"text": "create this cat listener this", "start": 1415.2, "duration": 4.44}, {"text": "continuation node that's going to listen", "start": 1416.94, "duration": 6.12}, {"text": "for the S parse and it knows that it", "start": 1419.64, "duration": 4.71}, {"text": "needs to follow up when it gets", "start": 1423.06, "duration": 4.11}, {"text": "something by looking for the a parse now", "start": 1424.35, "duration": 4.02}, {"text": "one thing that's kind of interesting", "start": 1427.17, "duration": 4.5}, {"text": "here is there's already a node in our", "start": 1428.37, "duration": 7.02}, {"text": "work for the S parser starting at index", "start": 1431.67, "duration": 6.06}, {"text": "zero so there's no need to create a new", "start": 1435.39, "duration": 4.86}, {"text": "one here we just listen to the one that", "start": 1437.73, "duration": 7.11}, {"text": "already exists in our network okay now", "start": 1440.25, "duration": 6.06}, {"text": "we can go down to the lower left the", "start": 1444.84, "duration": 4.71}, {"text": "lower left is actually a node that can", "start": 1446.31, "duration": 5.46}, {"text": "do something not just add more stuff to", "start": 1449.55, "duration": 3.75}, {"text": "the network it's looking for the", "start": 1451.77, "duration": 3.0}, {"text": "character a at the beginning of the", "start": 1453.3, "duration": 3.84}, {"text": "string and it finds it so it produces", "start": 1454.77, "duration": 4.29}, {"text": "this result saying hey I found the", "start": 1457.14, "duration": 4.59}, {"text": "letter A and I've consumed one letter so", "start": 1459.06, "duration": 7.5}, {"text": "far that information gets transmitted up", "start": 1461.73, "duration": 7.56}, {"text": "to the alternation node which in turn", "start": 1466.56, "duration": 4.8}, {"text": "gets transmitted up to the S node and", "start": 1469.29, "duration": 5.91}, {"text": "gets labeled in the process that", "start": 1471.36, "duration": 5.94}, {"text": "information gets relayed to the cat", "start": 1475.2, "duration": 4.77}, {"text": "listener and now the cat listener has to", "start": 1477.3, "duration": 7.2}, {"text": "do that extra work that it does spinning", "start": 1479.97, "duration": 7.77}, {"text": "off a new node to do the remaining part", "start": 1484.5, "duration": 5.97}, {"text": "of the parse so this is a little tricky", "start": 1487.74, "duration": 5.6}, {"text": "so I want to make sure this is clear", "start": 1490.47, "duration": 5.79}, {"text": "this new node the way it's created this", "start": 1493.34, "duration": 7.54}, {"text": "a right here comes from the second part", "start": 1496.26, "duration": 7.77}, {"text": "of the cat listener the one it's going", "start": 1500.88, "duration": 6.0}, {"text": "to be looking for the a at index one", "start": 1504.03, "duration": 4.44}, {"text": "because that's how many letters were", "start": 1506.88, "duration": 3.33}, {"text": "consumed so it's looking at that number", "start": 1508.47, "duration": 6.09}, {"text": "to get that the result that was created", "start": 1510.21, "duration": 7.83}, {"text": "so far becomes this label along this", "start": 1514.56, "duration": 6.21}, {"text": "flow path this value that's going to", "start": 1518.04, "duration": 4.74}, {"text": "need to get prepended to any result", "start": 1520.77, "duration": 4.52}, {"text": "that's discovered by this parser and", "start": 1522.78, "duration": 5.49}, {"text": "this dashed line here was the thing that", "start": 1525.29, "duration": 4.75}, {"text": "sort of remembered who was the original", "start": 1528.27, "duration": 3.18}, {"text": "creator and that's going to be the", "start": 1530.04, "duration": 3.81}, {"text": "destination for this arrow so all the", "start": 1531.45, "duration": 4.68}, {"text": "things about this node are constructed", "start": 1533.85, "duration": 4.83}, {"text": "from information that is available to", "start": 1536.13, "duration": 6.3}, {"text": "this cat listener okay well again this", "start": 1538.68, "duration": 5.31}, {"text": "is a node that can do something right", "start": 1542.43, "duration": 6.03}, {"text": "away and it says yes there is a letter a", "start": 1543.99, "duration": 7.5}, {"text": "at index one so now I've consumed", "start": 1548.46, "duration": 4.8}, {"text": "another letter for a total of two", "start": 1551.49, "duration": 4.56}, {"text": "letters that information gets", "start": 1553.26, "duration": 4.86}, {"text": "transmitted along that path with that", "start": 1556.05, "duration": 6.54}, {"text": "value prepended and that gets reported", "start": 1558.12, "duration": 6.83}, {"text": "back to that alternation node", "start": 1562.59, "duration": 5.64}, {"text": "which in turn flows up to the original s", "start": 1564.95, "duration": 5.439}, {"text": "Snowden gets labeled in the process and", "start": 1568.23, "duration": 5.85}, {"text": "now we have a full parse the and we know", "start": 1570.389, "duration": 5.341}, {"text": "it's a full parse because we've consumed", "start": 1574.08, "duration": 3.63}, {"text": "two letters and the string is two", "start": 1575.73, "duration": 4.529}, {"text": "characters long so that flows up to the", "start": 1577.71, "duration": 4.65}, {"text": "top listener it also flows over to that", "start": 1580.259, "duration": 3.78}, {"text": "cat listener but it doesn't matter at", "start": 1582.36, "duration": 3.72}, {"text": "that point because it's exhausted the", "start": 1584.039, "duration": 3.39}, {"text": "string so the cat listener is not going", "start": 1586.08, "duration": 3.66}, {"text": "to try to do anything with it so the top", "start": 1587.429, "duration": 4.47}, {"text": "listener now has a result and this is", "start": 1589.74, "duration": 3.96}, {"text": "the piece that's going to be reported", "start": 1591.899, "duration": 4.551}, {"text": "back to the user so we have our parse", "start": 1593.7, "duration": 7.349}, {"text": "now I happen to demonstrate this in", "start": 1596.45, "duration": 6.67}, {"text": "terms of showing the right node before", "start": 1601.049, "duration": 3.75}, {"text": "the left node down here in the", "start": 1603.12, "duration": 3.33}, {"text": "alternation but think for a moment about", "start": 1604.799, "duration": 3.63}, {"text": "what would have happened if the left", "start": 1606.45, "duration": 4.679}, {"text": "node node result had gotten computed", "start": 1608.429, "duration": 6.061}, {"text": "first so this result would have flown", "start": 1611.129, "duration": 7.26}, {"text": "would have flowed up to the s parser but", "start": 1614.49, "duration": 5.73}, {"text": "that cat listener wouldn't have been", "start": 1618.389, "duration": 6.0}, {"text": "attached yet then this one comes through", "start": 1620.22, "duration": 7.559}, {"text": "and starts up that cat listener node", "start": 1624.389, "duration": 6.681}, {"text": "that's why remember I said earlier that", "start": 1627.779, "duration": 6.541}, {"text": "values need to old values need to be", "start": 1631.07, "duration": 5.41}, {"text": "relayed to new listeners that attach", "start": 1634.32, "duration": 4.92}, {"text": "that's why is because if we didn't do", "start": 1636.48, "duration": 6.029}, {"text": "that then if this result got here before", "start": 1639.24, "duration": 5.399}, {"text": "the listener was attached that listener", "start": 1642.509, "duration": 3.361}, {"text": "would never know about it", "start": 1644.639, "duration": 5.941}, {"text": "that's why that's important okay now I", "start": 1645.87, "duration": 6.84}, {"text": "promised for those of you who weren't", "start": 1650.58, "duration": 3.75}, {"text": "particularly interested in parser", "start": 1652.71, "duration": 3.51}, {"text": "implementation that there was a big idea", "start": 1654.33, "duration": 5.429}, {"text": "here worth knowing so let's kind of", "start": 1656.22, "duration": 5.76}, {"text": "reflect on what we've seen what I think", "start": 1659.759, "duration": 5.64}, {"text": "is the big idea here is that synchronous", "start": 1661.98, "duration": 6.539}, {"text": "function calls and recursion has this", "start": 1665.399, "duration": 5.52}, {"text": "potential to lead to infinite loops on", "start": 1668.519, "duration": 5.13}, {"text": "the other hand if you use asynchronous", "start": 1670.919, "duration": 5.34}, {"text": "calls and dataflow you have the", "start": 1673.649, "duration": 5.461}, {"text": "potential to get a more robust algorithm", "start": 1676.259, "duration": 5.28}, {"text": "and I actually found this to be a really", "start": 1679.11, "duration": 4.169}, {"text": "big surprise when I started working on", "start": 1681.539, "duration": 4.951}, {"text": "this I have always thought of dataflow", "start": 1683.279, "duration": 6.211}, {"text": "as more being about a way to organize my", "start": 1686.49, "duration": 5.34}, {"text": "program and a slightly more flexible or", "start": 1689.49, "duration": 4.62}, {"text": "clear way I never really thought about", "start": 1691.83, "duration": 4.68}, {"text": "it as something that might actually give", "start": 1694.11, "duration": 3.26}, {"text": "added", "start": 1696.51, "duration": 3.419}, {"text": "algorithmic capability I mean that", "start": 1697.37, "duration": 4.72}, {"text": "really never occurred to me before so", "start": 1699.929, "duration": 4.71}, {"text": "that's what I think is one of these big", "start": 1702.09, "duration": 6.089}, {"text": "ideas here I think I can safely predict", "start": 1704.639, "duration": 4.981}, {"text": "that over the next few days you're going", "start": 1708.179, "duration": 4.13}, {"text": "to be hearing a lot about asynchronous", "start": 1709.62, "duration": 5.76}, {"text": "channels data flow right all these", "start": 1712.309, "duration": 4.75}, {"text": "things are things that are going to come", "start": 1715.38, "duration": 3.419}, {"text": "up a lot here at the closure conference", "start": 1717.059, "duration": 3.6}, {"text": "that's really hot right now and I hope", "start": 1718.799, "duration": 3.96}, {"text": "that when you hear those sorts of talks", "start": 1720.659, "duration": 3.961}, {"text": "over the next couple of days you keep", "start": 1722.759, "duration": 5.431}, {"text": "this in mind as an example of how this", "start": 1724.62, "duration": 9.899}, {"text": "can actually give you new power so I", "start": 1728.19, "duration": 8.209}, {"text": "always think it's kind of interesting to", "start": 1734.519, "duration": 5.01}, {"text": "hear a little bit about how open-source", "start": 1736.399, "duration": 5.5}, {"text": "libraries came about so I want to just", "start": 1739.529, "duration": 3.9}, {"text": "take a moment to tell you about the", "start": 1741.899, "duration": 3.541}, {"text": "story behind insta parse you might", "start": 1743.429, "duration": 6.84}, {"text": "assume that I use parsing really heavily", "start": 1745.44, "duration": 9.329}, {"text": "and my job or you might assume that I'm", "start": 1750.269, "duration": 7.26}, {"text": "just really passionate about parsing and", "start": 1754.769, "duration": 4.681}, {"text": "it turns out that neither of those is", "start": 1757.529, "duration": 4.591}, {"text": "actually the case the true story behind", "start": 1759.45, "duration": 5.069}, {"text": "insta parse is it's actually a", "start": 1762.12, "duration": 7.2}, {"text": "father-son bonding story so some of you", "start": 1764.519, "duration": 6.14}, {"text": "may already know this but I actually", "start": 1769.32, "duration": 4.92}, {"text": "homeschool my kids and in part that's", "start": 1770.659, "duration": 6.311}, {"text": "because I am deeply passionate about", "start": 1774.24, "duration": 4.919}, {"text": "math and computer science education and", "start": 1776.97, "duration": 4.02}, {"text": "I really wanted to be intimately", "start": 1779.159, "duration": 4.701}, {"text": "involved in that aspect with my kids and", "start": 1780.99, "duration": 6.24}, {"text": "my son in particular really took an", "start": 1783.86, "duration": 4.779}, {"text": "interest of programming and I started", "start": 1787.23, "duration": 5.069}, {"text": "him very young on first scheme and then", "start": 1788.639, "duration": 7.321}, {"text": "a closure and from age 8", "start": 1792.299, "duration": 7.62}, {"text": "I was incorporating college-level", "start": 1795.96, "duration": 6.27}, {"text": "computer science material into his daily", "start": 1799.919, "duration": 4.801}, {"text": "lessons well as you can imagine by now", "start": 1802.23, "duration": 4.49}, {"text": "he's already a very very sophisticated", "start": 1804.72, "duration": 5.88}, {"text": "programmer but I kind of consider it my", "start": 1806.72, "duration": 5.709}, {"text": "responsibility to keep coming up with", "start": 1810.6, "duration": 4.35}, {"text": "new challenges for him new things that", "start": 1812.429, "duration": 5.071}, {"text": "will really stretch his capabilities so", "start": 1814.95, "duration": 5.609}, {"text": "last year when he was 14 I called him", "start": 1817.5, "duration": 6.87}, {"text": "over and I said Alex we need to have a", "start": 1820.559, "duration": 8.36}, {"text": "talk today is the day you become a man", "start": 1824.37, "duration": 10.11}, {"text": "today you're gonna learn about monads so", "start": 1828.919, "duration": 7.87}, {"text": "as part of teaching them about monads I", "start": 1834.48, "duration": 4.699}, {"text": "gave him an exercise in writing a", "start": 1836.789, "duration": 5.701}, {"text": "monadic parser Combinator library that's", "start": 1839.179, "duration": 6.191}, {"text": "actually a relatively standard exercise", "start": 1842.49, "duration": 5.389}, {"text": "to kind of get your head around monads", "start": 1845.37, "duration": 6.659}, {"text": "so he did this parser Combinator project", "start": 1847.879, "duration": 5.62}, {"text": "and I was playing around with it looking", "start": 1852.029, "duration": 4.23}, {"text": "at it and you know it was well done but", "start": 1853.499, "duration": 6.06}, {"text": "I was really struck by that inability to", "start": 1856.259, "duration": 4.981}, {"text": "do left recursion you know it was it was", "start": 1859.559, "duration": 4.531}, {"text": "irritating and I thought to myself", "start": 1861.24, "duration": 5.48}, {"text": "surely someone has solved this by now", "start": 1864.09, "duration": 4.77}, {"text": "someone must have solved this so I went", "start": 1866.72, "duration": 4.299}, {"text": "asking around people I knew people", "start": 1868.86, "duration": 4.35}, {"text": "online who had written parser libraries", "start": 1871.019, "duration": 4.86}, {"text": "trying to find out more about how to", "start": 1873.21, "duration": 6.809}, {"text": "tackle that eventually I found a pointer", "start": 1875.879, "duration": 7.26}, {"text": "to this paper about the GL algorithm so", "start": 1880.019, "duration": 5.341}, {"text": "I decided to do what all good teachers", "start": 1883.139, "duration": 4.53}, {"text": "do I handed it to my son and said go", "start": 1885.36, "duration": 4.309}, {"text": "figure out how to write this in closure", "start": 1887.669, "duration": 5.281}, {"text": "so he did that and he implemented in", "start": 1889.669, "duration": 5.08}, {"text": "closure and as I was playing around with", "start": 1892.95, "duration": 5.28}, {"text": "that I was really struck by how much", "start": 1894.749, "duration": 6.17}, {"text": "more freeing it was I really was", "start": 1898.23, "duration": 6.449}, {"text": "noticeably more enjoyable to work with a", "start": 1900.919, "duration": 5.59}, {"text": "library that could understand any", "start": 1904.679, "duration": 5.63}, {"text": "grammar so I thought this would be a", "start": 1906.509, "duration": 7.89}, {"text": "excellent opportunity to role model the", "start": 1910.309, "duration": 8.35}, {"text": "process of going that last mile to turn", "start": 1914.399, "duration": 6.691}, {"text": "something into a library that's usable", "start": 1918.659, "duration": 5.1}, {"text": "by the community so we talked about hey", "start": 1921.09, "duration": 4.439}, {"text": "you want to just make this alive really", "start": 1923.759, "duration": 3.451}, {"text": "should we make this a library and put it", "start": 1925.529, "duration": 3.661}, {"text": "out there yeah let's do it", "start": 1927.21, "duration": 5.01}, {"text": "so we decided to do that together I kind", "start": 1929.19, "duration": 5.069}, {"text": "of took over the codebase and worked", "start": 1932.22, "duration": 5.959}, {"text": "mostly on optimizing it a little bit", "start": 1934.259, "duration": 6.27}, {"text": "brighting the documentation we work", "start": 1938.179, "duration": 4.651}, {"text": "together on the front ends I wrote the", "start": 1940.529, "duration": 5.461}, {"text": "EB NF front end heroes a BNF front end", "start": 1942.83, "duration": 4.75}, {"text": "it was it was a collaboration and it was", "start": 1945.99, "duration": 4.019}, {"text": "a lot of fun and that's the true story", "start": 1947.58, "duration": 4.74}, {"text": "behind inste parses we really just did", "start": 1950.009, "duration": 8.76}, {"text": "it for the joy of it now I know some of", "start": 1952.32, "duration": 8.79}, {"text": "you probably did come here to learn a", "start": 1958.769, "duration": 3.541}, {"text": "little more about", "start": 1961.11, "duration": 4.02}, {"text": "how to use instep arse versus how to", "start": 1962.31, "duration": 4.32}, {"text": "implement insta purse", "start": 1965.13, "duration": 4.08}, {"text": "so we have a little bit of time here", "start": 1966.63, "duration": 4.62}, {"text": "what I want to do I again I'm not going", "start": 1969.21, "duration": 4.08}, {"text": "to just show every feature but I think", "start": 1971.25, "duration": 4.86}, {"text": "it's useful to understand the overall", "start": 1973.29, "duration": 5.28}, {"text": "sort of workflow the experience of what", "start": 1976.11, "duration": 4.41}, {"text": "it's like to work with insta parse and", "start": 1978.57, "duration": 3.78}, {"text": "hopefully that'll motivate you to go off", "start": 1980.52, "duration": 6.02}, {"text": "and read the full tutorial on github so", "start": 1982.35, "duration": 4.19}, {"text": "the basic process with insta parse and", "start": 1986.96, "duration": 3.79}, {"text": "I'll go into each of these steps in a", "start": 1989.49, "duration": 3.12}, {"text": "little more detail is first you just", "start": 1990.75, "duration": 3.87}, {"text": "write down your grammar and then you", "start": 1992.61, "duration": 4.11}, {"text": "play around with it see how it looks you", "start": 1994.62, "duration": 3.51}, {"text": "figure out what information you want to", "start": 1996.72, "duration": 3.44}, {"text": "hide and then you figure out how you", "start": 1998.13, "duration": 4.23}, {"text": "transform that tree into the actual", "start": 2000.16, "duration": 5.14}, {"text": "thing you want so going back at the very", "start": 2002.36, "duration": 4.14}, {"text": "beginning of the talk I showed that", "start": 2005.3, "duration": 5.37}, {"text": "Scala map format so that's I mean so far", "start": 2006.5, "duration": 5.31}, {"text": "we've been looking at all these grammars", "start": 2010.67, "duration": 3.69}, {"text": "that are AAA BBB AAA and I know that", "start": 2011.81, "duration": 4.77}, {"text": "gets a little mind-numbing so here's a", "start": 2014.36, "duration": 4.02}, {"text": "slightly more real-world example it's", "start": 2016.58, "duration": 3.84}, {"text": "it's still simple enough you could", "start": 2018.38, "duration": 3.63}, {"text": "tackle it with other techniques I", "start": 2020.42, "duration": 3.45}, {"text": "understand but it's at least a little", "start": 2022.01, "duration": 5.13}, {"text": "more real so what we do is we start by", "start": 2023.87, "duration": 6.33}, {"text": "writing down the grammar and by", "start": 2027.14, "duration": 5.34}, {"text": "convention usually the top the first", "start": 2030.2, "duration": 4.44}, {"text": "rule is kind of a top-level rule we're", "start": 2032.48, "duration": 4.35}, {"text": "defining a map what's the rule for a map", "start": 2034.64, "duration": 5.04}, {"text": "well it's got the string map a left", "start": 2036.83, "duration": 5.72}, {"text": "paren and a bunch of key value pairs", "start": 2039.68, "duration": 5.49}, {"text": "separated by commas that's basically", "start": 2042.55, "duration": 5.71}, {"text": "what the first line says what's a key", "start": 2045.17, "duration": 5.76}, {"text": "value well it's a string and then an", "start": 2048.26, "duration": 5.31}, {"text": "arrow and then another string what's a", "start": 2050.93, "duration": 6.24}, {"text": "string well we can define that with a", "start": 2053.57, "duration": 5.19}, {"text": "regular expression so you can actually", "start": 2057.17, "duration": 3.87}, {"text": "use regular expressions in insta parse", "start": 2058.76, "duration": 7.89}, {"text": "to define your tokens then we feed this", "start": 2061.04, "duration": 8.88}, {"text": "to the parser function and the insta", "start": 2066.65, "duration": 6.45}, {"text": "parse namespace and I have this little", "start": 2069.92, "duration": 5.4}, {"text": "flag here Auto whitespace standard it's", "start": 2073.1, "duration": 4.35}, {"text": "a relatively new feature in insta parse", "start": 2075.32, "duration": 4.8}, {"text": "for grammars where the whitespace really", "start": 2077.45, "duration": 4.56}, {"text": "doesn't matter if it did matter you", "start": 2080.12, "duration": 4.86}, {"text": "would specify the whitespace as part of", "start": 2082.01, "duration": 6.93}, {"text": "the strings in your grammar rules and we", "start": 2084.98, "duration": 5.67}, {"text": "plug it in and we see what we get and", "start": 2088.94, "duration": 2.79}, {"text": "this is great you know this is rep", "start": 2090.65, "duration": 2.94}, {"text": "lorina development we get to try our", "start": 2091.73, "duration": 3.829}, {"text": "grammar see how it all works out", "start": 2093.59, "duration": 5.029}, {"text": "keep refining it and we basically get", "start": 2095.559, "duration": 4.44}, {"text": "the structure that we want but there's", "start": 2098.619, "duration": 3.42}, {"text": "these extra things in there like there's", "start": 2099.999, "duration": 5.19}, {"text": "the word map and that left paren it's in", "start": 2102.039, "duration": 5.46}, {"text": "there because those were part of the", "start": 2105.189, "duration": 4.471}, {"text": "structure but once we've got the overall", "start": 2107.499, "duration": 3.51}, {"text": "structure we don't need those words", "start": 2109.66, "duration": 3.809}, {"text": "anymore we don't need that left paren as", "start": 2111.009, "duration": 6.72}, {"text": "part of our tree so we come to step two", "start": 2113.469, "duration": 6.84}, {"text": "and insta parse we just put angle", "start": 2117.729, "duration": 5.04}, {"text": "brackets in our grammar around anything", "start": 2120.309, "duration": 4.53}, {"text": "that we want to hide that we don't", "start": 2122.769, "duration": 4.5}, {"text": "really care about appearing in our tree", "start": 2124.839, "duration": 6.291}, {"text": "so I've put angle brackets down below on", "start": 2127.269, "duration": 6.75}, {"text": "around the word map and around the paren", "start": 2131.13, "duration": 6.609}, {"text": "and around the arrow and now when we", "start": 2134.019, "duration": 6.45}, {"text": "rerun it you can see those things are", "start": 2137.739, "duration": 5.01}, {"text": "missing from the tree this is pretty", "start": 2140.469, "duration": 4.32}, {"text": "good this is you know getting really", "start": 2142.749, "duration": 5.58}, {"text": "close to what we want but ideally we", "start": 2144.789, "duration": 6.42}, {"text": "want to get it to an actual closure map", "start": 2148.329, "duration": 7.351}, {"text": "right that's our end goal well insta", "start": 2151.209, "duration": 7.681}, {"text": "parse includes a function called", "start": 2155.68, "duration": 5.46}, {"text": "transform and I mean you can use", "start": 2158.89, "duration": 4.409}, {"text": "whatever tools are you know you have all", "start": 2161.14, "duration": 4.139}, {"text": "these rich closure functions and tools", "start": 2163.299, "duration": 3.99}, {"text": "to manipulate data you can do this", "start": 2165.279, "duration": 3.96}, {"text": "however you want but you can use the", "start": 2167.289, "duration": 3.72}, {"text": "built in transform function which lets", "start": 2169.239, "duration": 5.55}, {"text": "you put for each node type in the tree a", "start": 2171.009, "duration": 6.3}, {"text": "function to be applied to the children", "start": 2174.789, "duration": 6.03}, {"text": "and this is done in kind of a bottom-up", "start": 2177.309, "duration": 5.28}, {"text": "transformation to the tree and when you", "start": 2180.819, "duration": 4.46}, {"text": "plug in these particular functions", "start": 2182.589, "duration": 5.73}, {"text": "associated with these keywords then you", "start": 2185.279, "duration": 5.41}, {"text": "get back the actual map you're looking", "start": 2188.319, "duration": 4.62}, {"text": "for so that's the basic idea you want to", "start": 2190.689, "duration": 5.0}, {"text": "get from Scala maps to closure Maps", "start": 2192.939, "duration": 6.39}, {"text": "here's three easy steps step one was", "start": 2195.689, "duration": 6.37}, {"text": "create the grammar step two was hide the", "start": 2199.329, "duration": 3.811}, {"text": "things you don't care about with the", "start": 2202.059, "duration": 3.42}, {"text": "angle brackets and step three is either", "start": 2203.14, "duration": 4.139}, {"text": "use the built in transform function or", "start": 2205.479, "duration": 3.81}, {"text": "whatever closure functions you want to", "start": 2207.279, "duration": 5.851}, {"text": "get this into the final closure form", "start": 2209.289, "duration": 6.93}, {"text": "that you're looking for okay time to", "start": 2213.13, "duration": 7.349}, {"text": "wrap things up two main ideas here from", "start": 2216.219, "duration": 5.85}, {"text": "this talk first is just telling you a", "start": 2220.479, "duration": 3.33}, {"text": "little bit about insta parse insta parse", "start": 2222.069, "duration": 3.96}, {"text": "is a lightweight tool for converting", "start": 2223.809, "duration": 4.38}, {"text": "context-free grammars into an executable", "start": 2226.029, "duration": 2.971}, {"text": "parser", "start": 2228.189, "duration": 2.911}, {"text": "and those parsers can be used to convert", "start": 2229.0, "duration": 5.52}, {"text": "strings into data but the other big idea", "start": 2231.1, "duration": 5.9}, {"text": "from this talk is that under the hood", "start": 2234.52, "duration": 5.49}, {"text": "insta parse in my opinion is a really", "start": 2237.0, "duration": 6.61}, {"text": "great example of the extra algorithmic", "start": 2240.01, "duration": 6.3}, {"text": "power you get when you use asynchronous", "start": 2243.61, "duration": 6.27}, {"text": "calls and data flow I'd like to finish", "start": 2246.31, "duration": 5.79}, {"text": "off with something I saw on the IRC", "start": 2249.88, "duration": 4.68}, {"text": "channel I actually have absolutely no", "start": 2252.1, "duration": 4.11}, {"text": "idea who these two people are I hope", "start": 2254.56, "duration": 3.06}, {"text": "they don't mind my using this in the", "start": 2256.21, "duration": 4.56}, {"text": "talk I figure since this out there in", "start": 2257.62, "duration": 5.55}, {"text": "the public on the internet it's totally", "start": 2260.77, "duration": 6.21}, {"text": "a fair to use it the point I wanted to", "start": 2263.17, "duration": 5.55}, {"text": "make with this slide is that when when", "start": 2266.98, "duration": 4.83}, {"text": "Alex and I started out making insta", "start": 2268.72, "duration": 6.21}, {"text": "parse we were genuinely trying to make a", "start": 2271.81, "duration": 6.15}, {"text": "tool that people would find useful but", "start": 2274.93, "duration": 4.98}, {"text": "what I think has taken us by surprise", "start": 2277.96, "duration": 4.5}, {"text": "and really delighted us is that for many", "start": 2279.91, "duration": 4.98}, {"text": "people it seems to not just be a tool", "start": 2282.46, "duration": 4.83}, {"text": "but it's something that has suddenly", "start": 2284.89, "duration": 4.86}, {"text": "made for them made grammars and made", "start": 2287.29, "duration": 6.06}, {"text": "parsing more accessible and more fun I", "start": 2289.75, "duration": 5.49}, {"text": "mean who would have ever thought parsing", "start": 2293.35, "duration": 5.61}, {"text": "is fun you know whoa and honestly out of", "start": 2295.24, "duration": 5.64}, {"text": "all the things that has happened with", "start": 2298.96, "duration": 3.36}, {"text": "insta parse the fact that people are", "start": 2300.88, "duration": 5.4}, {"text": "using it to find parsing this fun I mean", "start": 2302.32, "duration": 5.76}, {"text": "that's honestly what we're most proud of", "start": 2306.28, "duration": 5.36}, {"text": "so thank you very much", "start": 2308.08, "duration": 3.56}]] |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| good morning I'm mark Engelbert welcome | |
| to closure West it's exciting to be here | |
| it's the first talk of the first morning | |
| and I feel like I should be hijacking | |
| this time slot to give a keynote and set | |
| the future of closures something but | |
| we're here to talk about insta parse | |
| let's begin with a little warm-up it's | |
| the morning get to get the brains going | |
| so what's this any it's a map it's a map | |
| its closure data right this is the Eden | |
| format we all know and love and one of | |
| the beautiful things about closer for | |
| those of you who are here trying out | |
| closure you know relatively recently one | |
| of the things in my opinion that is the | |
| most exciting thing about closure it | |
| gives us these great lightweight ways to | |
| express data to model our data and it | |
| gives us a huge toolkit for manipulating | |
| that data so once we can get things in | |
| this form we're really really happy | |
| now what's this yeah it's just a string | |
| it's got the same information in there | |
| but we can't really do anything with it | |
| yet right the good news is that built | |
| right into closure in the closure | |
| edan namespace is the read string | |
| function and if we apply the function to | |
| this string we get back that map that we | |
| can actually work with and that's also | |
| another really wonderful thing about | |
| closure is how easy it is to write out | |
| and read back in this kind of data we | |
| like working with okay how about this | |
| anyone recognize this yeah this is a | |
| JSON that's been read in as a string and | |
| we can't really work with it just yet | |
| but we have this function in the closure | |
| data Jason's namespace read stir that | |
| lets us read this in and get that | |
| closure map we want to work with how | |
| about this this one's a little trickier | |
| yeah exactly this is what you get if you | |
| slurp in a CSV file now we have a way to | |
| read in CSV files but notice you don't | |
| get a | |
| exactly what you want because it reads | |
| in that first row which was meant to be | |
| header information sort of as its own | |
| row so maybe this isn't exactly what you | |
| want but it's at least a good start | |
| right once we get this into our closure | |
| format we have ways of working with it | |
| massaging it into the map format we're | |
| looking for and this everyone knows this | |
| right so this is XML read in as a string | |
| and again we have a way to bring it into | |
| closure and work with it what we get | |
| back is some sort of generic tree | |
| structure that then we can work with and | |
| further refine it into what we want now | |
| the good news is that most of the time | |
| we're working with one of these standard | |
| formats we're working with Eden | |
| hopefully or possibly JSON CSV XML you | |
| know I mean what at least 90 percent of | |
| the time but these are not the only | |
| things you're gonna encounter | |
| what if someone gives you a file that | |
| looks like this I mean who would who on | |
| earth would represent a map this way | |
| that that's kind of a dig I guess but | |
| the I mean this is this is how Scala | |
| represents maps and and the point is | |
| that different communities represent | |
| their Maps differently or what if | |
| someone hands you a bunch of cave data | |
| in some kind of unusual exotic format | |
| that you know kind of looks almost like | |
| JSON if you look at it funny but it's | |
| not quite JSON or what if you want to | |
| work with you know like a Python config | |
| file or what if you want to make your | |
| own programming language or your own DSL | |
| for something all of these are things | |
| that you want to as quickly as possible | |
| get them into your closure Eden format | |
| so that you can work with them and do | |
| things with them and those last three | |
| examples by the way are all problems | |
| that were solved by actual users in the | |
| closure community with the insta parse | |
| library so now is the opportunity to | |
| kind of say | |
| way and start talking about insta parse | |
| but first I want to outline a couple key | |
| concepts so for the purposes of this | |
| talk I'm defining a parser to be a | |
| function that takes a string as an input | |
| and produces closure data as an output | |
| so all those things we saw before the | |
| you know the read XML Strunk ssin the | |
| read CSV function those are all examples | |
| of parsers and the idea is we want to be | |
| able to create parsers for these other | |
| kinds of formats well to understand how | |
| to create a parser first we need to ask | |
| the question how do we describe the | |
| structure of data well we can take a cue | |
| from automata theory in computer science | |
| automata theory describes two very | |
| important classes of data there's the | |
| kind of data that can be represented | |
| with regular expressions and those | |
| happen to correspond to data that can be | |
| processed with a state machine and then | |
| we also have this wonderful this | |
| wonderful language for expressing | |
| context-free grammars which is another | |
| class of which describes another class | |
| of data that can be processed with | |
| something called a pushdown automaton | |
| now the good news is that we have great | |
| support for regular expressions built in | |
| just about every modern language however | |
| there's many kinds of data that cannot | |
| be expressed well with a regular | |
| expression but can be expressed with a | |
| context-free grammar and unfortunately | |
| we don't have very good support in our | |
| languages for context-free grammars at | |
| least not that same kind of rich support | |
| that we have for regular expressions and | |
| I think that's kind of a shame because | |
| when a context-free grammar describes | |
| your data it automatically is also | |
| describing a tree structure that is in | |
| that data and that's called the | |
| derivation tree I literally walked over | |
| to my shelf for this slide and I pulled | |
| off the automaton | |
| book off the shelf flipped it open and | |
| open it up to the first context-free | |
| grammar I saw and copied it down and | |
| then in the book there is a picture of | |
| the derivation tree for that grammar for | |
| that particular string a a VBA a so you | |
| the how many of you have never seen a | |
| context-free grammar before it's okay so | |
| you know not not everybody's seen it but | |
| the basic idea is it's a series of rules | |
| and usually the implication is that the | |
| first rule is kind of your starting | |
| point so we have this label s and the | |
| first thing is a rule saying you know s | |
| is a and then the description on the | |
| other side and the vertical bar means or | |
| and the other things well I'll get into | |
| that a little bit so we've got two rules | |
| here and we see the tree structure of | |
| how you can sort of prove that this | |
| grammar fits that string now that | |
| example was just this kind of arbitrary | |
| you know a textbook example of a a B ba | |
| now that's not the kind of data we | |
| really work with right so I want to at | |
| least convince you that grammars are | |
| used in the real world to describe | |
| actual data this is from a specification | |
| for email addresses I mean who knew that | |
| email addresses were that complicated | |
| right but it took a couple people yes | |
| really annoying to validate it email | |
| addresses because it turns out that the | |
| universe of allowed email addresses is | |
| much broader than what you would think | |
| and to capture all those nuances really | |
| requires you know it's not something | |
| that can be described adequately with | |
| just regular expressions you need a | |
| context-free grammar to describe that | |
| okay so now we're ready to get into what | |
| is insta parse specifically and I like | |
| to think of insta parse as a really | |
| lightweight tool for converting | |
| context-free grammars into an executable | |
| parser one of these functions that will | |
| let you convert a string into a tree | |
| structure that you can work with in | |
| closure | |
| so going back to that example that I | |
| pulled from the automaton book on my | |
| shelf on the upper right corner you can | |
| see what I did is I actually just typed | |
| the context-free grammar into insta | |
| parse fed it to this function in the | |
| insta parse neck core namespace which I | |
| have aliased here is insta so there's a | |
| function they're called parser that | |
| takes grammars and returns a parser so I | |
| wrote down the context-free grammar | |
| passed it to the parser function and got | |
| back a function which I named automata | |
| book parser and you can see when I apply | |
| automata book parser to that exact same | |
| string that was in the example in the | |
| book I get back some sort of closure | |
| tree structure if you have trouble | |
| visualizing it from there there's | |
| actually a function built in insta parse | |
| Club visualize and it produces the tree | |
| that's in the lower left corner showing | |
| you what the tree actually looks like | |
| and it's got some extra information in | |
| there but you can see that the tree | |
| structure that it produces is exactly | |
| the same as the one that was shown in | |
| the textbook that's pretty nice to be | |
| able to just put this in and get | |
| something out that you can work with | |
| like this is great now my first version | |
| of this talk I have to admit was like | |
| twice as long as it needed to be and I | |
| was planning to spend a lot of time | |
| giving sort of a tour of the features of | |
| insta parse but I realized when I had to | |
| sort of pare things down to a reasonable | |
| length of time that there's already a | |
| really detailed tutorial about insta | |
| parse on github on the github site and | |
| so I'm not gonna make this about you | |
| know just showing you all the features | |
| of insta parse this is talk is going to | |
| be a little more about the | |
| implementation events to parse but I do | |
| feel like there's at least a few key | |
| features you need to know about so these | |
| are the three features that I think | |
| really helped make instapass a | |
| particularly nice lightweight tool for | |
| working with context-free grammars so | |
| first there are three ways to describe a | |
| grammar in insta parse most libraries | |
| especially in the closure ecosystem | |
| allow you to create a grammar using kind | |
| of a combination of functions and data | |
| that's often called the Combinator | |
| approach insta parse lets you do that | |
| but on top of that you can also just | |
| enter in these two syntaxes that are | |
| very popular for describing context-free | |
| grammars ebn f syntax and a B and F | |
| syntax and I really think that's gone a | |
| long way towards making insta parse feel | |
| like I said kind of as lightweight as | |
| regular expressions although I guess | |
| some people would argue how lightweight | |
| our regular expressions but it at least | |
| is is like gives you that feel that you | |
| can kind of enter in this notation | |
| that's very familiar also insta parse | |
| can produce the two most popular formats | |
| for expressing trees enclosure and when | |
| it produces these trees that | |
| automatically labels the nodes of the | |
| tree with the rules from your grammar | |
| the rule names from the grammar finally | |
| and I think this might be one of the | |
| most important features of insta parse | |
| is it lets you work with any | |
| context-free grammar and that actually | |
| turns out to be relatively unusual most | |
| parser libraries can only handle a | |
| certain subset of context-free grammars | |
| and it requires a fair amount of | |
| specialist knowledge to figure out how | |
| to take your grammar and turn it into | |
| something that this particular library | |
| can process insta parse is relatively | |
| rare in in that you can really put in | |
| any context-free grammar and it just | |
| works so | |
| one of the things I really want to | |
| address here in this talk is how does | |
| that sort of magic happen what is it | |
| that insta parse does that these other | |
| libraries aren't doing that lets it | |
| handle any grammar and I'm going to | |
| focus specifically on something called a | |
| left recursive grammar because that's | |
| something that other languages don't | |
| handle well | |
| first I need to explain to you for those | |
| of you who aren't quite as familiar with | |
| grammars the two main concepts in | |
| grammars is this notion of alternation | |
| so when you see that vertical bar that's | |
| telling you you know that's sort of | |
| defining that's like the word or so I'm | |
| looking for the letter A or the letter B | |
| that's alternation concatenation when no | |
| symbol appears is saying I'm looking for | |
| the letter A followed by the letter B | |
| and those two concepts are really the | |
| main ingredients in grammars there's a | |
| few other things but they can | |
| technically be built out of those so the | |
| grammar that I'm gonna focus on here to | |
| sort of show you how insta parse does it | |
| where other parser libraries would kind | |
| of break down is this left recursive | |
| grammar this is probably the simplest | |
| possible one it's the rule S is the | |
| letter A or the rule s followed by the | |
| letter A | |
| it's called left recursion because the S | |
| occurs on the left side of its | |
| concatenation just to give you an idea | |
| of how it's supposed to work and how | |
| insta parse handles it on the upper | |
| right I have entered that grammar and | |
| insta parse and we can see that if you | |
| feed the string AAA to that parser it | |
| successfully generates the proper tree | |
| structure which I've shown both in the | |
| closure code and the actual kind of | |
| visualized tree of what you get out of | |
| that | |
| now most libraries use a technique | |
| called recursive descent recursive | |
| descent sort of used these parsing rules | |
| as a bunch of mutually recursive | |
| components that call each other as they | |
| attempt to resolve the parse the problem | |
| is a recursive descent does not handle | |
| these left recursive grammars here's | |
| kind of at a high level why it doesn't | |
| work you can imagine stepping through | |
| the process like tracing through what a | |
| recursive descent parser would do with | |
| the string AAA it says okay well first I | |
| got to call this you know my overall | |
| rule is the rule s and I want to start | |
| from the very beginning of the string | |
| index zero and I want to do this parse | |
| well the rule s expands to a or s a so I | |
| got to do that parse starting from the | |
| beginning of the string well this is an | |
| or so I have to try both possibilities | |
| so first I'm gonna try the a parser | |
| starting at index zero and that works it | |
| succeeds there is an a at the beginning | |
| of the string but that's not enough to | |
| consume the whole string we need to keep | |
| going explore the other scenario the | |
| other scenario is s followed by a and | |
| well if you have a concatenation like | |
| that the first step is to try s starting | |
| from the beginning of the string and now | |
| we're caught in an infinite loop right | |
| so what I want to do now is kind of talk | |
| about how insta parse handles this and I | |
| know some of you in the audience | |
| probably you know have no interest in | |
| knowing all the details of how a parser | |
| library is implemented and that's fine | |
| but I hope you'll bear with me because I | |
| really think there's some big ideas here | |
| in the implementation of insta parse | |
| that could actually be applied to other | |
| programming paradigms so stay with me | |
| I'm going to sort of describe it at a | |
| high level and I think you'll come out | |
| of it with some interesting ideas so the | |
| engine that drives insta parse is | |
| something called the gll algorithm and | |
| even though it's not described this way | |
| in the literature I tend to think of | |
| this algorithm | |
| as well as a dataflow network really I | |
| think of it as a bunch of nodes that | |
| each represent a parser component trying | |
| to parse the string from a certain point | |
| and other components are listening for | |
| those results and waiting for those | |
| results to be transmitted to them and | |
| that's how I think of it as a network | |
| now as I mentioned there's these two big | |
| concepts alternation and concatenation | |
| so let's sort of look at how that would | |
| work in this dataflow network sense so | |
| if you have a parser a or B that's our | |
| alternation pattern basically it's gonna | |
| set up and say okay I want to start off | |
| the parser a and I want to start off the | |
| parser B and I'm gonna listen for the | |
| results when you find some results come | |
| report that back to me | |
| so that's the alternation they're pretty | |
| straightforward now the concatenation | |
| patterns a little trickier and the idea | |
| this isn't quite right but the idea is | |
| that if you're looking for a followed by | |
| B you start off a node that says okay I | |
| want to do parser a starting from the | |
| beginning of the string starting from | |
| index 0 when you get a result hand that | |
| off to the guy who follows that which is | |
| parser B so I'm going to start looking | |
| for parser B starting at the next index | |
| index 1 and when he succeeds then notify | |
| me back then you've successfully found | |
| an a followed by a B now the reason why | |
| this doesn't quite work is because in | |
| this particular example we know that the | |
| letter A is always one character long so | |
| we know that this B parser is always | |
| going to start looking one character | |
| later but in general we don't | |
| necessarily know how long the first | |
| parse result will be so we have to use | |
| something I call the cat listener | |
| pattern so the cat listener pattern | |
| basically says we need to create this | |
| object that is going to listen for that | |
| first thing to complete that a parser | |
| needs to complete and I'm going to be | |
| listening for that and when a is done I | |
| look at how much he consumed and then | |
| I'm gonna kick off the beat parser | |
| starting from that index and reporting | |
| back to the main guy the one who started | |
| it all so just to understand my notation | |
| here and the cat listener I used that | |
| triangle just to kind of denote that the | |
| cat listener knows that when he gets a | |
| result that a is done but the beast | |
| still needs to be processed you can | |
| almost think of it kind of like a | |
| continuation the the dotted line the | |
| dashed line is something that no values | |
| actually travel along that's just there | |
| to show the cat listener knows who | |
| initially created him and when he moves | |
| on to do that second when he starts the | |
| node to do the second parse he knows who | |
| need that result needs to get | |
| transmitted back to okay now these | |
| individual nodes in the network how do | |
| we program those what kind of model are | |
| they're using and it's almost like the | |
| publisher subscriber model but with a | |
| slight twist so usually when we think of | |
| the pub/sub model for data flow we | |
| imagine it a lot like a magazine | |
| subscription so if I subscribe to a | |
| magazine I expect them to send me all | |
| the issues from this point forward so | |
| the kind of model we're gonna use though | |
| is a little bit different the idea is | |
| that when I subscribe to this magazine | |
| I'm basically saying send me all your | |
| back issues and then start sending me | |
| the new stuff also and it turns out that | |
| this is the kind of node we need for | |
| this particular network and it's | |
| something you might want to think about | |
| using in your own programs when you see | |
| how it's useful here programming that is | |
| quite easy the each of these nodes | |
| basically just tracks who is listening | |
| who needs to know these results and what | |
| results that's found so far for this | |
| parser component at this particular | |
| point in the string and when a new | |
| result comes in well that's really | |
| obvious we just forward that information | |
| to all the listeners but we also have to | |
| keep track of it so that if a new | |
| listener comes in we can send to that | |
| new listener all the old results okay so | |
| now we're ready to actually get in and | |
| do kind of this high-level you know | |
| understanding how insta parse would | |
| handle that particular | |
| left recursive grammar with the input a | |
| a so we start off with something that I | |
| call the top listener it's job is to | |
| start off the parsing process listen for | |
| full results and when it hears full | |
| results transmit that back to the user | |
| so it start it says ok that top level | |
| rule is s so I'm going to start off the | |
| rule s starting from index zero and I'm | |
| listening for results and that little | |
| notation there as indicating right here | |
| is indicating that only complete parses | |
| need to be transmitted up to the top | |
| listener now the s parser expands to a | |
| or s a so it creates that parser and | |
| it's going to listen to it now I talked | |
| about how insta parse automatically | |
| labels all the nodes in the tree with | |
| the rule name so when values flow from | |
| here to here they have to get labeled | |
| with that s label now this is the | |
| alternation pattern right we have an A | |
| or s a so we spin off to other parse | |
| nodes a and s a starting from the | |
| beginning of the string and I'm | |
| listening to both those results now this | |
| is effectively happening asynchronously | |
| and that's the key you know one of the | |
| key differences here is usually in | |
| recursive descent style strategy we're | |
| calling one of the things in the | |
| alternation and it's a blocking call we | |
| wait for the result and we get that | |
| result then we try the other possibility | |
| but we're spinning both of these things | |
| off asynchronously and just waiting and | |
| listening for the results so we don't | |
| know which order these things are going | |
| to be processed for the moment I'm going | |
| to explore the rightmost node that's the | |
| concatenation pattern right s followed | |
| by a so we have to do that cat listener | |
| thing I talked about earlier so we | |
| create this cat listener this | |
| continuation node that's going to listen | |
| for the S parse and it knows that it | |
| needs to follow up when it gets | |
| something by looking for the a parse now | |
| one thing that's kind of interesting | |
| here is there's already a node in our | |
| work for the S parser starting at index | |
| zero so there's no need to create a new | |
| one here we just listen to the one that | |
| already exists in our network okay now | |
| we can go down to the lower left the | |
| lower left is actually a node that can | |
| do something not just add more stuff to | |
| the network it's looking for the | |
| character a at the beginning of the | |
| string and it finds it so it produces | |
| this result saying hey I found the | |
| letter A and I've consumed one letter so | |
| far that information gets transmitted up | |
| to the alternation node which in turn | |
| gets transmitted up to the S node and | |
| gets labeled in the process that | |
| information gets relayed to the cat | |
| listener and now the cat listener has to | |
| do that extra work that it does spinning | |
| off a new node to do the remaining part | |
| of the parse so this is a little tricky | |
| so I want to make sure this is clear | |
| this new node the way it's created this | |
| a right here comes from the second part | |
| of the cat listener the one it's going | |
| to be looking for the a at index one | |
| because that's how many letters were | |
| consumed so it's looking at that number | |
| to get that the result that was created | |
| so far becomes this label along this | |
| flow path this value that's going to | |
| need to get prepended to any result | |
| that's discovered by this parser and | |
| this dashed line here was the thing that | |
| sort of remembered who was the original | |
| creator and that's going to be the | |
| destination for this arrow so all the | |
| things about this node are constructed | |
| from information that is available to | |
| this cat listener okay well again this | |
| is a node that can do something right | |
| away and it says yes there is a letter a | |
| at index one so now I've consumed | |
| another letter for a total of two | |
| letters that information gets | |
| transmitted along that path with that | |
| value prepended and that gets reported | |
| back to that alternation node | |
| which in turn flows up to the original s | |
| Snowden gets labeled in the process and | |
| now we have a full parse the and we know | |
| it's a full parse because we've consumed | |
| two letters and the string is two | |
| characters long so that flows up to the | |
| top listener it also flows over to that | |
| cat listener but it doesn't matter at | |
| that point because it's exhausted the | |
| string so the cat listener is not going | |
| to try to do anything with it so the top | |
| listener now has a result and this is | |
| the piece that's going to be reported | |
| back to the user so we have our parse | |
| now I happen to demonstrate this in | |
| terms of showing the right node before | |
| the left node down here in the | |
| alternation but think for a moment about | |
| what would have happened if the left | |
| node node result had gotten computed | |
| first so this result would have flown | |
| would have flowed up to the s parser but | |
| that cat listener wouldn't have been | |
| attached yet then this one comes through | |
| and starts up that cat listener node | |
| that's why remember I said earlier that | |
| values need to old values need to be | |
| relayed to new listeners that attach | |
| that's why is because if we didn't do | |
| that then if this result got here before | |
| the listener was attached that listener | |
| would never know about it | |
| that's why that's important okay now I | |
| promised for those of you who weren't | |
| particularly interested in parser | |
| implementation that there was a big idea | |
| here worth knowing so let's kind of | |
| reflect on what we've seen what I think | |
| is the big idea here is that synchronous | |
| function calls and recursion has this | |
| potential to lead to infinite loops on | |
| the other hand if you use asynchronous | |
| calls and dataflow you have the | |
| potential to get a more robust algorithm | |
| and I actually found this to be a really | |
| big surprise when I started working on | |
| this I have always thought of dataflow | |
| as more being about a way to organize my | |
| program and a slightly more flexible or | |
| clear way I never really thought about | |
| it as something that might actually give | |
| added | |
| algorithmic capability I mean that | |
| really never occurred to me before so | |
| that's what I think is one of these big | |
| ideas here I think I can safely predict | |
| that over the next few days you're going | |
| to be hearing a lot about asynchronous | |
| channels data flow right all these | |
| things are things that are going to come | |
| up a lot here at the closure conference | |
| that's really hot right now and I hope | |
| that when you hear those sorts of talks | |
| over the next couple of days you keep | |
| this in mind as an example of how this | |
| can actually give you new power so I | |
| always think it's kind of interesting to | |
| hear a little bit about how open-source | |
| libraries came about so I want to just | |
| take a moment to tell you about the | |
| story behind insta parse you might | |
| assume that I use parsing really heavily | |
| and my job or you might assume that I'm | |
| just really passionate about parsing and | |
| it turns out that neither of those is | |
| actually the case the true story behind | |
| insta parse is it's actually a | |
| father-son bonding story so some of you | |
| may already know this but I actually | |
| homeschool my kids and in part that's | |
| because I am deeply passionate about | |
| math and computer science education and | |
| I really wanted to be intimately | |
| involved in that aspect with my kids and | |
| my son in particular really took an | |
| interest of programming and I started | |
| him very young on first scheme and then | |
| a closure and from age 8 | |
| I was incorporating college-level | |
| computer science material into his daily | |
| lessons well as you can imagine by now | |
| he's already a very very sophisticated | |
| programmer but I kind of consider it my | |
| responsibility to keep coming up with | |
| new challenges for him new things that | |
| will really stretch his capabilities so | |
| last year when he was 14 I called him | |
| over and I said Alex we need to have a | |
| talk today is the day you become a man | |
| today you're gonna learn about monads so | |
| as part of teaching them about monads I | |
| gave him an exercise in writing a | |
| monadic parser Combinator library that's | |
| actually a relatively standard exercise | |
| to kind of get your head around monads | |
| so he did this parser Combinator project | |
| and I was playing around with it looking | |
| at it and you know it was well done but | |
| I was really struck by that inability to | |
| do left recursion you know it was it was | |
| irritating and I thought to myself | |
| surely someone has solved this by now | |
| someone must have solved this so I went | |
| asking around people I knew people | |
| online who had written parser libraries | |
| trying to find out more about how to | |
| tackle that eventually I found a pointer | |
| to this paper about the GL algorithm so | |
| I decided to do what all good teachers | |
| do I handed it to my son and said go | |
| figure out how to write this in closure | |
| so he did that and he implemented in | |
| closure and as I was playing around with | |
| that I was really struck by how much | |
| more freeing it was I really was | |
| noticeably more enjoyable to work with a | |
| library that could understand any | |
| grammar so I thought this would be a | |
| excellent opportunity to role model the | |
| process of going that last mile to turn | |
| something into a library that's usable | |
| by the community so we talked about hey | |
| you want to just make this alive really | |
| should we make this a library and put it | |
| out there yeah let's do it | |
| so we decided to do that together I kind | |
| of took over the codebase and worked | |
| mostly on optimizing it a little bit | |
| brighting the documentation we work | |
| together on the front ends I wrote the | |
| EB NF front end heroes a BNF front end | |
| it was it was a collaboration and it was | |
| a lot of fun and that's the true story | |
| behind inste parses we really just did | |
| it for the joy of it now I know some of | |
| you probably did come here to learn a | |
| little more about | |
| how to use instep arse versus how to | |
| implement insta purse | |
| so we have a little bit of time here | |
| what I want to do I again I'm not going | |
| to just show every feature but I think | |
| it's useful to understand the overall | |
| sort of workflow the experience of what | |
| it's like to work with insta parse and | |
| hopefully that'll motivate you to go off | |
| and read the full tutorial on github so | |
| the basic process with insta parse and | |
| I'll go into each of these steps in a | |
| little more detail is first you just | |
| write down your grammar and then you | |
| play around with it see how it looks you | |
| figure out what information you want to | |
| hide and then you figure out how you | |
| transform that tree into the actual | |
| thing you want so going back at the very | |
| beginning of the talk I showed that | |
| Scala map format so that's I mean so far | |
| we've been looking at all these grammars | |
| that are AAA BBB AAA and I know that | |
| gets a little mind-numbing so here's a | |
| slightly more real-world example it's | |
| it's still simple enough you could | |
| tackle it with other techniques I | |
| understand but it's at least a little | |
| more real so what we do is we start by | |
| writing down the grammar and by | |
| convention usually the top the first | |
| rule is kind of a top-level rule we're | |
| defining a map what's the rule for a map | |
| well it's got the string map a left | |
| paren and a bunch of key value pairs | |
| separated by commas that's basically | |
| what the first line says what's a key | |
| value well it's a string and then an | |
| arrow and then another string what's a | |
| string well we can define that with a | |
| regular expression so you can actually | |
| use regular expressions in insta parse | |
| to define your tokens then we feed this | |
| to the parser function and the insta | |
| parse namespace and I have this little | |
| flag here Auto whitespace standard it's | |
| a relatively new feature in insta parse | |
| for grammars where the whitespace really | |
| doesn't matter if it did matter you | |
| would specify the whitespace as part of | |
| the strings in your grammar rules and we | |
| plug it in and we see what we get and | |
| this is great you know this is rep | |
| lorina development we get to try our | |
| grammar see how it all works out | |
| keep refining it and we basically get | |
| the structure that we want but there's | |
| these extra things in there like there's | |
| the word map and that left paren it's in | |
| there because those were part of the | |
| structure but once we've got the overall | |
| structure we don't need those words | |
| anymore we don't need that left paren as | |
| part of our tree so we come to step two | |
| and insta parse we just put angle | |
| brackets in our grammar around anything | |
| that we want to hide that we don't | |
| really care about appearing in our tree | |
| so I've put angle brackets down below on | |
| around the word map and around the paren | |
| and around the arrow and now when we | |
| rerun it you can see those things are | |
| missing from the tree this is pretty | |
| good this is you know getting really | |
| close to what we want but ideally we | |
| want to get it to an actual closure map | |
| right that's our end goal well insta | |
| parse includes a function called | |
| transform and I mean you can use | |
| whatever tools are you know you have all | |
| these rich closure functions and tools | |
| to manipulate data you can do this | |
| however you want but you can use the | |
| built in transform function which lets | |
| you put for each node type in the tree a | |
| function to be applied to the children | |
| and this is done in kind of a bottom-up | |
| transformation to the tree and when you | |
| plug in these particular functions | |
| associated with these keywords then you | |
| get back the actual map you're looking | |
| for so that's the basic idea you want to | |
| get from Scala maps to closure Maps | |
| here's three easy steps step one was | |
| create the grammar step two was hide the | |
| things you don't care about with the | |
| angle brackets and step three is either | |
| use the built in transform function or | |
| whatever closure functions you want to | |
| get this into the final closure form | |
| that you're looking for okay time to | |
| wrap things up two main ideas here from | |
| this talk first is just telling you a | |
| little bit about insta parse insta parse | |
| is a lightweight tool for converting | |
| context-free grammars into an executable | |
| parser | |
| and those parsers can be used to convert | |
| strings into data but the other big idea | |
| from this talk is that under the hood | |
| insta parse in my opinion is a really | |
| great example of the extra algorithmic | |
| power you get when you use asynchronous | |
| calls and data flow I'd like to finish | |
| off with something I saw on the IRC | |
| channel I actually have absolutely no | |
| idea who these two people are I hope | |
| they don't mind my using this in the | |
| talk I figure since this out there in | |
| the public on the internet it's totally | |
| a fair to use it the point I wanted to | |
| make with this slide is that when when | |
| Alex and I started out making insta | |
| parse we were genuinely trying to make a | |
| tool that people would find useful but | |
| what I think has taken us by surprise | |
| and really delighted us is that for many | |
| people it seems to not just be a tool | |
| but it's something that has suddenly | |
| made for them made grammars and made | |
| parsing more accessible and more fun I | |
| mean who would have ever thought parsing | |
| is fun you know whoa and honestly out of | |
| all the things that has happened with | |
| insta parse the fact that people are | |
| using it to find parsing this fun I mean | |
| that's honestly what we're most proud of | |
| so thank you very much |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment