Parsing Bottom Up - Computerphile

Having explained the top-down method, Professor Brailsford flips to bottom up Parsing.
EXTRA BITS: • EXTRA BITS: YACC & LEX...
/ 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

[@gravity4606]

I can't wait until they finish the "Middle-Out Parsing Method"

[@andy.robinson]

Didn't Richard Hendricks already solve that? 🙂

[@arbazna]

Nice "Dragon book" in the background

[@fn24atradio]

I still have mine.

[@big_b_radical3985]

As iconic as computer graphics, principles and practices.

[@pm31415]

He is like the david attenborough of computers

[@EternalAnomaly]

Paul McKeown 100% Imagine both of them in one video. Thats my ASMR dream video! 😁

[@chaoslab]

Always an awesome day when their is a new Prof Brailsford video posted. :-)

[@krishnabirla]

I want to meet him just for once in my life. I love him.

[@olavl8827]

Perhaps write him an e-mail? His address can be found easily on the university's web site.

[@domminney]

He’s a great guy.

[@i1a2159]

Thank you for these amazing and helpful videos!

[@crumbl3d]

Well just had a curriculum for a Compilers class last week and parsing was the main event but I guess a different point of view is always useful.

[@theassailer18]

I have your 'Dragon Book', and i learned bottom-up parsing from that one :) Thank you!

[@TheDarkOne629]

Tanks for the explanation. I always thought that bottom-up meant walking the AST from the bottom leaves up to the root and just could not wrap my head about it. Anyone I asked just said "Well, it goes from the bottom to the top."

[@ATG549]

This is actually crazy, this video went up as soon as I finished watching the original parsing video, what are the odds :P

[@Shadow81989]

At <a href="#" class="seekto" data-time="255">4:15</a> or so he should have mentioned that the next thing the parser would try to match (and fail to do so) would be "the robot stroked", in order to make sure that there's no longer chunk decodable rightaway. Other than that minor detail, great video, as usual from Professor Brailsford!

[@d7oo435]

Will, windows 7 looks lovely

[@zxuiji]

what about multi parsing? Identify objects, verbs and adjectives 1st while placing identifiers between each (I think the xml word work well there) and then recursively parse each section or subsection until no more sections can be made and then build the subject etc from what the combined information says, when no subject can be found then the precious context is used, if no previous context is used then a question can be generated to ask what/who etc was the verb etc relates to

[@vozzen]

They upload this the same day I had a lecture about it. That's quite a coincidence.

[@dovidsamuels5709]

Me too! That's crazy...

[@iamjimfan]

I learned parsing using bison and thus the shift-reduce approach. Just now I was doing ANTLR 4 but LL parsing really looks like an alien to me.

[@ShakaRule]

It bothers me that you show the stack sideways xD

[@olbluelips]

Jelmer Berghs it’s going to spill everywhere :(

[@CJBurkey]

The odds are stacked against you

[@x3ICEx]

The extra bits are STILL unlisted. I'm not hunting around in video descriptions for links... EXTRA BITS: YACC & LEX background - Computerphile Unlisted 4,401 views•Nov 27, 2019

[@HisMajesty99]

Lol I just finished a Parser project using YACC for a Compilers course. Had exactly to do with this.

[@Endomorphism]

is its online course ?

[@tscoffey1]

Rather than shifting characters, you actually shift lexical tokens onto the stack. (The lexical analyzer determined the token values, using a fairly simple finite state machine)

[@jpratt8676]

To be a bit more complete, not all parsers have lexers. You can parse from raw characters (not that I recommend it, too many edge cases that you could have simplified with lexing).

[@tscoffey1]

@@jpratt8676 Correct, but why not deal with the special cases using a much simpler FSM, instead of trying to put those rules into the parser?

[@jpratt8676]

@@tscoffey1 I totally agree, but that doesn't change the terminology, only the approaches that we believe are reasonable.

[@dstarfire42]

Since the start of the 'top-down parsing' I've assumed most compilers used a combination of these approaches. Is that accurate, or does it vary from compiler to compiler?

[@iamjimfan]

I think not. Try take a look at ANTLR which generates parser using top-down approach. I am trying to get familiarised with it.

[@stark_energy]

Some custom compilers like Android does to IntelliJ editor has put optimization code to trim off several impossibility (such as trimming possibility of parsing Statement tree outside of class scope in Java) this will skip the checking of heavy potential top-down branch by big margin. So the answer is that if that app has significantly faster performance than standard/other compiler, a custom (maybe a combination of both top-down, pruning and bottom-up) compiler was made to tuned to that specific language (e.g. special for Java). Compiler in editor such as in Dreamweaver or Eclipse is slow because those editors are for general language (either bottom up or top down) without optimization.

[@TheRealGuywithoutaMustache]

I don’t know anything about this topic, but I’m interested

[@sakeriyasaleh4820]

Same

[@rylaczero3740]

We had a dedicated subject for them in Uni under 'Compilers'

[@paneesh]

His sweater has, what looks like, a lot of cat fur :D

[@olavl8827]

Yes, saw it too and when I did it became somewhat distracting. I believe the person operating the camera should be alert to such things. For this channel the people being filmed probably don't need to be in full TV-studio makeup. But at least dust them off a little, pay some mind to their appearance.

[@paneesh]

@@olavl8827 I found it funny. Professor probably cuddled with his cat and never realized the trail of fur it left behind :)

[@caleb5688]

I don't think Dr Knuth knows how sus "the robot stroked two furries" sounds

[@ravewulf]

Sounds a bit like regular expressions in that regex is greedy/looking for the longest match (unless you tell it to be lazy)

[@JmanNo42]

Hello Professor Brailsford, if you have a large dataset is there a speed penalty for the bottom up approach, or is it same or faster parsing?

[@JmanNo42]

I was thinking parsing the words and later match two words with string may be faster, the doing the full character match of sting because the dataset will be the comarissons and the the more "simialar strings" the more comparissons? Less comparissons? So if you wrote an AI that could handle that type of sematnic buliding blocks, it would take a very long time doing the matching bottom up finding combined words in phrases? Right or wrong?

[@JmanNo42]

Well thiese type of ideas certainly was in the era of administrative programming back in the day "expertsystem and automatiion", what happened to them are they still prevalent?

[@simpletongeek]

Does that mean if the phrase is "the robot stroke the robot", then we will get 2 subjects? Or is there a workaround for that kind of problems?

[@profdaveb6384]

Yes if the shortcut phrase "the robot" was allowed in an object position you might end up reducing that to and end up with "two subjects" in your sentence.. A simple-minded bottom-up parser might well end up with and then have to backtrack and try again because the final goal *must* be . Nothing else will do. But the parser that yacc will generate for you takes great care, by reordering the input grammar and "looking ahead" a little,, to take you only through those reductions that might eventually result in .

[@HechTea]

*Notices furry* OwO what's this?

[@RufusShinraPower]

It's a compiler for the furry language =p

[@DonovanDMC]

I'm half expecting that youtube user just called "OwO" to pop up out of nowhere

[@exoticcoder5365]

<a href="#" class="seekto" data-time="632">10:32</a> I was concerned about that teddy bear behind

[@schumbo8324]

Why this catches my attention and makes me watch it all as a law student someone needs to explain this to me!!

[@Not.Your.Business]

subconscious mind having doubts regarding career choice, maybe?

[@schumbo8324]

@@Not.Your.Business Ehm i dont think i have a regret about my profession choice but i still like to listten about these stuff. This must be more like attraction of unknown.. i guess.

[@eschelon9067]

Next up: Bottom Up AI vs Bottom Down AI explained

[@DonovanDMC]

The word "furry" is used too much here

[@mfbx9da4]

Dudes got a cat...

[@rpcruz]

He uses Windows? I was expecting to see Minix or some other weird Unix variant hehe.

[@NoNameAtAll2]

unix is good for proffesional work windows is good for normal work

[@Dong_Harvey]

To note Windows 7, still better than 10 BTW I just learned about PureDarwin today, check out it's logo

[@KuraIthys]

He used a terminal program in windows to SSH into a Linux system. Is that heresy? Or is it pragmatism? ;p

[@daveachuk]

... or just use S-expressions #lisp4lyfe

[@Jeacom]

I'll never understand why computer science trees are upside down.

[@carlosmendes7]

Easier to draw on paper without wasting space

[@Jeacom]

@@carlosmendes7 I dont think that's an excuse to make millions of students confused.

[@b2gills]

It's because written English starts at the top left of the paper. You start with the first thing you know, which is the root. You write that first, because you know it first. Then you follow the branches, which you know second, so you write it second. Eventually you get to the leaves last, so you write them last. Which means they end up at the bottom.

[@Jeacom]

@@b2gills So why not call it a root instead of a tree? The, bottom-up top-down terminology would be so much easier to get that way.

[@b2gills]

@@Jeacom Because English doesn't have names for roots that branch, and for the ends of roots. English DOES have plenty of words to describe branches and leaves. (Mainly because people speaking English as it was developing rarely if ever saw the roots of a tree.) I mean it is easier to say: “start at the root of the tree, work your way along the branches until you get to the leaves.” It isn't very easy to understand: “start at the root of the root, work your way along the roots until you get to the roots.” Basically we use the word tree because we have words to describe that.

[@pruusnhanna4422]

Flex & bison.

[@profdaveb6384]

Yep! My SuSe Linux (apparently) supplies "lex" and "yacc" but they are redirected via shellscript interfaces to flex and bison. Main thing to remember is that this aliasing does not seemingly extend to libraries. On my setup, at least, you can't get away with '-ll' The link-loader insists on '-lfl'

[@pierreabbat6157]

two furry dice stroked the robot

[@pmcgee003]

I'm thinking the screen text has been CGI'd in, over the actual screen text ... and then some focus blur added on the edge just as a flex. :)

[@spoonikle]

using windows 7 to ssh into your linux server.

[@baileyharrison1030]

spoonikle that’s how most people seem to do it.

[@MrNacknime]

This grammar is such a bad example. Nowhere is there any ambiguity in what kind of rule produced a certain result. It would be much more interesting to see how the parser handles it when there are currently two possibilities producing a certain handle, and how this is resolved when more of the input is considered.

[@muninmatt]

Someone get this man a lint roller

[@justahker3988]

Speaking of which, I would love to have an episode on linters and how they differ in purpose from compilers.

[@gohchi]

deep inside everyone loves the furries. okno

[@dipi71]

Considering the target group of these videos, I doubt it’s necessary to »protect« us from those too intricate »extra« details anymore. When those »EXTRA BITS« (all caps, ugh!) begin to be the actual meat of the matter, the »main« videos remain little more than fluffy preludes. Therefore I suggest integrating the extra bits and the preludes to proper videos about one topic. No to channel hopping.

[@TarasMazepa]

Bottom up grammar parsing

[@anthonyvays5786]

putty on windows 7 in 2019

[@DamonWakefield]

First for once!

[@naufragio5842]

If you wanna try this stuff under your linux boxes look for bison+flex lol.

[@neozeus2222]

first!

[@abdallahmanasrah2317]

You win good sir

[@derHutschi]

nice video. it has furries ;-)