Grammar【NandGame編】

2023年11月27日

構文ツリー化

トークン化の処理後、トークンを構文ツリー化します。

トークンとしては数値、括弧、演算子があります^[1]NandGameではTokenizeレベルで数値、2つの演算子「+」と「-」、普通の括弧「(」「)」だけを処理するルールを追加しました。。そして、特定のルールに従ってトークンが並んだものを式（Expression）とします。このルールこそがCPUが理解できる文法（Grammar）というわけです。

式の構造を解析した結果が構文ツリーであり、その解析処理のことを構文ツリー化と呼びます（呼ぶことにします）。

構文ツリー化によって、トークンが複雑につながったり入れ子上になったりした式を分解していくわけです。

NandGameではGrammer部で文法を定義する

NandGameにおいては中央のGrammar部で指定したルールに従って処理されます。

矢印の左右にテキストボックスがあります。左側にはプロダクション名、右側にプロダクション名またはトークン名を入力できます。

デフォルトでは、次の2つのルールが設定されています。

• Expression⇒Expression ＋ Number
• Expression⇒Number

NandGameではSyntax tree部で構文ツリー化の流れがわかる

デフォルトでSource codeには「2 + 2」が入力されています。

トークン化により、[Number][+][Number]に処理されます（ここまではTokenizeレベルの議論と同じ）。

Grammarのルールに従って、構文ツリー（Syntax tree）は次のようになります。

ルートが[Expression]で、最初3つのノード（[Expression],[+],[Number]）に枝分かれし、最初の[Expression]は[Number]というノードを子に持っています。

Grammarレベル

Grammarレベルは、次の式に対応するルールをGrammar部に設定することです。

• Expression + Expression
• Expression – Expression
• – Expression
• ( Expression )

Grammarレベルを解く

1：実験する

前提知識があれば正解のルールをすぐにわかるかもしれませんが、ここでは具体的なテストパターンを考えてみて処理の流れを見てみましょう。

Source codeに「3 – 2」を入力してみます。すると、"Parse error: Unexpected '-'"エラーが発生しました。

Tokens部では[Number][-][Number]となっており、トークン化には成功しています。

Syntax tree部に"Parse error: Unexpected '-'"というメッセージが表示されています。Grammar部で設定したルールから逸脱した式であり、構文ツリー化できなかったということです。

Grammar部にルール「Expression⇒Expression – Number」を追加します。

※「-」記号の前後に空白を入れるのを忘れないでください。

すると、Syntax tree部に構文ツリーが表示されました。Source code部に戻るとエラーが消えています。

2：残りのルールを追加する

ところで、本レベルで要求されている式の文法は次の通りです。1番目と2番目が解決しました。残りは3番目と4番目になります。

• Expression + Expression
• Expression – Expression
• – Expression
• ( Expression )

それでは3番目の式の文法を処理できるGrammarのルールを特定してみます。

試しにSource codeに「- 2」を入力します。Parse errorが出ます。

Grammar部に「Expression⇒- Number」を追加します。構文ツリーが表示され、Syntax errorも消えました。うまくいったようです。

続けて、4番目の式の文法を処理できるGrammarのルールを特定します。

試しにSource codeに「(1 + 2)」を入力します。Parse errorが出ます。

Grammar部に「Expression⇒( Expression )」を追加します。Syntax errorが消えました。構文ツリーは複雑ですが、問題なく分解できています。

3：微調整する

これですべてのルールを設定し終えたと判断して、[Check solution]ボタンを押してテストしてみます。しかしながら、「6 – (3 – 1)」のときにParse errorが発生してしまいます。

エラーを見ると「(」が分解できないといっています。このテストパターンだと後半に「(3 – 1)」があり、この括弧が解釈されないというわけです。

「(○○)」はExpressionであり、「6 – (3 – 1)」は「Number – Expression」という状況です。

ルール内に「Expression – Number」はありますが、「Number – Expression」はありません。

そこで、Grammar部に次の2つのルールを追加します。

• Expression⇒Number + Expression
• Expression⇒Number – Expression

Source codeにテストパターンの「6 – (3 – 1)」を入力してみます。構文ツリーが表示されており、いまくいっています。

4：テストする

[Check solution]ボタンを押してテストします。無事クリアできました。