Mengapa C ++ tidak dapat diuraikan dengan parser LR (1)?

Saya membaca tentang parser dan generator parser dan menemukan pernyataan ini di halaman parsing LR wikipedia:

Banyak bahasa pemrograman dapat diuraikan menggunakan beberapa variasi parser LR. Satu pengecualian penting adalah C ++.

Kenapa gitu? Apa properti khusus dari C ++ yang menyebabkannya tidak mungkin diurai dengan parser LR?

Menggunakan google, saya hanya menemukan bahwa C dapat diurai sempurna dengan LR (1) tetapi C ++ membutuhkan LR (∞).

Ada utas menarik tentang Lambda the Ultimate yang membahas tata bahasa LALR untuk C ++ .

Ini termasuk tautan ke tesis PhD yang mencakup diskusi tentang penguraian C ++, yang menyatakan bahwa:

"Tata bahasa C ++ bersifat ambigu, bergantung pada konteks dan berpotensi membutuhkan pencarian tak terbatas untuk menyelesaikan beberapa ambiguitas".

Selanjutnya memberikan sejumlah contoh (lihat halaman 147 dari pdf).

Contohnya adalah:

int(x), y, *const z;

berarti

int x;
int y;
int *const z;

Dibandingkan dengan:

int(x), y, new int;

berarti

(int(x)), (y), (new int));

(ekspresi yang dipisahkan koma).

Dua urutan token memiliki urutan awal yang sama tetapi pohon parse yang berbeda, yang tergantung pada elemen terakhir. Mungkin ada banyak token yang sewenang-wenang sebelum yang ambigu.

Parser LR tidak dapat menangani aturan tata bahasa yang ambigu, berdasarkan desain. (Membuat teori lebih mudah di tahun 1970-an ketika ide sedang dikerjakan).

C dan C ++ keduanya memungkinkan pernyataan berikut:

x * y ;

Ini memiliki dua parse yang berbeda:

1. Ini bisa berupa deklarasi y, sebagai pointer untuk mengetik x
2. Ini bisa berupa kelipatan x dan y, membuang jawabannya.

Sekarang, Anda mungkin berpikir yang terakhir itu bodoh dan harus diabaikan. Sebagian besar akan setuju dengan Anda; Namun, ada kasus-kasus di mana ia mungkin memiliki efek samping (misalnya, jika multiply kelebihan beban). tapi bukan itu intinya. Intinya adalah ada yang dua mem-parsing yang berbeda, dan karena itu program dapat berarti hal yang berbeda tergantung pada bagaimana ini harus telah dipecah.

Kompiler harus menerima yang sesuai dalam keadaan yang sesuai, dan jika tidak ada informasi lain (misalnya, pengetahuan tentang tipe x) harus mengumpulkan keduanya untuk memutuskan nanti apa yang harus dilakukan. Jadi tata bahasa harus memungkinkan ini. Dan itu membuat tata bahasa ambigu.

Jadi parsing LR murni tidak bisa menangani ini. Juga tidak banyak generator parser lain yang tersedia secara luas, seperti Antlr, JavaCC, YACC, atau Bison tradisional, atau bahkan parser gaya PEG, yang digunakan dengan cara "murni".

Ada banyak kasus yang lebih rumit (sintaks templat parsing memerlukan tampilan acak, sedangkan LALR (k) dapat melihat ke depan di sebagian besar token k), tetapi hanya dibutuhkan satu sampel balik untuk menembak parsing LR murni (atau yang lain).

Kebanyakan parser C / C ++ nyata menangani contoh ini dengan menggunakan beberapa jenis parser deterministik dengan hack tambahan: mereka parsing terjalin dengan koleksi tabel simbol ... sehingga pada saat "x" ditemui, parser tahu jika x adalah tipe atau tidak, dan dengan demikian dapat memilih antara dua parse potensial. Tetapi parser yang melakukan ini tidak bebas konteks, dan parser LR (yang murni, dll.) Bebas konteks.

Satu dapat menipu, dan menambahkan pemeriksaan semantik waktu pengurangan aturan untuk parser LR untuk melakukan disambiguasi ini. (Kode ini seringkali tidak sederhana). Sebagian besar tipe parser lain memiliki beberapa cara untuk menambahkan pemeriksaan semantik di berbagai titik di parsing, yang dapat digunakan untuk melakukan ini.

Dan jika Anda cukup curang, Anda dapat membuat parser LR bekerja untuk C dan C ++. Orang-orang GCC melakukannya untuk sementara waktu, tetapi menyerahkannya untuk parsing kode tangan, saya pikir karena mereka menginginkan diagnostik kesalahan yang lebih baik.

Ada pendekatan lain, yang bagus dan bersih dan mem-parsing C dan C ++ dengan baik tanpa peretasan tabel simbol: parser GLR . Ini adalah parser bebas konteks penuh (memiliki lookahead efektif tak terbatas). Pengurai GLR hanya menerima kedua pengurai, menghasilkan "pohon" (sebenarnya grafik asiklik terarah yang sebagian besar seperti pohon) yang mewakili penguraian ambigu. Sebuah pascarsing pas dapat menyelesaikan ambiguitas.

Kami menggunakan teknik ini di ujung depan C dan C ++ untuk Perangkat Lunak DMS Reengineering Tookit kami (per Juni 2017 ini menangani C ++ 17 penuh dalam dialek MS dan GNU). Mereka telah digunakan untuk memproses jutaan baris sistem C dan C ++ besar, dengan parse lengkap, presisi yang menghasilkan AST dengan rincian lengkap dari kode sumber. (Lihat AST untuk parse yang paling menjengkelkan C ++. )

Masalahnya tidak pernah didefinisikan seperti ini, padahal seharusnya menarik:

apa set modifikasi terkecil untuk tata bahasa C ++ yang diperlukan agar tata bahasa baru ini dapat diurai sempurna oleh parser yacc "non-konteks-gratis"? (hanya menggunakan satu 'retasan': disambiguasi ketik nama / pengidentifikasi, pengurai yang menginformasikan lexer dari setiap typedef / class / struct)

Saya melihat beberapa:

1. Type Type;terlarang. Identifier yang dideklarasikan sebagai typename tidak bisa menjadi non-typename identifier (note yang struct Type Typetidak ambigu dan masih bisa diizinkan).

   Ada 3 jenis names tokens:

   • types : tipe builtin atau karena typedef / class / struct
   • fungsi template
   • pengidentifikasi: fungsi / metode dan variabel / objek

   Mempertimbangkan fungsi templat sebagai token yang berbeda memecahkan func<ambiguitas. Jika funcnama fungsi templat, maka <harus menjadi awal dari daftar parameter templat, jika tidak, funcadalah penunjuk fungsi dan <operator pembanding.

2. Type a(2);adalah instantiasi objek. Type a();dan Type a(int)merupakan prototipe fungsi.

3. int (k); benar-benar dilarang, harus ditulis int k;

4. typedef int func_type(); dan typedef int (func_type)();dilarang.

   Fungsi typedef harus berupa function pointer typedef: typedef int (*func_ptr_type)();

5. rekursi templat terbatas pada 1024, jika tidak, maksimum yang ditingkatkan dapat diteruskan sebagai opsi ke kompiler.

6. int a,b,c[9],*d,(*f)(), (*g)()[9], h(char); bisa juga dilarang, diganti dengan int a,b,c[9],*d; int (*f)();

   int (*g)()[9];

   int h(char);

   satu baris per fungsi prototipe atau deklarasi fungsi pointer.

   Alternatif yang sangat disukai adalah mengubah sintaks pointer fungsi yang mengerikan,

   int (MyClass::*MethodPtr)(char*);

   disinkronisasi ulang sebagai:

   int (MyClass::*)(char*) MethodPtr;

   ini koheren dengan operator pemeran (int (MyClass::*)(char*))

7. typedef int type, *type_ptr; bisa juga dilarang: satu baris per typedef. Dengan demikian akan menjadi

   typedef int type;

   typedef int *type_ptr;

8. sizeof int, sizeof char, sizeof long longDan co. dapat dideklarasikan di setiap file sumber. Jadi, setiap file sumber yang menggunakan tipe ini intharus dimulai dengan

   #type int : signed_integer(4)

   dan unsigned_integer(4)akan dilarang di luar #type arahan itu, ini akan menjadi langkah besar ke dalam sizeof intambiguitas bodoh yang ada di begitu banyak header C ++

Kompiler yang mengimplementasikan C ++ yang disinkronisasi ulang akan, jika menemukan sumber C ++ yang menggunakan sintaks ambigu, memindahkan source.cppjuga ambiguous_syntaxfolder, dan akan secara otomatis membuat terjemahan yang tidak ambigu source.cppsebelum mengkompilasinya.

Silakan tambahkan sintaks C ++ ambigu Anda jika Anda tahu beberapa!

Seperti yang Anda lihat dalam jawaban saya di sini , C ++ berisi sintaksis yang tidak dapat diuraikan secara parser oleh parser LL atau LR karena tahap resolusi tipe (biasanya pasca parsing) mengubah urutan operasi , dan oleh karena itu bentuk dasar AST ( biasanya diharapkan disediakan oleh parse tahap pertama).

Saya pikir Anda cukup dekat dengan jawabannya.

LR (1) berarti penguraian dari kiri ke kanan hanya membutuhkan satu token untuk melihat-depan untuk konteks, sedangkan LR (∞) berarti pandangan ke depan yang tak terbatas. Artinya, parser harus mengetahui segala sesuatu yang datang untuk mengetahui di mana tempatnya sekarang.

Masalah "typedef" di C ++ dapat diuraikan dengan parser LALR (1) yang membuat tabel simbol saat parsing (bukan parser LALR murni). Masalah "templat" mungkin tidak dapat diselesaikan dengan metode ini. Keuntungan dari jenis LALR (1) parser ini adalah bahwa tata bahasa (ditunjukkan di bawah) adalah tata bahasa LALR (1) (tidak ada ambiguitas).

/* C Typedef Solution. */

/* Terminal Declarations. */

   <identifier> => lookup();  /* Symbol table lookup. */

/* Rules. */

   Goal        -> [Declaration]... <eof>               +> goal_

   Declaration -> Type... VarList ';'                  +> decl_
               -> typedef Type... TypeVarList ';'      +> typedecl_

   VarList     -> Var /','...     
   TypeVarList -> TypeVar /','...

   Var         -> [Ptr]... Identifier 
   TypeVar     -> [Ptr]... TypeIdentifier                               

   Identifier     -> <identifier>       +> identifier_(1)      
   TypeIdentifier -> <identifier>      =+> typedefidentifier_(1,{typedef})

// The above line will assign {typedef} to the <identifier>,  
// because {typedef} is the second argument of the action typeidentifier_(). 
// This handles the context-sensitive feature of the C++ language.

   Ptr          -> '*'                  +> ptr_

   Type         -> char                 +> type_(1)
                -> int                  +> type_(1)
                -> short                +> type_(1)
                -> unsigned             +> type_(1)
                -> {typedef}            +> type_(1)

/* End Of Grammar. */

Input berikut dapat diuraikan tanpa masalah:

 typedef int x;
 x * y;

 typedef unsigned int uint, *uintptr;
 uint    a, b, c;
 uintptr p, q, r;

The LRSTAR generator parser membaca notasi tata bahasa di atas dan menghasilkan parser yang menangani para "typedef" masalah tanpa ambiguitas dalam pohon parse atau AST. (Pengungkapan: Saya orang yang menciptakan LRSTAR.)