week4.md

參考 魏仲彥筆記

程式碼解說 03-compiler

gcc genEnlish.c rlib.c : 生成執行檔案 a.exe

./a.exe: 執行檔案

00-gen

genEnglish.c: 產生英文句子

#include "rlib.h"

// === EBNF Grammar =====  //  生成語法
// S = NP VP               //  代表一個句子
// NP = DET N              //  量詞+名詞
// VP = V NP               //  動詞+量詞+名詞
// N = dog | cat           //  名詞
// V = chase | eat         //  動詞
// DET = a | the           //  量詞

char* n[] = {"dog", "cat"};
char* v[] = {"chase", "eat"};
char* det[] = {"a", "the"};

void N() {
  printf("%s", randSelect(n, 2));  // 從n陣列隨機選一個列出，後面代表陣列大小
}

void V() {
  printf("%s", randSelect(v, 2));
}

void DET() {
  printf("%s", randSelect(det, 2));
}

void NP() {
  DET();
  printf(" ");
  N();
}

void VP() {
  V();
  printf(" ");
  NP();
}

void S() {
  NP();
  printf(" ");
  VP();
  printf("\n");
}

int main() {
  timeSeed();  // 讓每次產生的數字不一樣，用時間當作亂數種子
  S();
}

genExp.c: 產生數學隨機運算式

#include "rlib.h" // 引用不是系統路徑的函式庫要用 ""

void E();
void T();
void F();

// === EBNF Grammar ===== 
// E=T ([+-] T)*          // [+-]: 選擇+或- 、 ()*: (內容可以重複一次以上)
// T=F ([*/] F)? 
// F=[0-9] | (E)          // [0到9選擇一個] 或是 呼叫上面的E，這有遞迴

// argc 和 argv[] 接收到終端機的字元，帶到main裡面
int main(int argc, char * argv[]) {  
    timeSeed();
    // E();
    int i;
    for (i=0; i<10; i++) {
        E();
        printf("\n");
    }
}

// E=T ([+-] T)*
void E() {
    T();
    while (randInt(10) < 3) {
       printf("%c", randChar("+-"));
       T();
    }
}

// T=F ([*/] F)?
void T() {
    F();
    if (randInt(10) < 7) {
        printf("%c", randChar("*/"));
        F();
    }
}

// F=[0-9] | (E)
void F() {
    if (randInt(10) < 8) {
        printf("%c", randChar("0123456789"));
    } else {
        printf("(");
        E();
        printf(")");
    }
}

rlib.c

#include "rlib.h"

// int randInt(int n):隨機傳回一個小於 n 的整數 (0,1,2..., n-1)
// 用法:randInt(5) 會傳回 0, 1, 2, 3, 4 其中之一
int randInt(int n) { // 隨機傳回一個小於 n 的整數 (0,1,2..., n-1)
  return rand() % n;
}

// int randChar(char *set):隨機傳回 set 中的一個字元
// 用法:randChar("0123456789") 會傳回一個隨機的數字
int randChar(char *set) { // 隨機傳回 set 中的一個字元
  int len = strlen(set);  // string.h
  int i = rand()%len;
  return set[i];
}

// int randSelect(char* array, int size):隨機傳回 array 中的一個字串
// 用法:randSelect({"dog", "cat"}, 2) 會傳回二選一的字串
char *randSelect(char* array[], int size) {
  int i = rand()%size;
  return array[i];
}

void timeSeed() {  // 產生亂數種子
  long ltime = time(NULL);  // long = long int
  // printf("ltime=%ld\n", ltime);
  int stime = (unsigned) ltime/2; // 轉型態，這行可以省
  srand(stime);  // srand(time(NULL))  // int long有些會平台相容有些不會
}

rlib.h，.h檔可以讓其他.c檔案引用，需要把函式型態宣告在裡面

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

int randInt(int n);
int randChar(char *set);
char *randSelect(char* array[], int size);
void timeSeed();

01-exp0

運算式編譯器

EE.c

#include <stdio.h>
void F();

// E = F
void E() {
  printf("E started\n");
  // E();
  F();
  printf("E finished\n");
}

// F = 'F'
void F() {
  printf("  F started\n");
  printf("    F\n");
  printf("  F finished\n");
}

int main() {
  E();
}

exp0.c: 編譯器程式碼(把過程打印在終端機)，這個程式碼只能處理單字元 3+1 不能 30+1，不能處理變數

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <ctype.h>

int tokenIdx = 0;
char *tokens; // 紀錄容器位置(argv[1])

int E();
int F();

void error(char *msg) {
  printf("%s", msg);
  assert(0);
}

// 取得目前字元
char ch() {
  char c = tokens[tokenIdx];
  return c;
}

// 取得目前字元，同時進到下一格
char next() {
  char c = ch();
  tokenIdx++;
  return c;
}

// ex: isNext("+-") 用來判斷下一個字元是不是 + 或 -
int isNext(char *set) {
  char c = ch();
  return (c!='\0' && strchr(set, c)!=NULL);
}

// 產生下一個臨時變數的代號， ex: 3 代表 t3。
int nextTemp() {
  static int tempIdx = 0; // 會一直存在裡面，值不會改變(放在bss段)
  return tempIdx++;
}

// F =  Number | '(' E ')'
int F() { // Factor
  int f;
  char c = ch();
  if (isdigit(c)) {  // 確認是不是單一數字
    next(); // skip c
    f = nextTemp();
    printf("t%d=%c\n", f, c);
  } else if (c=='(') { // '(' E ')'
    next(); // 把誇號去掉
    f = E();
    assert(ch()==')'); // 如果誇號的後面還是誇號就跳出程式
    next();
  } else { // 不是數字也不是誇號就報錯
    error("F = (E) | Number fail!");
  }
  return f; 
}

// E = F ([+-] F)*
int E() {  
  int i1 = F();
  while (isNext("+-")) {
    char op=next();
    int i2 = F();
    int i = nextTemp();
    printf("t%d=t%d%ct%d\n", i, i1, op, i2);
    i1 = i;
  }
  return i1;
}

void parse(char *str) {
  tokens = str;
  E();
}

int main(int argc, char * argv[]) {
  printf("argv[0]=%s argv[1]=%s\n", argv[0], argv[1]);
  printf("=== EBNF Grammar =====\n");
  printf("E=F ([+-] F)*\n");
  printf("F=Number | '(' E ')'\n");
  printf("==== parse:%s ========\n", argv[1]);
  parse(argv[1]);
}

exp0var.c: 把指令轉換成組合語言，一樣只能處裡單一字符，把結果變成hack CPU的組合語言，可以記憶變數(x+y)，到這裡還是只能判斷 +-

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <ctype.h>

int tokenIdx = 0;
char *tokens; // 紀錄容器位置(argv[1])

int E();
int F();

void error(char *msg) {
  printf("%s", msg);
  assert(0);  // 只要值是0或是false就強制退出，並印出stack
}

char ch() {  // 取得字符並傳回
  char c = tokens[tokenIdx];
  return c;
}

char next() {  // 前往下一個字符
  char c = ch();
  tokenIdx++;
  return c;
}

int isNext(char * set) {  // 判斷下一個自符又沒有在集合裡面
  char c = ch(); 
  return (c!='\0' && strchr(set, c)!=NULL);
}

int nextTemp() {  // 創造新的臨時變數
  static int tempIdx = 0;
  return tempIdx++;
}

void genOp1(int i, char c) {
  printf("# t%d=%c\n", i, c);
  // t1=3 轉成 @3; D=A; @t1; M=D
  // t1=x 轉成 @x; D=M; @t1; M=D
  printf("@%c\n", c);
  char AM = (isdigit(c)) ? 'A':'M';
  printf("D=%c\n", AM);
  printf("@t%d\n", i);
  printf("M=D\n");
}

void genOp2(int i, int i1, char op, int i2) {
  printf("# t%d=t%d%ct%d\n", i, i1, op, i2);
  // t0=t1+t2 轉成 @t1; D=M; @t2; D=D+M; @t0; M=D;
  printf("@t%d\n", i1);
  printf("D=M\n");
  printf("@t%d\n", i2);
  printf("D=D%cM\n", op);
  printf("@t%d\n", i);
  printf("M=D\n");
}

// F =  Number | ID | '(' E ')'
int F() {
  int f;
  char c = ch();
  if (isdigit(c) || (c>='a'&&c<='z')) {  // 這個可以處裡變數
    next(); // skip c
    f = nextTemp();
    genOp1(f, c);
  } else if (c=='(') { // '(' E ')'
    next();
    f = E();
    assert(ch()==')');  // 誇號開頭就要誇號結束，如果沒有誇號就強制退出
    next();
  } else {
    error("F = (E) | Number fail!");
  }
  return f; 
}

// E = F ([+-] F)*
int E() {
  int i1 = F();
  while (isNext("+-")) {  // 偵測到 +- 就前往下一個字符
    char op=next();  // 前往下一個字符
    int i2 = F();  
    int i = nextTemp();
    genOp2(i, i1, op, i2);
    i1 = i;
  }
  return i1;
}

void parse(char *str) {
  tokens = str;
  E();
}

int main(int argc, char * argv[]) {
  printf("=== EBNF Grammar =====\n");
  printf("E=F ([+-] F)*\n");
  printf("F=Number | ID | '(' E ')'\n");
  printf("==== parse:%s ========\n", argv[1]);
  parse(argv[1]);
}