言語を作ろうプロジェクト（2020年）

１３－０６．構文解析（Bisonファイルの記述）

CLangProject.y

　Flexの定義ファイルはCLangProject.lですが、Bisonの定義ファイルはCLangProject.yです。
　まず全体像を紹介します。

%{
#include "../CLangProject/proc.h"
#define YYDEBUG 1
extern int yylex(void);
extern char *yytext;
int yyerror(char const *str){
    extern int gLine;
    fprintf(stderr,"%s, line: %d, near %s\n",str, gLine, yytext);
    return 0;
}
%}
%code requires {
#include "../CLangProject/proc.h"
}
%union {
    clg::Expression* pExpression;
    clg::Statement* pStatement;
    clg::StatementList* pStatementList;
    clg::Declaration* pDeclaration;
    clg::DeclarationList* pDeclarationList;
    clg::ParameterList* pParameterList;
    clg::Root* pRoot;
}
%token IDENTIFIER INT_LITERAL DMP  INT_TYPE SEMICOLON 
%token LC RC LP RP
%type <pExpression> expression intliteral_expression identifier_expression postfix_expression
%type <pStatementList> statement_list
%type <pStatement>  dump_statement expression_statement compound_statement statement
%type <pDeclaration> declaration
%type <pDeclarationList> declaration_list
%type <pRoot> root
%type <pParameterList> parameter_list
%%
root
    : declaration_list
    {
        $$ = clg::StackMachine::get()->addRootDeclarationList($1);
    }
    ;
declaration_list
    : declaration
    {
        $$ = clg::StackMachine::get()->createDeclarationList($1);
    }
    | declaration_list declaration
    {
        $$ = clg::StackMachine::get()->createDeclarationList($1,$2);
    }
    ;
declaration
    : INT_TYPE identifier_expression LP parameter_list RP compound_statement
    {
        $$ = clg::StackMachine::get()->createIntFunctionDeclaration($2,$6);
    }
    ;
parameter_list
    : /*empty*/
    {
        $$ = clg::StackMachine::get()->createParameterList();
    }
    ;
statement_list
    : statement
    {
        $$ = clg::StackMachine::get()->createStatementList($1);
    }
    | statement_list statement
    {
        $$ = clg::StackMachine::get()->createStatementList($1,$2);
    }
    ;
statement
    : dump_statement
    | compound_statement
    | expression_statement
    ;
expression_statement
    : expression SEMICOLON
    {
        $$ = clg::StackMachine::get()->createExpressionStm($1);
    }
    ;
dump_statement
    :DMP expression SEMICOLON
    {
        $$ = clg::StackMachine::get()->createDumpStm($2);
    }
    ;
compound_statement
    : LC RC
    {
        $$ = clg::StackMachine::get()->createCompoundStatement();
    }
    | LC statement_list RC
    {
        $$ = clg::StackMachine::get()->createCompoundStatement($2);
    }
    ;
expression
    :intliteral_expression
    |identifier_expression
    |postfix_expression 
    ;
postfix_expression
    : identifier_expression LP  RP
    {
        $$ = clg::StackMachine::get()->createFunctionCallExp($1);
    }
    ;
identifier_expression
    : IDENTIFIER
    {
        $$ = clg::StackMachine::get()->createIdentifierExp(yytext);
    }
    ;
intliteral_expression
    : INT_LITERAL
    {
       $$ = clg::StackMachine::get()->createIntLiteralExp(yytext);
    }
    ;
%%

CLangProjectとのかかわり

　１３－０１．構造の修正で実装した内容は、四則演算を乗除算優先で実行できる簡易的なものでしたが、実際にプログラム言語を作成するには、順次処理のほかに分岐、ループ、関数呼び出しなどの機能が必要になります。
　それらを実装するには、単純にスクリプトを順次トレースして実行するのではなく、いったん、何らかの形でコード全体を保持しておき、文法に従って実行する、という手順を踏む必要があります。
　とくにC言語では、あらかじめいくつもの関数が定義され、実行はmain関数を探して、そこから実行という文法になります。
　コード全体を保持する方法として、いくつか手法がありますが、このドキュメントではスタックマシーンにするというのが最終目標です。スタックマシーンは、プログラムのソースコードを、バイナリコードに変換して保存します。ここでバイナリコードというのは、CPUを直接操作できる、いわゆるマシン語ではありません。擬似マシン語といわれる、マシン語を模した、単純なニーモニック言語です。その形にしておくのが一番なのですが、その一歩手前の手順として、せっかくVisualStudioを使っているのでC++のオブジェクトとして、保持しておき、実行はそのオブジェクトに任せる、という手法で実装したいと思います。
　こうすることで、細かなオブジェクトを作成することができ、オブジェクト指向で作成することができます。
　そしてある程度形になった段階で、スタックマシーンとして、再実装していきたいと思います。
　ということで、Bisonファイルでは、各文法ごとにCLangProjectに含まれるオブジェクトを作成するという処理を行います。
　ここでは、まずその構造を説明します。

StackMachineクラス

　CLangProjectプロジェクトにはstackMachine.h/cppファイルにStackMachineクラスが定義されています。名前こそスタックマシンですが、まだスタックマシンではありません。今のところCLangProject.yとのインターフェイスが実装されています。
　StackMachineクラスにはCreateなんとかというメンバ関数が多数存在します。それぞれ、CLangProject.yから呼び出されることを想定した関数群です。
　これらの関数では、オブジェクト化された式や文や文リストなどを構築します。関数も構築します。
　それらは、例えば整数リテラル式であればIntLiteralExpクラスのインスタンスを作成し、オブジェクトプールに保持する、という役割を担います。
　ですので、CLangProject.yは、解析した構文によって、式クラスや文クラスなどを構築するメンバ関数を呼び出します。
　そこまで説明したところで、CLangProject.yを詳しく見ていきましょう。
　まず

%{
#include "../CLangProject/proc.h"
#define YYDEBUG 1
extern int yylex(void);
extern char *yytext;
int yyerror(char const *str){
    extern int gLine;
    fprintf(stderr,"%s, line: %d, near %s\n",str, gLine, yytext);
    return 0;
}
%}

　の部分は、ほぼ定番の内容です。

#include "../CLangProject/proc.h"

　はCLangProjectプロジェクトのproc.hをインクルードしていて、これは

#pragma once

#undef INT8_MIN
#undef INT16_MIN
#undef INT32_MIN
#undef INT8_MAX
#undef INT16_MAX
#undef INT32_MAX
#undef UINT8_MAX
#undef UINT16_MAX
#undef UINT32_MAX

#include <cstdlib>
#include <cstring>
#include <iostream>
#include <fstream>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <memory>
using namespace std;

#include "common.h"
#include "value.h"
#include "expression.h"
#include "statement.h"
#include "declaration.h"
#include "stackMachine.h"

　といった内容になっています。すなわちCLangProjectプロジェクトに含まれる多くのヘッダファイルをインクルードしています。これにより、CLangProjectプロジェクトで宣言されるクラスや構造体にアクセスできます。
　続く

%code requires {
#include "../CLangProject/proc.h"
}

　でもどうようのインクルードをしています。Bisonの定義ではこのように2か所必要なようです。
　続く

%union {
    clg::Expression* pExpression;
    clg::Statement* pStatement;
    clg::StatementList* pStatementList;
    clg::Declaration* pDeclaration;
    clg::DeclarationList* pDeclarationList;
    clg::ParameterList* pParameterList;
    clg::Root* pRoot;
}

　はBisonの定義で使用する、型とその型の変数名について登録します。例えば

    clg::Expression* pExpression;

　というのはclg::Expression*型のpExpression変数、という意味です。これらの設定は、後ほど%typeの設定で重要になります。
　続く

%token IDENTIFIER INT_LITERAL DMP  INT_TYPE SEMICOLON 
%token LC RC LP RP
%type <pExpression> expression intliteral_expression identifier_expression postfix_expression
%type <pStatementList> statement_list
%type <pStatement>  dump_statement expression_statement compound_statement statement
%type <pDeclaration> declaration
%type <pDeclarationList> declaration_list
%type <pRoot> root
%type <pParameterList> parameter_list

　で%tokenおよび%typeの設定をします。
　%token構文は

%token IDENTIFIER INT_LITERAL DMP  INT_TYPE SEMICOLON 
%token LC RC LP RP

　のようにFlexと共有するトークンの名前を登録します。
　すなわち前項で述べたIDENTIFIERとかINT_LITERALとかです。Flexでも使用するトークンの名前をここで登録します。複数行にわたってもかまいません。
　%type構文は

%type <変数名> 使用する定義ブロック

　という使い方をします。例えば

%type <pExpression> expression intliteral_expression identifier_expression postfix_expression

　というのは

pExpression　は　expression intliteral_expression identifier_expression postfix_expression
で使用する変数名である、

　ということです。

BNF法による表記

　Bisonはバッカス・ナウア記法（英: Backus-Naur form）という方法を使って、演算の優先順位などを設定します。
　具体的には、以下の部分です。

%%
root
    : declaration_list
    {
        $$ = clg::StackMachine::get()->addRootDeclarationList($1);
    }
    ;
declaration_list
    : declaration
    {
        $$ = clg::StackMachine::get()->createDeclarationList($1);
    }
    | declaration_list declaration
    {
        $$ = clg::StackMachine::get()->createDeclarationList($1,$2);
    }
    ;
declaration
    : INT_TYPE identifier_expression LP parameter_list RP compound_statement
    {
        $$ = clg::StackMachine::get()->createIntFunctionDeclaration($2,$6);
    }
    ;
parameter_list
    : /*empty*/
    {
        $$ = clg::StackMachine::get()->createParameterList();
    }
    ;
statement_list
    : statement
    {
        $$ = clg::StackMachine::get()->createStatementList($1);
    }
    | statement_list statement
    {
        $$ = clg::StackMachine::get()->createStatementList($1,$2);
    }
    ;
statement
    : dump_statement
    | compound_statement
    | expression_statement
    ;
expression_statement
    : expression SEMICOLON
    {
        $$ = clg::StackMachine::get()->createExpressionStm($1);
    }
    ;
dump_statement
    :DMP expression SEMICOLON
    {
        $$ = clg::StackMachine::get()->createDumpStm($2);
    }
    ;
compound_statement
    : LC RC
    {
        $$ = clg::StackMachine::get()->createCompoundStatement();
    }
    | LC statement_list RC
    {
        $$ = clg::StackMachine::get()->createCompoundStatement($2);
    }
    ;
expression
    :intliteral_expression
    |identifier_expression
    |postfix_expression 
    ;
postfix_expression
    : identifier_expression LP  RP
    {
        $$ = clg::StackMachine::get()->createFunctionCallExp($1);
    }
    ;
identifier_expression
    : IDENTIFIER
    {
        $$ = clg::StackMachine::get()->createIdentifierExp(yytext);
    }
    ;
intliteral_expression
    : INT_LITERAL
    {
       $$ = clg::StackMachine::get()->createIntLiteralExp(yytext);
    }
    ;
%%

　Bisonは、下方ほど優先順位が高くなります。上記の記述では

intliteral_expression
    : INT_LITERAL
    {
       $$ = clg::StackMachine::get()->createIntLiteralExp(yytext);
    }
    ;

　が最上位です。

intliteral_expression
は INT_LITERAL　が1つだけあるトークンです。
clg::StackMachine::get()->createIntLiteralExp()関数に
yytext（トークンの文字列）を渡して実行しなさい。

　という意味になります。
　ではclg::StackMachine::get()->createIntLiteralExp()関数とは、どのような関数でしょうか？

    Expression* StackMachine::createIntLiteralExp(const char* ptr) {
        string str = clampToken(ptr);
        auto pObj = new IntLiteralExp(std::stoi(str));
        m_objPool.push_back(pObj);
        return pObj;
    }

　といった関数です。yytextはconst char* ptrで受けられます。ここではIntLiteralExpクラスを構築し、m_objPoolという領域に保存しておきます。
　そして、そのポインタを返します。IntLiteralExpクラスはExpressionクラスの派生クラスですので、Expression*型の戻り値として使用できるのです。
　Bison側に戻ります

intliteral_expression
    : INT_LITERAL
    {
       $$ = clg::StackMachine::get()->createIntLiteralExp(yytext);
    }
    ;

　では$$に戻り値を代入してます。この$$こそが

%type <pExpression> expression intliteral_expression identifier_expression postfix_expression

　で指定したpExpression変数なわけです。ここで赤くなっている部分のようにintliteral_expressionを指定しています。ですので、intliteral_expressionと、ここでの$$は等価であり、それはpExpression変数といいことになります。
　このように、clg::StackMachine::get()->createIntLiteralExp(yytext);の実行により、intliteral_expressionはpExpression変数になりました。
　そうすると

expression
    :intliteral_expression
    |identifier_expression
    |postfix_expression 
    ;

　のようにexpressionとまとめられるようになり、それは

dump_statement
    :DMP expression SEMICOLON
    {
        $$ = clg::StackMachine::get()->createDumpStm($2);
    }
    ;

　とdump_statementの定義に再利用できるようになります。
　ここで

        $$ = clg::StackMachine::get()->createDumpStm($2);

　の$2は2番目のトークンという意味で、

DMP  1番目
expression  2番目
SEMICOLON  3番目

　と数えますので、clg::StackMachine::get()->createDumpStm関数にはpExpression変数が渡されます。ですのでCLangProject側のcreateDumpStm関数は以下のような宣言になります。

   Statement* createDumpStm(Expression* exp);

　このような形でCLangProject.yでは、優先順位の高いブロックで取得した文字列を、優先順位の低いブロックで再利用しながら、CLangProject側の関数に渡すことで、オブジェクトとして構築していきます。

　さて、この項ではBisonファイルによるCLangProject側の関数呼び出しの構造を説明しました。
　必ずしもこの構造が、よいとも限りません。あくまでぼくの書き方がこの構造なので、例えばオブジェクト指向を使用しない設計方法もあると思います。
　このドキュメントを参考にしながら自分のC言語を考えてみるのもよいと思います。

１３．シンプルな実装をする

１３－０６．構文解析（Bisonファイルの記述）

CLangProject.y

CLangProjectとのかかわり

StackMachineクラス

BNF法による表記