www.fatihkabakci.com

Personal Website and Computer Science TUR EN

REGEX GREEDY RELUCTANT ve POSSESSIVE KAVRAMLARI

Last update: 12/28/2014 3:30:00 PM

Yazan:Fatih KABAKCI

Bilgisayar Bilimleri ve formal dil teorisinde, kısaca regex olarak anılan bir regular expression(düzenli deyim), temel olarak 'find and replace', 'bul ve değiştir' gibi işlemleri için kullanılan, arama desenine(pattern) sahip karakterler sırasına(sequence of characters) verilen bir addır. İlk olarak Amerikan matematikçi Stephen Kleene düzenli bir dil tanımını açıklamış ve bu düşünce 1950 yılında ortaya çıkmıştır.

Regular expression' da genel olarak 3 farklı arama metodolojisi bulunur. Bunlar greedy, reluctant ve possessive sıfatlarıdır. Quantifier olarak adlandırılan her bir belirteç aşağıda açıklanmaktadır.

Greedy, aç gözlü anlamına gelir ve ilk fırsatta olabilecek en uzun kelimeyi arar. Bulursa eşleme işlemini sonlandırır. Bulamazsa, backtrack(geriye doğru tekrar arama) yaparak bütün permütasyonları yeniden dener. Greedy eşlemesinde, öncelikle aranan kelimelerin tümü, tek seferde desene(pattern) uyup uymadığı kontrol edilir. Şayet ilk deneme başarısız olursa, en sağdan 1 karakter yutar(swallow) ve sağdan sola doğru(right to left) olacak şekilde kalan tüm karakterleri yeniden okur(backtracking). Bu durum başarılı olana dek veya ortada hiç bir karakter kalmayana dek devam eder. Greedy quantifier’ ' ı en uzun eşleşmeyi hedefleyen bir nicelik belirtecidir.

Reluctant, gönülsüz, isteksiz anlamına gelir. Aranan kelimenin başından itibaren, bir eşleme sağlayana dek karakterleri tek tek okur. Eşleme sağladığı anda okuduğu tüm karakterleri yutar ve kaldığı yerden ikinci bir eşleme bulana dek devam eder. İkinci eşleşmeyi de bulursa, bu sefer bir sonraki eşleşme için yine kaldığı yerden devam eder. Bu durum ortada hiç bir karakter kalmayana dek devam eder. Arama sırasında eşleme bulamazsa, aramayı bitirmez ve kaldığı yerden devam eder. Ta ki 0 karakter kalana kadar. Reluctant quantifier' I en kısa eşleşme gruplarını alan bir nicelik belirtecidir.

Possessive, tutucu, sahiplenici anlamına gelir. Adını bu şekilde almasının sebebi ise, aradığı kelimenin tümüne 1 seferde bakmasıdır. Bir possessive quantifier ile tanımlanan desene uygun kelime ya da kelime gruplarına yalnızca bir sefer bakılır. Eşleşme başarısız ise, possessive asla backtrack yapmaz ve aramayı sonlandırır. Şayet bir aramayı tek seferde tüm girdi dizgisi için yapacaksanız, possessive belirtecini kullanabilirsiniz.

Aşağıda her bir quantifier için verilen örnekler, Oracle' ın hazırladığı regex dokümanından alınmıştır http://docs.oracle.com/javase/tutorial/essential/regex/quant.html.

Enter your regex: .*foo  // greedy quantifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfooxxxxxxfoo" starting at index 0 and ending at index 13.

Enter your regex: .*?foo  // reluctant quantifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfoo" starting at index 0 and ending at index 4.
I found the text "xxxxxxfoo" starting at index 4 and ending at index 13.

Enter your regex: .*+foo // possessive quantifier
Enter input string to search: xfooxxxxxxfoo
No match found.

Yukarıdaki örneklerin tümünde sonu foo ile biten, başlangıcında herhangi bir karakter alabilen ve bu karakterlerden ise 0 ya da n tane olabilen bir patern tanımlanmaktadır. Örnekler arasındaki farklar ise quantifier belirteçleridir.

İlk örnek bir greedy örneğidir ve .* ifadesi daha kelimenin sonu foo' ya bakmadan tüm karakterleri bir anda okur. Eşleşme başarısızdır ve backtracking ile en sağdan 1 karakter hariç baştan itibaren tekrar okur. Detaylar aşağıdaki tabloda gösterilmektedir.

Adım İfade Okunan Kalan Eşleşme
1.iterasyon .*foo xfooxxxxxxfoo   Başarısız !
2.iterasyon .*foo xfooxxxxxxfo o Başarısız !
3.iterasyon .*foo xfooxxxxxxf oo Başarısız !
4.iterasyon .*foo xfooxxxxxx foo Başarılı !

İkinci reluctant örneğinde ise, bütün karakterler tek tek okunur. Bir grup eşleşme bulunduktan sonra bu karakter atılır ve bir sonraki aramaya devam edilir. Detaylar aşağıdaki tabloda gösterilmektedir.

Adım İfade Okunan Kalan Eşleşme
1.iterasyon .*?foo x fooxxxxxxfoo Başarısız !
2.iterasyon .*?foo xf ooxxxxxxfoo Başarısız !
3.iterasyon .*?foo xfo oxxxxxxfoo Başarısız !
4.iterasyon .*?foo xfoo xxxxxxfoo Başarılı !
5.iterasyon .*?foo x xxxxxfoo Başarısız !
6.iterasyon .*?foo xx xxxxfoo Başarısız !
7.iterasyon .*?foo xxx xxxfoo Başarısız !
8.iterasyon .*?foo xxxx xxfoo Başarısız !
9.iterasyon .*?foo xxxxx xfoo Başarısız !
10.iterasyon .*?foo xxxxxx foo Başarısız !
11.iterasyon .*?foo xxxxxxf oo Başarısız !
12.iterasyon .*?foo xxxxxxfo o Başarısız !
13.iterasyon .*?foo xxxxxxfoo Başarılı !

Son possessive örneğinde ise tek iterasyonda işlem biter ve sonuç başarısızdır. Hatırlanacağı üzere, bir possessive quantifier' ı yalnızca bir kere tüm girdiyi kontrol eder. Şayet bir eşleşme bulamazsa geri dönmez ve aramayı sonlandırırdı. .* ifadesi ile ilk başta tüm karakterler okunur ve geriye hiç bir şey kalmaz. Bu noktada zaten araştırma tamamlanmıştır ve possessive işini bitirir. Çünkü bir kez daha zaten denemeyecektir. Detay aşağıdaki tabloda gösterilmektedir.

Adım İfade Okunan Kalan Eşleşme
1.iterasyon .*+foo xfooxxxxxxfoo   Başarısız !
There has been no comment yet

Name:


Question/Comment
   Please verify the image




The Topics in Computer Science

Search this site for





 

Software & Algorithms

icon

In mathematics and computer science, an algorithm is a step-by-step procedure for calculations. Algorithms are used for calculation, data processing, and automated reasoning.

Programming Languages

icon

A programming language is a formal constructed language designed to communicate instructions to a machine, particularly a computer. It can be used to create programs to control the behavior of a machine. Java,C, C++,C#

Database

icon

A database is an organized collection of data. The data are typically organized to model aspects of reality in a way that supports processes requiring information.

Hardware

icon

Computer hardware is the collection of physical elements that constitutes a computer system. Computer hardware refers to the physical parts or components of a computer such as the monitor, memory, cpu.

Web Technologies

icon

Web development is a broad term for the work involved in developing a web site for the Internet or an intranet. Html,Css,JavaScript,ASP.Net,PHP are one of the most popular technologies. J2EE,Spring Boot, Servlet, JSP,JSF, ASP

Mobile Technologies

icon

Mobile application development is the process by which application software is developed for low-power handheld devices, such as personal digital assistants, enterprise digital assistants or mobile phones. J2ME

Network

icon

A computer network or data network is a telecommunications network that allows computers to exchange data. In computer networks, networked computing devices pass data to each other along data connections.

Operating Systems

icon

An operating system is software that manages computer hardware and software resources and provides common services for computer programs. The OS is an essential component of the system software in a computer system. Linux,Windows

Computer Science

icon

Computer science is the scientific and practical approach to computation and its applications.A computer scientist specializes in the theory of computation and the design of computational systems.