UCFS

UCFS

• Tentang
• Penggunaan
  • Dari sumber
  • Menggunakan stoples
  • Contoh Format CFG
  • Contoh Format RSM
• Pertunjukan
  • Grafik
  • Tata bahasa
  • Hasil
  • Lebih banyak hasil

Catatan: Proyek di bawah Pengembangan Besar!

Tentang

UCFS adalah u nuversal c ontext- f ree s olver: alat untuk memecahkan masalah yang terkait dengan persimpangan bahasa bebas konteks dan reguler. Contoh masalah seperti itu:

• Penguraian
• Querying jalur bebas konteks (CFPQ)
• Context-Free Language Reachability (CFL-R)

Penggunaan

Antarmuka baris perintah

 Usage: kotgll options_list
Options: 
    --input -> Input format (always required) { Value should be one of [string, graph] }
    --grammar -> Grammar format (always required) { Value should be one of [cfg, rsm] }
    --sppf [ON] -> Sppf mode { Value should be one of [on, off] }
    --inputPath -> Path to input txt file (always required) { String }
    --grammarPath -> Path to grammar txt file (always required) { String }
    --outputPath -> Path to output txt file (always required) { String }
    --help, -h -> Usage info

Dari sumber

Langkah 1. Klon Repositori

git clone https://github.com/FormalLanguageConstrainedPathQuerying/kotgll.git

atau

git clone [email protected]:FormalLanguageConstrainedPathQuerying/kotgll.git

atau

gh repo clone FormalLanguageConstrainedPathQuerying/kotgll

Langkah 2. Pergi ke folder

cd kotgll

Langkah 3. Jalankan perintah bantuan

gradle run --args="--help"

Anda akan melihat pesan "Daftar Opsi".

Contoh

 gradle run --args="--input graph --grammar rsm --sppf off --inputPath src/test/resources/cli/TestGraphReadWriteCSV/dyck.csv --grammarPath src/test/resources/cli/TestRSMReadWriteTXT/dyck.txt --outputPath ./result.txt"

Menggunakan stoples

Langkah 1. Unduh toples terbaru

 curl -L -O https://github.com/FormalLanguageConstrainedPathQuerying/kotgll/releases/download/v1.0.0/kotgll-1.0.0.jar

Langkah 2. Jalankan Jar dengan Java

 java -jar kotgll-1.0.0.jar --input graph --grammar rsm --sppf off --inputPath src/test/resources/cli/TestGraphReadWriteCSV/dyck.csv --grammarPath src/test/resources/cli/TestRSMReadWriteTXT/dyck.txt --outputPath ./result.txt

Contoh Format CFG

 StartNonterminal("S")
Nonterminal("S") -> Terminal("subClassOf_r") Nonterminal("S") Terminal("subClassOf")
Nonterminal("S") -> Terminal("subClassOf_r") Terminal("subClassOf")
Nonterminal("S") -> Terminal("type_r") Nonterminal("S") Terminal("type")
Nonterminal("S") -> Terminal("type_r") Terminal("type")

Contoh Format RSM

 StartState(id=0,nonterminal=Nonterminal("S"),isStart=true,isFinal=false)
State(id=0,nonterminal=Nonterminal("S"),isStart=true,isFinal=false)
State(id=1,nonterminal=Nonterminal("S"),isStart=false,isFinal=false)
State(id=4,nonterminal=Nonterminal("S"),isStart=false,isFinal=false)
State(id=3,nonterminal=Nonterminal("S"),isStart=false,isFinal=true)
State(id=2,nonterminal=Nonterminal("S"),isStart=false,isFinal=false)
State(id=6,nonterminal=Nonterminal("S"),isStart=false,isFinal=true)
State(id=5,nonterminal=Nonterminal("S"),isStart=false,isFinal=false)
TerminalEdge(tail=0,head=1,terminal=Terminal("subClassOf_r"))
TerminalEdge(tail=0,head=4,terminal=Terminal("type_r"))
TerminalEdge(tail=1,head=3,terminal=Terminal("subClassOf"))
NonterminalEdge(tail=1,head=2,nonterminal=Nonterminal("S"))
TerminalEdge(tail=4,head=6,terminal=Terminal("type"))
NonterminalEdge(tail=4,head=5,nonterminal=Nonterminal("S"))
TerminalEdge(tail=2,head=3,terminal=Terminal("subClassOf"))
TerminalEdge(tail=5,head=6,terminal=Terminal("type"))

Pertunjukan

Algoritma GLL telah dimodifikasi untuk mendukung input grafik. Modifikasi yang diusulkan telah dievaluasi pada beberapa grafik nyata untuk skenario menemukan semua pasangan jangkauan.

Konfigurasi Mesin : PC dengan Ubuntu 20.04, Intel Core i7-6700 3.40GHz CPU, DDR4 64GB RAM.

Konfigurasi lingkungan :

• Java Hotspot (TM) 64-Bit Server Virtual Machine (Build 15.0.2+7-27, Mode Campuran, Berbagi).
• Konfigurasi Heap JVM: 55GB Baik XMS dan XMX.

Grafik

Data grafik dipilih dari dataset CFPQ_DATA.

Deskripsi terperinci dari grafik terdaftar di bawah.

Grafik analisis RDF

Nama Grafik	| V |	| E |	#subclassof	#jenis	#BroaderTransitif
Enzim	48 815	86 543	8 163	14 989	8 156
Eclass	239 111	360 248	90 962	72 517	0
Pergi hierarki	45 007	490 109	490 109	0	0
Pergi	582 929	1 437 437	94 514	226 481	0
Geospesies	450 609	2 201 532	0	89 065	20 867
Taksonomi	5 728 398	14 922 125	2 112 637	2 508 635	0

Tata bahasa

Semua pertanyaan yang digunakan dalam evaluasi adalah varian dari kueri generasi yang sama. Kebalikan dari hubungan x dan tepi masing -masing dilambangkan sebagai x_r .

Tata bahasa yang digunakan untuk grafik RDF :

G ₁

 S -> subClassOf_r S subClassOf | subClassOf_r subClassOf 
     | type_r S type | type_r type

Representasi tata bahasa bebas konteks G ₁ dalam repositori dapat ditemukan di sini.

Representasi tata bahasa bebas konteks G ₁ sebagai otomat rekursif dalam repositori dapat ditemukan di sini.

Hasil

Hasil evaluasi kueri jangkauan semua pasangan pada grafik yang terkait dengan analisis RDF tercantum di bawah ini.

Di setiap baris, waktu rata -rata terbaik dalam hitungan detik disorot dalam huruf tebal .

Grafik	CFG	RSM	Gll4Graph
Enzim	0.107	0,044	0.22
Eclass	0.94	0.43	1.5
Pergi hierarki	4.1	3.0	3.6
Pergi	3.2	1.86	5.55
Geospesies	0.97	0.34	2.89
Taksonomi	31.2	14.8	45.4

Lebih banyak hasil

Lebih banyak hasil, tetapi dalam bentuk mentah, dapat ditemukan di repositori Kotgll_benchmarks