Name: Functional Parsing - Computerphile
Uploaded: 2020-03-27T16:56:58.000Z
Duration: 22 min 46 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

Today we're going to do some more live coding, and we're going to talk

Transition words & phrases

about something which is quite close to my heart, because I wrote some of the

early papers on it many years ago, and that's something called functional

parsing, or combinator parsing. Before we get started with actual live coding, I

want to begin with the question. And the question is: what actually is a parser?

So for me a parser is a program which takes a string of characters as its input, and

as its output produces some form of tree. And the idea is that the tree makes

explicit the structure in the input string. So that's a bit of a mouthful, so

let's have a simple example to explain what's going on with this. So what we've

got here is we've got a string of five characters -- 2 plus 3 times 4 -- and

that's our input string. But when we look at this we know that that's not just a

random sequence of five characters, it's actually got some structure to it. So in

particular, we've got three numbers here -- 2, 3 and 4 -- and we've got two

arithmetic operators -- we've got the plus and the times -- and one of the things we

learn at school is that the times happens before the plus. So you really do 3 times 4

here, and then you add the 2 on at the end. So that's our input string.

So what a parser does, is it takes a string of characters -- like that -- and it

tries to recognize the structure in the form of a tree. And the tree we would get

from a parser is something like this here. And you see we've got some leaves

in the tree -- the leaves are the numbers 2, 3 and 4 -- and the nodes in the

tree are the two arithmetic operators -- that's the plus symbol and the times

symbol -- and you can see the structure of the tree reflects the fact that we do

the multiplication. First we multiply 3 by 4, and then we do the

addition second. So that's the basic idea of what a parser is: it takes as input a

string of characters, and as output it produces a tree. So it's really a

function -- it's taking as input a string and as output as a tree. So we've seen

what a parser is. It's a function that takes a string as an input and produces

a tree as an output. So now we want to think how can we actually implement this:

how can we implement the idea of a parser? And I'm going to do this in Haskell

today, but it doesn't matter if you don't know anything about Haskell because

I'll be explaining everything as I go along. And actually, nothing I'm going

to show you today is specific to a language like Haskell.

You can do it in any general-purpose programming language. So if you do a web

search for a 'combinator parsing' or 'functional parsing', and then whichever

language you're interested in, you'll find the same kind of stuff which I'm

going to show you today. So it's not specific to the Haskell setting. So

what we're going to do then first, is we're going to define precisely, in our

programming language, what it means to be a parser. We're going to define a new

type called Parser, and it's simply going to be a function which takes a string as

an input and produces a tree as an output. So it captures the very simple

idea of what we are wanting to do -- a parser is a function that takes a string

as an input, and gives the tree as an output, and the arrow here just means

that we have a function from one thing into the other. So this captures the

basic idea of what a parser is. But unfortunately, it's not sufficient to

program with. We need to refine this a little bit to actually write programs

with this. So the first little refinement we're going to make is that a parser

might not consume all of its input. So for example, if we're trying to parse a

number, like 2, we maybe we find the 2, and then maybe we've got some more stuff

left in the input string that we need to parse. And if we want to chain parsers

together, we're going to need to have access to the remaining input string

that we didn't manage to consume. So the first little refinement that we'll make

is rather than just returning a single tree, we're actually going to return a

pair now. We're going to return two things -- we're going to return a tree as

before, and we're also going to return the unconsumed part of the input string.

So that's the first refinement we've made. The second refinement we're going

to make is that a parser may not always succeed. We may be trying to parse a

number, and we don't find the number, we find something else. So we need to have a

way of representing that a parser can fail. So the way we're going to do that, is

we're actually going to make a parser return a list of results, rather than a

single result. So lists in Haskell are denoted using square brackets. So this

simply means that rather than returning one pair of results, we could return zero,

or one, or two, or as many as we like. And the idea is going to be if our parser can't

parse, so it doesn't succeed, we'll return an empty list of results. And if it does

succeed, we'll return a list with one pair -- we'll return a tree,

that represents the structure of the input string, and we'll return the

unconsumed part of the input.  But because we're working with lists here,

we could actually be more flexible.  We could return two, three, or four, or five,

or as many as we like parses. And this is actually quite a good flexibility,

because for some languages the input string may be ambiguous -- maybe we're

trying to parse English, and English sentences don't always have one parse,

they can be interpreted in many ways. So this type here is giving us a

flexibility to return many results if we wanted. We're not actually going to use

that flexibility today, but it's nice to actually have it. So I haven't told you

what the tree data type is here. And that's because I'm actually going to get

rid of that now. Sometimes you may want to return a number, or a program, or some

kind of other structure. So we're going to replace that specific type of trees

by some arbitrary type 'a'. And I'll make this a parameter of my type. This is our

final type, which we're going to work with today. What we're saying is that a

parser whose results have type 'a' is simply a function which takes a string

as an input, and then it gives a list of results. And each result is a pair

comprising a single value of type 'a' -- maybe a tree, maybe a number, maybe

something else -- and then an unconsumed part of the input string. Okay, so this is

our final type. And if you look in any of the articles, or books, about these kind

of parser combinators, or functional parsers, you'll find a type very

similar to this there. It's quite a mouthful again, so let's think about how

we could understand this in a simpler way. And actually, we can write a little

rhyme to understand what's going on with this type. So let me write the rhyme out

for you as a comment. So what we can say is: a parser for things, is a function

from strings, to lists of pairs, of things and strings. This is a little Dr. Seuss

rhyme to tell you what a parser is, or what a functional parser is. And that's

actually how I remember this type. So that's our basic type now. We've seen so

far, a parser is basically a function from strings to trees, but in order to

actually program with these kind of things, we need to refine the type a

little bit. And this is the type we'll be working with today. But you don't need to

worry about the details of it. Just basically think it's a function from

strings into trees, or some other kind of structure. What we're going to do now,

is we're going to load up the parsing library. So I'll start up

the compiler. This is a library, which contains a whole bunch of parsing stuff,

which allows us to program with parsers of this form. And this is a parsing library I

wrote myself. I'll see if I can get Sean to upload it as part of the video.

Subtitles ListPlay Video

Functional Parsing - Computerphile

specific

bunch

sophisticated

recognize