運算子與運算式

任何語言中最基本的運算子，無非就是 +、-、*、/ 等算術運算子，用在數值運算時就是加、減、乘、除運算。

Toy 語法

+ 在許多語言中可以串接字串，Toy Lang 中也不例外：

println('Just' + 'in') # 顯示 Justin

在 Toy Lang 中，可以用於運算式的運算子有：

算術運算：+、-、*、/、%
邏輯運算：and、or、not
關係運算：==、!=、>=、>、<=
位元運算：&、|、^、>>、<<
實例運算：new
物件操作：.

and、or 有捷徑運算的效果，運算元不用是 true 或 false 的結果，0、''、false 都會被當成不成立，其他都是成立，and 與 or 在可以判定結果成立與否時，當時的運算元會被傳回。例如：

println(0 or 'Justin')          # 顯示 Justin
println('Justin' and 'Monica')  # 顯示 Monica

嗯？null 呢？Toy Lang 中沒有這東西，Toy Lang 中沒有顯式的 null 可以使用，放棄它吧！…XD

運算子有其優先順序，大致上與其他語言相同，如果不確定的話，當然就是加上括號：

x = (1 + 2) * (3 + 4)
println(x)  # 顯示 21

= 是個指定，除了它之外，還有 +=、-=、*=、/=、%=、&=、|=、^=、<<=、>>=，這之後的文件再來談。

Toy 實現

在實現語言時，最基本的開始就是實現運算式，就最簡單的加法來說，想要實現 1 + 2 的話：

class Context {
}

class Num {
	constructor(value) {
		this.value = value;
	}

	evaluate(context) {
		return this;
	}
}

class Add {
	constructor(left, right) {
		this.left = left;
		this.right = right;
	}

	evaluate(context) {
		return new Num(
			this.left.evaluate(context).value + this.right.evaluate(context).value
		);
	}
}

const r = new Add(new Num(1), new Num(2)).evaluate(new Context());

若要取得運算後的值，透過 r.value 就可以了，對於基本型態來說，Context 這個環境物件通常沒有作用，之後還會看到 Context 實際發揮效用的場合，目前只是為了令語法節點有一致的 evaluate 協定而傳入。

就單詞的語法節點來說，真正重要的只在建構式，evaluate 則是賦予該節點實際運算意義的部份，Toy Lang 是將兩者寫在一起同一個類別之中。

那麼，對於 (1 + 2) * (3 + 4) 該如何展現呢？基本上是這樣的：

class Multiply {
	constructor(left, right) {
		this.left = left;
		this.right = right;
	}

	evaluate(context) {
		return new Num(
			this.left.evaluate(context).value * this.right.evaluate(context).value
		);
	}
}

const node = new Multiply(
	new Add(new Num(1), new Num(2)),
	new Add(new Num(3), new Num(4))
);

const r = node.evaluate(new Context());

對於語法樹來說，節點的組合本身，已經包含了運算的先後順序，問題就在於，那這個節點的建立順序是怎麼完成的，總要有個地方處理括號、決定節點的組合方式吧！

這部份就是 Parser 的職責，而且 Parser 在處理運算式這方面的實現並不輕鬆，畢竟整個程式，就像是一條超大型運算式組合而成，當中會有許多運算子、運算元，充滿了文法的遞迴性。

你可以試著從 +、-、*、/ 的剖析開始，至於運算子的優先順序處理，我採用的方式是中序式轉後序式，接著是用後序式進行運算，沒錯，就是〈中序式轉後序式〉、〈後序式的運算〉作出發點。

首先，必須將 (1 + 2) * (3 + 4)，因而必須切割單詞，然後轉為 12+34+*，單詞的切割是使用 Regex，這就是先前為何要談到，如何為數值、字串等定義 Regex 的原因。

接著下一步並不是直接對 12+34+* 作運算，而是對 12+34+* 進行節點的組合，這部份的實現撰寫在 expr_parse.js 之中，// expression 註解的後面：

// expression

function exprAst(tokenables) {
	return tokenables.reduce((stack, tokenable) => {
		if(isBinaryOperator(tokenable.value)) {
			return reduceBinary(stack, tokenable);
		} 

		if(isUnaryOperator(tokenable.value)) {
			return reduceUnary(stack, tokenable);
		}         

		return stack.push(
			OPERAND_PARSER.parse(tokenable)
		);
	}, new Stack()).top;
}

function precedence(operator) {
	switch(operator) {
		case '.':    return 14;
		case 'new':  return 13;
		case '$neg': return 12;
		case 'not':  return 11;
		case '*': case '/': case '%':
						return 10;
		case '+': case '-':
						return 9;
		case '<<': case '>>':
						return 8;
		case '>=': case '>': case '<=': case '<':
						return 7;
		case '==': case '!=':
						return 6;
		case '&':    return 5;
		case '^':    return 4; 
		case '|':    return 3;
		case 'and':  return 2;
		case 'or':   return 1;
		default:     return 0; 
	}
}

略 ...

運算子的優先順序只要定義好，〈中序式轉後序式〉、〈後序式的運算〉中的方式就可以適用更多的運算子，precedence 函式中定義的就是運算子的優先順序。

文件中有提到，在化簡二元運算子時，會從堆疊中取出兩個運算元，文件中沒提到的是，運算子中其實會有單元運算子，這部份只要取出一個運算元就可以了。

還有文件中沒提到的是 -，它可以當成是減法二元運算子，然而，也可以當成是負號單元運算子，Regex 中可以使用旁觀（look around）比對，不過我當時忘記運用它了，因而是直接在程式中判斷。無論是採用哪種方式，如果 - 前並不是運算元（而是 ) 或其他運算子）的話，就表示它是個負號單元運算子。

運算子的語法節點，獨立定義在 operator.js 裏頭，雖然大部份運算子，我都直接對應至 JavaScript 的運算子，然而必須注意有捷徑運算功能的 and 與 or。

我一開始也忘了處理捷徑運算，直到後來在實作〈常見程式演算〉裏的題目找 bug 時，才發現怎麼沒有捷徑運算的效果，簡單來說，不能左右運算元都估值，而是先估值左運算元，接著才決定要不要估值右運算元，以 and 的節點為例：

class AndOperator {
	constructor(left, right) {
		this.left = left;
		this.right = right;
	}

	evaluate(context) {
		const maybeCtxLeft = this.left.evaluate(context); // 先估值左運算元
		return maybeCtxLeft.notThrown(
			left => {
				if(left.value === undefined ? left.toString(context) : left.value) {
					// 左運算元成立才會執行右運算元估值
					return this.right.evaluate(context).notThrown(right => right);
				}
				return left;
			}
		);
	}
}

如先前談到的，運算式的剖析與處理並不輕鬆，Regex 的定義以及比對的順序至關重要，你可以在 regex.js 中看到一些比對的範本，若是你想挑戰看看實作運算式，可以參考一下。

必須說的是，使用 Regex 來做運算式的比對，並不完全適合，因為 Regex 是上下文無關（context-free）的語言，然而，若想實作的語言是上下文相關語言，會有許多 Regex 做不到的事，例如之後會談到，任意深度的對稱括號比對就是一個例子。

我若有心力實作下一門語言的話，將單詞切割階段獨立出來，自行設計狀態機之類的東西來辨別語法結構等，會是屆時的實現目標。