自作プログラミング言語を初級者が1週間で作る方法 (4) 計算の優先順位とif式
自作プログラミング言語をなるべく簡単に作る方法を紹介します。また、実際に自作プログラミング言語を作ってみます。
前回の記事の続きです。今回は二項演算子 13 種類と if 式と () を使えるようにします。
掛け算と割り算
Yuz 言語に掛け算と割り算の文法を付け足します。ここで大事なのが演算子の優先順位です。たとえば 2 + 3 * 4 という式は (2 + 3) * 4 ではなく 2 + (3 * 4) の順で計算する必要があります。このことを、+ よりも * のほうが優先順位が高いといいます。
+ - よりも * / の優先順位が高くなるようにすると Peggy は次のようになります。ただしコードが長くなってしまうので前回の記事で作った Variable と Identifier についてのコードは一旦省きます。
Start
= _ p:Program _ { return eval(p); }
Program
= AddExpression
AddExpression
= head:MultExpression tail:(_ AddOperator _ MultExpression)* {
return tail.reduce((acc, x) => `(${acc}) ${x[1]} (${x[3]})`, head);
}
AddOperator
= "+"
/ "-"
MultExpression
= head:Float tail:(_ MultOperator _ Float)* {
return tail.reduce((acc, x) => `(${acc}) ${x[1]} (${x[3]})`, head);
}
MultOperator
= "*"
/ "/"
Float
= Integer ("." [0-9]+)? { return text(); }
Integer
= [1-9] [0-9]* { return text(); }
/ "0"
_
= [ \t\n\r]*
二項演算の定義を、加減算の AddExpression と乗除算の MultExpression に分けました。そして tail.reduce(...) の ${acc} と ${x[3]} に () を付けました。そうすると Yuz コードが
1 - 2 + 3 * 4 / 5 + 6 * 7 - 8
のとき、変換後の JavaScript コードは
((((1) - (2)) + (((3) * (4)) / (5))) + ((6) * (7))) - (8)
となります。不要な () を一つずつ取り去ってみると
1 - 2 + (3 * 4 / 5) + (6 * 7) - 8
となっており、乗除算が優先されるコードになっていることがわかります。
このような () を付けずに 1 - 2 + 3 * 4 / 5 + 6 * 7 - 8 をそのままにしまっても実は問題ありません。JavaScript の eval() が勝手に乗除算を優先して計算してくれるからです。しかし演算子の優先順位を JavaScript と異なるものにしたり JavaScript にない演算子を作ったりするときにはここで紹介した方法が必要になります。
比較演算と論理演算と真偽値
同じやり方で二項演算子をたくさん作ることができるのでここでまとめて作っておきます。演算子の優先順位は下表のように JavaScript と同じにします。数字が小さいほど（表の下に行くほど）優先順位が高いです。優先順位 1 位は乗除算です。
| 優先順位 | 演算子 | 文法の名前 | 連鎖 |
|---|---|---|---|
| 6 | || |
OrExpression | できる |
| 5 | && |
AndExpression | できる |
| 4 |
== !=
|
EqualExpression | できない |
| 3 |
>= > <= <
|
RelatExpression | できない |
| 2 |
+ -
|
AddExpression | できる |
| 1 |
* / %
|
MultExpression | できる |
上表の EqualExpression と RelatExpression は演算子を連鎖できないようにします。a == b == c や a > b > c は意図したとおりの計算にならないからです。ほかの演算子は a + b - c のように連鎖できるようにします。
また、今までは整数と浮動小数点数しか使えませんでしたが、真偽値も使えるようにします。真偽値は true と false とします。
Peggy のコードは次のようになります。長くなってしまいますが、前回の記事で作った Variable と Identifier のコードも入れておきます。
Start
= _ p:Program _ { return eval(p); }
Program
= vars:(Variable _ ";" _)* e:Expression {
const varsCode = vars.reduce((acc, x) => `${acc}${x[0]}; `, "");
const returnCode = `return ${e};`;
return `(() => { ${varsCode}${returnCode} })()`;
}
Variable
= "let" __ i:Identifier _ "=" _ e:Expression {
return `const ${i} = ${e}`;
}
Expression
= OrExpression
OrExpression
= head:AndExpression tail:(_ OrOperator _ AndExpression)* {
return tail.reduce((acc, x) => `(${acc}) ${x[1]} (${x[3]})`, head);
}
OrOperator
= "||"
AndExpression
= head:EqualExpression tail:(_ AndOperator _ EqualExpression)* {
return tail.reduce((acc, x) => `(${acc}) ${x[1]} (${x[3]})`, head);
}
AndOperator
= "&&"
EqualExpression
= head:RelatExpression tail:(_ EqualOperator _ RelatExpression)? {
return tail === null ? head : `(${head}) ${tail[1]} (${tail[3]})`;
}
EqualOperator
= "==" { return "==="; }
/ "!=" { return "!=="; }
RelatExpression
= head:AddExpression tail:(_ RelatOperator _ AddExpression)? {
return tail === null ? head : `(${head}) ${tail[1]} (${tail[3]})`;
}
RelatOperator
= ">="
/ ">"
/ "<="
/ "<"
AddExpression
= head:MultExpression tail:(_ AddOperator _ MultExpression)* {
return tail.reduce((acc, x) => `(${acc}) ${x[1]} (${x[3]})`, head);
}
AddOperator
= "+"
/ "-"
MultExpression
= head:Primary tail:(_ MultOperator _ Primary)* {
return tail.reduce((acc, x) => `(${acc}) ${x[1]} (${x[3]})`, head);
}
MultOperator
= "*"
/ "/"
/ "%"
Primary
= Float
/ Boolean
/ Identifier
Float
= Integer ("." [0-9]+)? { return text(); }
Integer
= [1-9] [0-9]* { return text(); }
/ "0"
Boolean
= ("true" / "false") !IdentifierContinue { return text(); }
Identifier
= !ReservedWord IdentifierStart IdentifierContinue* {
return `$${text()}`;
}
ReservedWord
= ("let" / "true" / "false" / "if" / "then" / "else") !IdentifierContinue
IdentifierStart
= [a-z_]
IdentifierContinue
= [0-9a-z_]
__
= [ \t\n\r]+
_
= [ \t\n\r]*
EqualOperator は JavaScript の厳密演算子 === !== に変換されるようにしました。
上記の文法だと 4.7 + true && 1 > false のような式を受け入れることになります。このような式の計算結果は JavaScript の仕様に従うことにします[1]。
A / B の注意点
上記のコードで RelatOperator の定義は
">=" / ">"">" !"=" / ">="
のどちらかである必要があります。
">" / ">="
としてしまうと >= にマッチさせることができなくなります。Peggy[2] の A / B は、まず A にマッチするかどうかを調べます。もし A にマッチしたら B を調べずに A を採用します。A にマッチしなかったときは B にマッチするかどうかを調べます。
何が起こるのかを詳しく考えてみます。3 >= 2 という Yuz コードが RelatExpression にマッチするかどうかを考えます。
-
RelatOperatorの定義が">" / ">="だと>にマッチして= 2が余ります。RelatOperatorの次はAddExpressionでなければなりませんが、= 2はAddExpressionにマッチしません。したがって3 >= 2というコードを受理できません。 -
RelatOperatorの定義が">=" / ">"だと>=にマッチして2が余ります。RelatOperatorの次はAddExpressionでなければなりませんが、2はAddExpressionにマッチします。したがって3 >= 2というコードを受理できます。
以上のことから RelatOperator の定義は ">=" / ">" である必要があります。否定先読みを用いて ">" !"=" / ">=" としても構いません。
if 式
比較演算や論理演算ができるようになったので if 式の文法を作ってみます。if 式は
let hoge = if x < 100 then x else 100;
のような式です。これと同じことをする JavaScript のコードは
const hoge = x < 100 ? x : 100;
となります。JavaScript にも if 文はありますが、値を返すことができません。今回は値を返せる if 式を作ろうと思いますので a ? b : c に変換します。
if 式の定義は Expression のところに加えます。
Expression
= IfThenElseExpression
/ OrExpression
IfThenElseExpression
= "if" __ a:Expression __ "then" __ b:Expression __ "else" __ c:Expression {
return `${a} ? ${b} : ${c}`;
}
IfThenElseExpression の定義の中にもう一度 Expression を入れました。このような循環した定義にすると if 式の中に if 式を入れられるようになります。そうすると
if 1 < 2 then 3 else if 4 < 5 then 6 else 7
のように else if を書くことができるようになります。
優先順位の小括弧
if 式は二項演算よりも優先順位が低いので
1 + 2 + if 3 < 4 then 5 else 6 + 7
と書いたときには
1 + 2 + if 3 < 4 then 5 else (6 + 7)
という計算になります。この計算を
1 + 2 + (if 3 < 4 then 5 else 6) + 7
という順番にしたいときには優先順位を表す () が必要です。また、1 + 2 * 3 を (1 + 2) * 3 にしたいときにも () が必要です。
そこで Yuz 言語でも () を使えるようにします。Primary に () についての定義を加えます。
Primary
= Paren
/ Float
/ Boolean
/ Identifier
Paren
= "(" _ e:Expression _ ")" { return `(${e})`; }
これで () を使えるようになりました。
コードブロック
普通は () の中に入れられるのは Expression までです。しかしここでは () の中に Program を入れられるようにしてみます。
Paren
= "(" _ p:Program _ ")" { return `(${p})`; }
そうすると () 内で変数宣言をすることができ、
if x > 1 then (
let a = 1;
a + 2
) else (
let a = 3;
let b = 4;
a + b + 5
)
のような複雑な if 式を書けるようになります。() 内で宣言された変数はその () 内でのローカル変数となります。
高速化
この記事は自作言語を手軽に作ってみることを目的としているので実行速度のことはあまり気にしていません。しかし全く気にしないでいると不安になってくるので少し工夫をしてみます。Program のところに次のような if 文を付け足します。
Program
= vars:(Variable _ ";" _)* e:Expression {
if (vars.length === 0) {
return e;
}
const varsCode = vars.reduce((acc, x) => `${acc}${x[0]}; `, "");
const returnCode = `return ${e};`;
return `(() => { ${varsCode}${returnCode} })()`;
}
そうすると Yuz コードの () 内に変数宣言がないときに変換後の JavaScript コードが簡略化されます。Yuz コードが 2 * (3 + 4) のとき、簡略化前の JavaScript コードは
(() => { return (2) * (((() => { return (3) + (4); })())); })()
ですが、簡略化後の JavaScript コードは
(2) * (((3) + (4)))
となります。参考程度としておきます。
まとめ
今回は二項演算子 13 種類と if 式と () が使えるようになりました。次回は関数を使えるようにします。
Discussion