marihachi marihachi

2020/01/12時点の内容です。
間違いや表現の訂正、内容の追加等ある場合はコメントからお願いします。

ASTメモ

全てのオブジェクトはidとtypeを持つ。
リテラルのオブジェクトはvalueを持つ。
関数コールのオブジェクト(ブロック)は配列argsとvalueを持ち、valueは常にnull(？)
ルート配列直下のオブジェクト(変数)は追加でnameを持つ。

リテラルタイプ

https://epsil.github.io/gll/ の一部の翻訳です。(Google翻訳)

Continuation-passing style

これまで、多くの文法をプログラムに直接翻訳できるという事実を利用してきました。このようなプログラムは、文字列照合のレベルまで関数を呼び出す関数を備えた、単純な階層構造になります。単一の結果を返すか、まったく結果を返さないかのいずれかです。

ただし、すべての文法がこれほど単純なわけではありません。再帰を導入すると、文法が明確に定義されている場合でも、文法が終了プログラムに変換される保証はありません。さらに、文法があいまいになる可能性があります。いくつかの一致する選択肢がある場合、文字列は複数の等しく有効な方法で解析できます。簡単にするために、altコンビネータは単一の結果（最初に一致した結果）のみを返しました。より完全な実装では、一連の結果が返されます。

これらの問題に対処するために、パーサーをより柔軟な方法で書き直して表現します。継続渡しスタイルです。パーサーに結果を呼び出し元に返す代わりに、パーサーは結果を継続に渡します。その後、継続は構文解析を続行します。すべてのパーサーには、結果を渡す継続についての追加の引数があります。継続自体は1つの引数の関数です。（Racketには実際にはネイティブの継続がありますが、実装をより移植性の高いものにするために、継続として関数を使用します。）

Terrario for AiScript

v1.1.1
for AiScript v0.12.x (>= v0.12.1)

original implementation:
https://github.com/marihachi/terrario

Basic APIs

str(value)

Generates a parser that consumes the specified string.

これは以下のページの一部を翻訳したものです。
https://eli.thegreenplace.net/2012/08/02/parsing-expressions-by-precedence-climbing

Precedence climbing - 何を実現しようと目指すか

precedence climbingを理解するために、式解析の他のアルゴリズムを熟知している必要はありません。
実は、この中で最もシンプルなのが「precedence climbing」だと考えています。
それを説明するために、まず、このアルゴリズムが何を目指しているのかを紹介したいと思います。
この後、どのようにこれを行うかを説明し、最後にPythonで完全に機能する実装を紹介します。

このアルゴリズムの基本的な目的は、式をネストされた部分式(nested sub-expressions)の束として扱い、

	/*
	* Generated by PEG.js 0.10.0.
	*
	* http://pegjs.org/
	*/

	"use strict";

	function peg$subclass(child, parent) {
	function ctor() { this.constructor = child; }

	/*
	* MIT License
	* (c) 2019 marihachi.
	*/

	interface Edge {
	src: number;
	dest: number;
	}

	interface INode {
	type: string;
	children?: INode[];
	[x: string]: any;
	}

	interface BooleanLiteral extends INode {
	type: 'bool';
	value: boolean;
	}

	const T_EOF = 'EOF'; // end of input
	const T_NUM = 'NUM'; // [0-9]+
	const T_ADD = 'ADD'; // "+"
	const T_SUB = 'SUB'; // "-"
	const T_MUL = 'MUL'; // "*"
	const T_DIV = 'DIV'; // "/"

	/**
	* @param {string} input
	*/

	/**
	* 英米式の時刻表記でフォーマット
	*
	* @param { number } hour 0-23
	* @param { number } min 0-59
	* @param { number } sec 0-59
	* @returns { string }
	*/
	function formatTimeEn(hour, min, sec) {
	// AM 12 1 2 3 4 5 6 7 8 9 10 11