「コンパイラ・スクリプトエンジン」相談室15

JavaScriptのV8エンジンの文字列処理の最適化について教えてください
例えば、
var s = "";
for(var i=0; i<1000; i++) {
s = "s" + s + i + "e";
}
のようなコードをCやほかの言語で実行しても
V8エンジンほど速くはならないのですが、
V8エンジンは内部でどういう最適化をしているのでしょうか？

文字列処理の最適化より
配列処理の最適化した方が良い

つーかスレ違い

V8はがべこれしてない

>>707
関係無けど、こういう原理的にはコンパイル時に決定できる最適化関係はV8エンジンは異様に強いよね

>>707
Cでどんなコード書いたのか気になるところ

Cのコード
#include <stdio.h>

char buf1[1000000];
char buf2[1000000];

char *bench(int n)
{
int flag = 0;
int i;
char *p1, *p2;
buf1[0] = '\0';
buf2[0] = '\0';

for(i=0; i<n; i++) {
if(flag) {
flag = 0;
p1 = buf2;
p2 = buf1;
} else {
flag = 1;
p1 = buf1;
p2 = buf2;
}

sprintf(p1, "s%s%de", p2, i);
}
return flag ? p2:p1;
}
続く

続き
int main()
{
int i;
for(i=0; i<2000; i++) {
printf("%s\n", bench(i));
}
return 0;
}

JavaScriptのコード
function bench(n) {
var s = "";
for(var i=0; i<n; i++) {
s = "s" + s + i + "e";
}
return s;
}

for(var i=0; i<2000; i++) {
print(bench(10));
}

環境
OS: Fedara 19
CPU: Core2 Duo T7500 (2.20 GHz)
gcc 4.8.1
glibc 2.17
v8 3.14.5.10
コンパイルオプション
gcc -O2 -march=native bench.c
結果
time ./a.out > /dev/null

real 0m12.917s
user 0m12.900s
sys 0m0.010s

V8結果
time d8 bench.js > /dev/null

real 0m0.063s
user 0m0.044s
sys 0m0.012s

こんなに違うのですがどういう最適化をしているのでしょうか

関数benchで副作用が(関数内で)閉じている事はコードを静的解析すれば分かるから、
V8処理系が自動的にメモ化しているのではないかと思われ

def bench(n)
　　s = ""
　　for i in 0..(n - 1)
　　　　s = "s" + s + i.to_s + "e"
　　end
　　s
end

MEMO_BENCH = Hash.new { |hash, key| hash[key] = bench(key) }　　# メモ化
def memo_bench(n)
　　MEMO_BENCH[n]
end


def run(n)
　　t0 = Time.new
　　for i in 1..n
　　　　yield
　　end
　　t1 = Time.new
　　p (t1 - t0)
end

N = 2000
run(N) { bench(10) }
# => 0.358945
run(N) { memo_bench(10) }
# => 0.016584

Cがbench(i)で
JSがbench(10)なのはここに書き込む際のミス?
bench()内のループの実効回数が100倍くらい違ってくるんだけど。

というか、sprintf() 使っている時点で勝負ありだろ

Cのsprintfもprintfも外部ライブラリの関数なので
インライン展開が効かない
2000回のループをひとまとめにすることは出来ないしdenchの
呼び出しのsprintfの引数に与える変数をコンパイル時に決定することも出来ない
対して、JavaScpiptのコードは組み込み関数なので
実質的に全てを展開可能で、最大限に最適化した場合に
print("s0e\ns1e\n......
のような一行だけ実行するかも知れない
Cで最適化が効くように書く事は可能かもしれない
ただ、言語に組み込まれた組み込み関数がある事は
最適化にとって有利なのは間違いないだろう
少なくとも例示された書き方は、Cの速度を評価するには
余りに不適切な書き方ではあるし、Cで意図した処理を
JavaScriptより高速に書くことは常に可能ではある
（手動最適化を含める必要がある場合はあるかも知れない）

>>720
>Cで意図した処理をJavaScriptより高速に書くことは常に可能ではある

Rubyにはクロージャとしてのブロックがあるので、
>>717で示したようにメモ化を用いた高速化は容易に実装できる

Cの場合にはクロージャが無いからRuby同様なメモ化は実装できないが、
代わりに「遅延データ構造」という手法を用いれば実装できる

ただし、遅延データ構造による実装が「常に可能である」か否かは知らない
おそらく対象が何らかの代数構造を満たす必要があるだろう
少なくとも今回のお題の(対象としての)文字列はモノイドなので、これを満たす

>>717
ではbench(10)をbench(i)になおした以下のコードもV8 Engineではメモ化されるのでしょうか。
これでも先ほどのC言語のコードより速くなった(0.462s)のですがどのような最適化によると思われますか？
function bench(n) {
var s = "";
for(var i=0; i<n; i++) {
s = "s" + s + i + "e";
}
return s;
}

for(var i=0; i<2000; i++) {
print(bench(i));
}

717じゃなくて悪いけど、逆順から呼び出してみ。
for(var i = 2000; i-- < 2000; ) { print(bench(i)); }
これで実行時間が変わらないなら事前計算された文字列をハッシュテーブルから
引いてるんじゃない?
大幅に遅くなるなら、実行結果をキャッシュして次の計算に使用してるんでしょ。
bench(10)の結果はbench(9)の結果を使って計算できるんだしさ。
そういう風にCで作ったら、bench()呼ぶ毎にmallocでメモリ確保しても
ゴミCPU(C-50)で853msだったし。

あ、ごめん。i-- < 2000 じゃなくて i-- != 0 で。

>>724
0.168sでした
事前計算というのはどういう手法なんでしょうか？

これで
http://codepad.org/CZldxktk

$ gcc -O2 -march=native main.c -o main
$ time ./main >/dev/null

real 0m0.001s
user 0m0.000s
sys 0m0.000s

こうだった

あぁ、ちょっと勘違いしてた
http://codepad.org/hiJz0zt5
こうだな
real 0m0.063s
user 0m0.061s
sys 0m0.001s
printf呼び出しが冗長だから、それを少なくするように書けば
いくらでも速くなると思う。（メモリーとの兼ね合い）
多分処理時間の大部分はIOで食ってると思う
これを取り除くとCPU時間はほとんど０に近くなるんじゃ無いかな

>>726
それ実行結果違わね?

>>725
むしろ速くなってるね。
コンパイル時に引数に対応した文字列のテーブルを作っておいて
bench内ではテーブル引いて返すだけって意味で事前計算って言った。
たぶん717のやってることだと思うんだけど、こういう言語
触ったことないからわからん。

>>727
[30, 40]行目をこれと交換して
char* p2;
p = buf;
p2 = buf + n;
for(i = 0; i < n; ++i) {
*p++ = 's';
_itoa(i , &p2);
*p2++ = 'e';
}
*p2++ = '\0';
puts(buf);

ごめん。これじゃだめだ。

あ、だめじゃなかった。ほんとごめん。

>729
thx
40行目のnullターミネィトだけ必要ですね
putsの方が速いか

>>729
人間が処理を理解して工夫すれば、
このようにとても早いアルゴリズムに直せると思うのですが、
V8のスクリプトエンジンなどは's'の並びがbufからbuf+nまで連続することに
あらかじめ気づくのでしょうか？

何とかJSの速度を超えられないかと思ってC++で
std::string s;
for(int i = 0; i < n; ++i) {
s = 's' + s;
std::ostringstream os;
os << i;
s += os.str();
s += 'e';
}
とかやってみたけどさ、全然遅いのよね。
速いアルゴリズムに代えられることに気付いているとしか思えない速さだと思うよ。
この分野さっぱりだからさ、アドバイスはできないんだけどね。ごめんね。

あぁこう言うことか
http://codepad.org/rSzsp8sE

これで良いんだよね？

V8 Engineはバッファの基点をbuf[0]にしないことで
for(...) {
s = S + s + E;
}
という文字列処理の最適化を行っているんでしょうか

V8エンジンってのはそんなに凄い物なの？
ちょっと聞いたことが無いんだけど
この程度の最適化を自慢してるくらい何だから
作ってる奴らは
どうせ口ばっかりでたいしたことない奴なんだよ
おれなら10倍高速に書けるのに

>>737
針デカ過ぎです

コピペかと思ったら違った

まぁ、そもそもコンパイラーなんて書く気も無い
ワナビーはそろそろ場違いなんでお引き取り願った方が良いのでは

ごく普通のBASIC的なスクリプトを作って実行するとHSPぐらいは行ってるな。べんちとると。

ポジショントークだよな。
>>734とか速いわけがないコード出して遅いっていう意味がわからないもの

あああ

http://katahiromz.web.fc2.com/mathai/mzcalc1.zip

これをC++のプログラムにしたいんだけど、どうすればいいかな？

lexとyacc通してcにすればいいんじゃないかな
そういう意味じゃないってんならlexはともかくyaccの方はコンパイラコンパイラでC++に落ちる奴使えばええんでないの？
あるいは文法規則をc++のtemplateで生成する奴使うとか

そこで具体的なツールの名前が出てくるのがこのスレなんじゃないの

>>746
前スレだか前々スレにcaparってのが紹介されてた
このスレでも>>462でちょろっと名前が出る
ただ文法規則は違うんだよね、移植は必須

やはりBison++は互換性に問題があるようだ。さらにWin32では新しいバージョンが用意されていない。

結論：Bison++は使えない

どのみちそんなもんラップして使うだろ
C++のライブラリに拘る意味がわからない

一つのプログラムでパーサーが２つ以上必要なときや、再入可能じゃないといけないときは、困るだろう

ドキュメントくらいしっかり読めよ
YYPARSE_PARAMなんて基本中の基本だぞ

その用途で解決策が乏しくて不満が出るのは普通はFlexの方だ

>>750
お題程度ならC++でゴリゴリ書いても良いじゃんよ
元の目的がはっきりしてないから質問の答えだって迷走すらぁね

staticにするなり、defineで別名にするなり、手で別名にするなり、どうとでもすればいい気が…
そのまんまC++に持ってって動くコードなら適当な名前空間などで括るとかどうにでもすればいい

lexer と parser の協調動作（parser 側から lexer のステートを切り替えるとか）が
必要な場合、何かお薦めの方法ある?
yacc とかが生成したパーザだと、先読みの可能性を考えながら文法書くのが辛すぎる。

先読みが問題になるって事はreduce以外のタイミングでlexer側のステートを切り替えたい要件？
それをyacc系でやるのは茨の道かな…切替タイミングをreduce時に絞れるなら何とでもなるけど
それ以外はケースバイケースでアクロバティックになる事も割と多かった気がする

LRパーサをやめてANTLRとかに走ってみるとか

keyword_or_identifierみたいなトークンに織り込んでしまえ
汚くなるけど一貫した方法で処理できるからスキャナの状態触るよりはマシ

>>755
LR パーザの動作をちゃんと理解している自信がないのだけど、
LR(0) でない限り、 reduce のタイミングでも次のトークンが
食われてる可能性はあるような。
先読みせずに reduce できることが一意に決まれば先読みされないはずだけど、
綱渡り感がすごい。

>>756
LL 系パーザでも、パーザジェネレータを使うと先読みのコントロールが
利用者から奪われるのは変わらない気がする。

>>757
過去、二回くらい試して挫折した。たぶん一番正しい方法なんだけど、
スキャナが余分なトークンを生成する（空白文字の取り扱いが変わるため）ことで、
文法が LR(1) に収まらなくなるという…。

> 先読みせずに reduce できることが一意に決まれば先読みされないはずだけど、
ごめん。これ嘘。
もちろん実装依存ではあるのだけど、現実的には常に先読みされていると
思っていいのかもしれない。

http://katahiromz.web.fc2.com/mathai/mzcalc2.zip
Boost.Spiritを使ってみた。変数への代入ができないよお。
助けてよお。

終端記号にトークンを必要としない文法ならreduceのタイミングでは先読みはないよ
Bisonなら吐かれた制御ロジックや表を理解しなくても詳細ファイルを出力させるだけで大体そこは読み取れる
ただし先読みを行う行儀の悪い実装が無いとは言えないし、
parser上の先読みは無くともlexer上の先読みの話は残るので文法によってはyyunput()等での調整は必須になる

終端記号にトークンを必要とする文法ではlexerへの干渉内容次第でyacc系での実装が無理筋なのはその通り
一応色々対策はあるけどそこまで来たら文法と手段の見直しが先決

Boost.Spiritは難易度高いよな。。。

スキャナアクセスが考慮されてるパーサジェネレータもあった気がする

%option reentrant と %pure-parser(再入)と
%glr-parser(LALRじゃなくGLRによる衝突遅延)と
%x (スキャナの状態)

Flex+Bison で何が不足か

Boost.Spirit V2は難解すぎ。アクションメソッドがconstで何ができるっつーんだよ。
BisonはGPLに汚染されていてC++への対応が悪い。
消去法でANTLRが良さそうなので使ってみるか

Bisonは大して不満ないけどFlexの足回りはやや進化が遅い気がする
前使った時に泥臭いなと思ったのは入力ストリームを一度割り当てて読み切った後に
他の入力ストリームに交換してクリーンリセットする正規の手段がない事と翻訳単位変数依存がある事

あの時は.l側にyy_init=1やyy_start=0等を実行する小さな関数を作って%initial-action他から
実行させて凌いだけど、最近のバージョンは正規の手段準備されたんかね

>>762
Caper使えよもう

Bisonが吐いたコードまでGPLに感染するわけじゃないだろ
C++はわからんな･･･結局Bisonが吐いたコードをC++のコンパイラが処理できれば足りるはず
アクションにどこまでC++を書けるかはやってみたこと無いからわからん

まあANTLRなら戦えるだろう

シェルを作ってみたい

一瞬で作れる

ANTLRWorks 1.5.2ゲットだぜ！

>>766
re2c 使うべし。

サンクス、こんな流れがあったのか、それも結構前から
個人的には近年のツールなのにきちんとCをサポートしてる所がいいな
Flex同様ドライバの一部にも多種の組み込みにも使える余地を残してると

Flexの長所と短所を踏まえて作られた流れみたいだしその内試してみる

ANTLRv3で!ってどういう意味？
v4でどう書けばいいのかわからん

ANTLR3でbacktrackが必要な文法だとFOLLOW_set_in_問題が
発生して死ぬ可能性あり。詳しくはFOLLOW_set_in_でググれ。

Cパーサーを作成中。

識別子の解析でreduce/reduce conflictが起こってしまうよ。助けて偉い人

とりあえず関数の中を全部捨てて一通りパースを通すのがいいんじゃまいか
関数の中はむずかしいｗ

あるいは typedefを捨てればチョー簡単になる

わかった。typedefにある識別子は型名と見なしていいんだな。

ああ、typedefがあるおかげで、識別子が型名に化けるという問題か。
Cだと確かアドホックにやるしかないんじゃなかった？

Javaの場合確か文脈によって区別できたと思うけど。

Javaにはポインタがないというさりげない工夫

それ、この話とどう関係が？

Javaは関係ないだろといいたいのか
何でポインタが出てくるのかわかんねーといいたいのか
コンフリクトが解消できません

識別子が型名に化けるので、文法がLALR(1)のようなシンプルな範囲に
厳密には収まっていない、ということと、Javaにはポインタがない、ということに
関連はありますか、ということ。

よくわからん話題だな。俺はchar[]を１文字ごと解析してる。

javaアプリに組み込むインタプリタを作りたいのだが、
それは諦めて、スクリプトを自作パーサでjavaソースに変換し、
javassistで実行中のjavaアプリに動的ロード＆実行しようと
計画を立てたものの、一向に進まないやｗ

>>785
LuaJava
luaj

>>785
思い切って機能を端折って、とにかく動くものをエイヤで作らないと、いつまでも進まないと思う。
ひとつめは捨てることになろうとも、とにかく作れ。

>>786
javascriptとかPHPみたいにcharも触れない言語は糞なの。

>>787
まずはクラスとか捨てて関数とプリミティブ型と文字列でコンソールにhello worldやな。

LispやForthみたいなParserなにそれ？みたいなのからAlgol系みたいなパーサが楽なのからやらないでいきなりC++みたいなキ印パーサとか正気とはおもえない。。

お前の書き込みは如何なるパーサーでも解析できない

C系は構文解析と意味解析が綺麗には分離出来ず、パーサからレキサへのフィードバックが
必ず必要になる(寿命管理のおまけつき)から目的を問わず最低開発コストは高いよ
原始的なC構文だけでもエラーや回復、構造体や共用体、ポインタの咀嚼までgdgdにならず完走するのは一仕事

でもこの辺一通り実装出来なきゃCパーサとしては使い物にならない

つかみんなCの新しい実装をつくりたいの？

楽しいよ？
C90ぐらいだとけっこう手ごろな規模だし

トークンを区切るところまでできた。
まずは関数単位でブロックに分けてみる。

関数の中から先にやるといっているのだろうか

>>785 の続きか。すまないわすれてくれ

Cパーサのプロトタイプができたよ！！！！
http://katahiromz.web.fc2.com/mathai/cparser2.zip

暇だったら見てやって下さい

>>796
うん。関数の中以外を分けてブロック化した。

do main : int {
return 0;
}

class A
{
do hello(){}
var i : int;
class B { enum C { a, b, c} }
}

こんな感じのものから、ソースファイル内にある
クラス名・メンバ関数名・メンバ変数名を全部抽出する。
冗長になるけど、関数宣言はdo, 変数宣言はvarを付けて分割しやすくした。

javassist練習中。スクリプトがmain()メソッドひとつで完結していれば
なんとかなりそうだけど、他の関数を呼んだりクラスを後に追加するに
あたってはまるで見当がつかないや

java (スクリプトロード前)

class ScriptRunner {
..void load(String script_file, String script_main){}
..void go(){
....// nothing
..}
..void unload(){}
}

script側

do main(){
..log <= "hello"+" & "+"world";
}

java(スクリプトロード後)

class ScriptRunner {
..void go(){
....Log.log("hello"+" & "+"world"); // changed
..}

..void load(){} void unload{}
}

__attribute__のパースに失敗する。reduce/reduce conflictが大量に発生する。大変難しい。

__attribute__を文法から除外することで解決した。

SLR文法であるような現実的なプログラミング言語って何か例ある？

なんでわざわざSLRにこだわるんだ？
SLRと状態数がほぼ同じで、より広い範囲の文法を扱えるLALRがあるのに

じゃあGLRの教科書教えてください。

GLRはamazonで検索すると出てくるよ

あんがとあんがと。

CD GLR385760 ハイドン弦楽四重奏曲選集/スコア&パートセット (2003/2/25)
現在お取り扱いできません

こんなのしかない・・・

「コンパイラ」とかで検索かけて商品説明で自然言語とか扱ってるのを買えばいいんじゃね

やあみんな、Scala開発者のための新しいopen-sourceのPEGパーサライブラリ−
"parboiled for Scala"を紹介しよう。Scalaのパーサコンビネータに似た内部DSLで
PEGパーサを作ることができ、以下の優位点を持つ。
　・パーサ規則作成と、入力の解析とがきれいに分かれているので、速度が速い
　・親切なエラー報告機能がある
　・シンタックスエラーがあってもエラーリカバリして、最後までパースできる

GLRって日本人が考えたんでしょ？
なんで日本語の本が無いの？

すげえ！まるでbisonだ！

PEGはメモリーを使いすぎることと、構文規則を書くときに左再帰が
許されないのが弱点だって。
左再帰は自動除去も考えられるけど、メモリーはどうなんだろな。

何百メガもあるようなソースを処理するのでなければ今時問題ない。

@jonigataさんのCaperが劇的に高速化されたらしいぞ！！！
github.com/jonigata/caper

PEG/Packratのメモリ使用量ってソース規模の関数？そうだっけ？

バックトラックで数百メガ使うことはないだろ
右再帰だと関数とかの単位でけつまで抱え込むみたいだが

メモ化で大量のメモリを消費する

テキストの長さに比例しただけのメモリの消費を、今時「大量」とか言う奴は、
物事の感覚がおかしい。

Packratはもちろん空間計算量O(n)ではあるんだけど
文法によっては入力テキストの100倍とかメモリを消費するので……
たかが比例する程度だから問題ないと言えるほどでもないと思う

このスレがワードの文字カウントで108881文字ある。
てことは、仮にUTF-8だった場合、300KB位じゃないの？
sjisだよとかそういう話じゃなくて。
PEGで書かれたHTMLパーサがCGIで使われていて、同時に100人がアクセスしてきたら
とか考え始めると、やっぱりメモリーも大事なんじゃないのかな。

あと、PEGの本紹介してください。
ドラゴンブックは読んで、自分でLALRパーサジェネレータまでは書いた。
100年かかった。
10年で出来るPEGの本があったら教えて！
メモリーを心配してるのは、字句解析器が吐くコードがやたら大きくなるので、
こりゃまずいと思ったから。

IDの所為か人がいなくなった。
地球には自分一人しかいないような気がしてきた。
みんなどこ行ったんだ。

元から人口はこんなもんだった気がする

2月3月の書き込み多いやん。このスレ的には。

>>814
ブログとgoogle codeしか見てなかったthx

GitHubのCaperって今の時点で2つしかwatch無いのね
watch入れてない自分が言うのもなんだけど。(だって入れなくてもcloneできるしー)

注視しているならwatchをonにした方がいい。作者にも情報が伝わるし気合いが入ると思うから

>>826
Pull request出してるのみたお
応援するお

何で突然設定変更？と思ったら勢い5以上のスレ限定で告知とかやってたのか
何かお前は板の住人じゃないって言われてるみたいでちょっともやっとするなー

全スレに貼る労力を考えたら仕方ないのかも知れんが

Caperって、コメントアウトしてあるけどLR文法を受理するパーサーも出力できるんだね。
ちょっとソースコードいじってみようかな。
いまどきLALRにこだわる理由もないし。

>>829

ごめん、そのアルゴリズム考えた人に「うまく動かないんだけど」って
連絡したら、「そのアルゴリズムバグってる」って言われたんで
潰した。手元のバージョンでは消してあります。

おお、お久しぶり、っていうかCaperを自己紹介した時以来？
あのときから時々ではありますが、パーサが必要なときにいつも使っているので感謝してます。

LRを考えた人って言ったらKnuthか！

結局、LispやForthのような構文解析が簡単な言語には
BASICのようなインタプリタは速度面で勝てないのだろうか。

>>833
構文解析なんか最初の一回きりだろう？
構文解析が原因で実行速度で追いつけてないのはインタプリタの設計で毎回パースするようなアホな事してるかじゃないの？

BASICは解析結果を別ファイルに保存しておく機能がよくあったじゃん。

>>831
ありがとう、使いづらいところがあったら教えて下さい！
今なら対応できるかもしれません。
（最近片山さんに煽られてエラーリカバリ実装するために
ソースほとんど全部読みなおしたところなので、把握出来てる）

>>832
david.tribble.com/text/honalee.html
これです！　うまく動かなかった！

>>830
返信と現状の情報ありがとうございます。
ドラゴンブック読んだら自分でもLRくらいなら実装できそうなのでがんばってみます。

Caper の FUTURE WORKS の項目に EBNF の対応が課題としてありますが、
kp19pp では (group) / ? / * / + による修飾に伴って型とセマンティックアクションを指定し、
内部処理ではそれらを一種の Lambda 的な扱いで解決しています。
これらを参考として Caper 組み込んで下さるといろんな方達が助かります。

>>838
じゃあ何でkp19ppを使わないの？

kp19pp を作った人が死亡したからです。

勝手にシンデレラ

死んでても使えませんか？

ちょっと良く覚えてないですが、
EBNFに対応するにはstd::vectorとか特定のデータ構造が必要になるなと思って、
セマンティックアクション側に特定の構造を期待しないcaperとしては
実現不可能だなと思ってやめた気がします。

今だったら、variadic template使えばいいかな？

いやvariadic template使っても難しいかな……
SemanticAction側の条件を厳しくする以外に
いい仕様が思いつかない

あ、次の引数を受け取る関数をセマンティックアクションに渡して、
セマンティックアクション側はテンプレートで受け取ればいいのか。

struct SemanticAction {
template <class F>
void SumList(F f) {
std::vector<Value*> a;
Value* v
while(f(v)) {
a.push_back(v);
}
}
};

こんな感じ

質問っす。

インタプリタのVMについてです。
明快入門　コンパイラ・インタプリタ開発を読み終えましたが、
バイトコード生成から命令実行のスイッチまでのあたりで、
あれよりいい方法はありませんか
また典型的にはどの様に実装されますか

規模と寿命と使われ方、他にもターゲットマシンの性格によって使い分けるんでその質問に的確に答えるのは難しいんじゃないかな？

>>845ですです。

プラットフォームは当分x86ですが、
場合によっては移植できるよう機種依存コードはできるだけ書きたくありません。

目的は、インタプリタの実装の学習とテストです。

「いい方法」とは具体的には、速度と拡張性のことです。
まだ、有名どころのコードを読むまでのスキルがなく、参考にすることができません。

参考書籍の紹介だけども助かるのでお願いします。

だけども->だけでも
です。

LR系のテーブル/オートマトン作成方法って調べれば調べるほど出てくるな。

>>847
VMの高速化技法っつってもJITもあれば言語が動的オブジェクトへのメッセージ送りもってれば辞書キャッシュとかVM命令の粒度変更とかいろいろある
学習が主題かつ他人のコードを読みこなせないのであれば数こなすとか、出てる本片っ端から(外れもあるんだけど)読むとかから手つけておくのが一番の近道だと思うぞ

ebnfブランチ github.com/jonigata/caper/tree/ebnf で
EBNFを実装してみた（C++ジェネレータのみ）ので暇な人いたら人柱募集。
使い方はsamples/cppのlist0, list1, list2, optionalを参考のこと。

list2のスラッシュオペレータは独特のやつで、
X/Yと書くと X Y X Y XにマッチしてYを捨ててXのリストを返す。
引数リストなどに使う目的で作った。
カッコは役に立つところが思いつかないので実装してない
（今のところ実装する気もない）。
というか実用的な言語ではスラッシュ以外ほとんど使うところないと思ってる。

出力されるパーサ・ジェネレータのソースはより読みやすくなったはず。

EBNFってCaperみたいな強い静的型付け言語の機能を利用したものだとYaccみたいに全てを諦めるしか実装方法ない様に思えるんだけどどうなの？

とりあえずイテレータ対とかboost::optional的なものを返すようにしてみたよ。
それをどう使うかはセマンティックアクション側で勝手にしてね、的な。

template <class S>
int Document(const S& x) {
for(typename S::const_iterator i = x.begin();i!=x.end();++i) {
}
return 42;
}

こんな感じで受ける。
なぜかrange-based forは使えなかった。
返すイテレータの実装が悪いのかな？
誰かに添削して欲しい。

あ、気のせいだった。普通に使えた。

template <class S>
int Document(const S& x) {
for (const auto& y: x) {
}
return 42;
}

これで受けれる。

マイクロソフトが、MS-DOSとWordのソースコードを一般公開したらしい。
サイズはなんと、300kb未満。(2014年3月26日)

「MS-DOS　ソース公開」で検索。これは参考になるかな?

アセンブラ読む気あるの？

アセンブリ

アセンブル

EX10

確かに、公開しても、あるいは昔のCPUで簡単としても、
解読する暇はないな。意外な盲点だった。

MS-DOSの頃なら大半はC記述じゃないか？
前身のMSX-DOSの頃ですらM80/L80/Cと一連の移植ツールセットを売ってたし、
いかにもCP/Mベタ移植っぽい効率の悪い動きしてたからな

> 前身のMSX-DOSの頃

単に事実誤認。
MS-DOS 2.0 のリリースと MSX の誕生が 1983 年。

関係ないけどjonigata氏を今まで20代後半くらいかなと思ってたら全然違った

>861
MSX-DOS出たときにMSDOSはとっくに存在しとるじゃないか。
PC98でMSDOS上のCross AssemblerとかカノープスのZ80ボード経由でMSXのソフトとか開発するの普通じゃん。

>>859
むせる方か、東芝の12ビットチップの方かどっちだ？

>>864の言ってるソフトの括りは偏ってる気がする

I/O直叩きや高速性が求められるゲームなんかは当時はほぼ機械語でゴリゴリ書くしかなかったが
DOS系コード(チップ制御以外)は違いますがな、性能より開発コスト重視で割と酷い動きしてたじゃん
システムコールのレコード長周りとか

MSXDOS.SYSやCOMMAND.COMのレジスタの使い方はコンパイラの匂いしてた記憶あるな。
MS-DOSもそうなってるかまでは知らんけど。

省メモリ最優先なんじゃないの？
COMMAND.COMは所詮オプションだからCで書けるかも知れんな

主要部分は640Kの最後のほうに置いて、下位アドレスに常に常駐するメモリ量は
最小限にするとか、COMMAND.COM だってけっこうエグいトリック使ってるよ。

>>865
そうなのか?,あの頃ってMSX単体開発するのにMSXDOS出るまでって相当厳しかったんじゃ？
ASCII編のアセンブラとかもMSXDOS前提な書籍とかあったし。
おいらは若松のCP/Mマシンに9918AとPSGつないでMSXのソフト作ってた
タイトル言うと即バレするので書かないけど2つ程ROMカセットで売って貰った、98でクロスアセムでもROMエミュ持ってたらそっちの方が楽かもしれないと思った。

っていうかこれスレ違いだなぁ orz

いらん話題持ち込んで糞スレと化したw

>>868
その手のCで書き辛い部分はDOSに関しちゃごく一部だから、そこだけ別ルーチンで書いてリンクすれば終わるよ
容量制限の厳しいROMBIOSなんかはMSも涙ぐましい努力してたけど、DOSにそこまでの対効果を見込んだかどうか…

まあここでゴチャゴチャ言うより誰かDLして確認すれば正確に分かると思う

>>869
ここで言ってるDOS系コードはDOSの構成要素である各種コード群や
その上で動くソフトの事で、それらはCを排除する絶対的な要件って無かったよなって話
単体開発とかMSX限定とかそういう話じゃないよ、それらで大半を機械語で書く必然性の話

ダウンロードして展開してみたけども、
msdos\v11source\ の中は *.ASM が7個と Tim_Paterson_16Dec2013_email.txt というテキストファイルが 1個。
msdos\v20source\ の中はファイル118個中 *.ASM が丁度100個、Cで書かれたソースコードは無し。
以上

>>873
今の時代でも、参考になりそうなテクニックは網羅されていたかな?

>>869
御冗談を
MSXでMSX-DOSのシステムコールが必要なソフトなんて
グラフサウルスくらいしかしらないんだが

MSX-DOSのシステムコールどころかBIOSすらほとんど使ってないはず
市販ソフトはほぼ自前で実装でしょ
MSX-DOSが無いと厳しいという話は聞いたことが無いなあ

ソフトの実行じゃなくて開発の事を言ってるんだと思う
DOSが必要だったというかメモリが64KB使える環境でないとメガROM以前の
16KB/32KBROMの開発すら無理だったと言いたいんじゃないかな

http://ascat.jp/tg/tgd3.htm

ただMSX-DOSには多分一般リリースされた日と一通り仕上がった日に結構な開きがある気はする

MSXはシステムコールの実体を全てFDC-ROMが供給という特殊な構成を取ってるから(なのでDOSが
無くとも全てのシステムコールが可能)、初期にFDD付きMSXを売ってたナショナルやヤマハ等の
ベンダー向けに出回った内製のMSX-DOSがあって、FDC-ROMの雛形と一緒に本体開発前に配られてたのでは
でないとROMのデバッグが相当面倒臭い事になる

いい加減にスレ違いと気づいて呉

まぁこういった話は正確なことを残しておかないと間違いが後に残る

残しておく価値もない

残すべきスレはここじゃない

シリコンコンパイラ作れる猛者はこんな所に居るかい？？？
居る訳ないよね？ とっくにカメラメーカーの研究所とかに就職してるよね？

つらそう

PEGとパックラットについて知りたいのですが、
オライリーの言語実装パターンっておすすめですか？
記述が少しあるようなのですが。

LLVMこそ至高
ならば全人類のためにLLVMのシリコンコンパイラを作ろうではないか

はい

シリコンコンパイラ、何かと思ったら…研究費ふんだくってくるためのネタみたいなやつやな

ハードウェア記述言語の言語処理系のことを昔はそう呼んでたと思うけど、
それとはまた違うものを最近はそう呼んでるの？

Caper更新ｷﾀーーーー！！！

test

［速報］米マイクロソフト、C#／Visual Basic次世代コンパイラ「Roslyn」を
オープンソースで公開。独自言語など開発可能に。Build 2014
ttp://www.publickey1.jp/blog/14/cvisual_basicroslynbuild_2014.html

MZたんがんがってるなぁ
mergeしてるjonigataさんも大変かも

シリカコンパイラ

>>890
開発部隊がバラバラだから、JavascriptもC++(/CLI)も含まれてないw
だせえ

アホか
Roslynは現在C++で書かれているC#とVBのコンパイラをブートストラップで書き直すことで
メタプログラミングに使いやすくするプロジェクトだ

何のために公開すると思ってんだという話

社内にはC++やJavascriptのプロジェクトはないんだろうな。
C#とVBとその二つへの埋め込みDSL以外はドキュメントでも触れてないから。

つうかc#もjavascriptもまだ未完成で
perl6とかmozilla tamarinとかdehydra gccとか
ウヤムヤプロジェクトになってもおかしくないレベル。

>>896-897
とりあえず完結した入力文法持ってる言語ってFORTHとLISP以外ないんじゃないの？

>>897
間違えた。
javascript→VB

未完成ってのは仕様が固まってないじゃなくて
実装が不十分ってことかい

仕様もないけど。
実装=仕様の状態だから。
AST, APIが不完全。

rubyでつね

roselyn APIのことね。
C#とVBのbindingがあってそれぞれの言語が対象になってる。

x86のintrinsicのまとまった情報が欲しい

この辺かい？

アセンブリ命令
http://www.intel.co.jp/content/www/jp/ja/architecture-and-technology/64-ia-32-architectures-software-developer-manual-325462.html?wapkw=x86+manual

Intrinsic
https://software.intel.com/sites/products/documentation/doclib/iss/2013/compiler/cpp-lin/index.htm#GUID-28F49E4A-615D-4373-A36E-C8A92E913325.htm

>>905
ありがとう。助かった。

CaperにちょっとしたC言語ソースのパーサのサンプルを追加しました。
興味があったらご覧下さい。
https://github.com/jonigata/caper

lexerの自動生成って必要?
ANTLRみたいなタイプならともかく、flexみたいなのって
よほど単純な言語でない限りは余計に複雑になるしデバッグもしづらくなる気がする

必要ないものは使わなければいい。
parser generatorも同様。

そらまあ慣れてればパーサも手書きで十分だろうけど

LALR手書きできるスキルがあれば…orz

Caperにスマートポインタサポートを追加しました。

はいはいはいはーい質問でーす

処理系のVMについてですが
オペコードはスイッチ文(switch, if)で一つずつ分岐するのと
命令一つ一つを関数でつくりそれを実行するのではどちらが早いですか？
ちなみに処理系はCでできています

おながいします！

>>913
実測値を信じろ

名前どうしたw

>>914
大手スクリプト言語どっちなんじゃ？

>>913
タイトなとこだけ展開。
昔のJITじゃないVMの読むと結構出てくる。
https://sites.google.com/site/io/dalvik-vm-internals
ちょこまかとした書き換えがすごく効く。
gotoとかloadとか小さい命令で。

>>911
LALR(1) も変形すれば LL(2) くらいにはなるので
あとは再起下降でもなんでも好きなようにすればいい

(1)じゃないたいていの言語でも、たいていは(2)ぐらい、というのは真だが、
変形すればLL(2)ってことはない。

手書きするなら左再帰に注意してLL(1)で十分だと思うよ。

ていうか手書きなら自然にループとか書けるから、再帰使わなくても
<X> = a (b c)* d
みたいな拡張BNFをそのままプログラムにすると思えばいい。

文法が再帰的なのにか。

本質的に再帰的なのと実装の都合で再起を使ってるのは区別しようね

LL (1) で足りるかどうかの方が問題なんじゃね

パーザは本質的に再帰。

入力の読み取りを後戻りさせたくないとか、mallocとかしたくないという昔の事情が (1) を欲しただけで、
部分的にちょっと (2) になってる、とかなら今時のマシンと言語とライブラリならたいして問題ない。

本質的に再帰になってるものとしては、式の構文とかがあるけど、普通にループで書ける。

<EXPR> : <TERM> (('+'|'-') <TERM>)*
<TERM> : <FACTOR> (('*'|'/') <FACTOR>)*
<FACTOR> : num | '(' <EXPR> ')'

<FACTOR> のルールにある、「カッコ内の<EXPR>」みたいなのを「本質的に再帰」と言う、
と言えば、まぁそうなんだけど。

abcとaをはんべつするときは
文字を2こ戻す必要ありますよね。
abdとかabeを弾いてaにしなければならなのですから。

boost.spiritはLL(∞)です。

くわしく

LL(*)とか言ってるのはANTLRじゃなかったっけ
なんかPLDIの論文で見たような記憶が

LL(k) k:定数

みんなどんな言語つくってるの？

ひらがな電卓、作ったよ！！！

ひらがな電卓CalcH
http://katahiromz.web.fc2.com/calch/

片山博文MZさんはGithubというキーワードでぐぐると幸せになれる。

GitHubはバリバリ使ってるよ。リクエストはまだないけど

日本語は同音異義語が多い。人工言語に比べて、自然言語は多態性が問題となる。
そこでこれまで使われてきたのが形態素解析だが、
多態性が解消できれば人工言語の構文解析の手法がそのまま使える可能性が高い。
そのことをひらがな電卓で示そうと思う。

お前は何を言ってるんだ
そんなもんBrainfuckのオペを日本語に置き換えたネタと変わらんわ

>>936
lojban で示してくれ
生来 esiperantisto の俺も lojban に傾倒しつつある

日本文化には敢えて日本語の多態性をフル活用するカテゴリーがあるからねえ

自然言語から多態性を排除したモノをプログラム言語として使うというのはアリだけど

各非終端記号を囲むカッコが2つ以上あるとLL文法じゃなくなるな。

具体的にBNFで

B:=C|(C)
A:=B|(B)
こんな感じ？

A:=BC
B:=D|(D)
C:=E|(E)
こっちの方が分かりやすいな。

A:=B|C
B:=D|(D)
C:=E|(E)
違った。

その例なら、

A := BC
BC := '(' DE ')' | DE
DE := D | E

と、くくり出せる。

なるほど。

このスレのテンプレにCaperを追加しておくれ。
jonigataさんのパーサジェネレータCaperは充分に実用的になった。

Caper
https://github.com/jonigata/caper

>>947
アレは良い物ですな、つかなかなかここまで細かい事できるのに使い方が簡単なのってなかなか無いんだよね。
自分使うだけでアレだけど、MZはpullrequest結構出しててそれもとっても有り難かったです。

今作ってる言語でCaper組み込む予定だよ。
いいよね、Caper。

実行時に文法を動的に変えることできますか？

主語を明示してください

プログラムが実行時に解析する文法を動的に変えることできますか？

eval

>>952
たとえばオブジェクト指向言語であれば
Gof本のInterpreterパターンで実装することによって
「実行時に解析する文法」を動的に構成できます
関数型言語だとコンビネータやモナドを使った
構文解析器(パーザ)の動的な構成技法があります

>>954
わかった
ちょっとjonigataさんに相談してみる

解析実行時に文法を切り替えるっていうと
Boost::Spiritでruleインスタンスを差し替えるのを先に思いついた

caper、動的エンジンもともともってるよ。
caperの文法ファイルは動的エンジンで起動時に文法作って読んでる。