Month: January 2024

print文専用の構文解析ではなく、汎用的な関数呼び出しの構文解析にする
関数呼び出しのfunccallを作り、どれにも該当しない場合、そのままの値を返す

### parser.js

module.exports = parser;
var {expect, accept, show, error} = require("./utils.js");

var tokens;

function parser(t){
    tokens = t;
    var ast = semi();
    if(tokens.length>0){
        show("ast=", ast);
        show("処理後tokens =", tokens);
        error("tokensが余っています。");
    }
    return ast;
}

function value(){
    if(tokens.length == 0) return;
    return tokens.shift();
}

function funccall(){
    var left = value();

    var op;
    while(op = accept(tokens, "(")){
        var right = semi();
        op += expect(tokens, ")");

        left = {left, op, right};
    }
    return left;
}

function semi(){
    var left = funccall();

    var op;
    while(op = accept(tokens, ";")){
        var right = funccall();
        left = {left, op, right};
    }
    return left;
}

関数valueで、tokens.shift();で値を取ってleftに入れて、()をop、中をrightにして、セミコロンがあった場合は全体をleft、opをセミコロン、セミコロン後をrightにしている。

これは、この言語が必ず　関数名、()、; の順番で書かれていることを前提に立っている。

言語設計者側に立つと、命名規則ってのはちゃんと意味があるんだなぁ
function valueのtokens.shiftのところで、case文で関数名による処理を分岐するのかな？

複数文はセミコロンで区切るとする。
### source.3

print("hello world1");
print("hello world2");
print("hello world3");

### lexer.js
正規表現にセミコロンを追加

module.exports = function(source){
    var tokens = source.split(/(".*"|print|;)|\n/);

    tokens = tokens.filter(a=>a);

    return tokens;
}

### parser.js

module.exports = parser;
var {expect, accept, show, error} = require("./utils.js");

var tokens;

function parser(t){
    tokens = t;
    return semi();
}

function semi(){
    var left = callprint();

    var op;
    while(op = accept(tokens, ";")){
        var right = callprint();
        left = {left, op, right};
    }
    return left;
}

function callprint(){
    if(tokens.length==0) return;

    var left = expect(tokens, "print");

    var op = expect(tokens, "(");

    var msg = tokens.shift();
    num = calc(msg.length);

    var right = msg.substr(1, num);

    op += expect(tokens,")");

    return {left, op, right};
}

function calc(len) {
    var total = len - 2;
    return Number.isInteger(total) > 0 ? total : 0;
}

上記を実行すると、leftが入れ子になる
[[print, (), hell1] [;] [print, (), hell1]] [;] [print, (), hell1]

### run.js

const { error } = require("./utils");

module.exports = run;

function run(a){
    if(!a) return;
    if(!a.op){
        if(a[0] == '"') return a.substr(1, a.length-2);
        return a;
    } else if (a.op==";"){
        run(a.left);
        run(a.right);
    } else if(a.op == "()") {
        var func = run(a.left);
        if(func == "print"){
            var msg = run(a.right)
            console.log(msg);
        } else {
            error("未実装の関数呼び出し func=", func);
        } 
    } else {
        error("未実装の演算子 op=", a.op)
    }
} 

run(a.left); run(a.right); と左から実行することで、上から入れ子になっている式を上から順番に実行する。

$ node interpretor.js
token =[
‘print’, ‘(‘,
‘”hello world1″‘, ‘)’,
‘;’, ‘print’,
‘(‘, ‘”hello world2″‘,
‘)’, ‘;’,
‘print’, ‘(‘,
‘”hello world3″‘, ‘)’,
‘;’
]
ast={
left: {
left: {
left: { left: ‘print’, op: ‘()’, right: ‘hello world1’ },
op: ‘;’,
right: { left: ‘print’, op: ‘()’, right: ‘hello world2’ }
},
op: ‘;’,
right: { left: ‘print’, op: ‘()’, right: ‘hello world3’ }
},
op: ‘;’,
right: undefined
}
hello world1
hello world2
hello world3

parserでセミコロンが来たら、セミコロンをopにしてleftとrightに入れるというのは面白い
C, C++はセミコロンがあるが、pythonは文末にセミコロンがないけどどうやってるんだろうか？

構文解析の結果として抽象木構文(AST)で出力する

### 抽象木構文(AST)とは
木構造はオブジェクトで表す

{
	left: "print",
	op: "()",
	right: "hello world"
}

以下のように表す

var left = "print";
var op = "()";
var right = "hello world";

var obj1 = {left:left, op:op, right:right};

var obj2 = {left, op, right};

run.jsを追加する
$ tree
.
├── interpretor.js
├── lexer.js
├── main.js
├── parser.js
├── run.js
├── source.3
└── utils.js

### interpretor.js

var {read, show} = require("./utils.js");
var lexer = require("./lexer.js");
var parser = require("./parser.js");
var run = require("./run.js");

var source = read("source.3");

var tokens = lexer(source);

var token = lexer(source);
show("token =", tokens);

var ast = parser(tokens);
show("ast=", ast);

run(ast);

### parser.js

module.exports = parser;
var {expect, accept, show, error} = require("./utils.js");

var tokens;

function parser(t){
    tokens = t;
    return callprint();
}

function callprint(){
    if(tokens.length==0) return;

    var left = expect(tokens, "print");

    var op = expect(tokens, "(");

    var msg = tokens.shift();
    num = calc(msg.length);

    var right = msg.substr(1, num);

    op += expect(tokens,")");

    return {left, op, right};
}

function calc(len) {
    var total = len - 2;
    return Number.isInteger(total) > 0 ? total : 0;
}

### run.js

const { error } = require("./utils");

module.exports = run;

function run(a){
    if(!a) return;
    if(!a.op){
        if(a[0] == '"') return a.substr(1, a.length-2);
        return a;
    } else if(a.op == "()") {
        var func = run(a.left);
        if(func == "print"){
            var msg = run(a.right)
            console.log(msg);
        } else {
            error("未実装の関数呼び出し func=", func);
        } 
    } else {
        error("未実装の演算子 op=", a.op)
    }
} 

$ node interpretor.js
token =[ ‘print’, ‘(‘, ‘”hello world”‘, ‘)’ ]
ast={ left: ‘print’, op: ‘()’, right: ‘hello world’ }
hello world

最初にopを見て、それからprintかどうかを判定している。
astでは、ソースコードをleft, right, opに分けている。

hello worldを出力する言語を開発する。
言語仕様としては文字列とprint関数だ。
source.3というファイルを作成する。

print("hello world")

### インタプリタのファイル構成
– interpretor.js
– lexer.js
– parser.js
– utils.js

### interpretor.js

var {read, show} = require("./utils.js");
var lexer = require("./lexer.js");
var parser = require("./parser.js");

var source = read("source.3");

var tokens = lexer(source);

var token = lexer(source);
show("token =", tokens);

parser(tokens);

### lexer.js
split(/(“.*”|print)|\n/)で、文字列、print、改行で分割
filter(a=>a);で不要な物を捨てる

module.exports = function(source){
    var tokens = source.split(/(".*"|print)|\n/);

    tokens = tokens.filter(a=>a);

    return tokens;
}

### parser.js
callprintでは文法規則に沿って関数名(文字列)の順番通りになっているかを確認し、問題なければその場で文字列の部分を表示(実行)
substr(開始位置、文字数)なので、msg.substr(1, msg.legnth-2);として文字列を切り出す

module.exports = parser;
var {expect, accept, show, error} = require("./utils.js");

var tokens;

function parser(t){
    tokens = t;
    return callprint();
}

function callprint(){
    if(tokens.length==0) return;

    expect(tokens, "print");

    expect(tokens, "(");

    var msg = tokens.shift();
    num = calc(msg.length);

    var msg2 = msg.substr(1, num);

    
    console.log(msg2);

    expect(tokens,")");
}

function calc(len) {
    var total = len - 2;
    return Number.isInteger(total) > 0 ? total : 0;
}

### utils.js
shift()は配列の最初の要素を取り除く

module.exports = {read, show, error, accept, expect}

function read(filename) {
    return require('fs').readFileSync(filename,"utf-8");
}

function show(msg, obj){
    obj = require('util').inspect(obj, {
        showHidden: false, depth: null, maxArrayLength: null, colors: true
    });
    console.log(msg + obj);
}

function error(...msgs){
    console.log(msgs.join(""));
    process.exit();
}

function accept(tokens, ...cs){
    if(tokens.length==0) return;

    if(cs.includes(tokens[0])) return tokens.shift();
    return;
}

function expect(tokens, ...cs){
    var t = accept(tokens, ...cs);

    if(t) return t;

    error("tokens[0]=",tokens[0],"が",cs,"に含まれていたため終了");
}

lexer.jsはsplit以外は殆ど何もしていないのね。parseの方で、msgの切り抜きをやっている。

1. どんなプログラミング言語を作りたいか　が大事
2. 小さいプログラミング言語を作り育てていく
3. 開発OSはUbuntuを使用する
4. 開発のためのプログラミング言語はC, js, javaを使う
※コンパイラを作る場合は、アセンブラ言語を用いる必要があり、アセンブラ言語の知識が必要

どんな言語を作りたいかが骨格だが、他の言語の特徴を知っておくことが必要だろう
Python, C, C++, Java, C# などは昔から人気だ。
近年ではTypeScript, Go, Rustなども支持を集めている。

すぐに思いつくだけでもこれだけある
– インタプリタかコンパイル型か
– オブジェクト型かどうか
– 型指定があるかどうか

ブロックチェーン用のプログラミング言語の場合、
– 誰向けの言語か
– Dappsとしての機能を備えるか
– チューリング完全か

また、Solidityなど、他のブロックチェーンが採用している言語は最低限調べる必要がある
インタプリタ型かコンパイル型かについては、両方の開発方法を知っておく必要がある

奥を知ろうと思うと結構時間がかかりそうだ

プログラミング言語を作るには、ルールに合致した機械的な文字列だけを扱う割り切ったプログラムを作ること
インタプリタとコンパイラの共通処理として、字句解析と構文解析がある
※インタプリタは1行ずつ変換すると同時に、その都度命令を処理実行する
※コンパイラは全ての命令をまとめて一括で変換して、一気に処理実行する

### 字句解析(lexical analysis)とは
単語を意味のあるトークンに区切る

num=13-5*2;
print(num);

こちらをtoken配列に入れる文字列処理する

tokens = [
	"num", "=", "13", "-", "5", "*", "2", ";",
	"print", "(", "num", "num", ";"
];

文字列を分割するsplit機能や正規表現は最近の言語では備わっている
C言語の場合は、一文字ずつアルファベットか数字か記号かをチェックしていく
字句解析は、簡単な文字列分割機能だけで十分

### 構文解析(parsing)
処理を途中で止める手段が必要だが、例えば引き算を解析する関数を呼ぶ
tree構造のデータにすると分かりやすくなる。抽象構文木(AST: abstract syntax tree)
tree構造にすると、leftとrightに分けて、=, *, -, () などはopと呼ぶのが面白い。bitcoinのOPやハッシュ値のparseとプログラミング言語のparsingにかなり共通点があることがわかる。

{
	left: {
		left: 'num',
		op: '=',
		right: {
			left: '13',
			op:'-',
			right: {
				left: '5',
				op: '*',
				right: '2' 
			}
		}
	},
	op: ';'
	right: {
		left: 'print',
		op: '()',
		right: 'num'
	}
}

parsingとは、token配列をASTに変換する

### インタプリタ
字句解析、構文解析の後、ASTをそのまま実行する

### コンパイラ
字句解析、構文解析の後、ASTを元に、アセンブラを出力する
アセンブラのテキストファイルはasコマンドでバイナリに変換する
その後、リンカと呼ばれるldコマンドで、複数のオブジェクトファイルを連結して1つの実行ファイルにする
実行ファイルを実行すると、execシステムコールが呼ばれ、OSはバイナリ中で指定されたローダーと呼ばれる外部プログラムを起動する。
ローダーは実行ファイルや動的ライブラリなどをメモリ上に配置して、指定されたエントリポイントからCPUに制御を渡す