Logika -kalkulus memiliki representasi sintaksis abstrak yang bersifat siklik. μ
Pål GD
Jawaban:
14
Output parser tidak harus berupa pohon. Memang, ketika Anda mempertimbangkan hal-hal seperti referensi dari USE dari variabel ke DEFinition-nya yang dilapiskan pada pohon sintaksis abstrak, Anda langsung memiliki grafik.
Masalahnya adalah bahwa parsing umumnya dirancang untuk dilakukan dalam satu lintasan - ini penting karena alasan historis, seperti kurangnya ruang dan kecepatan prosesor, tetapi juga karena lebih mudah untuk dipikirkan. Kemudian fase selanjutnya menghias pohon parse dengan informasi tambahan.
Ada beberapa hal seperti tata bahasa grafik, meskipun saya tidak tahu apakah mereka digunakan untuk parsing bahasa pemrograman.
Sangat dimungkinkan untuk menampilkan struktur grafik, seperti pohon sintaksis yang dihiasi dengan tautan Definisi-Penggunaan, dalam satu lintasan. Banyak kompiler melakukannya pada tahun enam puluhan.
babou
4
Pertanyaan OP agak mundur. Tentu saja, algoritma penguraian dapat menampilkan apa pun yang diinginkan. Pertanyaannya adalah lebih untuk memahami untuk apa parsing dan apakah parser menghasilkan hasil yang memenuhi tujuan ini. Maka orang dapat bertanya-tanya apa representasi yang tepat untuk itu, misalnya pohon atau grafik.
Yah, saya kira parser adalah algoritma yang akan memberi Anda struktur sintaksis kalimat yang diberikan sebagai input, menurut definisi formal yang diberikan dari sintaks bahasa.
Perhatikan bahwa orang mungkin tidak setuju tentang apa yang merupakan sintaksis bahasa. Beberapa mungkin membatasi itu ke tulang punggung bahasa formal murni, sementara yang lain mungkin memperkenalkan pertimbangan yang sedikit lebih semantik seperti jenis, genre, jumlah atau yang lebih kompleks lainnya (saya tidak membedakan NLP atau bahasa pemrograman). Sebagian besar bahasa memiliki fitur yang memerlukan grafik untuk diwakili, tetapi terserah "implementor" (karena tidak ada kata yang lebih baik) untuk memutuskan apakah ia ingin memasukkan itu dalam sintaksis.
Jadi tergantung pada apa yang Anda definisikan menjadi sintaksis, Anda mungkin harus menampilkan jenis struktur formal yang berbeda.
Dalam kasus sederhana penguraian Bebas Konteks, pohon parse dapat dilakukan, kecuali untuk masalah ambiguitas yang dibahas di bawah ini, atau untuk fakta bahwa Anda mungkin ingin sedikit memodifikasinya untuk mendapatkan AST (lihat di bawah).
Namun, dalam kasus yang lebih kompleks, Anda mungkin memerlukan struktur yang berbeda, sering diwakili oleh tautan di pohon, sehingga mengarah ke struktur grafik. Ini sangat tergantung pada definisi Anda tentang sintaks bahasa.
Juga, pohon apa yang Anda harus hasilkan tidak jelas. Jika Anda mengambil kasus tata bahasa yang berdekatan (TAG), mereka bekerja sedemikian rupa sehingga pohon sintaksis tidak sama dengan pohon derivasi, meskipun yang pertama dapat diturunkan dari yang terakhir. Yang ingin Anda sampaikan mungkin merupakan pertanyaan yang relevan.
Ada juga masalah lain tentang ambiguitas. Sebuah kalimat yang diberikan, meskipun termasuk bahasa Anda, dapat melakukannya dalam banyak cara berbeda, dapat diberikan struktur sintaksis dalam berbagai cara.
Kemudian Anda dapat memilih untuk menampilkan hanya satu dari struktur ini, yang dipilih secara acak atau sesuai dengan kriteria yang didefinisikan dengan baik (seperti misalnya misalnya). Anda juga dapat memilih untuk menampilkan beberapa atau semuanya. Jika Anda ingin menghasilkan beberapa, biasanya nyaman untuk dikemas kemudian dalam struktur unik yang akan berbagi apa yang mereka miliki bersama. Ini menghemat ruang dan waktu komputasi, dan kompleksitas mungkin merupakan masalah nyata.
Saat Anda memilih untuk menampilkan semuanya, Anda tidak punya pilihan selain berbagi, karena mungkin ada jumlah parse yang tak terbatas. Dan tanpa batas dapat diwakili secara terbatas hanya dengan memiliki suatu siklus dalam suatu grafik. Jadi, Anda harus menghasilkan struktur grafik secara umum. Tetapi sifat-sifat struktur grafik ini berkaitan dengan jenis sintaksis formal yang telah Anda pilih.
Tentang Pohon Sintaksis Abstrak
Sekarang pertanyaannya juga tentang Pohon Sintaks Abstrak. Saya melewatkan bagian "abstrak" karena itu akan membawa kebingungan, imho. Memang pertanyaannya sudah membingungkan dalam berbagai penyajiannya.
Mengenai AST dalam perspektif historis, mereka berasal dengan bahasa Lisp dan sistem manipulasi program pada tahun 1960-1970. Idenya adalah untuk mempertimbangkan program sebagai ekspresi besar, sebagai rumus matematika, baik untuk tujuan manipulasi dan untuk menganalisis properti atau mendefinisikan semantik secara formal, yang ahli matematika tahu bagaimana melakukannya pada rumus. Sebagai formula, mereka secara alami terstruktur pohon, tetapi dapat dihiasi dengan berbagai informasi yang mengubah pohon-pohon ini menjadi grafik. Ini nyaman baik secara formal maupun pragmatis dan selanjutnya digunakan oleh kompiler dan sistem pemrograman.
Jadi pada dasarnya, AST adalah pohon, seperti yang tersirat dari namanya, tetapi dapat membawa informasi lebih lanjut. Sisanya ada di pilihan implementor dan di mata yang melihatnya. Apakah itu grafik atau pohon berhias? Namun, pohon AS dasar penting, karena itu adalah perancah yang Anda bangun berdasarkan teori dan pemrograman.
Perhatikan bahwa AST berbeda dari parse tree (sintaksinya berdasarkan konteks) seperti yang dihasilkan oleh algoritma parsing sebagaimana dipelajari dalam teori bahasa formal. Alasannya adalah bahwa desain sintaks dibatasi oleh teknologi penguraian waktu, itu sendiri dibatasi oleh daya komputasi rendah yang tersedia. Hasilnya adalah bahwa pohon sintaks hanya varian tersiksa dari apa yang secara alami akan mempertimbangkan struktur program, dan pemrosesan lebih lanjut, tidak benar-benar bagian dari proses penguraian formal dasar, harus dilakukan untuk mendapatkan versi yang lebih bersih dan lebih sederhana yang disebut AST.
Namun, representasi pohon di komputer, apakah abstrak atau tidak, agak dibatasi ketika Anda ingin mewakili semua struktur kalimat yang ambigu. Secara khusus, ini menyembunyikan masalah kompleksitas. Pelestarian ambiguitas dalam struktur grafik, sementara menerjemahkan dari pohon parse ke Pohon AS juga dapat menjadi masalah. Namun, jika Anda khawatir dengan itu, sering kali mungkin untuk mendefinisikan sintaks beton Anda sedemikian rupa sehingga pohon parse dapat berfungsi sebagai AST. Ini diizinkan oleh algoritma yang sangat umum yang menangani ambiguitas, dan oleh kekuatan komputer saat ini.
Jika Anda parse menggunakan parsing GLR (Generalized LR), dan jika parse input ambigu (ada beberapa cara yang mungkin untuk mem-parsing input), maka hasil parse dapat dianggap sebagai DAG parse, daripada pohon parse. DAG parse secara kompak mengkodekan banyak kemungkinan parse: beberapa kemungkinan pohon parse.
Namun, intinya tetap bahwa jika Anda memiliki tata bahasa bebas konteks, dan jika string input Anda dapat diuraikan secara jelas (hanya ada satu derivasi tunggal dalam tata bahasa yang menghasilkan string input ini), dan jika tugas parsing adalah menghasilkan derivasi itu ... maka dalam kondisi ini, output parsing akan selalu menjadi pohon parse, karena setiap produksi tata bahasa bebas konteks secara inheren memiliki struktur pohon.
Parser GLR asli (yang disebut demikian) mungkin telah menghasilkan parse DAG karena disadap. Karena jumlah parse yang mungkin dapat menjadi tak terbatas pada umumnya, tidak ada cara Anda dapat mewakili ketidakterbatasan ini dengan struktur berhingga yang tidak mengandung cyle. Struktur sebenarnya adalah semacam grafik bipartit, sedikit mirip dengan grafik dan-atau. Ia juga dikenal dengan nama lain. Ketidakmampuan untuk mewakili ambiguitas tak terbatas ini bisa menjadi masalah dalam berbagai situasi NLP. Akhir kalimat terakhir agak aneh (atau tidak berarti), dan saya mengoreksi kesalahan ketik ganda (kurasa).
babou
0
Dalam NLP, representasi sintaksis abstrak diarahkan grafik asiklik (DAG). Situasi ketika dua sisi menunjuk ke simpul yang sama disebut "berbagi struktur".
Saya pernah menulis seorang juru bahasa untuk C di mana "AST" untuk operator + = (misalnya) bukan pohon. Pertimbangkan a[i++] += dmana a[i++]adalah intdan dadalah double. Konversi implisit dan operasi pengambilan secara eksplisit di pohon, jadi masalahnya adalah di mana harus meletakkan pengambilan a[i++]dan konversi menjadi dua kali lipat. Solusi kami adalah meninggalkan pohon. "ASG" yang dihasilkan tampak seperti ini
+=
/ | \
/ | \
/ | \
/ convert \
| | \
| fetch fetch
| / |
index d
/ \
a postinc
|
i
Saya bingung dengan ini sendiri, sampai saya baru menyadari bahwa itu bukan pohon yang abstrak, juga bukan tentang beberapa "pohon sintaksis" abstrak, tetapi sintaksisnya abstrak.
Jadi, untuk menjawab pertanyaan Anda, saya menyimpulkan bahwa pohon sintaksis abstrak, serta pohon sintaksis konkret atau pohon keputusan, atau pohon lain, lebih baik menjadi pohon.
Di sisi lain, tidak ada yang harus mencegah siapa pun menggunakan grafik sintaksis abstrak, atau diagram sintaksis abstrak, atau kubus sintaksis abstrak, atau spesifikasi sintaksis abstrak.
Saya kira pohon sintaksis abstrak "pohon sintaksis abstrak" akan membantu saya untuk menghindari kebingungan.
Jawaban:
Output parser tidak harus berupa pohon. Memang, ketika Anda mempertimbangkan hal-hal seperti referensi dari USE dari variabel ke DEFinition-nya yang dilapiskan pada pohon sintaksis abstrak, Anda langsung memiliki grafik.
Masalahnya adalah bahwa parsing umumnya dirancang untuk dilakukan dalam satu lintasan - ini penting karena alasan historis, seperti kurangnya ruang dan kecepatan prosesor, tetapi juga karena lebih mudah untuk dipikirkan. Kemudian fase selanjutnya menghias pohon parse dengan informasi tambahan.
Ada beberapa hal seperti tata bahasa grafik, meskipun saya tidak tahu apakah mereka digunakan untuk parsing bahasa pemrograman.
sumber
Pertanyaan OP agak mundur. Tentu saja, algoritma penguraian dapat menampilkan apa pun yang diinginkan. Pertanyaannya adalah lebih untuk memahami untuk apa parsing dan apakah parser menghasilkan hasil yang memenuhi tujuan ini. Maka orang dapat bertanya-tanya apa representasi yang tepat untuk itu, misalnya pohon atau grafik.
Yah, saya kira parser adalah algoritma yang akan memberi Anda struktur sintaksis kalimat yang diberikan sebagai input, menurut definisi formal yang diberikan dari sintaks bahasa.
Perhatikan bahwa orang mungkin tidak setuju tentang apa yang merupakan sintaksis bahasa. Beberapa mungkin membatasi itu ke tulang punggung bahasa formal murni, sementara yang lain mungkin memperkenalkan pertimbangan yang sedikit lebih semantik seperti jenis, genre, jumlah atau yang lebih kompleks lainnya (saya tidak membedakan NLP atau bahasa pemrograman). Sebagian besar bahasa memiliki fitur yang memerlukan grafik untuk diwakili, tetapi terserah "implementor" (karena tidak ada kata yang lebih baik) untuk memutuskan apakah ia ingin memasukkan itu dalam sintaksis.
Jadi tergantung pada apa yang Anda definisikan menjadi sintaksis, Anda mungkin harus menampilkan jenis struktur formal yang berbeda.
Dalam kasus sederhana penguraian Bebas Konteks, pohon parse dapat dilakukan, kecuali untuk masalah ambiguitas yang dibahas di bawah ini, atau untuk fakta bahwa Anda mungkin ingin sedikit memodifikasinya untuk mendapatkan AST (lihat di bawah).
Namun, dalam kasus yang lebih kompleks, Anda mungkin memerlukan struktur yang berbeda, sering diwakili oleh tautan di pohon, sehingga mengarah ke struktur grafik. Ini sangat tergantung pada definisi Anda tentang sintaks bahasa.
Juga, pohon apa yang Anda harus hasilkan tidak jelas. Jika Anda mengambil kasus tata bahasa yang berdekatan (TAG), mereka bekerja sedemikian rupa sehingga pohon sintaksis tidak sama dengan pohon derivasi, meskipun yang pertama dapat diturunkan dari yang terakhir. Yang ingin Anda sampaikan mungkin merupakan pertanyaan yang relevan.
Ada juga masalah lain tentang ambiguitas. Sebuah kalimat yang diberikan, meskipun termasuk bahasa Anda, dapat melakukannya dalam banyak cara berbeda, dapat diberikan struktur sintaksis dalam berbagai cara.
Kemudian Anda dapat memilih untuk menampilkan hanya satu dari struktur ini, yang dipilih secara acak atau sesuai dengan kriteria yang didefinisikan dengan baik (seperti misalnya misalnya). Anda juga dapat memilih untuk menampilkan beberapa atau semuanya. Jika Anda ingin menghasilkan beberapa, biasanya nyaman untuk dikemas kemudian dalam struktur unik yang akan berbagi apa yang mereka miliki bersama. Ini menghemat ruang dan waktu komputasi, dan kompleksitas mungkin merupakan masalah nyata.
Saat Anda memilih untuk menampilkan semuanya, Anda tidak punya pilihan selain berbagi, karena mungkin ada jumlah parse yang tak terbatas. Dan tanpa batas dapat diwakili secara terbatas hanya dengan memiliki suatu siklus dalam suatu grafik. Jadi, Anda harus menghasilkan struktur grafik secara umum. Tetapi sifat-sifat struktur grafik ini berkaitan dengan jenis sintaksis formal yang telah Anda pilih.
Tentang Pohon Sintaksis Abstrak
Sekarang pertanyaannya juga tentang Pohon Sintaks Abstrak. Saya melewatkan bagian "abstrak" karena itu akan membawa kebingungan, imho. Memang pertanyaannya sudah membingungkan dalam berbagai penyajiannya.
Mengenai AST dalam perspektif historis, mereka berasal dengan bahasa Lisp dan sistem manipulasi program pada tahun 1960-1970. Idenya adalah untuk mempertimbangkan program sebagai ekspresi besar, sebagai rumus matematika, baik untuk tujuan manipulasi dan untuk menganalisis properti atau mendefinisikan semantik secara formal, yang ahli matematika tahu bagaimana melakukannya pada rumus. Sebagai formula, mereka secara alami terstruktur pohon, tetapi dapat dihiasi dengan berbagai informasi yang mengubah pohon-pohon ini menjadi grafik. Ini nyaman baik secara formal maupun pragmatis dan selanjutnya digunakan oleh kompiler dan sistem pemrograman.
Jadi pada dasarnya, AST adalah pohon, seperti yang tersirat dari namanya, tetapi dapat membawa informasi lebih lanjut. Sisanya ada di pilihan implementor dan di mata yang melihatnya. Apakah itu grafik atau pohon berhias? Namun, pohon AS dasar penting, karena itu adalah perancah yang Anda bangun berdasarkan teori dan pemrograman.
Perhatikan bahwa AST berbeda dari parse tree (sintaksinya berdasarkan konteks) seperti yang dihasilkan oleh algoritma parsing sebagaimana dipelajari dalam teori bahasa formal. Alasannya adalah bahwa desain sintaks dibatasi oleh teknologi penguraian waktu, itu sendiri dibatasi oleh daya komputasi rendah yang tersedia. Hasilnya adalah bahwa pohon sintaks hanya varian tersiksa dari apa yang secara alami akan mempertimbangkan struktur program, dan pemrosesan lebih lanjut, tidak benar-benar bagian dari proses penguraian formal dasar, harus dilakukan untuk mendapatkan versi yang lebih bersih dan lebih sederhana yang disebut AST.
Namun, representasi pohon di komputer, apakah abstrak atau tidak, agak dibatasi ketika Anda ingin mewakili semua struktur kalimat yang ambigu. Secara khusus, ini menyembunyikan masalah kompleksitas. Pelestarian ambiguitas dalam struktur grafik, sementara menerjemahkan dari pohon parse ke Pohon AS juga dapat menjadi masalah. Namun, jika Anda khawatir dengan itu, sering kali mungkin untuk mendefinisikan sintaks beton Anda sedemikian rupa sehingga pohon parse dapat berfungsi sebagai AST. Ini diizinkan oleh algoritma yang sangat umum yang menangani ambiguitas, dan oleh kekuatan komputer saat ini.
sumber
Jika Anda parse menggunakan parsing GLR (Generalized LR), dan jika parse input ambigu (ada beberapa cara yang mungkin untuk mem-parsing input), maka hasil parse dapat dianggap sebagai DAG parse, daripada pohon parse. DAG parse secara kompak mengkodekan banyak kemungkinan parse: beberapa kemungkinan pohon parse.
Namun, intinya tetap bahwa jika Anda memiliki tata bahasa bebas konteks, dan jika string input Anda dapat diuraikan secara jelas (hanya ada satu derivasi tunggal dalam tata bahasa yang menghasilkan string input ini), dan jika tugas parsing adalah menghasilkan derivasi itu ... maka dalam kondisi ini, output parsing akan selalu menjadi pohon parse, karena setiap produksi tata bahasa bebas konteks secara inheren memiliki struktur pohon.
sumber
Dalam NLP, representasi sintaksis abstrak diarahkan grafik asiklik (DAG). Situasi ketika dua sisi menunjuk ke simpul yang sama disebut "berbagi struktur".
sumber
Saya pernah menulis seorang juru bahasa untuk C di mana "AST" untuk operator + = (misalnya) bukan pohon. Pertimbangkan
a[i++] += dmanaa[i++]adalahintdandadalahdouble. Konversi implisit dan operasi pengambilan secara eksplisit di pohon, jadi masalahnya adalah di mana harus meletakkan pengambilana[i++]dan konversi menjadi dua kali lipat. Solusi kami adalah meninggalkan pohon. "ASG" yang dihasilkan tampak seperti inisumber
Saya bingung dengan ini sendiri, sampai saya baru menyadari bahwa itu bukan pohon yang abstrak, juga bukan tentang beberapa "pohon sintaksis" abstrak, tetapi sintaksisnya abstrak.
Jadi, untuk menjawab pertanyaan Anda, saya menyimpulkan bahwa pohon sintaksis abstrak, serta pohon sintaksis konkret atau pohon keputusan, atau pohon lain, lebih baik menjadi pohon.
Di sisi lain, tidak ada yang harus mencegah siapa pun menggunakan grafik sintaksis abstrak, atau diagram sintaksis abstrak, atau kubus sintaksis abstrak, atau spesifikasi sintaksis abstrak.
Saya kira pohon sintaksis abstrak "pohon sintaksis abstrak" akan membantu saya untuk menghindari kebingungan.
sumber