パーサジェネレーターLIME入門その３(単項演算子にマッチさせる)

この記事は
[パーサジェネレーターLIME入門](https://qiita.com/ryu_shizumi/items/254c09736526878e4639)
[パーサジェネレーターLIME入門その２(二項演算式にマッチさせる)](https://qiita.com/ryu_shizumi/items/f4ef3c016a8968516cfa)
の続きになります。

今回は「後置デクリメント」「前置デクリメント」「前置マイナス」といった単項演算子にマッチさせる定義と、単項と二項演算の減算が複合する Nnn----Aaa のような式を正確にマッチングさせる方法を解説します。



#今回大事になる用語の説明
「オペレータ」は演算子、「オペランド」は演算の対象です。

例えば`810+114514` という二項演算式の場合、
`810`は「左オペランド」
`+`が「オペーレータ(演算子)」
`114514`は「右オペランド」となります。

演算子とオペランドが合わさった式を「演算式」と呼ぶ事にします。

#式(expression) と 文(statement) の違い
オペランドになれたり変数に代入できるものが「式」です。
実は整数リテラルも識別子も、オペランドになれたり変数に代入できるので式です。

オペランドになれないし変数に代入できないものが「文」です。
そもそも「変数に代入できない」という事は「代入演算のオペランドになれない」という事です。
今回は代入演算文を実装します。

#`-` と `+` の連続に注意

|演算式|解釈|備考|
|---|---|---|
|-Aaa|符号反転||
|--Aaa|前置デクリメント|「マイナスのマイナス」は不可|
|---Aaa|-(--Aaa) 後置デクリメントの符号反転|--(-Aaa) は不可|
|----Aaa|解釈不能|-の連発は４個以上全て不可|
|+Aaa|符号そのまま||
|++Aaa|前置インクリメント|「プラスのプラスは不可」|
|+++Aaa|+(++Aaa) 後置インクリメントの符号そのまま|++(+Aaa) は不可|
|++++Aaa|解釈不能|+の連発は４個以上全て不可|

順に注意点を解説します。

#「マイナスのマイナス」「プラスのプラス」は不可能
--Aaa を「マイナスのマイナス」と解釈してしまっては前置デクリメントを表現する手段が無くなってしまいます。
++Aaa を「プラスのプラス」と解釈してしまっては前置インクリメントを表現する手段が無くなってしまいます。

#--(-Aaa) や ++(+Aaa) と解釈してしまうのは不可
インクリメントやデクリメントのオペランドは書き込み可能変数・書き込み可能プロパティ・書き込み可能インデクサーである必要があるからです。
-(--Aaa) や +(++Aaa) という解釈なら成り立ちます。

…理論上は確かに成り立つのですが、世間に存在するIDEやコンパイラの中には +++Aaa や ---Aaaを受理しないものがあります。Visual Studioも対応していません。
恐らくは構文解析の前段階となる「字句解析(正規表現でソースコードを最小単位に分割する)」の段階で「早い段階で見つかった最長一致」という原則に基づいて `++ +Aaa` や `-- -Aaa` と分割している為と思われます。

一方LIMEは正規表現に頼る必要が無いので字句解析の段階はありません。
１文字単位からパターンを構築する事が可能で、かつ、取り得る可能性の全ての状態を同時に保持しながらマッチングを実行します。
取り得る可能性を勝手に切り捨てないので、複数の解釈が成り立つ場合はマッチ結果を複数返すという動作をします。
デクリメント演算式やインクリメント演算式のオペランドとして変数・プロパティ・インデクサのみを指定するパターンを定義する事で --(-Aaa) や ++(+Aaa) と誤解釈する可能性を無くしつつ -(--Aaa) や +(++Aaa) と解釈するマッチングが可能です。

#----Aaa や ++++Aaaはなぜ不可能なのか？
まずは ----Aaa を考えます。
括弧を補ってみましょう。
-(-(-(-Aaa))) マイナスのマイナスのマイナスのマイナス。論外です。
--(-(-Aaa)) マイナスのマイナスのデクリメント。論外です。
-(-(--Aaa)) デクリメントのマイナスのマイナス。論外です。

--(--Aaa) デクリメントのデクリメント も不可能です。
(--Aaa) の部分はは代入不能な一時変数です。--(代入不能式) は成り立ちません。

結局----Aaaはどうやっても成り立ちません。
同様の理由で++++Aaaも成り立たないのはもう説明不要でしょう。

#次は二項演算の場合
`-` も `+` も要諦は同じなので今回は`-`だけを示します。

|演算式       |解釈|
|-------------|---|---|
|Aaa-Bbb      |(Aaa)-(Bbb)|
|Aaa--Bbb     |(Aaa)-(-Bbb)|
|Aaa---Bbb    |(Aaa)-(--Bbb) 又は (Aaa--)-(Bbb)|
|Aaa----Bbb  |(Aaa)-(-(--Bbb)) 又は (Aaa--)-(-Bbb)|
|Aaa-----Bbb  |(Aaa--)-(--Bbb)|
|Aaa------Bbb |(Aaa--)-(-(--Bbb))|
|Aaa-------Bbb|解釈不能|

`-`の連発は６連発まで可能で、７連発以上は不可能となります。

３連発と４連発はそれぞれ解釈が２通りあり、それぞれが正しいと言えます。
どちらを採用するかは言語仕様によりますが、今回は３連発なら (Aaa--)-(Bbb) を採用し、４連発なら (Aaa--)-(-Bbb) を採用する事にします。

#採用しない方の解釈にマッチさせない方法は？
先の述べたようにLIMEは複数のマッチ結果を返す可能性があります。
現時点でのLIMEの実装では「マッチさせない」はできませんが、「一旦マッチさせておいて後で破棄する」は可能です。
要するにパターンマッチングで合致してしまったマッチは別の検査方法で改めてふるい落とす事になります。
ふるい落とす方法は一旦棚上げしてマッチャーの実装に進みます。

以上、例外的に対応しなければならない単項演算および単項と二項の複合を挙げました。

#実装する演算式の一覧
今回より整数値が複数ケタに対応します。
`(5+9)`のように丸括弧で括って優先順位を高める式を「括弧式」と命名して導入します。
メンバアクセス式・関数呼び出し式・インデックスアクセス式も導入します。
インクリメント・デクリメント・メンバアクセス式のオペランドとして識別子が必要になります。
代入演算も導入します。

今回実装する演算式の優先順位としては下記の通りです。
演算子の優先順位は[C# 演算子](https://docs.microsoft.com/ja-jp/dotnet/csharp/language-reference/operators/)に従っています。

|優先順位|項数|種類  |許容するオペランド  |
|---|----|----------------------|---|
|1  |    |リテラル値式            |各種リテラル値  |
|1  |    |識別子                  |(無し)  |
|1  |単項|括弧式                  |代入可能式以外の全ての式|
|1  |    |代入可能式              |識別子・メンバアクセス式・インデックスアクセス式・代入可能式を括弧で括ったもの|
|1  |単項|関数呼び出し式          |関数呼び出し式・インデックスアクセス・入可能式。各引数は全ての演算式を許容する|
|1  |単項|インデックスアクセス式  |関数呼び出し式・インデックスアクセス・代入可能式。各引数は全ての演算式を許容する|
|1  |単項|後置デクリメント式      |代入可能式|
|1  |単項|後置インクリメント式    |代入可能式|
|1  |二項|メンバアクセス式        |左オペランドは<1> 。右オペランドは識別子|
|1  |    |(1)  (優先順位1)        |リテラル値式・識別子・括弧式・代入可能式・関数呼び出し式・インデックスアクセス式・後置デクリメント式・後置インクリメント式・メンバアクセス式| 
|2  |単項|前置デクリメント式      |代入可能式|
|2  |単項|前置インクリメント式    |代入可能式|
|2  |単項|前置マイナス式          |(1)・前置デクリメント式・前置インクリメント式・前置プラス式|
|2  |単項|前置プラス式            |(1)・前置デクリメント式・前置インクリメント式・前置マイナス式|
|2  |    |(2)  (優先順位2より高い)|(1)・前置デクリメント式・前置インクリメント式・前置マイナス式・前置プラス式| 
|3  |二項|乗除算式                |左オペランドは(3)。右オペランドは(2)|
|3  |    |(3)  (優先順位3より高い)|<2>・乗除算式| 
|4  |二項|加減算式                |左オペランドは(4)。右オペランドは(3)|
|4  |    |(4)  (優先順位4より高い)|(3)・加減算式| 
|999|二項|代入文                  |左オペランドは代入可能式。右オペランドは優先順位4を超えるの全て|


前回解説した二項演算式の場合はオペランドは
「自分と同等以上の優先度の演算式」か「自分を超える優先度の演算式」でした。
今回の表では優先順位3～999に当たります。

優先順位2以上は前回までの常識が通じません。同じ優先度の式であっても同一に扱う事はできません。
ですがこのようにキチンと明文化できるならば実装は可能です。

#リテラル値式
今回の場合該当するのは整数値だけですが、実用的な言語のパーサを実装するなら浮動小数点数・文字・文字列に加えて配列リテラルやラムダ式もこれに該当します。

#識別子
先頭はアンダースコアかアルファベット、２文字目以降は数字も使えます。
C#のように日本語でも有効という仕様は今回は考えません。

#括弧式
優先順位が最優先の整数値・識別子に並ぶという点が重要です。
代入可能式を括弧で括ったものは代入可能式に含め、括弧式に含めません。
代入可能式を除外しないと優先順位の関係で`(6)++`のような式を許す事になってしまいます。

#代入可能式
これは演算ではなく複数の要素をまとめただけです。
インクリメント・デクリメント・代入文のオペランドになれます。
`(Aaa)++`や`(((Aaa)))++`のように括弧で括った状態にも対処する為に、括弧で括った代入可能式もまた代入可能式に含めています。
#関数呼び出し式
`Fff(5,8)`のように関数型の値に引数を与えて実行して値を得る演算です。
0個以上の引数をカンマで区切る事とします。
`Fff`の部分がオペランドとなります。
関数型の値になり得ない整数値・インクリメント演算式・デクリメント演算式はオペランドになれません。
引数リストの中身は全ての演算式が許可されます。
関数呼び出し式が関数型を返すならば`Fff(5,8)(4)`のようにいくつでも連結する可能性があります。

#インデックスアクセス式
`Aaa[5]`のようにインデックスでAaaの内部データにアクセスする演算です。
そもそも「インデックスアクセス式」という名称が正しいのかわかりませんがこう呼んでおく事にします。
1個以上の引数をカンマで区切る事とします。
引数リストの中身は全ての演算式が許可されます。これは関数呼び出し式と共通です。
`Aaa[5][8]`のようにいくつでも連結する可能性がある事も関数呼び出し式と共通です。

#メンバアクセス式
`Aaa.Length`のようにメンバを呼び出す式です。
左オペランドは「自分と同等以上の優先度の演算式」という二項演算の普通のルールに則っています。
右オペランドとなるメンバ名は識別子のみとなります。
Swift言語のようにメンバ名として数値を許可する特別な仕様の言語もありますが、今回は考えない事とします。

#(1)
これは演算ではなく優先順位1の式をまとめただけです。

#後置デクリメント式・後置インクリメント式・前置デクリメント式・前置インクリメント式
前置と後置で優先順位に差があります。
`++Aaa.ToString()`という式は「前置インクリメントのオペランドが代入不能なのでアウト」です。
優先順位2の前置インクリメントより優先順位1のメンバアクセス式・関数呼び出し式が優先されます。

`Aaa++.ToString()`という式は許されます。後置インクリメントはメンバアクセスのオペランドになり得ます。

#前置マイナス式
前置マイナス式を含まない優先順位2以上がオペランドになります。

#前置プラス式
前置プラス式を含まない優先順位2以上がオペランドになります。

#(2)
これも演算ではなく優先順位2以上の式をまとめただけです。
優先順位2以上なので<1>を含む定義となっています。

#乗除算式・加減算式
前回解説した二項演算式です。
前回一般化した通り、左オペランドは自分と同等以上の式、右オペランドは自分を超える優先度の式となります。
もしシフト演算や論理和などを表に組み込みたい場合は加減算と代入文の間に挿入する事になります。

#代入文
二項演算で最も優先順位の低いものがこの代入文です。
式ではなく文なのでどの式のオペランドにもなれません。
代入文自体は代入文のオペランドにはなれませんので`Aaa=Bbb=1+4`のような書き方はできません。

#優先順位1000より先とは？
変数宣言文・if文・switch文・try文 などといった「文」が該当します。

例えば`var Aaa=1+2`といった変数宣言文の場合、宣言文は代入文より低い優先順位が必要になります。
「優先順位が低い」という事を言い換えると「自分より優先順位が高い要素を部品として取り込める」です。
この例では変数宣言文の一部として代入文を取り込んでいますし、代入文の一部として加減算式を取り込んでいます。

文をゼロ個以上取り込む事で「関数宣言文」が定義可能になります。
関数宣言文も含めた文を取り込んで「クラス宣言文」を定義可能です。
クラス宣言文も含めた文を取り込んで「名前空間宣言文」を定義可能です。
名前空間宣言文も含めた文を取り込んで「●●言語のソースコード」を定義可能です。

「●●言語のソースコード」として定義したマッチャーに文字列を入力してマッチすればパースできた事になります。

#ラムダ式は表のどこに入るのか？
リテラル値式として処理する事になります。

#構文解析のついでに型検査もできるんじゃないの？
そんなふうに考えていた時期が俺にもありました。
結論から言うとできません。

確かに`133`はint型と確定できますし`133+986`もint型と確定できますが、識別子の型は確定できません。
識別子の型を確定するのは構文解析の先の段階です。
`()=>{1+2}++`といったトンチンカンなソースコードでも構文解析の段階では一旦受け入れておいて、その先の段階でエラー扱いにする事になります。

#実装

```C#

//
// 優先度１
//

// 整数値
Matcher Number = '1'.To('9') + '0'.To('9')._0Max();
//アルファベット
Matcher Alphabet = ('A'.To('Z') | 'a'.To('z'));
// 識別子
Matcher Identifier = (Alphabet | '_') + (Alphabet | '0'.To('9') | '_')._0Max();

// 「リテラル値式」のマッチャーを作る。(但し中身は空っぽ)
RecursionMatcher LiteralExp = new RecursionMatcher();

// 「括弧式」のマッチャーを作る。(但し中身は空っぽ)
RecursionMatcher ParenExp = new RecursionMatcher();

// 「代入可能式」のマッチャーを作る。(但し中身は空っぽ)
RecursionMatcher AssignableExp = new RecursionMatcher();

// 「関数呼び出し式」のマッチャーを作る。(但し中身は空っぽ)
RecursionMatcher FunctionCallExp = new RecursionMatcher();

// 「メンバアクセス式」のマッチャーを作る。(但し中身は空っぽ)
RecursionMatcher MemberAccessExp = new RecursionMatcher();

// 「インデックスアクセス式」のマッチャーを作る。(但し中身は空っぽ)
RecursionMatcher IndexAccessExp = new RecursionMatcher();

// 「後置デクリメント」のマッチャーを作る。(但し中身は空っぽ)
Matcher PostDecrementExp = AssignableExp + "--";

// 「後置インクリメント」のマッチャーを作る。(但し中身は空っぽ)
Matcher PostIncrementExp = AssignableExp + "++";

// 優先順位１式
Matcher Priority1Exp = LiteralExp | Identifier | ParenExp | AssignableExp | 
    FunctionCallExp | IndexAccessExp | MemberAccessExp | PostDecrementExp | PostIncrementExp ;


//
// 優先度２
//

// 「前置デクリメント」のマッチャーを作る。(但し中身は空っぽ)
Matcher PreDecrementExp = "--" + AssignableExp;

// 「前置インクリメント」のマッチャーを作る。(但し中身は空っぽ)
Matcher PreIncrementExp = "++" + AssignableExp;

// 「前置マイナス」のマッチャーを作る。(但し中身は空っぽ)
RecursionMatcher PreMinusExp = new RecursionMatcher();

// 「前置プラス」のマッチャーを作る。(但し中身は空っぽ)
RecursionMatcher PrePlusExp = new RecursionMatcher();

// 優先順位２式
Matcher Priority2Exp = PreDecrementExp | PreIncrementExp | PreMinusExp | PrePlusExp ;

// 優先順位２以上式
Matcher PriorityAbove2Exp = Priority1Exp | Priority2Exp ;


//
// 優先度３
//

// 「乗除算式」のマッチャーを作る。(但し中身は空っぽ)
RecursionMatcher MulDivExp = new RecursionMatcher();

// 優先順位３式
Matcher Priority3Exp = MulDivExp ;

// 優先順位３以上式
Matcher PriorityAbove3Exp = PriorityAbove2Exp | Priority3Exp ;


//
// 優先度４
//

// 「加減算式」のマッチャーを作る。(但し中身は空っぽ)
RecursionMatcher AddSubExp = new RecursionMatcher();

// 優先順位４式
Matcher Priority4Exp = AddSubExp ;

// 優先順位４式
Matcher PriorityAbove4Exp = PriorityAbove3Exp | Priority4Exp ;

//
// (優先順位の低い演算子を増やしたい場合はここに挿入する。)
//

// 式の全て
Matcher Exp = PriorityAbove4Exp;

//
// 優先度９９９
//

// 代入演算文
Matcher AssignStatement = AssignableExp + '=' + Exp;


//
// 以下、中身が未設定なマッチャーの中身を設定
//

// 括弧式の中身
ParenExp.Inner = '(' + 
    (
    // 代入可能式を除く優先順位１式
    LiteralExp | Identifier | ParenExp | FunctionCallExp | 
    IndexAccessExp | MemberAccessExp | PostDecrementExp | PostIncrementExp |
    
    // 優先順位２以下の全ての式
    Priority2Exp | Priority3Exp | Priority4Exp
    )
     + ')';

// 代入可能式の中身
AssignableExp.Inner = Identifier | MemberAccessExp | IndexAccessExp | ( '(' + AssignableExp + ')' );

// 関数呼び出し式の中身
FunctionCallExp.Inner = (FunctionCallExp | IndexAccessExp | AssignableExp) + '(' + Exp._0Max(',') + ')';

// インデックスアクセス式の中身
IndexAccessExp.Inner = (FunctionCallExp | IndexAccessExp | AssignableExp) + '[' + Exp._1Max(',') + ']';

// メンバアクセス式の中身
MemberAccessExp.Inner = Priority1Exp + '.' + Identifier;

// 前置マイナス式の中身
PreMinusExp.Inner = '-' + (Priority1Exp | PreDecrementExp | PreIncrementExp | PrePlusExp);

// 前置プラス式の中身
PrePlusExp.Inner = '+' + (Priority1Exp | PreDecrementExp | PreIncrementExp | PreMinusExp);

// 乗除算式の中身
MulDivExp.Inner =  PriorityAbove3Exp + ('*'._() | '/') + PriorityAbove2Exp;

// 加減算式の中身
AddSubExp.Inner =  PriorityAbove4Exp + ('+'._() | '-') + PriorityAbove3Exp;
```

関数呼び出しやインデックスアクセスでデリミタとしてカンマを指定しています。
MatcherのTimes()や_0Max()や_1Max()がデリミタ指定に対応している仕様は引数リストの定義を簡潔に記述する為です。

Matcher と宣言するか RecursionMatcher と宣言するかの使い分けは、宣言した時点で初期化できるか否かです。
実は全ての宣言を RecursionMatcher でまとめて行い、後から中身をまとめて設定する事も可能です。

#次回の予定
LIMEの動作原理を解説する予定です。

#2019/03/03 追記
続きができました。
[パーサジェネレーターLIME入門その４(マッチング動作の原理)]
(https://qiita.com/ryu_shizumi/items/cbdbda211555e84dadd0)