Taste of Tech Topics

Acroquest Technology株式会社のエンジニアが書く技術ブログ

ChatGPT (Advanced Data Analysis)でBNF式からパーサーを生成する

こんにちは、最近ピアノを習い始めた安部です。

今回は、ChatGPTのAdvanced Data Analysis (旧Code Interpreter)にBNF式を与えてパーサーを作成してもらおうと思います。

BNF式のように機械的に解釈可能なものであれば、正確にコードを生成してくれるのではないでしょうか？

BNFでうまくいけば、その他の様々な形式のデータやフォーマットからパーサーを自動生成してくれることが期待できそうです。

1. BNFとは

　BNF（バッカス・ナウア記法）とは、プログラムの構文規則（文脈自由文法）を記述するための記法です。

　正確な定義よりも具体例を見た方が早く理解できると思うので、例を示します。

　『プログラム意味論』（横内寛文 著）の冒頭に登場する、非常に単純なプログラムを許容する言語の定義です。

<変数> ::= A | B | C | ... | Z
<定数> ::= 0 | 1 | 2 | ... | 9
<式> ::= <変数> | <定数> | <式> + <式> | <式> - <式>
<文> ::= <変数> := <式>
　　　 | if <式> = <式> then <文> else <文>
　　　 | for <式> do <文>
　　　 | noop
　　　 | <文>; <文>

眺めれば何となく分かると思いますが、このBNF式で定義される言語には以下のような特徴があります。

  • 変数として大文字アルファベット1文字のみを使える。
  • 定数は0～9の自然数のみ。
  • 演算は+と-だけ。
  • 代入 / 簡単な条件分岐 / ループ / 何もしない(noop) / 文の連続実行 ができる。

許容できるプログラムの例を示します(見やすいよう、適宜改行・インデンテーションをしています)。

X := 5;
Y := 2;

Z := 0;
for Y do Z := Z + X;

2. 簡単なプログラム言語のパーサーを生成してもらう

ではさっそく、ChatGPTのAdvanced Data Analysis (旧Code Interpreter)で上記のBNF式で定義される言語をパースするプログラムを、Pythonを使って書いてもらいましょう。

まずはシンプルにお願いしてみます。

最初の指示

特に凝った指示は出していませんが、字句解析器を実装してからパーサーを実装してくれるようです。

長いので、まずは字句解析器の実装部分をお見せします。

字句解析器を作成し、動作確認までしてくれた

簡単なテストまで実施してくれて、気が利いてますね！

続けて、抽象構文木(AST)を生成するパーサーの実装に入りました。

こちらも長いですが、ChatGPTからのレスポンスの続きをお見せします。 コード部分は長すぎるので、テキストで載せます。

続けて、パーサーを実装してくれる

class ParserError(Exception):
    pass

class ASTNode:
    pass

class Variable(ASTNode):
    def __init__(self, name: str):
        self.name = name

class Constant(ASTNode):
    def __init__(self, value: int):
        self.value = value

class BinaryOp(ASTNode):
    def __init__(self, left: ASTNode, op: str, right: ASTNode):
        self.left = left
        self.op = op
        self.right = right

class Assignment(ASTNode):
    def __init__(self, var: Variable, expr: ASTNode):
        self.var = var
        self.expr = expr

class IfStatement(ASTNode):
    def __init__(self, condition_left: ASTNode, condition_right: ASTNode, then_branch: ASTNode, else_branch: ASTNode):
        self.condition_left = condition_left
        self.condition_right = condition_right
        self.then_branch = then_branch
        self.else_branch = else_branch

class ForLoop(ASTNode):
    def __init__(self, count: ASTNode, body: ASTNode):
        self.count = count
        self.body = body

class NoOp(ASTNode):
    pass

class Sequence(ASTNode):
    def __init__(self, first: ASTNode, second: ASTNode):
        self.first = first
        self.second = second

class Parser:
    def __init__(self, tokens: List[Tuple[str, Union[str, int]]]):
        self.tokens = tokens
        self.pos = 0

    def consume(self, expected_type: str) -> Tuple[str, Union[str, int]]:
        if self.pos < len(self.tokens) and self.tokens[self.pos][0] == expected_type:
            token = self.tokens[self.pos]
            self.pos += 1
            return token
        else:
            raise ParserError(f"Expected token of type {expected_type}, but got {self.tokens[self.pos]}")

    def variable(self) -> Variable:
        _, name = self.consume(VAR)
        return Variable(name)

    def constant(self) -> Constant:
        _, value = self.consume(CONST)
        return Constant(value)

    def expression(self) -> ASTNode:
        left = self.term()

        # Check if there's a binary operator
        while self.pos < len(self.tokens) and self.tokens[self.pos][0] == OPERATOR:
            op = self.consume(OPERATOR)[1]
            right = self.term()
            left = BinaryOp(left, op, right)

        return left

    def term(self) -> ASTNode:
        # First try to parse a variable
        if self.pos < len(self.tokens) and self.tokens[self.pos][0] == VAR:
            return self.variable()

        # Then try to parse a constant
        elif self.pos < len(self.tokens) and self.tokens[self.pos][0] == CONST:
            return self.constant()

        else:
            raise ParserError(f"Unexpected token {self.tokens[self.pos]}")

    def statement(self) -> ASTNode:
        # Check for an assignment statement
        if self.pos < len(self.tokens) and self.tokens[self.pos][0] == VAR:
            var = self.variable()
            self.consume(ASSIGN)
            expr = self.expression()
            return Assignment(var, expr)

        # Check for an if statement
        elif self.pos < len(self.tokens) and self.tokens[self.pos][1] == "if":
            self.consume(KEYWORD)  # "if"
            condition_left = self.expression()
            self.consume(EQUAL)
            condition_right = self.expression()
            self.consume(KEYWORD)  # "then"
            then_branch = self.statement()
            self.consume(KEYWORD)  # "else"
            else_branch = self.statement()
            return IfStatement(condition_left, condition_right, then_branch, else_branch)

        # Check for a for loop
        elif self.pos < len(self.tokens) and self.tokens[self.pos][1] == "for":
            self.consume(KEYWORD)  # "for"
            count = self.expression()
            self.consume(KEYWORD)  # "do"
            body = self.statement()
            return ForLoop(count, body)

        # Check for a noop
        elif self.pos < len(self.tokens) and self.tokens[self.pos][1] == "noop":
            self.consume(KEYWORD)  # "noop"
            return NoOp()

        # Check for a sequence of statements
        elif self.pos < len(self.tokens) and self.tokens[self.pos][0] == SEMICOLON:
            self.consume(SEMICOLON)
            first = self.statement()
            second = self.statement()
            return Sequence(first, second)

        else:
            raise ParserError(f"Unexpected token {self.tokens[self.pos]}")

    def parse(self) -> ASTNode:
        ast = self.statement()
        if self.pos != len(self.tokens):
            raise ParserError("Extra tokens found after parsing")
        return ast

# Test the parser
parser = Parser(tokenize(test_input))
ast = parser.parse()
ast

こちらも自動でテストをしてくれましたが、失敗しました。

初回実装は失敗

すると、勝手にデバッグしてコードを修正してくれます。 修正過程のコードは省略してお見せします。

デバッグ・修正まで自動でやってくれる

この後もデバッグ・修正が続き、ついにパーサーが完成しました！

エラーが直り、パーサーが完成

さらに、お願いせずとも人間が読みやすいように抽象構文木を表示してくれます。

人間の読める形式でASTを表示してくれる

ここでは、テストとしてA : = 1+ B; if C = 2 then noop else B := 3の解析が行われています。

まだちょっと読みにくいので、もっと見やすくしてくれないかお願いしてみます。

ASTをツリー形式で表示するよう指示を出す

すると、多少見やすく修正してくれました。

ASTを少し見やすくしてくれた

ノードと線で表現された抽象構文木を画像で示してくれたら最高でしたが、さすがにそれは明示的に指示しないとダメでした。 （Advanced Data Analysisではgraphvizも使えるので、お願いしたらやってくれます。）

とはいえある程度見やすく表示してくれたので、今回はこれで良しとしておきましょう！

まとめ

何回かエラーが出ましたが、無事にパーサーができました。

長いやり取りがあったように見えたかもしれませんが、実はこちらが指示を出したのは2回だけです。 テスト/デバッグ/修正をChatGPTが勝手にやってくれるので、大変便利ですね。

自前のパーサーを作りたい場面はそう多くありませんが、自作プログラミング言語で遊びたい人には役に立つかもしれません！

Acroquest Technologyでは、キャリア採用を行っています。

  • ディープラーニング等を使った自然言語／画像／音声／動画解析の研究開発
  • Elasticsearch等を使ったデータ収集／分析／可視化
  • マイクロサービス、DevOps、最新のOSSを利用する開発プロジェクト
  • 書籍・雑誌等の執筆や、社内外での技術の発信・共有によるエンジニアとしての成長

　

少しでも上記に興味を持たれた方は、是非以下のページをご覧ください。

Kaggle Grandmasterと一緒に働きたエンジニアWanted！ - Acroquest Technology株式会社のデータサイエンティストの採用 - Wantedlywww.wantedly.com