Gelen bilgisayar bilimleri , sözcüksel analiz , Lexing , segmentasyon veya simgelileştirme bir dönüşüm olduğunu karakter dizesinin simgeler listesinden (içine (bir metin) Jetonlar İngilizce). Derleme zincirinin ilk aşamasının bir parçasıdır . Bu semboller daha sonra ayrıştırma sırasında tüketilir . Sözcüksel çözümleme gerçekleştiren bir programa sözcük çözümleyici , belirteç oluşturucu veya sözcük oluşturucu denir . Bir sözlük çözümleyicisi, genellikle bir metnin sözdizimini çözümlemek için bir sözdizimi çözümleyicisi ile birleştirilir .
Bir lexemenin sözlü bir sembolün deseni ile eşleşen bir şekilde sözcük analizörü tarafından analiz edilen bir kaynak programı bir karakter dizisi , örneğin bu sözcük sembolünün.
Bazı yazarlar, hem sözcük çözümleyicisi tarafından işlenen karakter dizisini hem de bu işlemin çıktısında üretilen veri yapısını temsil etmek için "belirteç" terimini kullanır.
Bilgisayar bilimindeki "sözcük birimi" terimi , dilbilimdeki sözlük birimi ile aynı anlama sahip değildir . Bilgisayar bilimindeki tanımı, dilbilimdeki biçimbirim tanımına benzer .
Bir sözcük birimi veya sözcük simgesi ya da daha basit bir biçimde simge, bir ad ve isteğe bağlı bir değerden oluşan bir çifttir. Sözlüksel birimin adı, sözlük biriminin bir kategorisidir.
En sık karşılaşılan sözcük birimlerinin adlarına bazı örnekler:
Soyadı | değerler |
---|---|
tanımlayıcılar | x, color, UP |
anahtar kelimeler | if, while, return |
noktalama | }, (, ; |
operatörler | +, <, = |
değişmezler | true, 6.02e23, "music" |
Bir sözlük birimi adı, gramer doğası kavramıyla karşılaştırılabilir .
Programlama dilleri bir dilbilgisi benimsemeye dizimi tanımlar sıklıkta, kuralları tanımlar. Bu kurallar genellikle düzenli ifadeler şeklini alır ve sözlükleri oluşturmak için kullanılan karakter dizilerini tanımlar.
Düzenli bir ifade ile tanınan dillere rasyonel diller denir . Sonlu bir otomatı herhangi bir normal ifadeyle ilişkilendirebiliriz . Rasyonel olmayan diller de vardır.
Sözlüksel birimlerin en önemli kategorilerinden ikisi boşluk karakterleri ve yorumlardır. Her ikisi de çoğu dilin gramerinde tanımlanır ve sözlükler tarafından kapsanır, ancak çoğu zaman önemsiz olarak kabul edilir; en iyi durumda, iki jetonu ayırmak ve kendi başlarına hiçbirini oluşturmamak. Bunun iki önemli istisnası vardır. Her şeyden önce, Python gibi , kod bloklarını girinti ile sınırlayan ve boşluk karakterlerinin önemli olduğu ve dolayısıyla belirteçler üretebilen sözde girinti benzeri sözdizimi dilleri . Daha sonra, bazı hata ayıklama araçları veya zarif izlenim (güzel yazıcılar İngilizcesi) dahil olmak üzere sözlüklerin belirli kullanımlarında, daha sonra kullanıcıya göstermek üzere orijinal kaynak kodunu korumak gerekli olabilir.
Aranan sözel çözümleyici ( lexer bir sözcük analizi yapmak Herhangi bir program İngilizce).
Sözlüksel çözümleyici şu amaçlarla kullanılır:
Sözlüksel çözümleyici geçersiz bir sözlük tespit ettiğinde bir hata bildirir. Buna karşılık, sözcük birleşimleri genellikle ayrıştırıcıya bırakılır: örneğin, tipik bir sözcük çözümleyicisi parantezleri sözcük birimleri olarak tanır, ancak açık bir parantezin "(" mutlaka bir kapanış paranteziyle " ) ” ilişkili olduğunu doğrulamaz.
Sözlüksel çözümleyici yazılabilir
Sözlükler esas olarak derleyici yazmak için kullanılsa da, tiftik veya zarif baskı sistemleri ( troff ) gibi bilgisayar dillerini işlemek için diğer araçların tasarımında kullanılırlar .
Sözlüksel çözümleme, modern derleme işlemlerinin ilk aşamasıdır . Analiz genellikle kaynak metin üzerinden sadece bir kez geçilerek yapılır.
Başka bir analiz biçimine aktarılacak olan bir dizi sözlükte giriş karakter dizisinin bölümlerinin sınırlarının belirlenmesinden ve mümkünse karakterizasyonundan oluşur.
Örneğin, C dilindeki talimat sum = 2 + 3;, sözlüksel analizden sonra aşağıdaki sembol listesini üretir:
Değer | sözlüksel kategori |
---|---|
toplam | Kullanıcı adı |
= | atama operatörü |
2 | gerçek tam sayı |
+ | toplama operatörü |
3 | gerçek tam sayı |
; | deklarasyon sonu |
Doğal dillerde olduğu gibi boşluklarla örtük olarak bölümlere ayrılan giriş karakterlerinin dizisi, altı sözcük biriminden oluşan bir listeye dönüştürülmüştür:
[(identifiant, sum), (opérateur d'affectation, =), (entier littéral, 2), (operator, +), (entier littéral, 3), (fin de déclaration, ;)]
Genel olarak, bir sözlük birimi birkaç sözlüğü temsil ettiğinde, sözlüksel çözümleyici, orijinal sözlüğü yeniden üretebilmek ve onu anlamsal analiz sırasında kullanabilmek için yeterli bilgiyi kaydeder. Ayrıştırıcı bu bilgiyi alır ve bir Özet Sözdizimi Ağacı (AST) biçiminde saklar . Bu, numaralar ve tanımlayıcılar söz konusu olduğunda bilgi kaybını önlemek için gereklidir.
Sözlükler, sözlük çözümleyicisi tarafından belirlenen kurallara göre tanımlanır. Sözlükleri tanımlamak için kullanılan yöntemler arasında düzenli ifadeler , bayrak adı verilen belirli bir karakter dizisi, ayırıcı adı verilen karakterler ve bir sözlük buluyoruz .
Sözlüksel çözümleyici genellikle sözcük birimlerinin kombinasyonlarını işlemez, bu görev ayrıştırıcıya bırakılır. Örneğin, tipik bir sözcük çözümleyici parantezleri tanıyabilir ve işleyebilir, ancak bunları sayamaz ve bu nedenle her kapatma parantezinin ")" bir önceki açık parantez "(" ile eşleşip eşleşmediğini doğrulayamaz.
Bir karakter dizisinin sözcüksel analizi üç aşamada gerçekleşir:
İlk adım olan tarama, genellikle bir durum makinesi tarafından gerçekleştirilir . Bu otomat, bir sözlükte içerilebilecek tüm karakter dizilerini işlemek için gerekli bilgilere sahiptir (bu dizilerin her bir karakteri bir sözlüktür). Örneğin, bir int , olası tüm basamak dizilerini içerebilir . Çoğu durumda, okunan ilk anlamlı karakter, geçerli sözlüğün yapısını anlamak için kullanılabilir ve sonraki her karakter, kabul edilemez bir karakter okunana kadar simge değerine eklenecektir. Bununla birlikte, bazı dillerde, kural daha karmaşık olabilir ve önceden okunan karakterler üzerinde geri izleme gerektirebilir . Örneğin C'de bir "L" karakteri, "L" ile başlayan bir tanımlayıcıyı bu tek karakterden oluşan bir hazır bilgiden ayırt etmek için yeterli değildir.
Sözlük, yalnızca bir tür tarafından karakterize edilen bir dizi karakterdir. Sözlüksel bir birim oluşturmak için sözcük çözümleyicisi, bir değer üreten ikinci bir adım olan değerlendirmeye ihtiyaç duyar. Değeri ile birleştirilen sözlüğün türü, daha sonra bir ayrıştırıcıya iletilebilen bir belirteci oluşturan şeydir. Noktalama işaretlerini temsil edenler gibi bazı sözlük birimlerinin gerçek değeri yoktur, bu nedenle değerlendirme işlevleri sıfır değeri döndürebilir; sadece onların türüne ihtiyaç vardır. Benzer şekilde, değerlendirme bir sözlüğü tamamen kaldırabilir ve boşluk karakterleri veya yorumlarda olduğu gibi onu ayrıştırıcıdan gizleyebilir. Tanımlayıcıların değerlendirilmesi genellikle, onları değer olarak oluşturan karakter dizisini doğrudan ileterek basittir, ancak sayısal değerler için sözcüksel çözümleyici, bunları karakter dizileri biçiminde sözcüksel birime dönüştürmeyi seçebilir (işleme anlamsal analizini erteleyerek) ya da kendisi değerlendirmek için.
Sözcüksel bir çözümleyiciyi "elle" yazmak mümkün veya az sayıda sözlük olması durumunda gerekli olsa bile, bunlar genellikle otomatik araçlar tarafından üretilir.. .................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................. içinde? Bu araçlar genellikle yetkili sözlük birimlerini tanımlayan normal ifadeleri kabul eder. Her normal ifade, değerlendirilen dilin biçimsel dilbilgisi için bir üretim kuralıyla ilişkilendirilir . Bu araçlar, derlenip yürütülebilen kaynak kodu oluşturabilir veya bir durum makinesi için bir durum geçiş tablosu oluşturabilir.
Normal bir ifade, geçerli bir sözcük birimi oluşturmak için sözlük birimlerinin izlemesi gereken kalıbın kompakt bir sürümünü temsil eder. Örneğin, Fransızca diline dayalı bir dil için, tanımlayıcı herhangi bir alfabetik karakter veya bir alt çizgi ve ardından herhangi bir alfasayısal basamak veya ASCII karakter ve/veya alt çizgi olabilir. Bu dizi, aşağıdaki karakter dizisi ile temsil edilebilir [a-zA-Z_][a-zA-Z_0-9]*.
Düzenli ifadeler ve ürettikleri sonlu otomatlar, Dyck dillerinde bulunanlar gibi özyinelemeli kalıpları işlemek için yeterince güçlü değildir . Bu işlemler sözdizimi çözümleyicisine bırakılır.
ALGOL gibi daha eski dillerde , derlemenin ilk aşaması , metni anahtar kelimeler için taramaktan ve boşlukları ve yorumları kaldırmaktan oluşan satır yeniden yapılandırması olarak adlandırıldı . Sözcüksel ve sözdizimsel analizler tek bir ayrıştırıcı-sözcük programı ile gerçekleştirilmiştir.
Tipik olarak, sözcüksel analiz sözcük düzeyinde çalışır . Bununla birlikte, bazen bir "kelime"nin ne olduğunu ayırt etmek zor olabilir. Sözcüksel çözümleyiciler genellikle basit buluşsal yöntemlere dayanır, örneğin:
Sözcükler arası boşluk kullanan dillerde (çoğu programlama dili ve Latin alfabesini kullanan doğal diller gibi) bu yaklaşımın uygulanması kolaydır. Buna rağmen, birçok durumda (vardır kasılmalar , ifadeler , bileşik kelimeler, URI , vb sözcük analiz cihazı tarafından işlenecek daha karmaşık buluşsal gerektirir). Klasik bir örnek, İngilizce'de tek bir kelime oluşturan ancak saf bir şekilde iki hatta üç sözlüğe ayrılabilen “New York merkezli” karakter dizisidir.
Sözcük analizi, eski Yunanca veya Çince'de olduğu gibi, noktalama işaretleri veya sözcük birimi ayrımı için hiçbir sembolün olmadığı, scriptio continua ile yazılmış doğal diller için özellikle zor olabilir .
Python gibi bazı diller, kod bloklarını sınırlamak için girinti kullanır . Bu nedenle sözcük çözümleyicisi, girinti arttığında bir INDENT sözcük birimi ve küçüldüğünde bir DEDENT sözcük birimi oluşturmalıdır. Bu sözcük birimleri, C gibi dillerde "{" açılıp "}" kapatılan köşeli parantezler okunurken oluşturulanlara karşılık gelir. Ayrıştırıcı tarafından dikkate alınabilmesi için mevcut durumu koruyabilmesi gerekir. girinti (çünkü bloklar iç içe yerleştirilebilir), bu nedenle analiz edilen dilin dilbilgisini bağlamsal hale getirir . INDENT-DEDENT bağlama bağlıdır (bu durumda önceki girinti düzeyi).
Sözcüksel çözümleyiciler genellikle sözcüksel çözümleyici oluşturucular adı verilen araçlar tarafından oluşturulur . Yaygın olarak kullanılan çoğu biri Lex ile birlikte, Yacc ayrıştırıcı jeneratör ve bunların serbest benzerlerinin Flex ve Bison . Bu oluşturucular, girdi olarak sözlüksel bir belirtim (genellikle normal ifadeler ve bazı etiketler) alan ve bir sözlük çıktısı veren özel bir dil biçimidir .
Bu araçlar, işlevsel bir sözcük çözümleyicisinin hızlı bir şekilde geliştirilmesine olanak tanır.
Sözcüklerin performansı, özellikle sözlüğe çok sık atıfta bulunulan kararlı dillerde (C veya HTML gibi) büyük bir endişe kaynağıdır. Lex / Flex kullanılarak oluşturulan Lexer'lar oldukça hızlı kabul edilir, ancak bazı durumlarda "elle" yazılan sözlüklerden veya re2c gibi araçlardan iki ila üç kat daha yavaş olabilir.
Programlama dilleri söz konusu olduğunda, bu algoritma genellikle giriş kelimesinin boyutuna göre doğrusal zamanda çalışır. Bununla birlikte, bunun gibi algoritmanın ikinci dereceden zamanda çalıştığı patolojik durumlar vardır: iki sözlükle: a ve a… ab, a n girişi , algoritmanın tanıdığı her a için kelimenin sonuna gitmesini gerektirir. . Karmaşıklık daha sonra ikinci derecedendir.
Bir kelimeyi doğrusal zamanda analiz edebilen başka algoritmalar da vardır.