運算子與運算式

December 18, 2021

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

Toy 語法

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

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

在 Toy Lang 中,可以用於運算式的運算子有:

  • 算術運算:+-*/%
  • 邏輯運算:andornot
  • 關係運算:==!=>=><=
  • 位元運算:&|^>><<
  • 實例運算:new
  • 物件操作:.

andor 有捷徑運算的效果,運算元不用是 truefalse 的結果,0''false 都會被當成不成立,其他都是成立,andor 在可以判定結果成立與否時,當時的運算元會被傳回。例如:

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 的運算子,然而必須注意有捷徑運算功能的 andor

我一開始也忘了處理捷徑運算,直到後來在實作〈常見程式演算〉裏的題目找 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 做不到的事,例如之後會談到,任意深度的對稱括號比對就是一個例子。

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