Saya membuat program yang memuat cfg dari file dan menggunakannya untuk memuat bahasa pemrograman ke dalam pohon sintaks.

Apa cara yang tepat untuk mendefinisikan pengidentifikasi dalam tata bahasa bebas konteks. Untuk saat ini, saya memiliki format seperti ini:

IdentifierStart => $l$ | _; 
IdentifierChar => "$l$$IdentifierChar$" | "_$IdentifierChar$" | "$i$$IdentifierChar$" | $e$;
Identifier => "$IdentifierStart$$IdentifierChar$" $w$; 

Format:

$l$ = any letter 
$e$ = epsilon
$i$ = any integer
$o$ = any operator
$n$ = new line
$w$ = whitespace
$a$ = any atom
Quotes mean the whitespace needs to match the inside of the quotes

Meskipun ini berhasil, ini tidak efisien karena menciptakan pohon yang dalam ketika setiap huruf dapat dibenarkan hanya dicantumkan di samping satu sama lain. Sebagai contoh, Pragma => $n$ "#direct" $w$ $String$; dengan aturan:

IdentifierStart => $l$ | _;
IdentifierChar => "$l$$IdentifierChar$" | "_$IdentifierChar$" | "$i$$IdentifierChar$" | $e$;
Identifier => "$IdentifierStart$$IdentifierChar$";

Symbol => $l$ | $i$ | $o$ | \$$Identifier$\$;
Def => $Symbol$ $Def$ | $Symbol$ | "Def";
Assignment => $Def$ \| $Assignment$ | $Def$;
Definition => $Identifier$ "=>" $Assignment$\;;

Membuat pohon berikut (di mana setiap ruang mewakili tingkat di pohon):

Definition:Pragma => $n$ "#pragma" $w$ $String$;
  Identifier:Pragma
   IdentifierStart:P
    Terminal:P
   IdentifierChar:ragma
    Terminal:r
    IdentifierChar:agma
     Terminal:a
     IdentifierChar:gma
      Terminal:g
      IdentifierChar:ma
       Terminal:m
       IdentifierChar:a
        Terminal:a
  Terminal:=
  Terminal:>
  Assignment:$n$ "#direct" $w$ $String$
...

Meskipun ini baik-baik saja dalam hal pengidentifikasi, saya perhatikan ada masalah ketika saya menyadari bahwa saya harus mendefinisikan format file dengan cara rekursif yang sama:

File => $ValidDirective$ $File$;
ValidDirective => $Comment$ | $Include$ | $Define$ | $Undef$ | $IfPart$ | $Error$ | $Pragma$ | $String$; 

Setiap elemen file akan disimpan dalam sub-pohon dari elemen sebelumnya! Saya tidak berpikir ini dapat diterima karena dalam program dengan jutaan baris, itu akan sangat tidak efisien.

Apakah ada cara saya dapat memperbaiki masalah ini sambil tetap setia pada konvensi CFG?

0
gozaimo 11 April 2020, 23:55

1 menjawab

Jawaban Terbaik

CFG sejati memang mendefinisikan pengulangan melalui rekursi, yang mengarah ke pohon parse bersarang yang Anda amati.

Bahasa pemrograman biasanya akan menggunakan ekspresi reguler (atau yang serupa) untuk mendefinisikan sintaks simbol seperti pengidentifikasi. Dalam hal ini, menguraikan pengidentifikasi akan menghasilkan satu token, bukan pohon, yang mungkin menjawab kekhawatiran Anda tentang inefisiensi.

Namun, pendekatan itu tidak berlaku untuk konstruksi berulang tingkat yang lebih tinggi, mis. a StatementList atau ArgumentList: untuk itu, ekspresi reguler tidak cukup, dan Anda memerlukan sesuatu yang setidaknya 'kuat' seperti CFG. Tidak jelas apakah menurut Anda menyimpan StatementList atau ArgumentList sebagai pohon bersarang dalam tidak efisien.

Jika Anda diwajibkan untuk menggunakan CFG yang sebenarnya, dan Anda tidak memiliki kendali atas struktur data yang dibuat selama proses penguraian, Anda dapat menjalankan proses pasca yang mengubah struktur rekursif menjadi struktur non-rekursif, tetapi Anda mungkin menemukan bahwa keuntungan efisiensi tidak terlalu banyak.

Namun, sebagian besar tata bahasa bahasa pemrograman tidak membatasi diri pada CFG murni.

1
Michael Dyck 12 April 2020, 16:11