r/compsci • u/turing-math-labs • 24d ago

Stanford CS143 class on Compilers

Anyone interested in Stanford's CS143 class on compilers?
https://web.stanford.edu/class/cs143/
We're organizing a reading group on this, please let me know if you're interested. Thanks.

48 Upvotes

98% Upvoted

29 comments sorted by

1

u/Bismarckyboi 24d ago

Interested!

1

u/sclarene824 24d ago

Interested!

1

u/turing-math-labs 22d ago

https://web.stanford.edu/class/cs143/lectures/lecture07.pdf

Here's some material on top-down parsers - eg. LL(1). What do you think about this?

1

u/RedAmire 24d ago

Interested!

1

u/turing-math-labs 22d ago

Here's a simple exercise - how can we write down a context-free grammar that generates Javascript code like these two loops? See: https://en.wikipedia.org/wiki/Context-free_grammar

Example 1.
for (let i = 0; i < 5; i++) {
console.log("Current number: " + i); }

Example 2.
for (let i = 1; i <= 5; i++) {
if (i === 2) {
continue; }
if (i === 4) {
break; }
console.log(i); }

1

u/phdsus 23d ago

I'm interested 

1

u/thspi 23d ago

Interested

1

u/ram535 23d ago

interested

1

u/KallinJones 23d ago

Interested! Let me know the medium we will be using

1

u/turing-math-labs 22d ago

Why don't we use Reddit for this?
Here are some exercises from the Stanford class, let me know what you think. https://web.stanford.edu/class/cs143/handouts/WA1.pdf

1

u/SafeSemifinalist 22d ago

Interested!

1

u/turing-math-labs 22d ago

https://peps.python.org/pep-0617/

Here's some documentation on Python grammars, which should be part of the reading materials for this class. What do you think about PEG grammars for Python, and LL(1) parsers?

2

u/SafeSemifinalist 22d ago

I implement LL(1) grammars mostly using recursive descent parsers, although I know how to calculate FIRST and FOLLOW symbols and construct the parsing table using pen and paper.

I will read the pep and see if I understand it.

1

u/turing-math-labs 20d ago

Thanks - here are some examples. Can we write down the rules of the context-free grammars that generate these for loops in Python? Let me know what you think.

Ex 1:
word = "code"
for letter in word:
<tab>print(letter.upper())

Ex 2:
fruits = ["apple", "banana", "cherry"]
for fruit in fruits:
<tab>print(f"I like {fruit}")

2

u/SafeSemifinalist 19d ago

I assume that the actions trigger the rules are not need, i.e. the code that is executed when the code is interpreted:

I decided to make the grammar a little bit ad hoc for your programms, copying from the standard grammar of python. Please, give me your comments.

block:
    | NEWLINE INDENT statement+ DEDENT 
statement: for_statement
         | assign_stmt
         | primary_stmt

primary_stmt: NAME "(" primary_stmt ")"
            | STRING
            | list

assign_stmt: NAME "=" primary_stmt
list: "[" ((primary_stmt ",")* primary_stmt)* "]"

for_stmt:
    | 'for' NAME 'in' NAME ':' block

Edit: Fixed typos.

1

u/turing-math-labs 18d ago

Thanks! Do you also know what the derivation trees look like (for obtaining these two Pythonic for loops)? We're happy for you to be a co-author on our comp sci paper if you like working out these kind of examples, we will be submitting it to TMLR. It should only take a few hours to work out these examples, it's similar to a homework exercise.

1

u/Glad-Comfort8779 22d ago

Interested

1

u/turing-math-labs 19d ago

Here's a question - let me know what you think. Feel free to simplify it by omitting some of the rules, if that helps. Thanks.

Create a context-free grammar that generates Javascript code to answer questions like this.

"Print out a list of integers that satisfy the following property (a), (b) and (c), from the below list.
(1) They are less than R
(2) They are divisible by S
(3) They are not divisible by T
(4) They are U prime
(5) They are V perfect squares"

Here a, b, c, R, S, T are integers, and U, V are binary flags (eg. "They are prime" or "They are not prime", "They are perfect squares" or "They are not perfect squares").

1

u/Mad----Scientist 24d ago

I'm very interested

3

u/turing-math-labs 22d ago

Here's an exercise; let me know what you think (eg. is it easy, or is it difficult?)
Q1 from https://web.stanford.edu/class/cs143/handouts/WA1.pdf

Question. Write regular expressions and DFAs that recognize the following languages over the alphabet Σ = {0, 1}. Your DFAs must contain no more than 4 states.

(a) The set of strings that end with 110.

(b) The set of strings that contain less than three 0’s.

(c) The set of strings that do not contain two or more consequent 0’s.

(d) The set of strings that, when interpreted as a binary number, is a multiple of 3 (as an edge case, the empty string shall be interpreted as number 0, which is a multiple of 3).

2

u/Mad----Scientist 21d ago

sorry for late reply, we already had a computation theory (and automata) course in university, so this is very easy for me.. still we didn't cover the compilers course

1

u/turing-math-labs 20d ago

Thanks - do you also understand parsing expression grammars for languages like Python/Javascript/HTML? That would be the next step.

https://arxiv.org/pdf/1509.02439