Discuss Scratch

pupon
Scratcher
100+ posts

プログラミング言語を作ろう(合作ではないです)

pupon wrote:

構文解析の方法のLR法が全く理解できないんですが誰か教えてください,,,(アクション表やらGOTO表やら文脈自由文法やら右端導出やらで理解不能)
ですが、とりあえず自分が調べて分かったことを書きます。(間違ってたら教えてください)

そもそも構文解析とは
構文解析とは、字句解析されたものを文法に従って分析をして、構文木を取得すること。

構文解析のやり方
構文解析のやり方には、大きく分けて二つがある。

トップダウン構文解析
開始記号(S)から始めて、文法に従って少しずつ入力値に近づけながら構文木を(根から)組み立てていく。
再帰下降構文解析・LL法などがある。

ボトムアップ構文解析
入力値を少しずつSに近づけていきながら構文木を(葉から)組み立てていく。
LR法などがある。

LR(1)法の流れ
  1. アイテム集合を作る
    アイテムとは、どこまで読み込んだかのマーカーを追加した構文規則で、その集合のことをアイテム集合という。

  2. アイテム集合から構文解析表(ACTION表・GOTO表)を作る
    ACTION表は、行:状態 列:終端記号の表で、shift,reduce,acc,空白の4種類のうちどれかが各マスに書かれている。
    shift(s{n})は、入力を一つ消費し、スタックに状態nをpushする。
    reduce(r{m})は、文法mの右辺にある記号の数だけスタックをpopし、文法mの左辺の記号に対してGOTO表を見て、そこに書かれた状態をpopする。
    accは、構文解析を完了する。
    空白は、構文エラーになる。
    GOTO表は、行:状態 列:非終端記号の表で、次にどの状態にするべきかが各マスに書かれている。
    この二つを合わせたものが構文解析表。

  3. 構文解析表に基づいて入力値を解析する
    あとは構文解析表にかかれたACTIONに従って入力値を解析するだけ。

Last edited by pupon (Aug. 24, 2023 07:30:13)

akinarin
Scratcher
500+ posts

プログラミング言語を作ろう(合作ではないです)

>> #839

LR法は難しいです。
なのでパーサーを直接書くというのは普通せず、
パーサージェネレーターからプログラムを自動生成します。

昔、C#でLRパーサージェネレーターを自作してみたのですが、
頭がこんがらがりました。

僕はこの記事やwikipedia等を参考にして作りました。
比較的解りやすいのでオススメです。
オススメは出来ません
http://tatamo.81.la/blog/2016/12/22/lr-parser-generator-implementation/

Last edited by akinarin (Aug. 24, 2023 13:50:08)

akinarin
Scratcher
500+ posts

プログラミング言語を作ろう(合作ではないです)

>> #841
合っていると思います。

1つ補足すると、アイテム集合には「どこまで読んだか」のマーカーだけでなく、
「この文法の後に現れる終端記号は何か」を表す先読み記号もあります。

構文解析表を作る際に「アイテム集合を作る」というのが1番複雑です。
逆に「アイテム集合を作る」の所さえ解ればLR法は解ります。
(僕は試行錯誤の末、感覚的には理解できたつもりです)

先程紹介した記事と、Wikipedia「正規LR法」の記事がオススメです。
ですが、書かれていないこともあったりするので
解らないところがあれば言って下さい。

Wikipediaの手法と、先程紹介した記事の手法は少し違うのですが、先程紹介した記事の方が解りやすいです。

Last edited by akinarin (Aug. 24, 2023 14:16:40)

pupon
Scratcher
100+ posts

プログラミング言語を作ろう(合作ではないです)

#842, 843
僕も実はそのサイト見てました。
結構わかりやすいのでだいたい(7割ぐらい?)理解できました。
でもさすがにScratchだとパーサジェネレータを作るのも厳しそうですね…

あと先読み記号って
E -> E・ + num [$]
の[$]みたいなやつであってますか?

Last edited by pupon (Oct. 26, 2023 07:34:29)

akinarin
Scratcher
500+ posts

プログラミング言語を作ろう(合作ではないです)

>>#844
あってます。
[$]が先読み記号です。

Last edited by akinarin (Aug. 25, 2023 10:55:22)

pupon
Scratcher
100+ posts

プログラミング言語を作ろう(合作ではないです)

というわけで(?)
LR(0)のパーサージェネレータをScratchで作ってみることにしました。二次元配列とかないからむずそう

10/26追記
完全に忘れてた()

Last edited by pupon (Oct. 26, 2023 07:32:33)

kuroge_
Scratcher
100+ posts

プログラミング言語を作ろう(合作ではないです)

こんにちは
かーなり前に作ったlispみたいな言語を覚えていますか?(2-3ページ前を見れば多分わかる)
今更ながら更新したので主な更新点を2つ紹介します

1. while文の追加
ついに純粋な繰り返しが可能になりました
{set x 0}
{while (invar "_") (> (get x) 10) {
{print "Hello\n"}
{set x (+ (get x))}
}}
また配列やrangeを入れればforのようにも使えます
{set x (Array ["A" "B" "C"])}

{while (invar i) (get x) {
{print (get i) "\n"}
}}

2. 関数の追加
関数の宣言
{func sayHello {
{print "Hello, " (get name) "!\n"}
} (name)}
関数の呼び出し
{sayHello (name="kuroge_")}
もし変数名がグローバル変数とかぶっていた場合は関数内のみローカル変数が優先されます

こんな感じです。
あとは配列や文字列操作をしやすくしたりしました。
tomato-0809
Scratcher
100+ posts

プログラミング言語を作ろう(合作ではないです)

MusicWriter、結局解析も記述も両方面倒な構文だったので原点0に戻ってやり直すことにしました。
言語名はNoteScriptに変更することにしました。
とりあえずおおまかな説明は書いたのでもしよければ見ていってください。
yoshikunTA
Scratcher
100+ posts

プログラミング言語を作ろう(合作ではないです)

最近フォーラム使ってない(見てはいる)
Orangeに図形表示を実装させる
Orangeに図形を表示させるプログラムを実装させます。
図形名
四角形 : square
円 : circle
棒 : stick
show
showを使って指定した図形を表示させます。
show(class) {
(図形名),(x座標1),(y座標1),(x座標2),(y座標2)
}
classは設定なしでもokです。
show-animation
showを使って表示させたものをアニメーションさせます。
show-animation(アニメーション方法),(class),(図形名),(x座標1),(y座標1),(x座標2),(y座標2),(速さ%)
classは図形名が設定されていれば設定されてなくてもokです。
図形名もclassと同じくclassが設定されていれば設定されてなくてもokです。
アニメーション方法
シンプル(defalt) : シンプルに移動します((((語彙力
減速(slow-down) : 減速しながら移動します。
バウンス(bounce) : バウンスしながら移動します。
rinasama_tabasi
Scratcher
100+ posts

プログラミング言語を作ろう(合作ではないです)

いまこれ(https://www.sigbus.info/compilerbook#)をしていて
だいぶ理解が深まってきたので、
少しばかり、プロジェクトを作っています
akinarin
Scratcher
500+ posts

プログラミング言語を作ろう(合作ではないです)

#847
whileや関数があるとかなり実用性が上がりますね。
やはり言語に統一感があるのは良いですね。

#848
新しい文法は解析しやすそうな形で良いですね。
汎用言語のような特徴があって、拡張性が高そうです。

#849
読みやすそうです。
ドメイン固有言語(特定の用途の為に作られた言語)として申し分ないと思います。

#850
機能が多くないScratchでは、存分に低レイヤの知識が活かせますね。
頑張って下さい。

最近、受験勉強に忙しくてここにはあまり顔を出せていませんが、
皆さん頑張っているようで何よりです。
僕は暇な時に言語案を考えていて、やはりToshを生成するよりも機械語モドキのインタプリタをScratchで実装した方が楽かな……なんて考えているところです。
また受験が終われば(1年数ヶ月後に終わる予定です)Scratchでの言語製作に再度取り組みたいので、それまでは言語案を温めておこうと思います。
受験が終わったら開発を再開して、1年くらい前に作った(月日が経つのが早い)Pumpkinの遅さの原因を再度分析して、それの改善方法を探ろうと思います。

また息抜きの為に、フォーラムに来るかも知れません
pupon
Scratcher
100+ posts

プログラミング言語を作ろう(合作ではないです)

最近全くやってなかったtoEndですが、
ASTに変換してから実行するという方式にしようと思います。
理由は、Csmのように構文解析と実行を同時並行でやっていると、
同じ文を複数回構文解析する必要があって(ループ・関数など)、速度が遅くなると思ったからです。

Last edited by pupon (Oct. 21, 2023 02:59:36)

pupon
Scratcher
100+ posts

プログラミング言語を作ろう(合作ではないです)

ASTに変換してから実行するということの練習に、+と*とかっこしかない計算機を作ってみました
https://scratch-mit-edu.ezproxyberklee.flo.org/projects/911496234/
pupon
Scratcher
100+ posts

プログラミング言語を作ろう(合作ではないです)

改 toEndのキャストについて
キャストの方法の一つとして、コンストラクタを使用する方法を紹介しましたが、その方法はやめて、
キャスト用のメソッド
@cast String{
    ...
}
のみにしようと思います。また、その時に
[Int]hoge = 3
hoge.String()
のように普通のメンバと同じ呼び出し方は不可能にして、
(String)hoge
の文法を用いるようにします。

あと、Swiftのextensionみたいな機能もつけたいと思ってます。
ーーーーーーーーーーーーーーーーーーーーーーーーー
ちなみに
toEnd v0.1の途中経過です↓

Last edited by pupon (Nov. 5, 2023 21:34:06)

rinasama_tabasi
Scratcher
100+ posts

プログラミング言語を作ろう(合作ではないです)

新しい言語
mozi script
プログラミング言語のテスト用にテキトーに作った言語です
mozi Script
構文としては

(
文字
{
(x|y|size|penSize|color|L/C/R)

}
)
colorの場合の値は#〇〇〇〇〇〇の形
L/C/Rは左/中央/右
これを繰り返し表示していきます。

いずれチューリング完全にしたいです。
pupon
Scratcher
100+ posts

プログラミング言語を作ろう(合作ではないです)

toEnd v0.1(今はv0.2)!!!
toEnd v0.1を共有しました。(フォーラムが使えなかったので投稿遅れました)

<言語仕様>
(詳しい仕様: https://scratch-mit-edu.ezproxyberklee.flo.org/projects/874494382/ )
コメントは//でできます。複数行のコメントはできません。

型はInt, Float, String, Boolの4つがあります。
文字列は“”で囲みます。

変数は
[Int]a
のように定義します。

制御構文はif文とwhile文が(do-whileも)あり、ブロックの中の文が1文の場合は{}を省略できます。
また、条件に()はいりません。
最後にサンプルコード
//FizzBuzz
[Int]count = 1
while count < 20 {
if count%15 == 0 println("FizzBuzz")
else if count%3 == 0 println("Fizz")
else if count%5 == 0 println("Buzz")
else println(count)
count = count + 1
}

Last edited by pupon (Jan. 15, 2024 10:01:04)

honnkon
Scratcher
62 posts

プログラミング言語を作ろう(合作ではないです)

ちょっと宣伝っぽいですが

Brainf*ckのインタープリンタをちょっと前に作りました
https://scratch-mit-edu.ezproxyberklee.flo.org/projects/945473537/

HQ9+のインタープリンタをちょっと前に作りました
https://scratch-mit-edu.ezproxyberklee.flo.org/projects/945470350/

(署名にもありますが)
pupon
Scratcher
100+ posts

プログラミング言語を作ろう(合作ではないです)

toEnd v0.3!!
toEndをv0.3にアップデートしました!

◯v0.3の変更点
ローカル変数(スタック変数)の実装
・メモリ確保やdo-while文のバグ修正

ローカル変数は関数の場合も想定済みなので、v0.4ぐらいで関数が実装されると思います。
pupon
Scratcher
100+ posts

プログラミング言語を作ろう(合作ではないです)

削除

Last edited by pupon (Feb. 4, 2024 04:58:56)

pupon
Scratcher
100+ posts

プログラミング言語を作ろう(合作ではないです)

toEndの今考えている文法や実装方法
import
ASTを書き換える(ASTの末尾に追加して、importした瞬間にそこだけ先に実行)

スタックや変数の型は型専用メモリに保存
[Array[Int]] a
[String] b
型専用メモリ
Int
Array
1
String
変数一覧
a: 2
b: 4

配列、タプル、辞書
配列 #[1, 2, 3] //Array[Int]
タプル #(1, "a", true) //Tuple[Int, String, Bool]
辞書 #{1: "a", 2: "b"} //Dict[Int, String]

値型の実装
配列は値型にする。
最初はただのコピーで実装する予定だが、Copy On Write になるかも
(つまり参照カウント? Partial Mark and Sweep?)

無名関数
第一級関数なので、引数や返り値に使用できる。
無名関数は
{(引数リスト): 返り値の型 -> 処理}
のように定義する。
返り値がない場合は
{(引数リスト) -> 処理}
となる。
処理の中にreturnがないときは、一番最後の式の評価結果を返す。
(型推論が可能な時)引数や返り値の型を省略することもできる。
返り値を省略すると、:がいらなくなる。
引数の型を省略できるときは、()を省略できる。
また、引数リストや->も省略して\0、\1のように引数を取得することもできる。
簡潔に言うと、ほぼSwift(若干違うので注意)
(例)
{([Int] a): Int ->
return a*a
}
↓ 返り値の型とreturnを省略
{([Int] a) -> a*a}
↓ 引数の型と()を省略
{a -> a*a} //このときaの型は「*」が宣言されている一番抽象的な型。
↓ 引数名と->も省略
{\0*\0}

記号
?:は三項演算子、;は文の区切りに使用する。
;は改行すれば省略できる。

データ型
クラス、構造体、代数的データ型は、全てインタフェースを実装できる。

◯インタフェース
interface 名前: 親インタフェース {
func メソッド(引数): 返り値の型
func メソッド(引数): 返り値の型
...
}
インタフェースを実装する時のみ、親を複数にすることができる(その場合は「,」で区切る)。
インタフェースは変数の型として使用することができる。キャストもできる。
//モナドの定義
interface Monad[T]: Applicative {
static func >>=([Monad[T]] x, Func[T, Monad[U]] f): Monad[U]
}

◯クラス
class 名前: 継承元 {
[Int] a //メンバ変数
const(self, [Int] a) { //コンストラクタ
self.a = a
}
func メソッド名(self) { //メソッド
...
}
static func メソッド名 { //静的メソッド
...
}
}
参照型で、クラスとインタフェースを継承することができる。
メソッドはpythonのように第1引数がself。
コンストラクタはfuncや返り値が省略できる。
型がスーパークラスの変数には、そのまま入れられる。

◯構造体
クラスとほとんど一緒。
struct 型: インタフェース {

}
相違点
  • 継承ができない(インタフェースの実装は可)
  • 値型

◯代数的データ型(Swiftのenum風)
値型なので、構造体と同じく継承はできない。
data 型: インタフェース {
コンストラクタ1(付属の型)
コンストラクタ2(付属の型)
...
}
data Maybe[T]: Monad {
$just(T)
$nothing

static ope >>=[U]([Maybe[T]] x, [Func[T, Maybe[U]] f): Maybe[U] {
switch x {
case Maybe.just([T] a):
return f(a)
case Maybe.nothing:
return Maybe.nothing
}
}
}

[Maybe[Int]] foo = nothing
[Maybe[Int]] bar = (foo >>= {just(\0*2)})

//演算子オーバーロードはデータ型のstaticメソッドで定義するので、左と右で型が違う演算子は定義できない。
//演算子には一部の記号が使用できる

追記
ジェネリクスをType型のメンバのようにすれば型に付属するIntとかも作れそう(?)
つまり
[Array[Int,3]] a = [1, 2, 3]
a = [3, 4, 5]
a = [6, 7] //エラー
みたいなことができそうってことです。
この仕組みの呼び方などはありますか?
また、こういうことができるプログラミング言語ってありますか?

長文失礼しました。

Last edited by pupon (Oct. 11, 2024 09:17:30)

Powered by DjangoBB