🦞
Rust で仮想言語のインタプリタを作る (その２)

2024/12/15に公開
Rust
language
bnf
tech
 概要https://zenn.dev/kaito_73519/articles/3dce56712cc430
前回独自定義した BNF を下にインタプリタを作成した.

独自に作ったため今後機能を追加行こうとすると if 文や while 文の取扱いに困ったので,

既にある言語をもとに開発をすすめて Rust を使ってコードを書くことにできるだけ専念できるようする方針に変えた.
c 言語を元にして機能を削って実装を行った.

下のサイトを参考にしている.
https://gist.githubusercontent.com/arslancharyev31/c48d18d8f917ffe217a0e23eb3535957/raw/45c6f49d927adf288aa3ac9fb0b88d2d569ed691/C_v1.bnf
C言語自体はそこまで複雑ではないと思ったけどいざ実装しようとなると,

色々と知らない機能があることがわかったので本当に必要なものだけ抽出して実装している.

最終的には以下のような BNF にしている.
仮想言語のBNF// トークンの定義
{
    tokens=[
         space='regexp:\s+'
         identifier='regexp:[a-zA-Z_][a-zA-Z0-9_]*'

         integer_constant='regexp:\d+'
         floating_constant='regexp:[+_]?([0_9]*[.])?[0_9]+f'
    ]
}

translation_unit ::= {external_declaration}*

external_declaration ::= function_definition
                         | declaration ';'

// 関数周りの定義
function_definition ::= type_specifier identifier '(' parameter_list ')' compound_statement

type_specifier ::= void
                   | int
                   | float

// ブロック内の処理
compound_statement ::= '{' {block_item}* '}'
block_item ::= declaration ';'
              | statement
statement ::= expression_statement
              | compound_statement
              | selection_statement
              | iteration_statement
              | jump_statement

// 変数の初期化
expression_statement ::= {assignment_expression}? ';'
assignment_expression ::= identifier '=' logical_or_expression ';'

// if文
selection_statement ::= if '(' expression ')' statement
                        | if '(' expression ')' statement else statement
                        
// while文
iteration_statement ::= while '(' expression ')' compound_statement

                          
// 演算子周りの優先順位
// OR 演算子
logical_or_expression ::= logical_and_expression
                          | logical_or_expression '||' logical_and_expression
// AND 演算子
logical_and_expression ::= equality_expression
                           | logical_and_expression '&&' equality_expression
equality_expression ::= relational_expression
                        | equality_expression '==' relational_expression
                        | equality_expression '!=' relational_expression
relational_expression ::= additive_expression
                          | relational_expression '<' additive_expression
                          | relational_expression '>' additive_expression
                          | relational_expression '<=' additive_expression
                          | relational_expression '>=' additive_expression

additive_expression ::= multiplicative_expression
                        | additive_expression '+' multiplicative_expression
                        | additive_expression '-' multiplicative_expression

multiplicative_expression ::= unary_expression
                              | multiplicative_expression '*' unary_expression
                              | multiplicative_expression '/' unary_expression
                              | multiplicative_expression '%' unary_expression
                              
unary_expression ::= postfix_expression
                     | unary-operator postfix_expression
                     
unary_operator ::= '-'
                   | '!'
                     
postfix_expression ::= primary_expression                               // 単項演算子
                       | identifier                                     // 変数
                       | identifier '(' {logical_or_expression}* {',' logical_or_expression}* ')'    // 関数呼び出し

primary_expression ::= constant
                       | '(' logical_or_expression ')'

assignment_operator ::= '='

constant ::= integer_constant
             | floating_constant

// 宣言周りの定義
declaration ::=  type_specifier init_declarator
init_declarator ::= direct_declarator                      // 宣言だけ
                    | direct_declarator '=' logical_or_expression    // 初期化付きの宣言
direct_declarator ::= identifier                           // 変数宣言 
                      | identifier '(' {identifier}* ')'   // 関数宣言 : 呼び出し時に使用する
          
parameter_list ::= parameter_declaration                        // 1つのパラメータ
                   | parameter_list ',' parameter_declaration   // 複数のパラメータ

parameter_declaration ::= type_specifier direct_declarator
                          
jump_statement ::= continue ';'
                   | break ';'
                   | return {logical_or_expression}? ';'
実装を進めていると結構間違いに気づくので, 矛盾はどこかにあるかも.

実装したソースコードは以下のもので現状, 四則演算と関数を実装している.
https://github.com/nagato0614/NagatoInterpreter

 仮想言語の BNFBNFの説明をまとめておく.

 translation_unitまずソースコードは, 関数または変数の定義として取り扱う.

ここでプロトタイプ宣言はないものとしている.
translation_unit ::= {external_declaration}*

external_declaration ::= function_definition // 関数定義
                         | declaration ';'   // 変数宣言 (グローバル変数)

 declaration変数宣言時の処理, 変数は型と識別子をベースに初期化値も設定できる.

logical_or_expression については後述するが, 四則演算や関数の呼び出しを行える.

ただ, c言語ではグローバル変数実行時に関数呼び出しはできないが, この仕様だとできてしまうので処理の中で解析やインタプリタ実行時に何かしらのエラーとする必要がある.
declaration ::=  type_specifier init_declarator
init_declarator ::= direct_declarator                      // 宣言だけ
                    | direct_declarator '=' logical_or_expression    // 初期化付きの宣言
direct_declarator ::= identifier                           // 変数宣言 
                      | identifier '(' {identifier}* ')'   // 関数宣言 : 呼び出し時に使用する

 logical_or_expressionlogical_or_expression は演算関係のおもとになる部分で優先度の高い演算子から処理する構造になっている.
// OR 演算子
logical_or_expression ::= logical_and_expression
                          | logical_or_expression '||' logical_and_expression
// AND 演算子
logical_and_expression ::= equality_expression
                           | logical_and_expression '&&' equality_expression
equality_expression ::= relational_expression
                        | equality_expression '==' relational_expression
                        | equality_expression '!=' relational_expression
relational_expression ::= additive_expression
                          | relational_expression '<' additive_expression
                          | relational_expression '>' additive_expression
                          | relational_expression '<=' additive_expression
                          | relational_expression '>=' additive_expression

additive_expression ::= multiplicative_expression
                        | additive_expression '+' multiplicative_expression
                        | additive_expression '-' multiplicative_expression

multiplicative_expression ::= unary_expression
                              | multiplicative_expression '*' unary_expression
                              | multiplicative_expression '/' unary_expression
                              | multiplicative_expression '%' unary_expression
                              
unary_expression ::= postfix_expression
                     | unary-operator postfix_expression
                     
unary_operator ::= '-'
                   | '!'
                     
postfix_expression ::= primary_expression                               // 単項演算子
                       | identifier                                     // 変数
                       | identifier '(' {logical_or_expression}* {',' logical_or_expression}* ')'    // 関数呼び出し

primary_expression ::= constant
                       | '(' logical_or_expression ')'

assignment_operator ::= '='

constant ::= integer_constant
             | floating_constant

 function_definition関数定義は, 戻り値の型, 識別子, 引数リストと compound_statement で構成される.

型は void, int, float の3つのみ.
compound_statement は {} で囲まれた式を処理して if, while 実行時に使用されるが,

今の実装では関数に紐づいて実行される物となっているので compound_statement 単体として動作するようにしてあげる必要がある.
statement の中で実装されているのは expression_statement, jump_statementで

jump_statementは return だけ対応している.
// 関数周りの定義
function_definition ::= type_specifier identifier '(' parameter_list ')' compound_statement

type_specifier ::= void
                   | int
                   | float

// ブロック内の処理
compound_statement ::= '{' {block_item}* '}'
block_item ::= declaration ';'
              | statement
statement ::= expression_statement
              | compound_statement
              | selection_statement
              | iteration_statement
              | jump_statement

jump_statement ::= continue ';'
                   | break ';'
                   | return {logical_or_expression}? ';'    
// 変数の初期化
expression_statement ::= {assignment_expression}? ';'
assignment_expression ::= identifier '=' logical_or_expression ';'

 最後にC言語すごいなというなという感想しか出てこない.

最初はC言語ならすぐ実装できそうだと思っていたけど, インタプリタとしてポインタの取り扱いをどうするのかという部分が今後問題になってきそう.

if, while の実装はまだまだ時間がかかりそうだけど,これがないとプログラミング言語として成り立たないのでそこまでは進めたいと思っている.
概要

仮想言語の BNF

translation_unit

declaration

logical_or_expression

function_definition

最後に

Discussion
