# Compiler Week 3
:::danger
[Course link](http://cc.ee.ntu.edu.tw/~farn/courses/Compiler/2021.spring/index.htm)
:::
:::success
Instead of the manual method described below, there is a productivity extension for controlling video playback rate with keyboard shortcuts:
[Video Speed Controller](https://chrome.google.com/webstore/detail/video-speed-controller/nffaoalbilbmmfgbnbgppjihopabppdk)
:::
:::info
To set the YouTube video playback rate to some particular number, e.g., $\pi$, execute the following command in the browser's console; use `Command + Option + J` or `Control + Shift + J` to access Chrome's console.
```javascript
document.querySelector('video').playbackRate = Math.PI
```
What this actually does is setting the playback rate of the first `<video>` tag on the page to $\pi$, which happens to be the main video on any YouTube page.
:::
:::warning
Many links in this page refer to [text fragments](https://web.dev/text-fragments/#text-fragments) which are known to work on Chrome 80 and above.
**I** can't say about other browsers.
:::
## Q&A
### Classify the following as front-end or back-end components
- **Target code optimizer**: back-end
- **Parser**: front-end
- **Scanner**: front-end
- **IR code generator**: front/middle-end
- **Type checker**: front-end
### Classify 1-3 as (a) or (b)
(a) a common back-end compiling system
(b) a retargetable compiler
1. **HP PA-RISC compiler/optimizer**: (a)
2. **Intel C++ Compiler Classic (ICC)**: (a) for C/C++ (b) for x86/x64
- According to the [developer's guide](https://software.intel.com/content/www/us/en/develop/documentation/cpp-compiler-developer-guide-and-reference/top.html#top:~:text=Intel%C2%AE%20C%2B%2B%20Compiler%20Classic%20(icc)), ICC actually stands for Intel C++ Compiler Classic.
- x86 refers to IA-32 whereas x64 refers to IA-64
3. **GNU Compiler Collection (GCC)**: (b)
- Nowadays, [GCC stands for GNU Compiler Collection]((https://gcc.gnu.org/)); historically, at version 1.0, [GCC actually stood for GNU C Compiler](https://en.wikipedia.org/wiki/GNU_Compiler_Collection#cite_ref-loc_4-1:~:text=GCC%201.0%20was%20named%20the%20GNU%20C%20Compiler).
- Even in the stricter sense, referring exclusively to the C compiler, GCC is still (b).
### How to create the first C compiler on the Itanium machine?
- [ ] Write a C compiler in C, compile it on Itanium machines using GCC.
- This line of reasoning is incoherent.
If the first C compiler for Itanium is being developed, GCC wouldn't be able to target Itanium.
- [x] Write a C compiler in Itanium machine code.
- One doesn't attempt this feat unless one is [Jeff Dean](https://www.reddit.com/r/todayilearned/comments/11qqrz/til_that_googles_most_badass_engineer_jeff_dean/c6ow1ff?utm_source=share&utm_medium=web2x&context=3).
- [x] Develop a cross-compiler on x86 and use it to compile itself into Itanium instructions.
- A cross compiler is a compiler that can generate instructions for some CPU architecture different from the one it is running on.
E.g., GCC running on an Intel machine can compile sources as ARM binaries.
A cross compiler targeting Itanium can compile its source code on x86 to produce its Itanium counterpart which can then be executed on Itanium as a native compiler.
- [This](https://hackmd.io/@mcnlab538/rk0rWidQP) illustrates the process.
- [ ] Leave it to Intel/Microsoft, i.e., evil empire.
- **Why not?** Why is the professor against this.
### How to create the first C compiler on the new Itanium if no cross-compiler is available?
Incremental ==bootstrapping==.
1. Craft a simple assembler, C1, in Itanium machine code, i.e., directly editing a binary file from scratch.
2. Craft a more complex assembler, C2, in Itanium assembly with C1.
3. Craft a simple C compiler, C3, with C2.
4. Craft a more complex C compiler, C4, with C3.
5. Continue step 4 for several iterations until a good enough C compiler, C0, is finally produced.
Then, C0 is what we seek for.
### Evaluate `1u > -1` in C/C++
Comparing `unsigned int` with `int` is defined behavior in C/C++: `int` is coerced to `unsigned int` for comparison.
Since -1 has all bits being 1 in 2's complement, `1u > -1` evaluates to ==`false`== in most cases.
In fact, C++20 mandates that [all values be represented in 2's complement](https://en.cppreference.com/w/cpp/language/types#Range_of_values:~:text=as%20of%20C%2B%2B20%2C%20it%20is%20the%20only%20representation%20allowed%20by%20the%20standard).
Here are more C\++ specific details.
- `1u` and `-1` are [integer literals](https://en.cppreference.com/w/cpp/language/integer_literal) that are of type `unsigned int` and `int`, respectively.
- Coercion of mismatched operand types of an [arithmetic (comparison) operator](https://en.cppreference.com/w/cpp/language/operator_comparison#Arithmetic_comparison_operators:~:text=If%20the%20operands%20has%20arithmetic%20or,The%20values%20are%20compared%20after%20conversions%3A) is called [usual arithmetic conversion](https://en.cppreference.com/w/cpp/language/operator_arithmetic#Conversions:~:text=as-,usual%20arithmetic%20conversions).
In this case, usual arithmetic conversion is due to [the unsigned operand's *conversion rank* being equal to the *conversion rank* of the signed operand, thus, requiring the signed operand to be converted to the unsigned operand's type](https://en.cppreference.com/w/cpp/language/operator_arithmetic#Conversions:~:text=Otherwise%2C%20if%20the%20unsigned%20operand's%20conversion,converted%20to%20the%20unsigned%20operand's%20type.) where [the *conversion rank* of any unsigned type is equal to the rank of the corresponding signed type](https://en.cppreference.com/w/cpp/language/operator_arithmetic#Conversions:~:text=The%20rank%20of%20any%20unsigned%20type%20is%20equal%20to%20the%20rank%20of%20the%20corresponding%20signed%20type.).
- For best practices, consult the [*Arithmetic*](https://web.dev/text-fragments/#text-fragments) section (consists of only 8 points; **highly recommended**) of C++ Core Guidelines.
Honorable mentions:
- ES.100: Don’t mix signed and unsigned arithmetic.
- ES.101: Use unsigned types for bit manipulation.
- ES.102: Use signed types for arithmetic.
- ES.106: Don’t try to avoid negative values by using `unsigned`.
- In fact, the C++ standard library devoted a whole class -- [`std::bitset`](https://en.cppreference.com/w/cpp/utility/bitset) -- to bit manipulation.
- For safer integral comparisons, C++20 provides [`std::cmp_{equal,not_equal,less,greater,less_equal,greater_equal}`](https://en.cppreference.com/w/cpp/utility/intcmp).
- C++20 also provides safer [math constants](https://en.cppreference.com/w/cpp/symbol_index/numbers) belonging to the namespace `std::numbers`.
### Which of the following are in the language defined by the AC syntax?
- [x] `f b i a a = 0 b = a + 3.2 p b`
```graphviz
digraph {
nodesep=0
node [fontname=Arial,shape=none]
1 [label="Dcls"]
2 [label="Dcl"]
3 [label="floatdcl\nf"]
4 [label="id\nb"]
5 [label="Dcls"]
6 [label="Dcl"]
7 [label="intdcl\ni"]
8 [label="id\na"]
9 [label="Dcls"]
10 [label="λ",shape=circle]
11 [label="Stmts"]
12 [label="Stmt"]
13 [label="id\na"]
14 [label="assign\n="]
15 [label="Val"]
16 [label="inum\n0"]
17 [label="Expr"]
18 [label="λ",shape=circle]
19 [label="Stmts"]
20 [label="Stmt"]
21 [label="id\nb"]
22 [label="assign\n="]
23 [label="Val"]
24 [label="id\na"]
25 [label="Expr"]
26 [label="plus\n+"]
27 [label="Val"]
28 [label="fnum\n3.2"]
29 [label="Expr"]
30 [label="λ",shape=circle]
31 [label="Stmts"]
32 [label="Stmt"]
33 [label="print\np"]
34 [label="id\nb"]
35 [label="Stmts"]
36 [label="λ",shape=circle]
Prog [shape=oval]
"$" [shape=circle]
Prog -> {1 11 "$"}
1 -> {2 5}
2 -> {3 4}
5 -> {6 9}
6 -> {7 8}
9 -> 10
11 -> {12 19}
12 -> {13 14 15 17}
15 -> 16
17 -> 18
19 -> {20 31}
20 -> {21 22 23 25}
23 -> 24
25 -> {26 27 29}
27 -> 28
29 -> 30
31 -> {32 35}
32 -> {33 34}
35 -> 36
{rank=same; 10 18 30 36 "$" 27}
{rank=same; 3 4 7 8 13 14 16 21 22 24 26 28 33 34}
}
```
- [ ] `p`++`15`++
An `id` must follow `print`.
```graphviz
digraph {
nodesep=0
node [fontname=Arial,shape=none]
Prog [shape=oval]
1 [label="Dcls"]
2 [label="λ",shape=circle]
3 [label="Stmts"]
5 [label="Stmt"]
6 [label="Stmts"]
4 [label="λ",shape=circle]
7 [label="print\np"]
8 [label="inum\n15"]
"$" [shape=circle]
Prog -> {1 3 "$"}
1 -> 2
3 -> {5 6}
5 -> 7
5 -> 8 [label="expects id", style=dashed, color=red, fontcolor=red]
6 -> 4
{rank=same; 2 4 "$" 5}
}
```
- [x] An empty file
```graphviz
digraph {
nodesep=0
node [fontname=Arial,shape=none]
Prog [shape=oval]
1 [label="Dcls"]
2 [label="λ",shape=circle]
3 [label="Stmts"]
4 [label="λ",shape=circle]
"$" [shape=circle]
Prog -> {1 3 "$"}
1 -> 2
3 -> 4
{rank=same; 2 4 "$"}
}
```
- [ ] `f b a = 1.0`++`i c`++`c = 0 p a`
Note that `a = 1.0` is not a syntax error but a semantics error.
```graphviz
digraph {
nodesep=0
node [fontname=Arial,shape=none]
1 [label="Dcls"]
2 [label="Dcl"]
3 [label="floatdcl\nf"]
4 [label="id\nb"]
11 [label="Stmts"]
12 [label="Stmt"]
13 [label="id\na"]
14 [label="assign\n="]
15 [label="Val"]
16 [label="fnum\n1.0"]
17 [label="Expr"]
18 [label="λ",shape=circle]
19 [label="Dcls"]
20 [label="Dcl"]
21 [label="intdcl\ni"]
22 [label="id\nc"]
23 [label="id\nc"]
24 [label="assign\n="]
25 [label="inum\n0"]
26 [label="Val"]
27 [label="Stmt"]
28 [label="Expr"]
29 [label="λ",shape=circle]
30 [label="Stmts"]
30 -> {27 31}
27 -> {23 24 26 28}
26 -> 25
28 -> 29
31 [label="Stmts"]
32 [label="Stmt"]
33 [label="print\np"]
34 [label="id\na"]
35 [label="Stmts"]
36 [label="λ",shape=circle]
Prog [shape=oval]
"$" [shape=circle]
Prog -> {1 11 "$"}
1 -> 2
2 -> {3 4}
11 -> 12
11 -> 19 [label="expects Stmts", style=dashed, color=red, fontcolor=red]
12 -> {13 14 15 17}
15 -> 16
17 -> 18
19 -> 20
19 -> 30 [label="expects Dcls", style=dashed, color=red, fontcolor=red]
20 -> {21 22}
31 -> {32 35}
32 -> {33 34}
35 -> 36
{rank=same; 17 20}
{rank=same; 18 36 "$" 29 26}
{rank=same; 3 4 13 14 16 21 22 33 34 23 24 25}
}
```
- [ ] `f b i a a = 0 b =`++`-`++`a - 3.2 p b`
```graphviz
digraph {
nodesep=0
node [fontname=Arial,shape=none]
1 [label="Dcls"]
2 [label="Dcl"]
3 [label="floatdcl\nf"]
4 [label="id\nb"]
5 [label="Dcls"]
6 [label="Dcl"]
7 [label="intdcl\ni"]
8 [label="id\na"]
9 [label="Dcls"]
10 [label="λ",shape=circle]
11 [label="Stmts"]
12 [label="Stmt"]
13 [label="id\na"]
14 [label="assign\n="]
15 [label="Val"]
16 [label="inum\n0"]
17 [label="Expr"]
18 [label="λ",shape=circle]
19 [label="Stmts"]
20 [label="Stmt"]
21 [label="id\nb"]
22 [label="assign\n="]
23 [label="?"]
37 [label="minus\n-"]
24 [label="id\na"]
25 [label="Expr"]
26 [label="minus\n-"]
27 [label="Val"]
28 [label="fnum\n3.2"]
29 [label="Expr"]
30 [label="λ",shape=circle]
31 [label="Stmts"]
32 [label="Stmt"]
33 [label="print\np"]
34 [label="id\nb"]
35 [label="Stmts"]
36 [label="λ",shape=circle]
Prog [shape=oval]
"$" [shape=circle]
Prog -> {1 11 "$"}
1 -> {2 5}
2 -> {3 4}
5 -> {6 9}
6 -> {7 8}
9 -> 10
11 -> {12 19}
12 -> {13 14 15 17}
15 -> 16
17 -> 18
19 -> {20 31}
20 -> {21 22}
20 -> 23 [label="expects Val", style=dashed, color=red, fontcolor=red]
20 -> 25
23 -> {37 24}
25 -> {26 27 29}
27 -> 28
29 -> 30
31 -> {32 35}
32 -> {33 34}
35 -> 36
{rank=same; 10 18 30 36 "$" 27}
{rank=same; 3 4 7 8 13 14 16 21 22 37 24 26 28 33 34}
}
```
### What is the associativity of `op` given the grammar `expr -> expr op primary`? How can the grammar be re-defined so as to invert the associativity of `op`?
- Left associative.
- `expr -> primary op expr`
### Identify expressions with *constant folding* potential
- [ ] `3 + 5 * b`
- [ ] ++`a + 5`++`- 4`
Left association doesn't make way for folding `5 - 4`.
- [x] `a +`==`2 * 5`==`+ c`
- [x] ==`2 + 5`==`+ c`
Sign in with Wallet
Connect another wallet