![10 式の解析(前置演算子、中置演算子) [オリジナル言語インタプリタを作る]](https://webbibouroku.com/wp-content/uploads/eye_gorilla.png)
前置演算子
ここでは前置演算子がくっついた式の解析を実装します。難しいことはありません。識別子も数値リテラルも、前置演算子の解析関数として関連付けて処理しました。それと同様の手順で進めます。
実装する前置演算子は、否定 ! と マイナス - です。それぞれ以下のような式を解析します。
-5;
!foo;
1 + -2;
中置演算子の直後に前置演算子が来るパターンも有効です。
次のような構造をしています。
<prefix operator><expression>;
前置演算子の後ろにはあらゆる式が友好です。
AST の定義
では前置演算子を用いた式のASTを定義します。
Ast/Expressions/PrefixExpression
using Gorilla.Lexing;
namespace Gorilla.Ast.Expressions
{
public class PrefixExpression : IExpression
{
public Token Token { get; set; }
public string Operator { get; set; }
public IExpression Right { get; set; }
public string ToCode() => $"({this.Operator}{this.Right.ToCode()})";
public string TokenLiteral() => this.Token.Literal;
}
}
前置演算子のトークンとその文字列、つまり “-” か “!” を持ちます。それから右に来る式をプロパティで保持します。
式なので IExpression を実装します。
ToCode() が返すコードは括弧でくるんでおきます。こうすることでオペランドがどの式にかかるものかを分かるようにしています -5; のASTは (-5); と等価です。
テストの実装
では解析結果が上記ASTを生成するようなテストを作成します。
[TestMethod]
public void TestPrefixExpressions1()
{
var tests = new[] {
("!5", "!", 5),
("-15", "-", 15),
};
foreach (var (input, op, value) in tests)
{
var lexer = new Lexer(input);
var parser = new Parser(lexer);
var root = parser.ParseProgram();
this._CheckParserErrors(parser);
Assert.AreEqual(
root.Statements.Count, 1,
"Root.Statementsの数が間違っています。"
);
var statement = root.Statements[0] as ExpressionStatement;
if (statement == null)
{
Assert.Fail("statement が ExpressionStatement ではありません。");
}
var expression = statement.Expression as PrefixExpression;
if (expression == null)
{
Assert.Fail("expression が PrefixExpression ではありません。");
}
if (expression.Operator != op)
{
Assert.Fail($"Operator が {expression.Operator} ではありません。({op})");
}
this._TestIntegerLiteral(expression.Right, value);
}
}
public void _TestIntegerLiteral(IExpression expression, int value)
{
var integerLiteral = expression as IntegerLiteral;
if (integerLiteral == null)
{
Assert.Fail("Expression が IntegerLiteral ではありません。");
}
if (integerLiteral.Value != value)
{
Assert.Fail($"integerLiteral.Value が {value} ではありません。");
}
if (integerLiteral.TokenLiteral() != $"{value}")
{
Assert.Fail($"ident.TokenLiteral が {value} ではありません。");
}
}
}
2つの前置演算子についてテストを行います。
式の部分については、整数リテラルなので前回作成したテストの一部をヘルパ関数に切り出してコードの見通しをよくしています。
テストを実行すると当然失敗します。
テスト名: TestPrefixExpressions1
テストの完全名: UnitTestProject.ParserTest.TestPrefixExpressions1
テスト ソース: E:\work\cs\Gorilla\UnitTestProject\ParserTest.cs : 行 175
テスト成果: 失敗
テスト継続時間: 0:00:00.0427569
結果 のスタック トレース: at UnitTestProject.ParserTest.TestPrefixExpressions1() in E:\work\cs\Gorilla\UnitTestProject\ParserTest.cs:line 189
結果 のメッセージ: Assert.AreEqual failed. Expected:<2>. Actual:<1>. Root.Statementsの数が間違っています。
前置のトークン種類に関連する解析関数がまだ定義されていないので ParseExpression() が Null を返すためです。
public IExpression ParseExpression(Precedence precedence)
{
this.PrefixParseFns.TryGetValue(this.CurrentToken.Type, out var prefix);
if (prefix == null) return null;
var leftExpression = prefix();
return leftExpression;
}
上記の prefix が Null になってしまいます。この時単純に Null を返すだけでなく、エラーメッセージを追加しましょう。
public IExpression ParseExpression(Precedence precedence)
{
this.PrefixParseFns.TryGetValue(this.CurrentToken.Type, out var prefix);
if (prefix == null)
{
this.AddPrefixParseFnError(this.CurrentToken.Type);
return null;
}
var leftExpression = prefix();
return leftExpression;
}
// ..
private void AddPrefixParseFnError(TokenType tokenType)
{
var message = $"{tokenType.ToString()} に関連付けられた Prefix Parse Function が存在しません。";
this.Errors.Add(message);
}
これでエラーの内容も出力されるようになりました。
テスト名: TestPrefixExpressions1
テストの完全名: UnitTestProject.ParserTest.TestPrefixExpressions1
テスト ソース: E:\work\cs\Gorilla\UnitTestProject\ParserTest.cs : 行 175
テスト成果: 失敗
テスト継続時間: 0:00:00.046412
結果 のスタック トレース:
at UnitTestProject.ParserTest._CheckParserErrors(Parser parser) in E:\work\cs\Gorilla\UnitTestProject\ParserTest.cs:line 99
at UnitTestProject.ParserTest.TestPrefixExpressions1() in E:\work\cs\Gorilla\UnitTestProject\ParserTest.cs:line 187
結果 のメッセージ: Assert.Fail failed.
BANG に関連付けられた Prefix Parse Function が存在しません。
BANG に関連付けられた解析関数がないと怒られたので、これを定義すればよいことがわかります。
ParsePrefixExpression()
前置演算子のついた式の解析関数 ParsePrefixExpression() を実装します。
上のテストで出力されたエラー内容の通り、BANG, MINUS に関連付ける処理 ParsePrefixExpression() を定義します。これを関連付ければテストが通るようになります。
Parsing/Parser.cs
public class Parser
{
// ..
private void RegisterPrefixParseFns()
{
this.PrefixParseFns = new Dictionary<TokenType, PrefixParseFn>();
this.PrefixParseFns.Add(TokenType.IDENT, this.ParseIdentifier);
this.PrefixParseFns.Add(TokenType.INT, this.ParseIntegerLiteral);
this.PrefixParseFns.Add(TokenType.BANG, this.ParsePrefixExpression);
this.PrefixParseFns.Add(TokenType.MINUS, this.ParsePrefixExpression);
}
// ..
public IExpression ParsePrefixExpression()
{
var expression = new PrefixExpression()
{
Token = this.CurrentToken,
Operator = this.CurrentToken.Literal
};
this.ReadToken();
expression.Right = this.ParseExpression(Precedence.PREFIX);
return expression;
}
}
今まで通り、前置演算子の種類に関連付けて、ParsePrefixExpression() を呼び出せるようにしています。
まずは現在のトークンが前置演算子になっているのでこれを演算子トークンとして PrefixExpression を生成します。その後演算子のトークンを読み進めて次のトークンに進みます。
上で確認した通り、前置演算子の後ろには式(expression)が来るので、式の解析関数を呼び出せば右に来る式のASTノードが得られます。つまりこのテストの内容だと整数リテラルのトークンがあるので、IntegerLiteral を見つけてくれることでしょう。
解析関数を呼ぶときに、優先度を前置演算子の順位 Precedence.PREFIX を指定しておきましょう。優先度についてはここまでの実装だとまだ意味を持ちません。ParseExpression() で特に使用していません。ただ、この後に実装を行う中置演算子の対応で必要になります。
これらを組み合わせると前置演算子のついた式の解析が完了しす。
テストが通れば前置演算子の解析は完了です。
中置演算子
続けて中置演算子の解析に移ります。これが終われば式の解析もひと段落となります。
中置演算子は全部で8つあります。
1 + 1;
1 - 1;
1 * 1;
1 / 1;
1 > 1;
1 < 1;
1 == 1;
1 != 1;
中置演算子の左右両辺にはすべての式が使えます。構造を示すと以下のようになります。
<expression> <infix operator> <expression>;
AST ノードの定義
Ast/Expressions/InfixExpression
using Gorilla.Lexing;
using System.Text;
namespace Gorilla.Ast.Expressions
{
public class InfixExpression : IExpression
{
public Token Token { get; set; }
public IExpression Left { get; set; }
public string Operator { get; set; }
public IExpression Right { get; set; }
public string ToCode()
{
var builder = new StringBuilder();
builder.Append("(");
builder.Append(this.Left.ToCode());
builder.Append(" ");
builder.Append(this.Operator);
builder.Append(" ");
builder.Append(this.Right.ToCode());
builder.Append(")");
return builder.ToString();
}
public string TokenLiteral() => this.Token.Literal;
}
}
前置演算子との違いは左辺の式が追加されているくらいです。ToCode() は “(左辺 演算子 右辺)” となるように再帰的に呼び出しを行っています。
括弧を付けることでコードに変換した際に演算子の優先度が反映された形で出力されるようになります。例えば 1+2-3 は ((1+2)-3) といった具合です。
テストの作成
ではテストを作成します。
[TestMethod]
public void TestInfixExpressions1()
{
var tests = new[] {
("1 + 1;", 1, "+", 1),
("1 - 1;", 1, "-", 1),
("1 * 1;", 1, "*", 1),
("1 / 1;", 1, "/", 1),
("1 < 1;", 1, "<", 1),
("1 > 1;", 1, ">", 1),
("1 == 1;", 1, "==", 1),
("1 != 1;", 1, "!=", 1),
};
foreach (var (input, leftValue, op, RightValue) in tests)
{
var lexer = new Lexer(input);
var parser = new Parser(lexer);
var root = parser.ParseProgram();
this._CheckParserErrors(parser);
Assert.AreEqual(
root.Statements.Count, 1,
"Root.Statementsの数が間違っています。"
);
var statement = root.Statements[0] as ExpressionStatement;
if (statement == null)
{
Assert.Fail("statement が ExpressionStatement ではありません。");
}
var expression = statement.Expression as InfixExpression;
if (expression == null)
{
Assert.Fail("expression が InfixExpression ではありません。");
}
this._TestIntegerLiteral(expression.Left, leftValue);
if (expression.Operator != op)
{
Assert.Fail($"Operator が {expression.Operator} ではありません。({op})");
}
this._TestIntegerLiteral(expression.Right, RightValue);
}
}
これも前置演算子のときのテストと違いはあまりありません。左辺と右辺それぞれで式の解析結果のテストが追加されているくらいです。
テスト名: TestInfixExpressions1
テストの完全名: UnitTestProject.ParserTest.TestInfixExpressions1
テスト ソース: E:\work\cs\Gorilla\UnitTestProject\ParserTest.cs : 行 233
テスト成果: 失敗
テスト継続時間: 0:00:00.0476324
結果 のスタック トレース:
at UnitTestProject.ParserTest._CheckParserErrors(Parser parser) in E:\work\cs\Gorilla\UnitTestProject\ParserTest.cs:line 99
at UnitTestProject.ParserTest.TestInfixExpressions1() in E:\work\cs\Gorilla\UnitTestProject\ParserTest.cs:line 251
結果 のメッセージ: Assert.Fail failed.
PLUS に関連付けられた Prefix Parse Function が存在しません。
前置解析関数(Prefix Parse Function )が存在しないとテスト結果のエラーにあります。しかしここでは前置解析関数ではなく、関連付けられた中置解析関数を見つけて実行してもらう必要があります。
ここからが式の解析で最も重要な部分です。どうにかして演算子ごとの優先度を考慮しつつASTを組み立てていかなければなりません。
演算子の順位付け
まずは演算子のトークンに応じた順位付けが得られるように、辞書でトークンの種類と優先度を管理します。
Parsing/Parser.cs
public class Parser
{
// ..
public Dictionary<TokenType, Precedence> Precedences { get; set; } =
new Dictionary<TokenType, Precedence>()
{
{ TokenType.EQ, Precedence.EQUALS },
{ TokenType.NOT_EQ, Precedence.EQUALS },
{ TokenType.LT, Precedence.LESSGREATER },
{ TokenType.GT, Precedence.LESSGREATER },
{ TokenType.PLUS, Precedence.SUM },
{ TokenType.MINUS, Precedence.SUM },
{ TokenType.SLASH, Precedence.PRODUCT },
{ TokenType.ASTERISK, Precedence.PRODUCT },
};
public Precedence CurrentPrecedence
{
get
{
if (this.Precedences.TryGetValue(this.CurrentToken.Type, out var p))
{
return p;
}
return Precedence.LOWEST;
}
}
public Precedence NextPrecedence
{
get
{
if (this.Precedences.TryGetValue(this.NextToken.Type, out var p))
{
return p;
}
return Precedence.LOWEST;
}
}
// ..
}
これでトークンの種類の演算子に応じて優先度が比較できるようになりました。例えば加算(+)と乗算(*)では、優先度がそれぞれ 2, 3 なので乗算のほうが高い優先度を持つ、といった具合です。
現在のトークン種類の優先度、次のトークン種類の優先度を得られるようなプロパティをそれぞれ取得できるようにしておきます。
優先度が定義されていないトークンの場合は最も低い優先度 LOWEST とします。
中置解析関数の登録
トークンの種類に応じた解析関数を呼べるように関連付けておきます。8つの演算子のトークン種類に対して ParseInfixExpression() という名前の構文解析関数に紐づけます。
前置解析関数は PrefixParseFns で関連付けを管理していますが、中置解析関数は InfixParseFns で管理します。これをコンストラクタから呼ばれるヘルパ関数で初期化しておきます。
Parsing/Parser.cs
public class Parser
{
// ..
public Dictionary<TokenType, Precedence> Precedences { get; set; } =
new Dictionary<TokenType, Precedence>()
{
{ TokenType.EQ, Precedence.EQUALS },
{ TokenType.NOT_EQ, Precedence.EQUALS },
{ TokenType.LT, Precedence.LESSGREATER },
{ TokenType.GT, Precedence.LESSGREATER },
{ TokenType.PLUS, Precedence.SUM },
{ TokenType.MINUS, Precedence.SUM },
{ TokenType.SLASH, Precedence.PRODUCT },
{ TokenType.ASTERISK, Precedence.PRODUCT },
};
// ..
public Parser(Lexer lexer)
{
// ..
this.RegisterInfixParseFns();
}
private void RegisterInfixParseFns()
{
this.InfixParseFns = new Dictionary<TokenType, InfixParseFn>();
this.InfixParseFns.Add(TokenType.PLUS, this.ParseInfixExpression);
this.InfixParseFns.Add(TokenType.MINUS, this.ParseInfixExpression);
this.InfixParseFns.Add(TokenType.SLASH, this.ParseInfixExpression);
this.InfixParseFns.Add(TokenType.ASTERISK, this.ParseInfixExpression);
this.InfixParseFns.Add(TokenType.EQ, this.ParseInfixExpression);
this.InfixParseFns.Add(TokenType.NOT_EQ, this.ParseInfixExpression);
this.InfixParseFns.Add(TokenType.LT, this.ParseInfixExpression);
this.InfixParseFns.Add(TokenType.GT, this.ParseInfixExpression);
}
// ..
}
ParseInfixExpression()
では解析関数の実装です。
Parsing/Parser.cs
public class Parser
{
// ..
public IExpression ParseInfixExpression(IExpression left)
{
var expression = new InfixExpression()
{
Token = this.CurrentToken,
Operator = this.CurrentToken.Literal,
Left = left,
};
var precedence = this.CurrentPrecedence;
this.ReadToken();
expression.Right = this.ParseExpression(precedence);
return expression;
}
}
InfixExpression の左辺は引数で受け取ったものを使い、演算子トークンについては現在のトークンです。ここまではいいでしょう。
右辺の式については ParseExpression() を呼べば得られますが、その際に優先度を引数で指定しなければなりません。そのため、先ほど定義したプロパティで現在のトークンに対応する優先度を取得します。それをローカル変数で保持し、演算子トークンを読み飛ばし、続く式の解析関数を呼ぶときに優先度を引数で渡すようにします。
これで完成 .. というわけではありません。なぜか。まだこのメソッドを呼ぶ箇所がありません。これは、ParseExpression() の中でトークンの種類に応じて呼ばれるべきです。
Parsing/Parser.cs
public class Parser
{
// ..
public IExpression ParseExpression(Precedence precedence)
{
this.PrefixParseFns.TryGetValue(this.CurrentToken.Type, out var prefix);
if (prefix == null)
{
this.AddPrefixParseFnError(this.CurrentToken.Type);
return null;
}
var leftExpression = prefix();
while (this.NextToken.Type != TokenType.SEMICOLON
&& precedence < this.NextPrecedence)
{
this.InfixParseFns.TryGetValue(this.NextToken.Type, out var infix);
if (infix == null)
{
return leftExpression;
}
this.ReadToken();
leftExpression = infix(leftExpression);
}
return leftExpression;
}
}
ParseExpression() に while文を追加しています。
おめでとうございます。これで中置演算子の式も正しく構文解析ができるようになりました。テストを動かしてみましょう。テストが通ることが確認できます！！
いったいなぜこれで動くのでしょうか。
追加したwhile文では、優先度がより低い演算子に遭遇するまで(より優先度の高い演算子が続く限りは)右辺の式として解析を続けます。つまり、より高い演算子からなる式を1まとまりのブロックとして扱います。数式でいうと括弧でくるむということです。
詳しい仕組みについては次回に譲るとして、本当に様々な演算子の優先度に応じて解析できているのか確認するテストを作成して終わりにします。
式の解析テスト
[TestMethod]
public void TestOperatorPrecedenceParsing()
{
var tests = new[]
{
("a + b", "(a + b)"),
("!-a", "(!(-a))"),
("a + b - c", "((a + b) - c)"),
("a * b / c", "((a * b) / c)"),
("a + b * c", "(a + (b * c))"),
("a + b * c + d / e - f", "(((a + (b * c)) + (d / e)) - f)"),
("1 + 2; -3 * 4", "(1 + 2)\r\n((-3) * 4)"),
("5 > 4 == 3 < 4", "((5 > 4) == (3 < 4))"),
("3 + 4 * 5 == 3 * 1 + 4 * 5", "((3 + (4 * 5)) == ((3 * 1) + (4 * 5)))"),
};
foreach (var (input, code) in tests)
{
var lexer = new Lexer(input);
var parser = new Parser(lexer);
var root = parser.ParseProgram();
this._CheckParserErrors(parser);
var actual = root.ToCode();
Assert.AreEqual(code, actual);
}
}
正しく実装できていれば、ToCode() が演算子の優先度の高い式についてはより深く括弧でくるんで出力してくれます。
テストが通れば完了です。次の記事ではなぜこのようにうまく解析できるのか、詳しく見ていきます。
以上。
ここまでのソース
