The soul of the beast: Everything about Python’s grammar - Pablo Galindo Salgado - PyLondinium19

so pablor he again another member of our team I remember Pablo joining is a pre FST many years ago now this is very scary so with great pleasure his Pavle talking about the soul of the beast awesome so thank you very much for coming so in this talk I would like to go deep into interesting question which is what makes Python Python right so we have two main parts that people recognize usually as Python one is the interpreter which is normally when you type Python it probably see Python the one who will appears which is the default implementation but the interpreter can be done in many languages as well we have other implementations for example in Java like JSON or item Python so that part can actually so see passing is not technically what would makes Python Python so there's another part what people usually recognize as Python which is the grammar right the the kind of problems you write and expression as you do so in this particular talk we are going to Center on all the world surrounding that particular aspect of the language and how tiny technical details of how is made up will impact a lot the code you write so I will start with an interesting question so the question is is this bollocks Python code will be like 10 seconds who thinks is Pollock Python code like crazy huh who thinks is in Bali well this doesn't add up right ok so actually it is Bali Python code and this is the ast of this thing so you don't need to understand it just that this means that python is able to parse this code so some some clever stuff like this is actually like - some bigger man and this is the lips which thing so but it was simply something horrible right and yeah that what with this what I want to say that the code that people normally recognize as Python is actually a tiny subset of what the language actually allows and there is some very twisted ways of writing valid Python programs right and in this talk we are going to try to understand how these rules are actually layout and with impact they have okay so so let us start with some grammar basics right because we are talking about the grammar so the grammar is basically a document that explains what is ballot pie right so let's start with how this document is described so we are going to have rules right and the rules are basically described as a name for the rule with social production and then some description of what the rule is so you have to be in mind that with the grammar describes exactly how to generate Python programs so the parser actually what is going to do is that is going to grab the grammar and it's going to sort of reverse engineer so in the opposite question which is given a particular text is dissipation program that can be generative to the grammar but you have to remind that grammar is laid out in a way it actually makes it very easy to say okay give me a random Python problem so in that way we will have rules here and then rule descriptions on the second side so we can have many descriptions for the same rules so this basically means that this rule can actually produce these two things instead usually instead of doing in this way we use the or operator so this means that this rule can be this chunk or this other chunk we will also have the plus sign so the black sign means one or more this means that this rule is one letter a or more than one it's very similar to regular expressions but it's actually much more powerful than them but you can familiarize more or less how to describe this thing if you have in mind regular expressions so in the same way we have the asterisk which means zero or more then we will have these square brackets which means this is optional so we will have something like this rule means that you can have an a or this particular other rule and this particular other root can be optional in that particular example and then so this is the actual so now that we have more or less but in mind this is the actogram a chunk of the ecto grammar of Python right so let's see how we interpret this thing so we're starting the first rule which is file input and then we say that basically a file what you can write in a file is start with a new line and then like zero or more statements and then the end of the file so you say okay what is a statement so then you go here and you say okay I statement is a simple statement or a component statement and then you say okay what is a simple statement I said okay it's a small statement or cetera editor and then in the component streaming we see things that we more or less recognize already right like if statement while statement so all of these are things that are possible and it is that the whole document which this is only a subset will basically describe what is possible in their Armour and then we have to distinguish two possible inputs here so one is let's go here yeah so one of these is what we call a terminal so a terminal here is a word which is surrounded by quotes this mean like little it is worse so for example for the wireless timing we expect the world while and then we have this non terminal so if you mind this grammar as a tree the terminals are the leaves and a non terminal any intermediate node right so a non terminal basically something that you need to expand it basically refers to another rule so one thing which is not super important here but one thing is that if if the basically the grammar is written away that is sort of substitution so basically you have here a rule and then you have always the description of the rule at the end it's called a context-free grammar this other definition for a but the idea that that simplifies a lot of things and maybe is that we have to be we'll see later how this thing play but it's very important to this thing with these two terms because the words that you can write at the beginning of the rule or the words that can start the rule will impact a lot how how certain structures are allowed in cpython so I skip this this slide so this is another part of the grammar so we will see the statements that we mention before right so we saw that component statement can be any of these and then we start seeing so for example an if statement is the word if followed by something that evaluates to a condition or an object you may that can be true or false then the column and then this suite is basically a block what people recognize usually as a block it's called here in the grammar suite and then you have the leaf and all the stuff so it is that we have this document right with this kind of rules which basically describe what is what is possible to write and what is not so let's analyze the impact that it has or the particular things that cpython imposes over this so particularly the simple grammar is another one grammar so let's see what is this so another one grammar it's a grammar that is part left to right do the leftmost derivation which means that you analyze first the talking which is on the on the left and the you star spanning from that and this is the most important rule which is that when you are parsing like the parser witness analyzing a particular program is comparing with the Rama can only look one token on the on the like one Tok is not a hat which means that if I need to distinguish a rule like mind you have a particular rule which has two possibilities like two productions and then I need to distinguish which one of the two is the correct one so for doing that I can only look the next token in the input right so for example if you are doing something like for X in range something and I find the word for if I need to distinguish two different productions I can only look one token ahead with will be these X in example eyeball so it turns out that this is a very well-known problem how to solve like this actually leads to very simple parsers but the Python grammar has two more particularities that may the parts are even simpler for the ones that know more a bit of grammar theory basically this is a partially generated with a partial table with what is known as the first cells and the follow sets more on this later but particularly we have two more things here one is that the Python grammar doesn't allow empty productions this means that every rule has to be something that doesn't and in the empty string so an empty production is basically a rule that can be empty and this makes the parts are more difficult because if you have rules that can be empty and you can only look one token ahead then if the rule is empty you need to actually look to so that's what leads to what is called the follow sets so we because we don't need them I know in displaying this tone and then we have another kind of rule which is a bit more lucy and this is not actually enforce but is basically the grammar is laid out in a way which means that in some levels only the last alternative route and have a non terminal so for example we can she oops okay so for example let's see this one so if you see this so the flower stamen so we have break continued return price and dill so you check all of them except jill they start with a non-terminal right so for example break a thermistor with break continuous ten minutes that we continue let's address Adama the only one who actually start with an terminal is deal statement which is here a non-terminal called deal expression so this is more or less layout and this simplifies a bit more how the first sets are layout on and it makes easier to produce the parcel so okay so this is more or less the grammar so let's let's describe what is these first sets so the first sets for a rule for example a simple statement are all the non terminals the rule can start with and this is very important because as we saw before if we are only allowed to look at the next token and we we need to see if a particular rule is valid it will be very interesting to know all the possible tokens that rule kind of start with right because if we have that token and the token is in one of these particular non terminals that are allowed then we know that we are good because it's possible that that rule has the start with that token but if we have a particular token and then we are trying to pass a rule and that rule doesn't start with that token we know that is invalid so we can say that it's a syntax error right so this is what is called the first set and it's going to be very important later so this is the first set of sound of the expression so for example playing can only start with Prine grayskin alistair we raised but simple statement can start with all of these things okay so let's see how the parser works so see Python actually doesn't have a hand written parser it has a parser generator so it's a tool that generates the parser for us from the grammar file which makes it much much more less error-prone because you don't need to manually modify the parser every time you generate more grammar rules so let's see how it works so it's actually a very simple thing so we start with the grammar in extended backwards not form which is the document that we saw before and this will product this will produce non-deterministic finite automata so we'll see what it is basically these things are just control graph flow so you like this kind of drawing when you have nodes and arrows telling you which option you have we'll see some examples and the things that this these initial things are very simple to produce but they are very complicated is full of errors and complexity so the the step that grabs one of these and convert them in with this correlator manectric final automata is basically simplifying it and making it more more easy to to follow so let's see one example so let's say we start with this rule which is the rule for fact right like a plus B a minus B not something right so this is this is the rule so then the first thing that the part the partial generator produces the non-deterministic finite automata which is this controller right so we will study in this state and then we will go down until we start seeing these these tokens so the idea is that you start here and then you read some particular program that is trying to follow that rule and if you are able to go from the state to the end then the rule is correct if you are not able to go to from the start to the end then the rule is invalid so you mind that instead of plus minus and till add you have asterisk right which is not part of this rule in particular so this didn't you kind of follow here because there is no step that has the stage it's actually hidden in power so it's a valid Python program but if you don't look at power for now you can imagine how you cannot follow this in now so this is very complicated because in 30 you can only follow the arrows if one of the tokens is allowed so it for example for the stay for two state eight is very easy to know if you can follow because if you find a minus sign then you can go ahead but if you don't find a minus sign that you cannot follow it and the problem is that we have here in the non-deterministic automata we have some stages which we don't know if we can like follow them or not for example for going for in state zero to state one or two we don't have any particular sign to follow so that is a problem because we don't know if we can wear the rule to transition to the other states or not that's the complicated part of the non-deterministic finite automata so the next step is to produce a deterministic one which is that one so in this case as you can see all the states the all the transition between a state and something is followed by a particular token so for example if one in a state 0 we just need to look on the next like token in the input either plus minus or till and if it's not any of these we say that the rule is invalid if it's one of these then we follow it and we Furr go to state one and state one goes to another rule call factor but as you can see in this particular brew a DFA sorry yeah DFA there is not transition between state and States with our unknown transition but you can see something which is still bad which is for example this node which is here isolated this node is rubbish it doesn't mean anything it just means that when we transform this thing into this thing we produce some things which are either tremely complicated or they can't they basically Travis which has no States so the next step is simplifying the thing into what is called the final defect so basically is removing complexity and removing this this particular node so this is basically what it is is producing this kind of control flow diagrams which are still very complicated with some particular algorithms you transform this to this which is very known and all and from this you run some simplification which is called minimization algorithm and then you produce those here and this this particular diagram is what the parser follows if you think about this is more or less like a hash table or a dictionary so basically during a particular state and then you look at the possible keys here are plus minus or tilde and if you have them in a dictionary or the hostel then you transition to whatever value you have and if you don't you say that the rule is invalid so that makes actually the parser so much so fast because it's basically some sort of hash table look up again and again and again next and these these rules here so for example when you owe to power like the square box in power you have another of these basically describing with a particular sub release so it's basically nested dioramas instead of nested diagrams so the sixth time examples here so for example we can see the roof for comparison so in this example you always will have the the complicated one right a non DFA on the left then the DFA here and the simplified one here so you more or less can can see what kind even if you notice I made the algorithm which is not super complicated I will take a lot of time to explain you can see more or less or you can feel the kind of simplification that the parser start doing so this is for example for comparing things between them this is the rule for like the comparison but with the actual tokens so you will see things that you recognize as comparison operator like note equals less than bigger than so you can see actually how when the rule is actually a bit more complicated the non DFA is actually a monster and this non DFA is actually very well simplify I didn't put the one in the middle because it still it doesn't fit in in the particular screen so we can see more so for example this is the decorator and this is a very very interesting example because you can see actually from a very high point of view what you can decorate so for example in the room for decorative things you can see that integrating functions class the finishes and functions and you cannot decorate anything more because the rule doesn't allow that and again we will see a way of adding things to this so you can play a bit later but you can see how these things are actually even if you don't see the rules and only you see this kind of automata switch on something lower level you can still recognize more or less what is valid or what is describing more of these you have the factor internal we saw before so you can see how here in the non DFA we have still this transition between states and in the like and one we have only transition between the two become numbers and you can see how they they actually much more simplify so I want to show you my favorite one which is this one so this one is the the diagram that parses function definitions which is this monster but don't worry because this is the non DFA right so let's see the simplified version which is much clearer to read this not so this is the most complicated rule but this is a reason is so complicated and this is one of the things we are going to see at the end so the reason it's so complicated is because the way we need to describe this rule is actually fighting the ll one limitation so the little one a lot of people see it as a blessed because they say okay because it's a so simple grammar that has this very strong conditions that make them like very strict then it's very difficult to have like very complicated rules which is good because at the end you want Python to be simple and readable and like not like other languages C++ so but there is a problem which is that sometimes what the user perceives has a very simple rule is actually not that simple or at least you cannot describe it there's another one rule and in that particular case you need to do a hack and you will see many hacks in the grammar which is called full leaf expansion which is literally grabbing all the tree and expand it at the end because you cannot have like these limitations will arise in a way but there is there is a way of solving this limitation which is having a rule full of non terminals and in that way you don't have this problem because you don't need to deal with first because it's all non terminals and the reason this particular rule is so complicated is because this is one of them this is the most complex example of the most beast example okay so let's continue so let's see what limitations on the 11 grammar are so one particular example for example they see let's see these rules so this rule we have is whatever rule and it will start with the word do then some particular sub rule called a building while an expression and then we have another possibility for the rule which is the same style except that it has another rule call B and then we go to the first set we remember are the non terminals at root canister with and we see that a can start with the letter A or the letter B and B can start with a little a or the letter C right then let's say we are trying to parse this input right there you should write that and we want to see if is a correct program in this case we know that is the first choice like the first rule because if we go to the first set this B can only be on the first set of capital A so we know is this particular here right because this a can only can start with a alket sorry with B and we have B so the option B doesn't have been inside so we know it's not B but let's say the user writes that code so now we have a problem because this particular lowercase a appears in both so is this one or is this one so we don't know and this makes the rule ambiguous because you don't know which one of the to write because if you go with all the tokens that the rule can start they share one of these non terminals so when you find this a you don't know which route to choice and this is a problem because this route is embodied in another one and this is the limitation right this is what makes ambiguous do you cool if you have a more powerful parser and then you say ok but in mind that I'm able to like follow and read more tokens from do backtracking then you can distinguish this one or this one but because we are only allowed to look at the next token we we cannot write so we're passing do and then we look at the next token we find a and then we know we don't know what to follow and that's the problem so this happens in C Python so actually it happens a lot so for example this is the rule that describes how to pass arguments how to code functions and particularly I want you to look at this argument rule so let's let's see what the argument is okay so we have test is basically an object so 3 4 X whatever then we have the keyword woman so a particular name equal and an object and then we have a star star like dictionary unpacking and listen package right so this one is actually not not valid because if we look at the first sets of tests so this one it actually contains name so these two are ambiguous because if you are here and you say okay I will I want to choose this one or this one and then you find name you don't know if you choose this one because test also start with name so you don't know which one to follow so this makes these rules not possible but you can still call functions in Python right so how is made so this is one of the first hack we have which is the actual rule is test equal test and this rule allows to through things like list comprehension equal to this comprehension or dictionary comprehension equal to the canary comprehension and then you say wait wait but I cannot write a same Python right so the reason is that we allowed of thing on the parser well the parser is pretty happy with that but when it comes to the ast which is much later in the in the compiled pipeline we say by a way this test actually anything other than just a name like keyword if it's not then say syntax error it's just a syntax error that can happen on the parser but you don't know so little lies that we have another interesting one is the do you know the water separator so the water separator also suffer this so this is the rule for the water separator which is like a particular name The Walrus operator and an object and this has the same problem right because the first set of tests also include name and you say hey but I don't see the pipe right so it's not this or or this thing but you think about is the same case because because this is optional right so if you are saying okay I need to pass this thing or what I actually have this optional path so because you can only look one token and both can start with a word name like a non-terminal name which is any Python module then you know what to choose so again you have the same problem and the actual rule again is this horrible thing and then we force it do it much later as you can imagine this is not very like maintainable and then we have one that Lukas here knows very well so this is with statements right and this is valid Python 3 so in Python 3 you can have multiple context managers in the same with expression so you for handle you can say with a sxb sy and then if you have a lot of these then you say well I don't want to put all of them in the same line so if you want to continue you use you need to use this line break character right which is sort of okay except that this theme really mess with indentation and out of formatter tools like black cannot really format this thing very what so you could do this thing if you allow this thing which is put parentheses around right so you see something like okay so with open parentheses and then you put all your context managers and then you close parentheses this this particular constructed but is it 4 out of 4 matters because they know what is the limited here right except that this is invalid and you say why it sounds like I mean I have seen this thing before right I seen the scene in the streams I say imports right you can say import an open parenthesis and a bunch of things well it turns out that if you analyze the rule which is this one and then you want to allow the parentheses then you say ok so I'm going to write the same rule so with and then I'm going to put two possibilities right the old rule and then I'm going to say open parenthesis the old rule and closed parenthesis right so it's either the rule or the rule in between parentheses so again the point of this is that this is ambiguous because this guy which is the item also kind of start with the open parenthesis so you say with open parenthesis now you don't know if the parentage belongs to because uy3 between parenthesis or because you are riprap grouping with parentheses the whole rule right and this is sad so we cannot improve in that I'd really try okay so you will see right so we have this dual thing in how we square the grammar we have a very powerful and simple way to describe because we have another one restriction and this makes not only the parts are very fast but also very simple to describe but then we have all these weird things because we we want to put some rules that we know they are simple enough for users to use but all these technical restrictions rest it what you can do and I want you to post here and make you think about this because the fact that they ruled the grammar is little one and all these things is they're actually very technical implementation details right like this is something that the user doesn't need to know but this thing which is of the core like three deep down this thing right now is percolating outside right like even if you are not a like writing cpython and you're writing your own interpreter and you want to fulfill Python grammar even if you have the most powerful parser right now you want to run Bali Python you cannot write this which is weird right it's like the implementation detail are portioning something as important as the grammar and and this is like sort of dangerous and like worrying and beautiful at the same time how this tiny technical decisions can can affect so much like what is a white Impala Python program so at the end just to conclude this particular step so with the person produces what is called a parse tree so if you write x plus y following all these DFS and basically the arguing that we saw it produces this particular structure and if you substitute those numbers to the actual rules you will have this right so that 3 plus 4 or 1 plus 14 or something is this particular work which is basically a flattened out version of the diagram that we saw before so this is what is fed to AST and we are going to stop here because we are going to talk asti's so this is when the parser ends so what I'm going to show you right now as a application is how imagine that you want to create a new grammar rule in C Python or in Python right like I won't extend Python for playing array so or or how we core developers actually write new Rama rules so they say you want to write this rule right so you have two objects and then you want to implement the arrow operator which is something that the user can implement right so the user in my in that the user has a class and the class implements underscore underscore arrow on the score underscore and you and that's about something right and you want to allowed to write a Aerobie and it calls this particular function right in the same way when you write a plus B it goes down there ad so first you need to do is up this token to the tokenizer so sorry to the grammar so you go to the grammar then you find the rule describing multiplication division and all the stuff and then you add the arrow here right so we have the star the slash all the things that are allowed and then we say also the arrow so when you add this thing and then you write the parser generator you need to include the token as a valid token right so in you go to this particular file which is in C so we are going to see a lot of sicko and then you say okay there is a new token which is going to be called arrow and we are not explained with token ease at this point so we just define the existence of the token so the idea is if you are ok Shangri two of us know already very fast okay so then you go to the tokenizer and describe how to parse the scene so you find like a minus sign and then follow like the bigger sign and you say okay that's the arrow and you say return the arrow then if you run the token I said you will see that the token I she already is able to parse the arrow so it's actually very simple to do even if you don't understand how I'm doing these things so these three lines here is the only thing you need to do for the ast two parts so you don't need to understand it you just need to say that if you know what you're doing is actually very simple and then finally do the only thing you need to do is implement the actual operator so in this case this is the bicycle for that which means like you find a R or B then pop a poor beat call the function we described in the arrow and then continue with interpreter which is again very simple you know what you're doing and finally you just need to describe that there is something called arrow and right arrow which can be describing the objects which is again these three lines plus the header file and with that you can try this code so you can create a class that implements understand the score arrow and in this case I'm going to map the operator to the other and then you can write this code F like our row B and it basically Maps the function over the list so as you see all these particular ending trainer so if you see all these particular like things make implementing new rules of the Wonder which are right now extremely simple but they carry out all this danger and all this impact on on the language that you see and appreciate so thank you very much I'm sorry for sooo possible you