btyacc - Online di Cloud

PROGRAM:

NAMA

btyacc — dan LALR(1) generator parser dengan dukungan untuk backtracking

RINGKASAN

btyacc [-B awalan] [-DDNAMA ...] [-E] [-l] [-r] [-S x.ske] [-t] [-v]
nama file.y

Deskripsi Produk

btyacc adalah versi modifikasi dari byacc (Berkeley YACC), yang merupakan domain publik
versi generator parser AT&T YACC asli.

btyacc membaca spesifikasi tata bahasa dalam file nama file.y dan menghasilkan LR(1)
pengurai untuk itu. Parser terdiri dari satu set LALR(1) tabel parsing dan rutin driver
ditulis dalam bahasa pemrograman C. btyacc biasanya menulis tabel parse dan
driver rutin ke file awalan.tab.c, Di mana awalan default ke `y'.

Untuk penjelasan rinci tentang format spesifikasi tata bahasa, dan sangat baik
tutorial tentang cara menggunakan alat seperti YACC, lihat manual info untuk GNU banteng. btyac-
ekstensi khusus dijelaskan di bawah ini.

Catatan: Kerangka parser yang disediakan oleh penulis upstream btyacc hanya dikompilasi sebagai C++. Menggunakan
kerangka /usr/doc/btyacc/contoh/btyacc-c.ske untuk menghasilkan parser yang mengkompilasi keduanya
seperti C dan C++. (Sayangnya, kerangka alternatif ini saat ini tidak memeriksa malloc()
mengembalikan nilai.)

Opsi

-b awalan Ubah awalan yang diawali dengan nama file output ke string yang dilambangkan dengan
awalan. Awalan default adalah karakter `y'.

-d Buat file header bernama awalan.tab.h bersama dengan awalan.tab.c,
berisi definisi simbol dan deklarasi untuk YYSTYPE dan yylval.

-DNAMA Tentukan variabel preprocessor btyacc NAMA, untuk digunakan dengan %ifdef NAMA
arahan dalam file tata bahasa.

-E Mencetak tata bahasa yang telah diproses sebelumnya ke keluaran standar.

-l Jangan masukkan #garis arahan ke dalam kode parser yang dihasilkan.

-r Tulis kode parser dan tabel terkait ke file yang berbeda. Sedangkan
tabel dapat ditemukan di awalan.tab.c seperti sebelumnya, kode sekarang ditulis
untuk awalan.kode.c.

-S x.ske Pilih kerangka parser yang berbeda. Kerangka default tertanam dalam
program, tetapi salinannya dapat ditemukan di file btyacpa.ske.

-t Menyebabkan kode debug dikompilasi ke dalam parser yang dihasilkan.

-v Tulis deskripsi yang dapat dibaca manusia dari parser yang dihasilkan ke y.keluaran. Itu
termasuk status parser, tindakan untuk token pandangan ke depan, dan informasi tentang apa pun
konflik.

BYACC ekstensi

Mundur mendukung
Setiap kali parser yang dihasilkan btyacc mengalami kesalahan shift-reduce atau reduce-reduce di
tabel parse, ia mengingat titik parse saat ini (stack dan input stream state), dan pergi
ke mode parse percobaan. Kemudian melanjutkan penguraian, mengabaikan sebagian besar tindakan aturan. Jika berjalan
menjadi kesalahan (baik melalui tabel parse atau melalui panggilan tindakan YERROR), Itu
mundur ke titik konflik terbaru dan mencoba alternatif yang berbeda. Jika
menemukan jalur yang berhasil (mencapai akhir input atau panggilan tindakan YYVALID), Itu
mundur ke titik di mana ia pertama kali memasuki mode parse percobaan, dan berlanjut dengan penuh
parse (mengeksekusi semua tindakan), mengikuti jalur percobaan yang berhasil.

Tindakan di btyacc datang dalam dua rasa: {} tindakan, yang hanya dieksekusi ketika tidak dalam
mode percobaan, dan [] tindakan, yang dieksekusi terlepas dari mode.

Contoh: Dalam tata bahasa YACC untuk C, peretasan standar yang dikenal sebagai "retas umpan balik lexer" adalah
digunakan untuk menemukan nama typedef. Lexer menggunakan informasi semantik untuk memutuskan apakah ada yang diberikan
pengenal adalah nama typedef atau tidak dan mengembalikan token khusus. Dengan btyacc, Anda tidak
lagi perlu melakukan ini; lexer harus selalu mengembalikan pengidentifikasi. btyacc
tata bahasa kemudian membutuhkan aturan bentuk:

ketik nama: ID [ if (!IsTypeName(IdPencarian($1))) YYEROR; ]

Namun, perhatikan bahwa menambahkan aturan pelacakan mundur memperlambat pengurai. Dalam praktiknya, Anda
harus mencoba untuk membatasi jumlah konflik dalam tata bahasa pada apa yang mutlak
diperlukan. Pertimbangkan untuk menggunakan "retas umpan balik lexer" jika itu adalah solusi yang bersih, dan
cadangan mundur untuk beberapa kasus khusus.

btyacc menjalankan uji cobanya menggunakan aturan "coba geser dulu, lalu coba kurangi urutannya
bahwa aturan yang bertentangan muncul di file input". Ini berarti Anda dapat menerapkan
aturan disambiguasi semantik seperti, misalnya: (1) Jika terlihat seperti deklarasi,
jika tidak (2) Jika terlihat seperti ekspresi, jika tidak (3) itu adalah kesalahan sintaksis
[Ellis & Stroustrup, Manual Referensi C++ Beranotasi, p93]. Untuk mencapai ini, letakkan semua
aturan untuk deklarasi sebelum aturan untuk ekspresi dalam file tata bahasa.

Backtracking hanya dipicu ketika parse mencapai shift/reduce atau reduce/reduce
konflik di meja. Jika Anda tidak memiliki konflik dalam tata bahasa Anda, tidak ada biaya tambahan,
selain beberapa kode tambahan yang tidak akan pernah dipanggil.

Saat ini, parser yang dihasilkan berfungsi tidak pemangkasan jalur parsing alternatif. Menghindari
ledakan eksponensial dari kemungkinan jalur (dan waktu penguraian), Anda perlu memberi tahu secara manual
parser ketika dapat membuang jalur yang disimpan menggunakan YYVALID penyataan. Di dalam
praktek, ini ternyata cukup mudah dilakukan. Misalnya, pengurai C++ hanya dapat
mengandung [YYVALID;] setelah setiap pernyataan lengkap dan aturan pernyataan, menghasilkan
status mundur sedang dipangkas setelah melihat `;' atau `}' - tidak akan pernah ada
situasi di mana berguna untuk mundur melewati salah satu dari ini.

peningkatan token posisi penanganan
Kompiler sering perlu membangun AST (pohon sintaksis abstrak) sedemikian rupa sehingga setiap simpul di pohon
dapat berhubungan dengan sumber program yang diurai itu berasal. NS YYPOSN mekanisme yang didukung
oleh btyacc membantu Anda dalam mengotomatisasi perhitungan posisi teks dan dalam menetapkan
posisi teks yang dihitung ke node AST.

Dalam YACC standar, setiap token dan setiap non-terminal memiliki YYSTYPE nilai semantik
melekat padanya. Dengan btyacc, setiap token dan setiap non-terminal juga memiliki YYPOSN teks
posisi yang melekat padanya. YYPOSN adalah tipe yang ditentukan pengguna.

btyacc mempertahankan tumpukan nilai posisi teks dengan cara yang sama seperti mempertahankan tumpukan
dari nilai-nilai semantik. Untuk memanfaatkan fitur posisi teks, Anda perlu #menetapkan itu
sebagai berikut:

Simbol Preprocessor YYPOSN untuk tipe C/C++ dari posisi teks yang dilampirkan ke setiap
token dan non-terminal.

yyposn Variabel global tipe YYPOSN. Lexer harus menetapkan posisi teks dari
mengembalikan token ke yyposn, seperti halnya memberikan nilai semantik dari
mengembalikan token ke yylval.

YYREDUCEPOSNFUNC
Simbol praprosesor untuk fungsi yang dipanggil segera setelah reguler
pengurangan aturan tata bahasa telah dilakukan, untuk mengurangi posisi teks yang terletak di
tumpukan.

Biasanya, fungsi ini mengekstrak posisi teks dari aturan sisi kanan
komponen dan menugaskannya ke struktur/pohon $$ yang dikembalikan atau, jika tidak
Nilai $$ dikembalikan, menempatkannya ke posisi teks ret di mana ia akan berada
diambil oleh aturan lain nanti. Prototipenya adalah:

membatalkan KurangiPosn(
YYPOSN& penolakan,
YYPOSN* istilah_posns,
TIPE* term_vals,
int istilah_tidak,
int stk_pos,
int yychar,
YYPOSN& kamu,
Tipe Pengguna tambahan);

ret Referensi ke posisi teks yang dikembalikan oleh aturan. Anda harus menimpa
ini dengan posisi teks yang dihitung yang dihasilkan aturan, analog dengan
nilai semantik $$.

istilah_posns
Array komponen aturan sisi kanan ' YYPOSN posisi teks,
analog dengan $1, $2, ..., $N untuk nilai semantik.

term_vals Array komponen aturan sisi kanan' YYSTYPE nilai-nilai. Ini adalah
$1, ..., $N itu sendiri.

term_no Jumlah komponen di sisi kanan dari aturan yang direduksi, yaitu
ukuran array term_posns dan term_vals. Juga sama dengan N dalam $1, ...,
$N.

stk_pos YYSTYPE/YYPOSN posisi tumpukan sebelum reduksi.

yychar Lookahead token yang segera mengikuti sisi kanan yang dikurangi
komponen.

kamu YYPOSN dari token yang segera mengikuti sisi kanan yang dikurangi
komponen.

ekstra argumen ekstra yang ditentukan pengguna diteruskan ke ReducePosn.

YYREDUCEPOSNFUNCARG
Argumen tambahan diteruskan ke fungsi ReducePosn. Argumen ini bisa apa saja
variabel yang didefinisikan dalam btyacpa.ske.

Token dealokasi selama kesalahan pemulihan
Untuk sebagian besar generator parser mirip YACC, aksi parser yang dihasilkan saat bertemu
kesalahan parse adalah membuang nilai semantik dan token input hingga aturan yang berisi
non-terminal khusus kesalahan dapat dicocokkan. Pembuangan token hanya dilakukan oleh
menimpa variabel dan entri array tipe YYSTYPE dengan nilai-nilai baru.

Sayangnya, pendekatan ini menyebabkan kebocoran memori jika YYSTYPE adalah tipe penunjuk. btyacc
memungkinkan Anda untuk menyediakan fungsi untuk membersihkan nilai posisi semantik dan teks, dengan
#menetapkaning simbol berikut dalam pembukaan file tata bahasa Anda:

YYDELETEVAL
Simbol praprosesor untuk fungsi yang dipanggil sebelum nilai semantik token
atau non-terminal dibuang.

YYDELETEPOSN
Simbol praprosesor untuk fungsi yang dipanggil sebelum posisi teks token
atau non-terminal dibuang.

Kedua fungsi dipanggil dengan dua argumen. Argumen pertama dari tipe YYSTYPE or YYPOSN
adalah nilai yang akan dibuang. Argumen kedua bertipe int dan merupakan salah satu dari
tiga nilai:

0 membuang token input

1 status pembuangan di tumpukan

2 membersihkan tumpukan saat membatalkan

Terperinci sintaksis kesalahan pelaporan
Jika kamu #menetapkan variabel praprosesor YYERROR_DETAILED dalam file tata bahasa Anda, Anda harus
juga tentukan fungsi pemrosesan kesalahan berikut:

membatalkan yyerror_detailed(
arang* teks,
int salah,
TIPE &
nilai_errt,
YYPOSN& errt_posn);

pesan kesalahan teks

kode errt dari token yang menyebabkan kesalahan

nilai_errt
nilai token yang menyebabkan kesalahan

errt_posn teks posisi token yang menyebabkan kesalahan

Preprosesor arahan
btyacc mendukung pendefinisian simbol dan bertindak pada mereka dengan arahan bersyarat di dalam
file tata bahasa, tidak seperti preprosesor C.

%mendefinisikan NAMA
Tentukan simbol praprosesor NAMA. Setara dengan saklar baris perintah
-DNAMA.

%ifdef NAMA
Jika variabel praprosesor NAMA didefinisikan, proses teks dari ini %ifdef untuk
penutupan %berakhir jika, jika tidak lewati.

%endif Arahan penutupan untuk %ifdef. %ifdefs tidak dapat disarangkan.

%termasuk NAMA FILE
Proses isi file bernama NAMA FILE. Hanya satu tingkat bersarang %termasuk
Diperbolehkan.

%ident STRING
Sisipkan `#ident STRING' ke dalam file output. STRING harus a
konstanta string terlampir dalam "".

Warisan atribut
Atribut yang diwariskan tidak didokumentasikan. (Lihat README dan kode sumber btyacc untuk a
sedikit informasi.) Jika Anda mengetahui cara kerjanya, hubungi saya di[email dilindungi]>!

Bug

Kompleksitas parsing kasus terburuk adalah eksponensial untuk tata bahasa apa pun yang memungkinkan
mundur terjadi. Dengan kata lain, parser yang dihasilkan btyacc merupakan a
bug penolakan layanan jika digunakan dalam aplikasi di mana penyerang dapat memasok
data yang dibuat khusus sebagai input ke parser. (Untuk semua data input "biasa",
kompleksitas yang berpotensi eksponensial biasanya tidak menjadi masalah.)

bison %mengharapkan direktif tidak didukung.

Tidak ada %lain dan %ifndef. %ifdefs dan %termasuks tidak dapat disarangkan.

penulis

Robert Corbett[email dilindungi]> /[email dilindungi]> adalah salah satunya
penulis asli Berkeley byacc. Chris Dodd[email dilindungi]> memiliki yang brilian
ide untuk menambahkan kemampuan backtracking, dan bertanggung jawab untuk backtracking awal
perubahan. Vadim Maslov[email dilindungi]> lebih meningkatkan kode.

Dokumentasi ini ditulis oleh Richard Atterer[email dilindungi]> untuk Debian
Distribusi GNU/Linux, tetapi disumbangkan ke domain publik dan dengan demikian dapat digunakan secara bebas
untuk tujuan apapun.

File

/usr/doc/btyacc/contoh/btyaccpa.ske

/usr/doc/btyacc/contoh/btyacc-c.ske

/usr/doc/btyacc/README

Lihat juga

banteng(1) (atau `info bison'), byac(1), yacc(1), semut(1)

btyacc(1)

Gunakan btyacc online menggunakan layanan onworks.net