Soru lexers vs parsers


Lexers ve ayrıştırıcılar teoride gerçekten farklı mıdır?

Normal ifadelerden nefret etmek modaya uygun geliyor: kodlama korku, başka bir blog yazısı.

Ancak, popüler lexing tabanlı araçlar: pygments, geshiveya güzelleştirmek, tüm düzenli ifadeler kullanın. Bir şey Lex'e benziyorlar ...

Ne zaman lexing yeterli, EBNF ne zaman ihtiyacınız var?

Bu lexers tarafından üretilen jetonları bizon veya antlr parser jeneratörü ile kim kullandı?


268
2018-05-16 06:47


Menşei


Evet. Autohotkey'i ayrıştırmaya çalışıyorum. Gerçekten hızlı bir şekilde pufları kullanarak bir sözdizimi vurgulayıcı oluşturabiliyordum. Ama antlr çok daha uzun sürüyor ... İki araç arasında çok fazla çapraz tozlaşma görmedim. - Naveen
Kötüye kullanıldığında düzenli ifadelerden nefret eden tek moda. Bağlamı olmayan ayrıştırma gerektiğinde birçok kişi düzenli ifadeleri kullanmaya çalışır. Her zaman başarısız olurlar. Ve düzenli ifade teknolojisini suçluyorlar. Çekicinin crummy bir testere olduğundan şikayet etmek gibi bir şey. Doğru, ama çok fazla sempati duymayacaksın. - Ira Baxter
Ben şahane bir şekilde antlr ile biraz hız almaya başladım. Birçok lexing, içerikten bağımsız ve hatta bazen de içeriğe bağlı olarak bağlamsaldır. - Naveen
Lexer ve ayrıştırıcı sorununun temel bir yönü, lexerların sonlu otomata (FSA) veya daha hassas sonlu transdüserlere (FST) dayalı olmasıdır. Ayrıştırma formalitelerinin çoğu (sadece Bağlamı değil) FSA ile ya da FST uygulamasıyla kesişme altında kapatılır. Bu nedenle, lexer için daha basit düzenli ifade esaslı formaliteyi kullanmak, daha karmaşık ayrıştırıcı formalizmlerinin sözdizimsel yapılarının karmaşıklığını artırmaz. Bu kesinlikle büyük modülerlik sorunu Dillerin yapısını ve anlamlarını tanımlarken, yüksek seçkin cevaplar tarafından memnuniyetsizce göz ardı edilir. - babou
Lexers ve parsers değil ki not edilmelidir var farklı olmak, ör. LLLPG ANTLR'nin önceki sürümleri hem lexer hem de parsers için aynı LL (k) ayrıştırma sistemini kullanır. Ana fark, regeekslerin genellikle lexer'lar için değil, parserler için yeterli olmasıdır. - Qwertie


Cevaplar:


Hangi ayrıştırıcıların ve lexerların ortak noktası:

  1. Okurlar semboller bazı alfabe Onların girişinden.

    • İpucu: Alfabenin mutlaka harf olması gerekmez. Ama o olan sembollerden olmalı atomik dil için çözümleyici / lexer tarafından anlaşıldı.
    • Lexer için semboller: ASCII karakterleri.
    • Ayrıştırıcının sembolleri: Dilbilgisinin uçbirim sembolleri olan özel simgeler.
  2. Bunları analiz ediyorlar semboller ve bunları dilbilgisi Anladıkları dilin

    • Gerçek fark genellikle burada yatıyor. Daha fazlası için aşağıya bakın.
    • Dilbilgisi tarafından anlaşılan dilbilgisi: düzenli dilbilgisi (Chomsky'nin seviye 3).
    • Dilbilgisi tarafından anlaşılan dilbilgisi: bağlamsız gramer (Chomsky'nin seviye 2).
  3. Ekliyorlar semantik Buldukları dil parçalarına (anlam).

    • Lexers sınıflandırma yaparak anlam katıyor lexemeler (girdiden sembol dizileri) belirteçleri. Örneğin. Bütün bu sözler: *, ==, <=, ^ C / C ++ lexer tarafından "operatör" jetonu olarak sınıflandırılacaktır.
    • Parserler, belirteç dizelerini belirli bir girdiden (cümleleri) sınıflandırarak anlam taşırlar. nonterminallerdir ve bina ayrıştırma ağacı. Örneğin. tüm bu belirteci dizeleri: [number][operator][number], [id][operator][id], [id][operator][number][operator][number] C / C ++ ayrıştırıcı tarafından nonterminal "ifade" olarak sınıflandırılacaktır.
  4. Tanınan öğelere bazı ek anlamlar (veriler) ekleyebilirler.

    • Bir lexer, uygun bir sayı oluşturan bir karakter dizisini tanıdığında, onu ikili değerine dönüştürebilir ve "sayı" jetonu ile saklayabilir.
    • Benzer şekilde, bir ayrıştırıcı bir ifadeyi tanıdığında, değerini hesaplayabilir ve sözdizimi ağacının "ifade" düğümüyle birlikte depolayabilir.
  5. Hepsi çıktılarında uygun bir şekilde üretiyorlar cümleler tanıdıkları dilin

    • Lexers üretiyor belirteçleri, hangileri cümleler arasında normal dil tanırlar. Her belirteci bir iç sözdizimine sahip olabilir (seviye 3, seviye 2 olmasa da), ancak bu çıktı verileri ve bunları okuyan için önemli değildir.
    • Parsers üretmek sözdizimi ağaçları, temsilleri cümleler arasında bağlamsız dil tanırlar. Genel olarak tüm belge / kaynak dosyası için tek bir büyük ağaçtır, çünkü tüm belge / kaynak dosyası uygun cümle onlar için. Fakat ayrıştırıcının çıktısında bir dizi söz dizimi ağacı üretememesinin hiçbir nedeni yoktur. Örneğin. Düz metne yapıştırılmış SGML etiketlerini tanıyan bir ayrıştırıcı olabilir. Yani olacak tokenize SGML belgesini bir dizi jetona dönüştürmek: [TXT][TAG][TAG][TXT][TAG][TXT]....

Gördüğünüz gibi, ayrıştırıcılar ve belirtecilerin çoğu ortaktır. Bir ayrıştırıcı, kendi belirteçlerini kendi alfabesinden (tokenler sadece bazı alfabe sembolleri) semboller olarak okuyan diğer ayrıştırıcı için bir belirteç olabilir. Bir dilden alınan cümleler, başka bir, daha yüksek düzeydeki alfabetik simgeler olabilir. dil. Örneğin, * ve - alfabenin sembolleridir M ("Morse kodu sembolleri" olarak), daha sonra bu noktaların ve çizgilerin dizelerini Mors kodunda kodlanmış harfler olarak tanıyan bir çözümleyici oluşturabilirsiniz. "Mors Kodu" dilinde cümleler olabilir belirteçleri bunlar için başka bazı ayrıştırıcılar için belirteçleri kendi dilinin atomik sembolleridir (ör. "İngilizce Kelimeler" dili). Ve bu "İngilizce Kelimeler", "İngilizce Cümleler" dilini anlayan bazı üst düzey ayrıştırıcılar için belirteçleri (alfabenin sembolleri) olabilir. Ve tüm bu diller sadece dilbilgisinin karmaşıklığına göre değişir. Daha fazla bir şey yok.

Peki bu "Chomsky'nin dilbilgisi seviyeleri" ile ilgili ne var? Eh, Noam Chomsky, gramerlerini karmaşıklığına bağlı olarak dört seviyeye ayırdı:

  • Seviye 3: Düzenli dilbilgisi

    Düzenli ifadeler kullanırlar, yani sadece alfabenin sembollerinden oluşabilirler.a,b), onların birleşimleri (ab,aba,bbb etd.) veya alternatifler (ör. a|b).
    NFA (Nondeterministic Finite Automaton) veya daha iyi DFA (Determinist Finite Automaton) gibi sonlu durumlu otomata (FSA) olarak uygulanabilirler.
    Düzenli dilbilgileriyle başa çıkamıyor iç içe geçmiş sözdizimi, Örneğin. düzgün iç içe / parantez (()()(()()))iç içe geçmiş HTML / BBcode etiketleri, iç içe geçmiş bloklar vb. Bunun nedeni, onunla başa çıkacak olan devlet otomatasının sonsuz sayıda çok sayıda yuvalama seviyesini ele almak için sonsuz sayıda devlete sahip olması gerekir.
  • Seviye 2: Bağlamsız gramerler

    Sözdizimi ağaçlarında iç içe geçmiş, özyineli, özdeş dalları olabilir, böylece yuvalanmış yapılarla iyi idare edilebilirler.
    Yığın ile devlet otomatı olarak uygulanabilirler. Bu yığın, sözdiziminin yuvalanma düzeyini temsil etmek için kullanılır. Pratikte, genellikle yuvalama seviyesini izlemek için makinenin prosedür çağırma istemi kullanan yukarıdan aşağıya, özyinelemeli bir ayrıştırıcı olarak uygulanırlar ve söz dizimi içinde her bir terminal dışı sembol için ardışık olarak adlandırılan prosedürleri / fonksiyonları kullanırlar.
    Ama onlar bir bağlama duyarlı sözdizimi. Örneğin. bir ifaden olduğunda x+3 ve bir bağlamda bu x bir değişkenin adı olabilir ve başka bir bağlamda bir fonksiyonun adı olabilir.
  • Seviye 1: Bağlam duyarlı gramerler

  • Seviye 0: Sınırsız dilbilgisi
    Ayrıca "faz-yapı dilbilgisi" olarak da adlandırılır.


422
2017-09-01 03:53



Ah evet? Peki bu "kelimeler ya da simgeleri" nelerdir? Onlar sadece cümleler Alfabenin harflerinden oluşan normal dilde. Ve ayrıştırıcıdaki "yapılar" veya "ağaçlar" nedir? Onlar da cümlelerAncak, belirli belirteçlerin alfabetik semboller olduğu farklı, daha üst düzey bir dilde. Fark ettiğin şey değil, ama KULLANILAN DİLİN KARMAŞIKLIĞI. Senin ayrıştırma teorisi hakkında herhangi bir el kitabı ile -1 karşı karşıya. - SasQ
@SasQ Hem Lexers hem de Parsers'ın bir gramer ve bir dizi jetonu girdi olarak aldığını söylemek adil olur mu? - Parag
Oldukça öyle. İkisi de tanıdıkları alfabeden bir dizi sembol alırlar. Lexer için, bu alfabe sadece düz karakterlerden oluşur. Ayrıştırıcı için, alfabe, tanımlanmış ne olursa olsun, terminal sembollerinden oluşur. Eğer lexer kullanmıyorsanız ve tek karakterli tanımlayıcıları ve tek basamaklı sayıları (eğer geliştirmenin ilk aşamalarında oldukça kullanışlıdır) kullanırsanız, karakterler de olabilirler. Ama genellikle jetonlar (sözcüksel sınıflar) çünkü belirteçler iyi bir soyutlamadır: durdukları gerçek sözcükleri (dizeleri) değiştirebilir ve ayrıştırıcı değişikliği görmez. - SasQ
Örneğin, bir terminal sembolü kullanabilirsiniz STMT_END sözdiziminde (çözümleyici için) talimatların sonunu belirtmek için. Artık, lexer tarafından oluşturulan, onunla ilişkili aynı ada sahip bir jetonunuz olabilir. Ama onun gerçek anlamını değiştirebilirsin. Örneğin. tanımlayabilirsiniz STMT_END gibi ; C / C ++ benzeri kaynak koduna sahip olmak. Ya da onu tanımlayabilirsiniz end Pascal tarzına benzer bir şekilde sahip olmak. Ya da sadece '\n' talimatı Python'da olduğu gibi satırın sonu ile bitirmek için. Fakat komutun sözdizimi (ve ayrıştırıcı) değişmeden kalır. :-) Sadece lexer'ın değiştirilmesi gerekir. - SasQ
Wikipedia ve google'daki saatler yardımcı olmadı, ama Chomsky'nin gramerlerini 3 dakikada açıkladın. Teşekkür ederim. - enrey


Evet, teoride ve uygulamada çok farklılar.

Lexers, dil öğelerini oluşturan "kelimeleri" tanımak için kullanılır, çünkü bu tür kelimelerin yapısı genellikle basittir. Düzenli ifadeler bu daha basit yapıyı ele almakta son derece iyidir ve lexer'ları uygulamak için kullanılan çok yüksek performanslı düzenli ifade eşleme motorları vardır.

Parsers, bir dil ifadelerinin "yapısını" tanımak için kullanılır. Böyle bir yapı genellikle "normal ifadelerin" ne fark edebileceğinin çok ötesindedir, dolayısıyla bir ihtiyaç vardır "bağlam duyarlı" ayrıştırıcıları bu yapıyı ayıklamak. İçeriğe duyarlı ayrıştırıcılar inşa etmek zor, bu yüzden mühendislik uzlaşma "bağlam-içermeyen" gramer kullanmaktır ve içeriğe duyarlı parçayı işlemek için ayrıştırıcılara ("sembol tabloları" vb.) hack'ler ekleyin.

Ne lexing ne de ayrıştırma teknolojisi çok yakında gitmeyecek.

Onlar Mayıs ayı Şu anda tarayıcı olmayan GLR ayrıştırıcıları tarafından araştırıldığı gibi "sözcükleri" tanımak için "ayrıştırma" teknolojisini kullanmaya karar vererek birleşmiş olabilirsiniz. Bu, daha fazla genel makine uygulamasına ihtiyaç duymayan, genellikle ihtiyaç duyulan bir soruna neden olduğunuz ve genellikle bunun için yükü ödediğiniz bir çalışma zamanı maliyetine sahiptir. Çok fazla serbest zamanınız olduğu yerde, bu yük önemli olmayabilir. Çok fazla metin işlediyseniz, genel gider önemlidir ve klasik normal ifade ayrıştırıcıları kullanılmaya devam edecektir.


93
2018-05-17 20:52



Güzel bir açıklama, Ira. Senin benzerine ekleme: Lexers kelimeleri doğru bulmakla ilgili olsa da, ayrıştırıcılar cümleleri doğru almakla ilgili. "Nokta koşusunu görme" ve "noktalama işlemi" nin her ikisi de bir lexer söz konusu olduğunda geçerlidir. İfade yapısının yanlış olduğunu belirlemek için bir ayrıştırıcı gereklidir (İngilizce dilbilgisinde). - Alan
sanırım bir ayrıştırıcı bir ağaç yürüteç bir ayrıştırıcıya olduğu gibi bir lexer içindir. Teorinin farklı olduğuna ikna olmadım: antlr.org/wiki/display/~admin/ANTLR+v4+lexers ama aralarındaki sözleşmedeki farklılıkları anlamaya başlıyorum ... - Naveen
Teori çok farklı. Parser teknolojilerinin çoğu, içerik içermeyen dilleri bir dereceye kadar ele almaya çalışmaktadır (bazıları sadece LALR, örneğin hepsi, örneğin GLR gibi). Çoğu lexer teknolojisi sadece normal ifadeler yapmaya çalışır. - Ira Baxter
Teori farklıdır, çünkü birçok farklı kişi tarafından önerilmiş ve farklı terminoloji ve algoritmalar kullanmıştır. Ama onları yakından bakarsanız, benzerlikleri görebilirsiniz. Örneğin, sol yineleme problemi, NFA'larda determinisizlik problemine çok benzerdir ve sol yinelemenin kaldırılması, determinsizliğin giderilmesine ve NFA'nın DFA'ya dönüştürülmesine benzerdir. Jetonlar, belirteci (çıktı) için cümlelerdir, ancak ayrıştırıcı için (alfabetik) alfabetik simgelerdir. Farklılıkları (Chomsky seviyeleri) inkar etmiyorum, ancak benzerlikler tasarımda çok yardımcı oluyor. - SasQ
Benim memurum kategori teorisi oldu. Kategorik teorik kavrayış kavramının nasıl her türlü desen eşleşmesini kapsadığını ve soyut bir kategorik spesifikasyondan LR ayrışmasını türetebildiğini gösterdi. Aslında, eğer yeterince soyut olursanız, bu tür ortaklıkları bulabilirsiniz. Kategori teorisinin noktası genellikle “tamamen yukarı” şeklinde özetlenebilir; Farklılıkları silen bir kategori teorisi ayrıştırıcısı kurabileceğine eminim. Fakat bunun herhangi bir pratik kullanımı, belirli problem alanlarına ulaşmak zorundadır ve farklılıklar gerçek olarak ortaya çıkar. - Ira Baxter


Ne zaman lexing yeterli, EBNF ne zaman ihtiyacınız var?

EBNF gerçekten çok fazla güç dilbilgisi Sadece bir kolaylık / kısayol notasyonu / "Sözdizimsel şeker" standart Chomsky'nin Normal Formu (CNF) dilbilgisi kuralları üzerinde. Örneğin, EBNF alternatifi:

S --> A | B

Her alternatif üretimi ayrı ayrı listeleyerek CNF'de elde edebilirsiniz:

S --> A      // `S` can be `A`,
S --> B      // or it can be `B`.

EBNF'den opsiyonel eleman:

S --> X?

kullanarak bir CNF elde edebilirsiniz null üretim, yani bir ile değiştirilebilen boş dize (burada sadece boş üretim ile gösterilir; diğerleri epsilon veya lambda veya çapraz daire kullanır):

S --> B       // `S` can be `B`,
B --> X       // and `B` can be just `X`,
B -->         // or it can be empty.

Sonuncusu gibi bir formda bir üretim B yukarıdaki "silme" olarak adlandırılır, çünkü diğer yapımlarda (ürün başka bir şey yerine boş bir dize) duruyorsa onu silebilir.

EBNF'den sıfır ya da daha fazla repetiton:

S --> A*

kullanarak obtan yapabilirsiniz özyinelemeli üretim, yani kendini bir yere gömen bir şey. İki şekilde yapılabilir. Birincisi sola dönüş (genellikle kaçınılmalıdır, çünkü Top-Down Recursive Descent parsers onu ayrıştırılamıyor):

S --> S A    // `S` is just itself ended with `A` (which can be done many times),
S -->        // or it can begin with empty-string, which stops the recursion.

Sadece boş bir dize (nihayetinde) ve ardından sıfır ya da daha fazlasını oluşturduğunu bilmek As, aynı dize (ama aynı dil değil!) kullanılarak ifade edilebilir sağ özyineleme:

S --> A S    // `S` can be `A` followed by itself (which can be done many times),
S -->        // or it can be just empty-string end, which stops the recursion.

Ve söz konusu olduğunda + EBNF'den bir veya daha fazla tekrar için:

S --> A+

Bir faktoring yaparak yapılabilir Ave kullanarak * eskisi gibi:

S --> A A*

CNF'de bu şekilde ifade edebileceğiniz gibi (burada doğru özyineleme kullanıyorum; diğerini bir egzersiz olarak kendiniz bulmaya çalışın):

S --> A S   // `S` can be one `A` followed by `S` (which stands for more `A`s),
S --> A     // or it could be just one single `A`.

Bunu bildiğinizde, muhtemelen düzenli bir ifade için bir dilbilgisi tanıyabilirsiniz (yani, düzenli dilbilgisi) sadece terminal sembollerinden oluşan tek bir EBNF üretiminde ifade edilebilen Daha genel olarak, bunlara benzer prodüksiyonlar gördüğünüzde, düzenli gramerleri tanıyabilirsiniz:

A -->        // Empty (nullable) production (AKA erasure).
B --> x      // Single terminal symbol.
C --> y D    // Simple state change from `C` to `D` when seeing input `y`.
E --> F z    // Simple state change from `E` to `F` when seeing input `z`.
G --> G u    // Left recursion.
H --> v H    // Right recursion.

Yani, sadece boş dizeleri, terminal sembolleri, ikameler ve durum değişiklikleri için basit terminaller ve tekrarı elde etmek için özyineleme (yineleme, sadece doğrusal tekrarlama - ağaç dalı gibi olmayan bir şey. Bunların üzerinde hiçbir şey daha gelişmiş değil, o zaman düzenli bir sözdizimi olduğundan emin olabilirsiniz ve bunun için sadece lexer ile devam edebilirsiniz.

Ancak sözdiziminiz yinelenen bir şekilde, aşağıdaki gibi ağaç benzeri, kendine benzeyen, iç içe geçmiş yapılar üretmek için özyineleme kullandığında:

S --> a S b    // `S` can be itself "parenthesized" by `a` and `b` on both sides.
S -->          // or it could be (ultimately) empty, which ends recursion.

daha sonra bunun normal ifadeyle yapılamayacağını kolayca görebilirsiniz, çünkü bunu herhangi bir şekilde tek bir EBNF üretimine çözemezsiniz; yerine geçmek ile sona erecek S süresiz olarak, her zaman başka bir tane ekleyecek as ve bher iki tarafta. Lexers (daha spesifik olarak: Lexer tarafından kullanılan Sonlu Durum Automata) keyfi sayıya dayanamaz (sonlu, hatırlıyor musunuz?), Bu yüzden kaç tane olduğunu bilmiyorlar aOnları o kadar çok ile eşit bir şekilde eşleştirmek için vardı bs. Bunun gibi dilbilgileri denir bağlamsız gramer (en azından) ve bir ayrıştırıcıya ihtiyaç duyarlar.

Bağlamsız gramerlerin ayrıştırılması iyi bilinir, bu yüzden programlama dilleri sözdizimini tanımlamak için yaygın olarak kullanılırlar. Ama dahası var. Bazen daha genel bir dilbilgisine ihtiyaç vardır - aynı anda saymak için daha fazla şeyiniz olduğunda, bağımsız olarak. Örneğin, yuvarlak parantezleri ve köşeli ayraçları bir arada kullanabileceği bir dili tanımlamak istediğinizde, ancak birbirleriyle doğru şekilde eşleştirilmeleri gerekir (parantezli parantezler, yuvarlak yuvarlak). Bu tür dilbilgisi denir bağlama duyarlı. Bunu, solda (okdan önce) birden fazla simgeye sahip olduğunu fark edebilirsiniz. Örneğin:

A R B --> A S B

Soldaki bu ek sembolleri, kuralı uygulamak için "bağlam" olarak düşünebilirsiniz. Bazı önkoşullar, posta koşulları vb. Olabilir. Örneğin, yukarıdaki kural yerine geçecek R içine Sama sadece aralarında olduğunda A ve Bbunları bırakmak A ve B kendileri değişmedi. Bu tür bir sözdizimi ayrıştırmak gerçekten çok zordur, çünkü tam gelişmiş bir Turing makinesine ihtiyaç duyar. Tamamen başka bir hikaye, bu yüzden burada biteceğim.


28
2018-06-11 14:19



EBNF'nin standart Chomsky'nin Normal Form (CNF) dilbilgisi kuralları üzerinde "sadece bir kolaylık / kısayol notasyonu /" sözdizimsel şeker "olduğunu belirtiyorsunuz. Fakat CNF'nin konuyla ilgisi yok. EBNF kolayca standart BNF'ye dönüştürülebilir. Dönemi. Standart BNF için sözdizimsel şekerdir. - babou


Soruyu sorulan soruya cevap vermek için ( diğer cevaplar)

Lexers ve ayrıştırıcılar tarafından önerilen gibi çok farklı değil kabul edilen cevap. Her ikisi de basit dil formalizmlerine dayanır: düzenli lexers için diller ve hemen hemen her zaman, içeriksiz (CF) diller parsers için. Her ikisi de oldukça basit bir hesaplama ile ilişkili modeller, sonlu durum otomatonu ve aşağı itilen yığın otomatı. Düzenli diller, içerik içermeyen dillerin özel bir halidir. o lexers biraz daha karmaşık CF ile üretilebilir teknolojisi. Ama bu iyi bir fikir değil en az iki sebepten dolayı.

Programlamada temel bir nokta, bir sistem bileşeninin En uygun teknoloji ile çalışmak, böylece kolay üretmek, anlamak ve sürdürmek. Teknoloji olmamalı overkill (tekniklerin ihtiyaç duyulandan çok daha karmaşık ve maliyetli kullanılması), ne de kendi gücünün sınırında olmalı, bu yüzden teknik gerektirir istenen hedefe ulaşmak için çarpıklıklar.

Bu yüzden "düzenli ifadelerden nefret etmek modaya uygun gözüküyor". Çok şey yapabilmelerine rağmen, bazen çok okunamayanlar gerektirir Bunu başarmak için kodlama, çeşitli uzantıları gerçeğinden bahsetmiyorum ve uygulamadaki kısıtlamalar teorik olarak biraz azaltmaktadır. basitlik. Lexers genellikle bunu yapmaz ve genellikle basittir. Vericiyi ayrıştırmak için verimli ve uygun teknoloji. CF ayrıştırıcılarını kullanma jeton için mümkün olsa da, overkill olurdu.

CF formalizmini lexers için kullanmamanın başka bir nedeni de daha sonra tam CF gücünü kullanmak için cazip olun. Ama bu yükselebilir Programların okunması ile ilgili yapısal sorunlar.

Temel olarak, program metninin yapısının çoğu anlam çıkarılır, bir ağaç yapısıdır. Bu ayrıştırma nasıl ifade eder cümle (program) sözdizimi kurallarından oluşturulur. Semantik kompozisyon teknikleri ile türetilmiştir (homomorphism için matematiksel yönelimli) sözdizimi kurallarından oluşur ayrıştırma ağacını oluşturmak. Bu nedenle ağaç yapısı önemlidir. Jetonların düzenli set bazlı bir lexer ile tanımlanmış olması gerçeği durum değişmez, çünkü CF düzenli olarak düzenli olarak CF verir (Ben düzenli transdüserler hakkında çok gevşek konuşuyorum, o Bir karakter dizisini bir simge akışına dönüştürün).

Ancak, CF (CF transducer ile) CF ile oluşan CF matematik), zorunlu olarak CF vermez ve işleri daha fazla yapabilir genel, ama pratikte daha az çekilebilir. Yani CF uygun değil Kullanılabilir olsa bile lexers için araç.

Düzenli ve CF arasındaki en büyük farklardan biri düzenli diller (ve dönüştürücüler) hemen her CF dilleri (ve dönüştürücüler) yaparken, çeşitli şekillerde formalizm değil, kendileriyle bile (birkaç istisna dışında).

(Normal dönüştürücülerin başkalarının kullandığı gibi olabileceğini unutmayın. Bazı sözdizimi hata işleme tekniklerinin resmi hale getirilmesi.)

BNF, CF dilbilgileri sunmak için özel bir sözdizimi.

EBNF, BNF için sözdizimsel bir şekerdirdüzenli tesislerin kullanımı BNF dilbilgisinin ters versiyonunu vermek için notasyon. Her zaman olabilir eşdeğer saf BNF'ye dönüştürülür.

Bununla birlikte, düzenli notasyon genellikle EBNF'de bunları vurgulamak için kullanılır. sözdiziminin yapısına karşılık gelen sözdizimi parçaları elemanları ile ve lexer ile tanınmalıdır, düz BNF'de sunulmak. Ama bu mutlak bir kural değildir.

Özetlemek, Jetonun daha basit yapısı daha iyi analiz edilir. ağaç yönelirken, normal dillerin daha basit teknolojisi dilin yapısı (programın sözdizimi) CF tarafından daha iyi ele alınır. gramerler.

Ayrıca bakmanızı öneririm AHR'nin cevabı.

Ama bu bir soru açık bırakır: Neden ağaçlar?

Ağaçlar sözdizimi belirtmek için iyi bir temeldir çünkü

  • Metne basit bir yapı kazandırıyorlar

  • metinle semantik ilişkilendirme için çok uygun Bu yapıya dayanarak, matematiksel olarak iyi anlaşılmış teknoloji (homomorfizmlerle bileşim) yukarıda belirtilmiş. Bu tanımlamak için temel bir cebirsel araçtır matematiksel biçimbilimlerin semantiği.

Bu şekilde gösterildiği gibi iyi bir ara temsildir. Soyut Sözdizimi Ağaçlarının (AST) başarısı. AST'nin sık sık olduğuna dikkat edin ayrıştırma teknolojisi birçok kişi tarafından kullanıldığı için ayrıştırma ağacından farklıdır profesyoneller (LL veya LR gibi) sadece CF'nin bir alt kümesine uygulanır Dilbilgisi, böylece daha sonra olan dilbilgisel çarpıtmaları zorlar AST'de düzeltildi. Bu daha genel ayrıştırma ile önlenebilir CF dilbilgisi kabul eden teknoloji (dinamik programlamaya dayalı).

Programlama dilleri gerçeği hakkında açıklama CF yerine içerik duyarlı (CS) keyfi ve tartışılabilir.

Sorun, sözdizimi ve semantiğin ayrılmasıdır. keyfi. Bildirimleri veya tür sözleşmeyi kontrol etmek aşağıdaki gibi görülebilir sözdizimi ya da semantiğin bir parçası. Aynısı geçerli olurdu Doğal dillerde cinsiyet ve sayı anlaşması. Ama doğal var çoğul anlaşmanın fiili semantiğe bağlı olduğu diller kelimelerin anlamı, bu yüzden sözdizimiyle uyuşmaz.

Anlamsal anlambilimde programlama dillerinin birçok tanımı semantiklerde yer bildirimleri ve tip denetimi. Olarak belirten tarafından tamamlandı Ira Baxter CF ayrıştırıcılarının bir içerik elde etmek için saldırıya uğradığı Sözdizimin gerektirdiği duyarlılık en iyi olanıdır. durum. Bazı derleyicilerde bir saldırı olarak organize edilebilir, ancak olmak zorunda değil.

Ayrıca, yalnızca bu CS ayrıştırıcılarının (burada diğer yanıtlarda kullanılan anlamda) inşa edilmesi zor ve daha az değil verimli. Onlar da göze çarpan bir şekilde ifade etmek için yetersizler. ihtiyaç duyulabilecek içerik duyarlılığı kinf. Ve onlar değil doğal olarak sözdizimsel bir yapı (ayrıştırma ağaçları gibi) üretir programın semantiklerini türetmek için uygundur, yani üretmek için derlenmiş kod.


11
2018-03-10 17:40





Derleyicinin analiz kısmının normal olarak bir dizi nedeni vardır. sözcüksel analiz ve ayrıştırma (sözdizimi analizi) aşamalarına ayrılmıştır.

  1. Tasarımın sadeliği en önemli husustur. Sözcüksel ve sözdizimsel analizlerin ayrımı, çoğu zaman bu görevlerden en az birini basitleştirmemizi sağlar. Örneğin, yorumlarla ve beyaz boşlukla sözdizimsel birimler olarak ilgilenen bir ayrıştırıcı olurdu. Yorum ve beyaz alanın varsayılabileceğinden çok daha karmaşık olan sözcük analizcisi tarafından zaten kaldırılmıştır. Yeni bir dil tasarlıyorsak, sözcüksel ve sözdizimsel endişeleri ayırmak, daha genel bir dil tasarımına yol açabilir.
  2. Derleyici verimliliği artırıldı. Ayrı bir sözcük analizcisi, ayrıştırma işini değil, yalnızca sözcüksel görevi yerine getiren özel teknikleri uygulamamıza izin verir. Ayrıca, giriş karakterlerini okumak için özel tamponlama teknikleri derleyiciyi önemli ölçüde hızlandırabilir.
  3. Derleyici taşınabilirliği geliştirildi. Giriş cihazına özgü özellikler sözcük analizcisi ile sınırlandırılabilir.

kaynak___Derleyiciler (2. Baskı) tarafından yazılmıştır- Alfred V. Abo Kolombiya Üniversitesi Monica S. Lam Stanford Üniversitesi Ravi Sethi Avaya Jeffrey D. Ullman Stanford Üniversitesi


5