Parser and Lexer — How to Create a Compiler part 1/5 — Converting text into an Abstract Syntax Tree

In this tool-assisted education video I create a parser in C++ for a B-like programming language using GNU Bison. For the lexicographical analysis, a lexer is generated using re2c.

This is part of a multi-episode series. In the next video, we will focus on optimization.

Downloads:

Acknowledgements:
— Picture: Processors :: Jason Rogers
— Music¹: Aryol :: The Strategy Continues :: Kyohei Sada (converted into MIDI and played through OPL3 emulation through homebrew software)
— Music²: Star Ocean :: Past Days :: Motoi Sakuraba (SPC-OPL3 conversion)
— Music³: Rockman & Forte :: Museum :: Kirikiri-Chan and others (SPC-OPL3 conversion)
— Music⁴: Famicom Tantei Club Part II: Ushiro ni Tatsu Shōjo :: Dean’s Room :: Kenji Yamamoto (SPC-OPL3 conversion), original composition: Bach's Invention № 15
— Music⁵: Aryol :: Arrest :: Kyohei Sada (SPC-OPL3 conversion)
— Music⁶: Ren & Stimpy Show : Fire Dogs :: Main Theme :: Martin Gwynn Jones and others (SPC-OPL3 conversion)
— Music⁷: Aryol :: Warmup :: Kyohei Sada (SPC-OPL3 conversion)
— Music⁸: Energy Breaker :: Golden-Colored Wind :: Yukio Nakajima (SPC-OPL3 conversion)
— Music⁹: Wonder Project J :: House :: Akihiko Mori (SPC-OPL3 conversion)
— SFX: Mostly from YouTube Audio Library. Some are recorded from video games like The Guardian Legend, Lunar Ball, and Super Mario All-Stars.

¹ 00:37, ² 02:46 & 39:26, ³ 10:10, ⁴ 16:06, ⁵ 27:18, ⁶ 37:20, ⁷ 38:58 & 45:58, ⁸ 49:00, ⁹ 50:40

My links:

---Rant---
[9:35 PM] Bisqwit: Now uploading to YouTube. Within about 24 hours I will know if the rogue AI at YouTube slams the “limited or no advertising" stamp into it, or not. Actually, I only know if it does so *when* it does it. Then, I need to wait an additional 25 hours for YouTube staff to manually review it and clear the flag. If the flag does not appear, then it is possible that the bot just has not scanned it yet and I need to wait longer. Premature publication could mean that the bot will mark it after it has already been published, and then I will not receive any revenue for the first spike of views. It used to be 18 hours (since uploading that the bot does its evil deeds), but nowadays YT recommends waiting just 3 hours. We will see, we will see.

#Bisqwit #Compiler #Tutorial

[DFsdfd]

"sometimes you just need to create a compiler"

[silverbrek]

Creating own compiler just to share knowledge with others. Programmers like you deserve more popularity on Youtube.

[rickyjoebobby]

bisqwit, on behalf of all computer science students, we thank you for this.

[Bisqwit]

This video was uploaded in 4K quality (3840x2160 @ 60 fps), but it seems YouTube is taking its sweet time to provide the 4K quality level. It may take anything from a day to a couple of months in my experience… Or it might not come at all. Who knows. The 360° video was uploaded in 8K, and this was 1.5 months ago, but it still has not provided the 8K quality (even though some of my unlisted test videos have it).

[banglaLang]

Sir, I can't thank you enough, I have learned more than my entire Master's Degree in less than two hours. I used to think Compilers were gift from God to Mankind not replicable by Mankind. Now I have made one just following you.

[StarContract]

2 years later, this still is the best intro to compiler architectures series on YouTube.

[MaxwellsWitch]

I've been studying lexers and parsers for about a month now, and this has helped me out tremendously.

[jamesbalajan]

Excellent introduction to compilers. On hearing that you were going to create a guide for making compilers I was immediately interested. This video way surpassed my expectations though. Can't wait for part 2.

[giantisopod]

Interesting, I had no idea that the "auto" keyword that was introduced in C++11 is actually older than C.

[dendygar]

Every video from you is a treat! This is definitely the channel I enjoy most on YouTube. Thank you Bisqwit!

[thedonner]

I cant explain how much i appreciate all of this. Its so well and patiently explained, plus the subtitles...! Thank you so, so very much for all your effort.

[Carl-giil]

Thank you very much for this video! Your explanation is very clear, and I can easily follow the graph you've created. This is the best tutorial on creating a compiler I've seen so far, and I really appreciate it!

[LeviSchuck]

The graphs were beautiful.
Happy new year!

[Neoclassicalmaese]

This channel is programming gold. One of the very first youtube channels that I subscribed into. Bisqwit you are amazing my dude!

[christopherchamberlain]

I am so excited for this series. I've been looking into this recently. Please more! :)

[czssyqx]

I love how practical and well thought the videos are! Now I finally understand why I had to learn EBNF in school :)

[blauergrashalm]

"So I make sure my design does not have too much fluff in it"

"🎵🎵 Fluffy music 🎵🎵" -> Genius! (at 31:45, in the captions)

[SimGunther]

What a glorious day! Thank you so much for a wonderful video :)

This was a glorious way to start off the new year. Wish you best of luck, Bisqwit.

[oof-software]

Finally YouTube recommended something good to me!
I was watching your channel a few years back but never came across this series.
Recently I started learning about parsing and lexing because of a university course and to understand it better I want to implement my own parser.
I couldn't find a video that gives a nice broad overview of the topic but this is exactly what I was looking for!
Thank you so much Bisqwit and much love from Germany!

[zadeh]

This is in insane. It's one thing that he can go on and on about deeper theoretical stuff. It's another thing that Bisqwit can actually figure out how to apply all this stuff in practical scenarios.