Parçacıkları Anlama ve Yazma

Question

İlk gerçek, biraz karmaşık ayrıştırıcımı oluşturmamı gerektiren bir program yazıyorum. Ayrıştırma algoritmalarının ne olduğunu ve bir "dilbilgisi" nasıl oluşturulacağını anlamak isterim. Bu yüzden benim sorum (lar):

1) Bir çözümleyicinin anlayabileceği biçimsel bir dilbilgisi nasıl oluşturulur? Bir dilbilgisinin temel bileşenleri nelerdir?

2) Hangi ayrıştırma algoritmaları vardır ve ayrıştırmada her bir girdi ne kadar aşılır? 3) Yukarıdaki soruların geniş doğası ışığında, 1 ve 2 numaralı soruların cevabını anlamak için okuyabileceğim iyi referanslar nelerdir?

İhtiyacım olan anahtar kelimeler/konu alanları ile daha geniş bir genel bakışa bakıyorum, böylece ayrıntılara kendim de bakabilirim. Herkese teşekkürler!

Answer 1

Genellikle bir bağlam serbest dilbilgisi yazmaL (örneğin tüm sözdizimsel olarak geçerli C programlarının seti) basitçe belli bir alfabe üzerinde dizeleri bir dizi (bütün düşünmek belli biçimsel dilini açıklar G iyi biçimlendirilmiş C programları ya da iyi biçimlendirilmiş tüm HTML belgelerinin ya da tüm iyi biçimlendirilmiş MARKDOWN direklerinin tümü, bunların hepsi ASCII karakter kümesinin belirli alt kümeleri üzerinde sonlu diziler kümesidir). Bundan sonra, verilen dilbilgisi için ayrıştırıcı ile gelirsiniz. Yani, w dizgisi verilen bir algoritmadizgisinin G dilbilgisi tarafından türetilebileceğine karar verir. (Örneğin, grammar of the C11 language tüm iyi biçimlendirilmiş C programlarının kümesini açıklar.)

Bazı dilbilgisi türleri, kullanımı kolay ayrıştırıcıları kabul eder. Pratikte sıklıkla kullanılan dilbilgisi örneği LL grammars'dur. LL dilbilgisinin özel bir alt kümesi, LL(1) dilbilgisi olarak adlandırılır, doğrusal zamanda çalışan ayrıştırıcılara sahiptir (ayrıştırdığımız dizenin uzunluğunda doğrusal).

inpuit olarak bir dize w ve dilbilgisi G alıp dize w dilbilgisi G ile derive olup olmadığını zaman O(|w|^3) karar en önemlisi Early parser ve CYK algorithm daha genel ayrıştırma algoritmaları --- --- vardır. (Bunun ne kadar havalı olduğuna dikkat edin: algoritma dilbilgisini agrument olarak alır. Ancak bunun pratikte kullanıldığını düşünmüyorum.)

Java'da Erken ayrıştırıcıyı bir süre önce uyguladım. Eğer insterested iseniz, kod available on GitHub. tüm sürecin somut Örneğin

vb parantez (), (()), ((()))()(())(), tüm dengeli dizeleri dilini düşünün Aşağıdaki serbest içerik ile onları tarif edebilirsiniz:

S -> (S) | SS | eps 

nerede eps boş üretimdir. Örneğin, (())() dizesini aşağıdaki gibi türetebiliriz: S => SS => (S)S => ((S))S => (())S => (())(S) => (())(). Bu dilbilgisi için bir ayrıştırıcıyı kolayca uygulayabiliriz (egzersiz :-) olarak kaldı). Çok iyi bir referans Aho ve ark. Tarafından Compilers: Principles, Techniques, and Tools adı verilen ejderha kitabıdır. Tüm önemli konuları kapsar. Bir başka iyi referans, Hopcroft et al. Tarafından Introduction to Automata Theory, Languages, and Computation numaralı klasik kitaptır.