Skip to content

Instantly share code, notes, and snippets.

View marihachi's full-sized avatar
🕹️

marihachi marihachi

🕹️
View GitHub Profile
@marihachi
marihachi / format-time.js
Last active January 14, 2024 10:33
英米式と日本式の時刻表記にそれぞれフォーマットするコード
/**
* 英米式の時刻表記でフォーマット
*
* @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
@marihachi
marihachi / parsing-01.js
Last active March 21, 2023 15:07
パーサーの例
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
*/

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

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

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

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

@marihachi
marihachi / readme.md
Last active January 6, 2023 15:24
Terrario for AiScript

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.

@marihachi
marihachi / gll.md
Created February 16, 2022 15:09
GLL parsing

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

Continuation-passing style

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

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

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

@marihachi
marihachi / aiscript_if.ts
Last active April 5, 2020 07:57
ai script parser (wip)
interface INode {
type: string;
children?: INode[];
[x: string]: any;
}
interface BooleanLiteral extends INode {
type: 'bool';
value: boolean;
}
@marihachi
marihachi / misskey_pages_doc.md
Last active January 12, 2020 12:11
Misskey Pagesで使われるAiScript(AST)についてのドキュメント

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

ASTメモ

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

リテラルタイプ

@marihachi
marihachi / dependencyResolution.ts
Last active July 2, 2020 20:29
モジュール間の依存関係を解決してみる実験
/*
* MIT License
* (c) 2019 marihachi.
*/
interface Edge {
src: number;
dest: number;
}
@marihachi
marihachi / csv-parser.js
Last active May 25, 2019 20:51
A csv parser written by PEG.js
/*
* Generated by PEG.js 0.10.0.
*
* http://pegjs.org/
*/
"use strict";
function peg$subclass(child, parent) {
function ctor() { this.constructor = child; }
@marihachi
marihachi / adder.c
Created December 22, 2018 08:18
任意のビット幅の2進数を加算演算するやつ
#include <stdio.h>
#define BIT_WIDTH 64
#define SUMS_SIZE BIT_WIDTH + 1
void half_adder(unsigned char left, unsigned char right, unsigned char *sum_out, unsigned char *career_out)
{
*sum_out = left ^ right;
*career_out = left & right;
}