Parsing Explained - Computerphile

How ambiguity is dangerous! Professor Brailsford simplifies parsing.
EXTRA BITS: • EXTRA BITS: How Chomsk...
Angle Brackets: • Angle Brackets - Compu...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com

[@profdaveb6384]

Hi everyone, I mentioned in the video that multiply over the positive integers was commutative but as some of you have pointed out, the more precise issue -- in terms of ambiguity side-effects from differing parses -- lies in the associative properties of multiply and divide . Thus, most languages will interpret 8 * 4 * 2 as being (8 *4) * 2 (i.e. left associative) but, in the case of *, the right associative version: 8 * (4 * 2) gives the same answer . This is not so for the / operation where left and right associative versions give different answers. In the absence of any parentheses, as in 8 / 4 / 2, the compiler's job is to enforce the default of: (8 /4) / 2 , i.e. left associativity, to get the correct result. I'm hoping to explain, at some stage, how compilers can do this .

[@CalvinHikes]

Yeah but your shirt was amazing!

[@iamjimfan]

If I recall correctly, bison the parser generator allow designation of operator left/right associativity. But I am not sure about the inner working of it. After all, my favourite language APL has completely eliminated this headache.

[@profdaveb6384]

Bought from Boden (UK) a few years ago. Sadly no longer available. Thanks for realising that it *is* a shirt - and not pyjamas .....

[@profdaveb6384]

Yes. I'm hoping in a later video to use the yacc (bison) parser generator to show how, by using left recursion, one can enforce left associativity. But you're quite right that yacc also lets you write overtly ambiguous grammars and gives you the ability to specify operator precedence with things like %prec

[@PurplProto]

I wish I went to Notts uni now. You have a fantastic way of explanation!

[@gregfletcher2360]

"the robot stroked two furry dice" --Professor Brailsford 2019

[@vd8642]

I paid £12.99 for that late night film in a holiday-inn.

[@louiscotteta566]

V D underrated

[@TasosAlvas]

But what did the Professor initially program the robot for? xD

[@oisnowy5368]

The 2020 edition will allow people to insert words like "my" and "your" between "stroked" and "two".

[@phisch95]

Deep

[@par5ek]

Every time I watch one of these videos I thank the man that put these great men in front of a camera and made it available to anyone for free. Grateful of being able to meet them and learn so much

[@Gornius]

After watching this, calling "programming language" a "language" makes waaay more sense than before.

[@granadosvm]

First time I see a video from this guy and I liked it very much. He reminds me of those few teachers at college that explained very complex issues in ways that are easy to understand.

[@fuuryuuSKK]

The issue is not commutativity, it is associativity

[@andurilan]

Even further down ( or up ) the line of syntactical translation, it really comes down to contextuality. Do we merge, or do we move? The root of the issue in a nutshell.

[@Richardincancale]

Big thumbs up! I spent months explaining to the language designers of a 3rd generation language in ICL in 1979 that their proposed syntax had loops / ambiguities! We used an automated tool called SAG (Syntax Analyser Generator) that generates a pseudo code for a little FSM to perform the parsing. It also allowed you to call ‘action routines’ to put the syntactic elements on a binary tree on the go.

[@chaoslab]

Always a good day when there is a new Prof Brailsford video on Computerphile!

[@MrAdamkimbo]

This was excellent, very clear informative and interesting. I'd love to see more on this topic. Especially anything to do with the difference between Parse Trees and Abstract Syntax Trees, what they are, and what use they serve. Also, anything on the Shunting Yard Algorithm and its relation to top-down parsing would be great. Thanks!

[@zyghom]

Man, I love your videos, you remind me one (only one) of my teachers - his classes were so cool - like your presentations. Thank you

[@StephenFarthing]

I was a second year undergraduate in 1973 studying biology when I first met BNF. I had to take a 6 lesson course in Algol 60 and the lecturer started off with BNF before immersing us in the language. At the time I wrote BNF off as something I had to get through to complete the module. It was only later I discovered how very useful it is for analysing and learning programming languages (a lot of us back then ended up in computing for paid work, Biology graduates were ten for a penny) I’m even using it now to help me learn Hungarian. So thanks, Prof, for this walk down memory lane.

[@WebMarketingStgs]

I would like to see the bnf for Hungarian!

[@KnakuanaRka]

@@WebMarketingStgs Me too; I’d love to see it in an actual language!

[@allanrichardson9081]

Some textbooks call it Backus-Naur and others call it Backus Normal form.

[@radoslawjocz2976]

Parsing in the computer science is lexical analysis and grammar analysis. Such approach simplify the job. Lexical analysis is usually regular grammar done by finite automata with checking one symbol ahead to determine the next step it's input are characters and output lexeme structures. Grammar analysis often works on context free grammar and usually checking one symbol ahead to determine next step it's input are lexeme structures and output is often tree of parsed structures of the language.

[@DigaDupSuck]

i keep thinking the seinfeld theme is going to play every time an item is popped off the stack

[@martincattell6820]

Yeah I was waiting for the funky bass to start. Always leave them wanting more, I suppose.

[@samuelmontypython8381]

Thank you so much for the concise explanation! I'm taking advanced programming languages and data structures as courses right now and I hate the way they introduce parse trees. I spent over an hour reading and re-reading my required reading on parse trees and just couldn't understand it. I got more out of this video in 15 minutes than I did sitting with my thumb up an ungodly location parsing through the text.

[@isabellabihy8631]

Among many other things I used to write data editors, that is tools that checked the validity of inputs. I used a grammar building tool with EBNF notation. It had a learning curve but I caught on. That grammar building tool taught me that defining a grammar is quite a job.

[@subnumeric]

Today I got an A from our (allegedly notoriously hard) algorithms exam. I've picked RPN and syntactical analysis. It was trough these types of videos from Prof. dfb that I've learned so much and sometimes much more then there was in our materials. Oftentimes these videos explain the concepts in a better and more concise manner than any lecture would. Thank your, professor, for what you have done for me and surely many more people trough these videos.

[@BertGrink]

Yay the Professor's back!

[@bredbert]

I'm a simple man, I see Professor Brailsford, I click.

[@tanujnagpal572]

I'm a simple man too, I see comments about Professor Brailsford, I click.

[@morgard211]

I'm a simple man.

[@hempwick8203]

I'm a simple man, I see a simple man comment and I comment.

[@azrobbins01]

That part at 12:47 was so subtle. The hilarious part is that he is so used to Binary that it is easier for him to think in terms of "32 twos" instead of "Two 32s". Also, "The robot stroked the fuzzy dice". Love it.

[@gamekiller0123]

I think it has more to do with the order of the numbers. I suppose he could have said "32 times two" or "32 two times", but "32 twos" is a bit more natural.

[@andurilan]

Couldnt have come at a perfect time, watching whil(st)e writing one for a compiler as I watch.

[@superscatboy]

Whilste?

[@andurilan]

@@superscatboy While I work. /whistles

[@MrRyanroberson1]

13:06 small mistake: mathematicians will tell you it's *associative*, because 8(4*2) = (8*4)2 is associativity.

[@MrRyanroberson1]

@Paul Kovalov except the operation itself was still 8*4*2 in that order for both cases. the tree itself constitutes the parantheses.

[@Gokuroro]

Came here for this :)

[@Kram1032]

Oh of course I was like an hour late on this. Just made a comment that said the exact same thing~

[@gwennaneliezer8490]

@Paul Kovalov The example he gives says that 8(4*2) = (8*4)*2, and he explained it using commutativity (a*b = b*a), but this is a mistake. This equality is because of the associativity of (*), which says that (a*b)*c = a*(b*c) In other words, we can write a*b*c without parentheses because the multiplication is associative (and not necessarily commutative)

[@pepega3344]

@@gwennaneliezer8490 you also said it wrong xd

[@gwennaneliezer8490]

13:06 It is not because a*b = b*a (commutation) that we can do the operation on either way, it is because (a*b)*c = a*(b*c) (which is associativity).

[@lolcat69]

Thanks a lot, i am making my own programming language and this made me understand what a parser is, thanks you a lot magic man ;) ❤

[@oscarfeliz9874]

This is my favorite type of ASMR.

[@Veptis]

I started computerlinguistics just weeks ago. We are learning those very things right now b

[@potatoradio]

Came for the parsing; stayed for the tractor paper... (ok and clear and interesting teaching that made me smile as my brain hurt a bit from getting filled)

[@nO_d3N1AL]

This video needs to be seen by anyone interested in tools like ANTLR and Xtext but with no knowledge of parsing

[@nealelliott]

This is a much better description then the boring infix calculator example I had to learn in college.

[@Kram1032]

13:05 the property that matters here isn't commutativity (you can multiply a * b and b * a and get the same outcome - i.e. order of values doesn't matter), it's associativity (you can mutiply (a * b) * c and a * (b * c) and it gives the same outcome. I.e. parentheses do not matter or, equivalently, parse tree structure doesn't matter)

[@Double-Negative]

reflexive: x=x symmetric a=b -> b=a transitive: a=b and b=c -> a=c irreflexive: ~(a

[@JMDinOKC]

I would love to hear Professor Brailsford read some of Shakespeare’s sonnets.

[@MK-rn2hm]

Yes and steer away from explaining anything technical

[@allanrichardson9081]

“Shall I compare thee to a summer’s day? Nay, thou dost not cause a case of melanoma!”

[@thegougeman]

Professor Brailsford - You could explain Quantum Physics to a Kindergartner and they would understand it. You are the master of story telling and explanation.

[@AlexandreGurchumelia]

12:27 I have created class of octonions overriding multiplication symbol. The two trees give you different results because of non-associativity of octonions i.e. (A*B)*C ≠ A*(B*C).

[@siberx4]

If you're wondering how the described mathematical associativity could have relevance in a normal english sentence to highlight parser ambiguity, the classic "Eats shoots and leaves" joke demonstrates how english sometimes relies on punctuation to hint the correct associativity - without it, the exact same trouble arises and you'll get a different meaning if you build your "tree" in a different order.

[@menachemsalomon]

And of course, "Time flies" is a common example of the difficulty of parsing spoken language. A longer example is the contrast: "Time flies like an arrow," and "Fruit flies like a banana."

[@Computerphile]

In fact an earlier Professor Brailsford video discusses this exact example :) >Sean

[@MSStuckwisch]

A great way to play with parsing is using Raku (née Perl 6) that has a built in grammar parser (basically, regex on steroids) that makes implementing BNF, etc, very easy.

[@yash1152]

1:29 redirect to "Angle Brackets" --> redirects to --> "Chomsky Hierarcy" & "Finite State Automata"

[@antivanti]

I like garden path sentences am delightful While Bob ate an apple was in the basket In writing, make sure to put commas where they belong and in maths make sure to put parenthesis where they belong to avoid parsing difficulties :)

[@andreaaristokrates9516]

When I use the divide sign on my calculator the result of 8:4:2 is 1 and when I use the fancy 2d fractions it results in 4, but a single pixel indicated the grouping, so I can force it into being 1 again, if I use a weird way to construct the fraction.

[@landsgevaer]

I would say that 8/4/2 is indeed 1 in the absence of brackets, because then it would be evaluated left to right.

[@gwennaneliezer8490]

Well, 8/4/2 is ambiguous anyways. Give this to a mathematician, and he will say it doesn't have much sense since this notation is not well defined

[@cigmorfil4101]

If you think of divide as multiply by the reciprocal then with fractions it becomes obvious: 8 ÷ 4 ÷ 2 = 8 × 1/4 × 1/2 and now you can do either multiply first: (8 × 1/4) × 1/2 = 2 × 1/2 = 1 8 × (1/4 ×'1/8) = 8 × (1×1)/(2×4) = 8 × 1/8 = 1 In a fraction the line between the numerator and denominator does mean divide, but what is never overtly taught is with a/b/c is the b a denominator of a/b which then becomes the numerator for c or is it the numerator of b/c which then becomes the denominator of a. The convention is to work left to right with most operators (of the sane precedence to get (a/b)/c; power is the opposite (working right to left) with a^b^c meaning a^(b^c) not (a^b)^c.

13:05 Commutation has nothing to do with this. The ambiguity here does not matter because multiplication is associative.

[@boheem3451]

What do you mean 'it makes sense'? How do you define 'sensible'?

[@tarekghosn3648]

i love this dude

[@yash1152]

14:53 wow, the extra bits part seems interesting > _"john, now that you're aware that this..."_

[@effmerunning]

So we would ask, ‘what are option of choices?’ when parsing?

[@MichaelQuad]

i vote for longer video 8)

[@beachboardfan9544]

HOly hell I wish this would have been shown to me in first grade math!

[@MrXperx]

When I read the title I immediately thought the Professor will be talking of compilers. It was as if he read my mind.

[@menyasavut3959]

computer science && parsing => compilers. it's pretty obvious, da?

[@londonnight937]

@@menyasavut3959 Menya Savut Kolya. =)))

[@menyasavut3959]

@@londonnight937 Привет, Коля, приятно познакомиться

[@sabriath]

If the ambiguity leads you to two outcomes that would be unequal, then the parse description isn't properly created. I prefer EBNF with slight personal modification to standard BNF....it denies ambiguity from the start.

[@211212112]

What about Chomsky?

[@andrewthompson9714]

Context needed!! Your question is context free.

[@andrewdunbar828]

The Indo half of the Indo-European languages tend to be SOV, like Hindi with the verb last. German is actually V-2, which means the verb always comes second, but other parts can move around a bit. That's for very simple three-word sentences. In more complex sentences with more than one verb, it's all the verbs except the main verb that move to the end. Even this is a gross simplification too of course.

[@Jamie-st6of]

irish gaelic is generally vso and i think every sentence form begins with the verb

[@Alche_mist]

And then there are Slavic languages (like Czech I use) that use flexion (slight changes in word form) and otherwise have a lot of freedom when it comes to word order (for example, using it to indicate stress).

[@BellesLettresMagazin]

@@Jamie-st6of That is a Punic (Semitic) substrate. It found ist way into Icelandic, where the verb can appear on Position 1 or 2 without difference in meaning.

[@menachemsalomon]

And of course, in OSV Yoda speaks.

[@allanrichardson9081]

@@menachemsalomon And The writers of the Torah often used VSO, as illustrated by Genesis 1:1 “In-beginning created Elohim the-heavens and- the-earth.” In- = “be-“ as a prefix = “et” The- = “ha-“ as a prefix And- = “ve-“ as a prefix And-= “ve-et”

[@7th_CAV_Trooper]

Why cut off when it was just getting interesting? I wanted to hear about Chompsky.

[@a33795]

I wish this professor was my grandpa

[@seventeeen29]

A mathematician would actually tell you that * is associative. Not commutative. Associativity is what gives you this property.

[@slash_me]

Multiplication is also commutative, but I agree, the issue in this case is associativity.

[@Kram1032]

​@@slash_me yeah it's just that commutativity doesn't matter here at all. This would be equally true for matrices or quaternions, say. But not for octonions.

[@Yotanido]

"If the answer is 1 demand your money back" I'd demand my money back if it were 4. Division is left-associative. Oh, but if 2^3^4 comes out as 4096, you should demand your money back. Exponentiation is right-associative :D

[@dnomyarnostaw]

Yes, mine came out = 1

[@NAME_SLUMS_MOMO]

I think he said "If the answer *isn't* 1 ...", but it's difficult to hear.

[@profdaveb6384]

Quite so! I said "isn't" ....

[@cernejr]

Minor error: In the given example it is important that multiplication is ASSOCIATIVE, the presenter said COMMUTATIVE.

[@donaldhobson8873]

Actually, the property of multiplication that you are using is associativity, not commutativity.

[@stevojohn]

Operator precedence.

[@enrico4776]

Interesting

[@FloydMaxwell]

Parsing has very little to do with compiling. Parsing has a great deal to do with how to live a good life.

[@centerfield6339]

The tree structures would be simpler if they had a * as the root, rather than E.

[@petermathie398]

Is this why languages read right to left?

[@SudaNIm103]

I just love the Professor; he’s like the “𝑗𝑜𝑙𝑙𝑦” 爪ᗩ𝕊Tᗴ尺 𝚈𝓞𝔇ᗩ of Computer Science fundamentals!

[@didiodulaw7417]

This extra video ("EXTRA BITS: How Chomsky Fits In - Computerphile") quite delightful you might find ;-)

[@SudaNIm103]

Didiodu Law I unfortunately, cannot find an Extra Bits video on Chomsky; only the original Computerphile episode on Chomsky hierarchies. :( If you have a link please consider posting it.

[@publicpitchblendeorg]

C is awesome

[@kuronosan]

removing bones from fish

[@faceofdead]

Unfortunately this is extremely complex for me. I hope i can understand better in time :)

[@A3Kr0n]

Thumbs up for the Chomsky mention!

[@stuartcoyle1626]

The Dragon book condensed into fifteen minutes. Maybe not quite.

[@recompile]

Not even close.

[@tecsmith_info]

What a total ledge

[@programorprogrammed]

Parsing, yes

[@superscatboy]

@MichaelKingsfordGray Parson's nose

[@inception252]

50years experience to make token

[@CoffeeTroll]

That robot lost no nut November

[@michalmikulasi5193]

i wish it was "furry balls" instead of dice. so much funnier :D

[@mannyc6649]

The property of multiplication that is shown is not commutativity (a*b = b*a) but associativity: (a*b)*c = a*(b*c)

[@BellesLettresMagazin]

The example sentences are correct (the obey the Grammar rules), but they are not valid, because there is no situation in reality where they would be uttered. That at least how linguists put it. Speaking of linguistics, the tree model is not the way, language actually works.

[@MadocComadrin]

It's because really languages aren't context free.

[@Conenion]

> Speaking of linguistics, the tree model is not the way, language actually works. A parse tree, or grammar tree is a representation of the concept of the generative grammar which was developed by Noam Chomsky. See also the Chomsky hierarchy of grammars to see were the computer scientists got their ideas from.

[@BellesLettresMagazin]

@@Conenion Bullseye! And it is dismissed by , say, 99 percent of all linguists. It already was, when I studied linguistics decades ago. It might be usefull for primitive things like XML, DOMs and modern programming languages, but natural language is 3.2 million years ahead of that.

[@enio.carlos]

the man was holding himself not to talk about compilers lol

[@whtiequillBj]

Here is a good example of where grammar matters in your writing. Commas matter. Let’s eat, Grandma. vs. Let’s eat Grandma.

[@BertGrink]

Even capitalisation matters: consider the difference between Peter helped his Uncle Jack off the horse. and Peter helped his uncle jack off the horse.

[@chloecui2774]

top down bottom up

[@nazcruz8284]

"if the answer isn't 1 demand your money back"

[@sampoerna2329]

i dun understand a single thing he is saying ...

[@another3997]

I parsed your sentence and analysed it. Compiler Error encountered at "dun". You mean "do not" or "don't"? Or perhaps "did not" or "didn't"? We can probably ignore the lack of capitalisation.

[@Nexus-rt1bm]

@@another3997 wouldn't it be a parsing error?

[@fredirecko]

I tried doing the math problem with my calculator and couldn’t get it .....

[@DiAL033]

~ 1:00 I am sorry, but I am afraid Prof. Brailsford mixes up verbs and predicates here. "John saw the man running." A verb at the end, but it is not the predicate, that is ok, even in English ;). So anywhere the word "verb" comes up in this vid: what's really meant is the predicate.

[@CaptainWumbo]

Generally languages are defined SOV SVO etc. You'll see that in grammar books. It doesn't matter that there are modifying elements within those structures. For the same reason the article a/the modifying robot is all part of the subject, running man is all part of the object. Then you can drill down further to find more specific structure. This was something that confused me when I first started learning a SOV language, because I wondered how they make sentences with more than one verb if it always has to come at the end. Unfortunately it's a problem of semantics.

[@DiAL033]

@@CaptainWumbo it's SPO or SOP. Again, it's the predicate that describes part of a sentence' structure. The term verb describes a class of words, just like the term noun. I haven't seen an actual grammar book that uses 'verb' to describe the predicate. Maybe you can name the book title?

[@CaptainWumbo]

DiAL033 Page 16 of A Dictionary of Basic Japanese Grammar, Seiichi Makino and Michio Tsutsumi, part one of a series of 3 pretty deep grammar books. It could be that they chose the more common and widely understood word to get across the point, but at the same time they're not afraid to throw words like copula at you which are just as poorly understood. I hear SOV SVO in plenty of videos as well from people repeating what they've read. It could be that predicate is more technically accurate. My book here does define and make use of the word predicate (and core predicate) in many places. And as you say it doesn't have to be a verb, although much of the time it is. I think maybe the point SOV gets across is to answer the question where does the verb go, rather than to describe all sentence structures.

[@superscatboy]

I'm so adjective, I verb nouns.

[@tzwacdastag8223]

So now Robot can Bite Dogs

[@itsjmmariano]

OMG

[@DeviChexx]

Ah yes, furry dice.

[@f4z0]

Do I need to be a furry to roll those dices?

[@pierreabbat6157]

Two furry dice bit a dog. They are flying airplanes. Are they pilots or are they airplanes?

[@murphy54000]

Yes.

[@GameCyborgCh]

He looks like he went to work in his Pyjamas

[@jacobscrackers98]

From the cover picture I expected to see a video of the professor picking his nose. Was disappointed.

[@BertGrink]

That footage is only available on the Director's Cut Special Edition DVD ;)

[@lucidmoses]

yacc

[@profdaveb6384]

coming soon (I hope) !

[@lucidmoses]

@@profdaveb6384 excellent^2

[@utopictech6425]

Sexo na praia.

[@firehawk128]

I'm getting nightmares of CFGs from my misspent youth taking CS courses. lol

[@andrewvella7829]

Just finished a parser, lol

[@andrewvella7829]

@MichaelKingsfordGray yup, found this video after my parser was finished, haha. I spent my weekend rebuilding a syntax analyzer, and this really could've been a help

[@sofia.eris.bauhaus]

*notices furry dice* what's this? OwO

[@plapbandit]

nth comment

[@downstream0114]

(n+7)th comment

[@utopictech6425]

@@downstream0114 (n+infinite) th

[@alvesvaren]

hello

[@rinasingh923]

Boring....... but important tho 😐

[@Aemilindore]

no whatsapp

[@insdel3227]

templeos

[@tanujnamdeo]

Whats up people

[@tompov227]

its fun listening to him say paaaaahhhzzeng instead of parsing lol

[@superscatboy]

He's saying "parsing" instead of "parsing".

[@rylaczero3740]

144th