Lexers ve ayrıştırıcılar teoride gerçekten farklı mıdır?
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ı?
Lexers ve ayrıştırıcılar teoride gerçekten farklı mıdır?
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ı?
Hangi ayrıştırıcıların ve lexerların ortak noktası:
*,
==,
<=,
^C / C ++ lexer tarafından "operatör" jetonu olarak sınıflandırılacaktır.
[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.
[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ı:
a,
b), onların birleşimleri (
ab,
aba,
bbbetd.) veya alternatifler (ör.
a|b).
(()()(()()))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.
x+3ve bir bağlamda bu
xbir değişkenin adı olabilir ve başka bir bağlamda bir fonksiyonun adı olabilir.
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.
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.
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.
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.
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