<p>I'd say don't overthink this too much. Most students of programming need to have a basic understanding of how things like compilers work, but don't need to be comfortable <em>writing</em> a compiler. So, if your course is one that students might be taking to mostly get credit, just make them do enough work to get a grasp of what is happening. If your course is an option for students taking it to really understand the subject matter, then yes, you need some of the theory as well as the practical knowledge.</p>
<p>As for parsing, simple recursive descent will serve well to get them understanding the concept. Parsing tools come and go. Don't make them learn a bunch of nitty gritty that they will likely never use outside of your course.</p>
<p>Note: I am a practical compiler-writer. I've written a half-dozen compilers, all without any lex/yacc-type tools. So, if my advice sounds wrong from a purely teaching point of view, by all means be more abstract.</p>

CC BY-SA 4.0
2024-10-08T21:43:30.777Z
2024-10-08T21:43:30.777Z
Chris G.
<p>Over my career I spend a lot of time with languages and compiler construction. My opinion is that <em>languages</em> should be LL(1), which optimizes human understanding of the constructs. I created quite a few &quot;mini&quot; LL languages to illustrate ideas and provide exercises for students. Imagine being <em>required</em> to do bottom up parsing of complex expressions in your mind without computer help. UGH.</p>
<p>And, students in a first compiler course already have a lot on the plate in understanding the syntax and semantics of the source and target languages as well, perhaps, as getting a bit familiar with an &quot;assembler like&quot; language as the target with goto/branch and labels and such.</p>
<p>Given that, while it is true that an LR (or LALR) compiler would be more efficient in the translation of such things, there is no reason, IMO, that a student's first compiler project shouldn't be top down (LL, recursive descent). For a second year course this seems enough to me. It also reinforces recursion in the minds of students, which is, itself, useful at this stage. I'm not sure why you call this 'trite'. Recursion is fundamental to computability theory of course.</p>
<p>Moreover, parsing is only one aspect of any compiler. If the parser is fairly straightforward then the semantics of the language might reasonably be more complex. Some of my mini languages exploited this, demonstrating how to deal with some things that the students weren't familiar with in their earlier work.</p>
<p>And, if you have time for multiple projects, there is no particular reason that you couldn't also have a LALR compiler project based on that same (or slightly modified) language.</p>

CC BY-SA 4.0
2024-10-08T22:10:13.400Z
A point I think is sometimes missed in discussions of compilers is that sometimes it's better to have a compiler include a stage to handle a few special token sequences than to try to write perfect token specifications.  Having an initial scanning phase treat `0E-4` as three tokens, and then having a middle stage combine a "non-hex number ending in E", a minus sign, and a decimal integer constant into a "floating-point constant" token may be cleaner than trying to avoid treading a minus as a token boundary when it follows an `E` within a numeric constant.
supercat
CC BY-SA 4.0
2024-10-07T10:57:49.107Z
2024-10-08T18:34:40.233Z
2024-10-08T18:34:40.233Z
Buffy
<p>Having the lecture after the lab is indeed a tricky wicket.</p>
<p>One way that I've approached similar problems is to make some self explanatory, <em>exploratory</em> portions of the lab.  This is a different sort of lab that introduces key concepts to students independently, and prior to, the lecture. It can be a great way to help the students build some serious intuition before a more thorough exploration in class.</p>
<p>I've made a lot of labs in this format, and it can be very rewarding. However, there are a few things to be aware of when making a lab like this:</p>
<p>First, the actual lab write-ups tend to be very long (by necessity), and some students may despair as soon as they see it. <em>What is this 20 page document I just received that I don't understand much of at a glance?</em></p>
<p>Depending on your student population, this could be a serious problem or not. Most students will steel their nerves and delve into reading at some point.  Even with excellent students, however, it's important to communicate why this lab is different from most labs they've seen before and its purpose.</p>
<p>Second, you should think carefully about how much you expect the students to accomplish when they are also teaching themselves the core course material with little support, and you should make this explicit as well. If you just want the kids to explore the ideas, and reap the benefits of that exploration, you should set up a grading scheme that rewards such risk taking, and deemphasizes the success of the final product. Once again, you should lay this out for the students so that they know how to approach the lab and what the standards of success are.</p>
<p>Finally, be aware that assignments like this can take a LONG time to complete.  If it's not appropriate to create labs that last 30 or 40 hours for students to work on, again make a grading scheme that relies on effort more than final product.  You can eve take it as far as setting a sort of time-limit such as, &quot;if you, on your own home nor, earnestly work 20 hours, stop working and make a note of that on your submission, and I'll be sure to give your grade only based on the portions you got to.&quot; Or some other, similarly freeing sort of grace.</p>
<p>In my own exploratory labs, I have to decide what success looks like, and think hard about what sort of grading scheme supports that success, and what supports I provide to help students achieve it.</p>
<p>Sometimes, wrestling with the materials prior to lecture is sufficient, and I make much of the lab &quot;just attempt this <em>on your honor</em>, and your grade will do well, because even a failed attempt will lay the mental seeds for the lessons to follow.&quot;  Other times, I lay out very specific guidelines for what they must accomplish for an A, what they must do for a B, etc.  Other times, I believe that the topic is small enough, and the office hours sufficient support, to simply demand a full solution.  But this is the central question of the lab design, and demands serious attention.</p>
<p>Exploratory labs are big, and somewhat intimidating, experiences you're creating for the students, and often require them to go out on serious, risk-taking limbs. They can be heavily rewarding, both in class, and later on in life when they are faced (once again) with dauntingly difficult problems. You should think carefully about what you want your students to get out of it in the context of your course, and design appropriately.</p>

CC BY-SA 4.0
2024-10-07T12:09:03.040Z
2024-10-07T12:09:03.040Z
Ben I.
<p>I would highly recommend the book <a href="https://craftinginterpreters.com/" rel="nofollow noreferrer">Crafting Interpreters</a>. It covers many, but not all of the topics one might find in a compiler course. You may read the entire source on line for free. The authors explanations are wonderful. I though his discussion of the visitor pattern was the best I've ever read.</p>

CC BY-SA 4.0
2024-10-07T20:22:00.687Z
I had a look but I cannot see how this can help.
anon
CC BY-SA 4.0
2024-10-07T21:10:06.360Z
Take a look at chapter 4. You might show some of the scanner code, then make an assignment to complete the implementation. Operations with multiple characters (+=, etc), and string literals are two places where the students can complete code. The author presents a challenge to add C-style comments. You could change the language slightly to force the students to modify what is shown. Good luck.
Fritz Sieker
CC BY-SA 4.0
2024-10-07T17:14:48.007Z
2024-10-07T17:14:48.007Z
Fritz Sieker
<p>I teach basic compiler design and parsing to software engineering bachelor students (second year).
Usually, the kind of exercises we do in the labs are limited by the students' lack of previous exposure to these topics and by the fact that the most compiler-related parts (bottom up, LR, etc.) lectures happen after the lab sessions, so we invariably end up with some trite recursive descent implementation.</p>
<p>I would like to refresh things a bit, but cannot think of an interesting, hands-on and generally suitable replacement, so I thought to ask here.
TIA!</p>

CC BY-SA 4.0
2024-10-08T20:23:19.007Z
Perhaps Pratt parsing would be a novel perspective?
D. Ben Knoble
<language-choice><cs-theory><compiling><syntax>
Ideas for exercise in parsing and compilers?
# Ideas for exercise in parsing and compilers?

(Asked by: username_0 on 2024-10-06)

I teach basic compiler design and parsing to software engineering bachelor students (second year).
Usually, the kind of exercises we do in the labs are limited by the students' lack of previous exposure to these topics and by the fact that the most compiler-related parts (bottom up, LR, etc.) lectures happen after the lab sessions, so we invariably end up with some trite recursive descent implementation.

I would like to refresh things a bit, but cannot think of an interesting, hands-on and generally suitable replacement, so I thought to ask here.
TIA!

**Tags:** language-choice, cs-theory, compiling, syntax

> **Comments:**
> **username_1**: Perhaps Pratt parsing would be a novel perspective?  

---

## 4 answers

### Answer by username_3 on 2024-10-07. Score: 6

Over my career I spend a lot of time with languages and compiler construction. My opinion is that *languages* should be LL(1), which optimizes human understanding of the constructs. I created quite a few "mini" LL languages to illustrate ideas and provide exercises for students. Imagine being *required* to do bottom up parsing of complex expressions in your mind without computer help. UGH.

And, students in a first compiler course already have a lot on the plate in understanding the syntax and semantics of the source and target languages as well, perhaps, as getting a bit familiar with an "assembler like" language as the target with goto/branch and labels and such.

Given that, while it is true that an LR (or LALR) compiler would be more efficient in the translation of such things, there is no reason, IMO, that a student's first compiler project shouldn't be top down (LL, recursive descent). For a second year course this seems enough to me. It also reinforces recursion in the minds of students, which is, itself, useful at this stage. I'm not sure why you call this 'trite'. Recursion is fundamental to computability theory of course.

Moreover, parsing is only one aspect of any compiler. If the parser is fairly straightforward then the semantics of the language might reasonably be more complex. Some of my mini languages exploited this, demonstrating how to deal with some things that the students weren't familiar with in their earlier work.

And, if you have time for multiple projects, there is no particular reason that you couldn't also have a LALR compiler project based on that same (or slightly modified) language.

> **Comments:**
> **username_4**: A point I think is sometimes missed in discussions of compilers is that sometimes it's better to have a compiler include a stage to handle a few special token sequences than to try to write perfect token specifications.  Having an initial scanning phase treat `0E-4` as three tokens, and then having a middle stage combine a "non-hex number ending in E", a minus sign, and a decimal integer constant into a "floating-point constant" token may be cleaner than trying to avoid treading a minus as a token boundary when it follows an `E` within a numeric constant.  

---

### Answer by username_5 on 2024-10-07. Score: 5

Having the lecture after the lab is indeed a tricky wicket.

One way that I've approached similar problems is to make some self explanatory, *exploratory* portions of the lab. This is a different sort of lab that introduces key concepts to students independently, and prior to, the lecture. It can be a great way to help the students build some serious intuition before a more thorough exploration in class.

I've made a lot of labs in this format, and it can be very rewarding. However, there are a few things to be aware of when making a lab like this:

First, the actual lab write-ups tend to be very long (by necessity), and some students may despair as soon as they see it. *What is this 20 page document I just received that I don't understand much of at a glance?*

Depending on your student population, this could be a serious problem or not. Most students will steel their nerves and delve into reading at some point. Even with excellent students, however, it's important to communicate why this lab is different from most labs they've seen before and its purpose.

Second, you should think carefully about how much you expect the students to accomplish when they are also teaching themselves the core course material with little support, and you should make this explicit as well. If you just want the kids to explore the ideas, and reap the benefits of that exploration, you should set up a grading scheme that rewards such risk taking, and deemphasizes the success of the final product. Once again, you should lay this out for the students so that they know how to approach the lab and what the standards of success are.

Finally, be aware that assignments like this can take a LONG time to complete. If it's not appropriate to create labs that last 30 or 40 hours for students to work on, again make a grading scheme that relies on effort more than final product. You can eve take it as far as setting a sort of time-limit such as, "if you, on your own home nor, earnestly work 20 hours, stop working and make a note of that on your submission, and I'll be sure to give your grade only based on the portions you got to." Or some other, similarly freeing sort of grace.

In my own exploratory labs, I have to decide what success looks like, and think hard about what sort of grading scheme supports that success, and what supports I provide to help students achieve it.

Sometimes, wrestling with the materials prior to lecture is sufficient, and I make much of the lab "just attempt this *on your honor*, and your grade will do well, because even a failed attempt will lay the mental seeds for the lessons to follow." Other times, I lay out very specific guidelines for what they must accomplish for an A, what they must do for a B, etc. Other times, I believe that the topic is small enough, and the office hours sufficient support, to simply demand a full solution. But this is the central question of the lab design, and demands serious attention.

Exploratory labs are big, and somewhat intimidating, experiences you're creating for the students, and often require them to go out on serious, risk-taking limbs. They can be heavily rewarding, both in class, and later on in life when they are faced (once again) with dauntingly difficult problems. You should think carefully about what you want your students to get out of it in the context of your course, and design appropriately.


---

### Answer by username_6 on 2024-10-07. Score: 4

I would highly recommend the book [Crafting Interpreters](https://craftinginterpreters.com/). It covers many, but not all of the topics one might find in a compiler course. You may read the entire source on line for free. The authors explanations are wonderful. I though his discussion of the visitor pattern was the best I've ever read.

> **Comments:**
> **username_0**: I had a look but I cannot see how this can help.  
> **username_6**: Take a look at chapter 4. You might show some of the scanner code, then make an assignment to complete the implementation. Operations with multiple characters (+=, etc), and string literals are two places where the students can complete code. The author presents a challenge to add C-style comments. You could change the language slightly to force the students to modify what is shown. Good luck.  

---

### Answer by username_2 on 2024-10-08. Score: 1

I'd say don't overthink this too much. Most students of programming need to have a basic understanding of how things like compilers work, but don't need to be comfortable *writing* a compiler. So, if your course is one that students might be taking to mostly get credit, just make them do enough work to get a grasp of what is happening. If your course is an option for students taking it to really understand the subject matter, then yes, you need some of the theory as well as the practical knowledge.

As for parsing, simple recursive descent will serve well to get them understanding the concept. Parsing tools come and go. Don't make them learn a bunch of nitty gritty that they will likely never use outside of your course.

Note: I am a practical compiler-writer. I've written a half-dozen compilers, all without any lex/yacc-type tools. So, if my advice sounds wrong from a purely teaching point of view, by all means be more abstract.


---

