BNF in Real Life – Intro to Computer Science


[Sarah] This question comes from Crazy Puff. “Can you give some examples of how Backus–Naur Form is used in practice? For example, being a formal way to describe a language, it seems that BNF might find some use in creating compilers or interpreters or other tasks involving teaching a computer to understand text. Also, BNF let’s you go from the abstract form to the concrete form, but it seems like in practice you’d more often want to go in the opposite direction. For example, given a concrete example of a Python statement, you’d want to know how the interpreter parses it. So, Dave, how would you do this?” [Dave] Thanks for the question, Tracy. That’s a great question. We’re using BNF in this class to understand languages to see how we can construct the expressions in Python. But grammars are also used by the interpreter to break the strings that we put in into their parts. When you write a Python program and you run that in the interpreter, the interpreter has to figure out what the things are. It has to figure out is this an assignment expression? Is it a variable? Are these parts of a number? Is it a string? All the things that we’ve seen in unit 1 and in later units are constructs in Python, and we need the grammar that’s built into the interpreter to break that string into its parts. That is part of what’s implemented, and when people implement interpreters or compilers, they usually do it by starting by writing a grammar. Then there’s a tool that takes that grammar and turns it into a program that will break the string down into its pieces. If you take the follow-on course to this–if you take CS262 programming languages course– that talks a lot more about how interpreters actually do that. There are lots of other uses of grammars besides just breaking down programming languages into pieces. Some are in the generative sense where you start from the grammar and produce strings. An interesting example of that is guessing passwords. There was a group at Florida State that looked at how to create passwords. First you learn a grammar from a set of passwords you might have. Then you can create more passwords, and you can use this as a way of guessing passwords or if you want to measure how strong a password is to estimate how hard it would be to produce that password from this grammar. There are lots of interesting uses of grammars to produce strings. The more common use in programming languages is where we use the grammar to break an input which is all one long string of text, that’s your Python program, to turn that into the components of that program using a grammar.

One Comment

Add a Comment

Your email address will not be published. Required fields are marked *