faqts : Computers : Programming : Languages : Delphi

+ Search
 Add Entry AlertManage Folder Edit Entry Add page to http://del.icio.us/
Did You Find This Entry Useful?

7 of 14 people (50%) answered Yes
Recently 5 of 10 people (50%) answered Yes

Entry

Delphi: Search: Regular expression: Create: How to create a regular expression parser in Delphi?

Aug 19th, 2005 10:21
Knud van Eeden, 


----------------------------------------------------------------------
--- Knud van Eeden --- 19 October 2003 - 01:48 am --------------------

---

Delphi: Search: Regular expression: Create: How to create a regular 
expression parser in Delphi?

---

The usual method contains 3 parts.

---

Steps: Overview:

 1. -Parse your given regular expression in its tokens

     1. Look closely at the Backus Naur form for the regular expression

     2. Create a top down parser from this

        1. For each production rule you create a separate procedure

 2. -Convert this tokens in a datastructure that can be used for
     matching the text you want to search later

     1. Create a dequeue (=a combination of a stack and a queue, you
        can insert new items at both ends)

        1. Create a table (e.g. array) which represents the states of
           your non-deterministic state machine for this regular
           expression (your regular expression is just a special case
           of a non-deterministic state machine)

 3. -Use this dequeue datastructure (e.g. table as an array) to search
     for the matching strings in your text

---
---

Internet: see also:


[Internet: see also: http://www.google.com search for 'regular 
expression searching Delphi create': 
http://www.bsdg.org/swag/DELPHI/0465.PAS.html]

---
---

Book: see also:

---

Recommended:

[book: see also: Bucknall, Julian - the Tomes of Delphi: Algorithms 
and Datastructures - p. 380 - 'Using regular expressions' - 
http://www.amazon.com/exec/obidos/tg/detail/-
/1556227361/qid=1065748783/sr=1-1/ref=sr_1_1/002-0122962-7851254?
v=glance&s=books]

---

Recommended:

[book: see also: Sedgewick, Robert - Algorithms (2nd edition) - p. 
293 - 'Pattern matching', p. 305 - 'Parsing' - 
http://www.amazon.com/exec/obidos/ASIN/0201066734/qid%3D1066520724/sr%
3D11-1/ref%3Dsr%5F11%5F1/103-7895116-2553433]

---

[book: see also: Kernigan / Plauger - software tools in Pascal - p. 
141 - 'Text patterns' - http://www.amazon.com/exec/obidos/tg/detail/-
/0201103427/ref=lib_dp_TFCV/103-7895116-2553433?
v=glance&s=books&vi=reader#reader-link]

---

[book: see also: Wirth, Niklaus - algorithms + datastructures = 
programs - p. 288 -Constructing a syntax graph', p. 291 -
 'Constructing a parser for a given syntax', p. 292 - 'Rules of graph 
to program translation', p. 295 - 'Constructing a table driven parsing 
program' - http://www.amazon.com/exec/obidos/tg/detail/-
/0130224189/qid=1066523226/sr=1-1/ref=sr_1_1/103-7895116-2553433?
v=glance&s=books]

---
---

Other books:

I checked further also the following books, but they were of not much
direct use here in showing some ready to use and also easy ways to
write a regular expression analyzer, compared with the above books
(in my current opinion)

---

[book: Wirth, Niklaus - compiler construction - 
http://www.amazon.com/exec/obidos/tg/detail/-
/0201403536/qid=1066525626/sr=8-1/ref=sr_8_1/103-7895116-2553433?
v=glance&s=books&n=507846]

---

[book: Wirth, Niklaus - systematic programming (an introduction) - p. 
116 - 'Recognition of regular patterns of symbols' - 
http://www.amazon.com/exec/obidos/ASIN/0138803692/qid%3D1066523406/sr%
3D11-1/ref%3Dsr%5F11%5F1/103-7895116-2553433]

---

[book: Gries, David - compiler construction for digital computers - p. 
59, 60 - 'Regular expressions' - 
http://www.amazon.com/exec/obidos/ASIN/0471327719/qid%3D1066523093/sr%
3D11-1/ref%3Dsr%5F11%5F1/103-7895116-2553433]

---

[book: Aho, Alfred V. / Ullman, Jeffrey D. - foundations of computer 
science (C edition) - p. 5, 556-590, 634-639 - 'Regular 
expressions'http://www.amazon.com/exec/obidos/tg/detail/-
/0716782847/qid=1066522675/sr=1-1/ref=sr_1_1/103-7895116-2553433?
v=glance&s=books]

---

[book: Tremblay, Jean-Paul / Sorenson, Paul G. - the theory and 
practice of compiler writing - p. 151-155, 170-181 - 'Regular 
expression' - http://www.amazon.com/exec/obidos/ASIN/0070651612/qid%
3D1066522362/sr%3D11-1/ref%3Dsr%5F11%5F1/103-7895116-2553433]

---

[book: Fischer, Charles N. / Le Blanc, Richard J. - crafting a 
compiler - http://www.amazon.com/exec/obidos/tg/detail/-
/0805332014/qid=1066522031/sr=8-1/ref=sr_8_1/103-7895116-2553433?
v=glance&s=books&n=507846]

---

[book: Bornat, Richard - understanding and writing compilers - 
http://www.amazon.com/exec/obidos/tg/detail/-
/0333217322/qid=1066522172/sr=8-1/ref=sr_8_1/103-7895116-2553433?
v=glance&s=books&n=507846]

---

[book: Aho, Alfred V. / Sethi, Ravi / Ullman, Jeffrey D. - compilers 
(principles, techniques and tools) - 
http://www.amazon.com/exec/obidos/tg/detail/-
/0201100886/qid=1066522256/sr=8-1/ref=sr_8_1/103-7895116-2553433?
v=glance&s=books&n=507846]

---

[book: Mak, Ronald - writing compilers and interpreters (an applied 
approach using C++) - http://www.amazon.com/exec/obidos/tg/detail/-
/0471113530/qid=1066522305/sr=1-1/ref=sr_1_1/103-7895116-2553433?
v=glance&s=books]

---

[book: Knuth, Donald E. - the art of computer programming (I, II, 
III) - http://www.amazon.com/exec/obidos/tg/detail/-
/0201485419/qid=1066522875/sr=2-1/103-7895116-2553433?v=glance&s=books]

---

[book: Levine, John R. / Mason, Tony / Brown, Doug - Lex & Yacc - 
http://www.amazon.com/exec/obidos/tg/detail/-
/1565920007/qid=1066525729/sr=1-1/ref=sr_1_1/103-7895116-2553433?
v=glance&s=books]

---

[book: Hopgood, F. R. A. - compiling techniques - 
http://www.amazon.com/exec/obidos/ASIN/0356024741/qid%3D1066525866/sr%
3D11-1/ref%3Dsr%5F11%5F1/103-7895116-2553433]

---

[book: Steele, Dennis R. - an introduction to elementary and compiler 
design - http://www.amazon.com/exec/obidos/ASIN/044400243X/qid%
3D1066525943/sr%3D11-1/ref%3Dsr%5F11%5F1/103-7895116-2553433]

---

[book: Hansen, Brinch - on Pascal compilers - 
http://www.amazon.com/exec/obidos/ASIN/0130830984/qid%3D1066526017/sr%
3D11-1/ref%3Dsr%5F11%5F1/103-7895116-2553433]

---

[book: Davie, A. J. T. / Morrison, R. - Recursive descent compiling - 
http://www.amazon.com/exec/obidos/tg/detail/-
/0853123861/qid=1066526107/sr=1-1/ref=sr_1_1/103-7895116-2553433?
v=glance&s=books]

---

[book: Hunter, Robin - compilers, their design and construction using 
Pascal - http://www.amazon.com/exec/obidos/tg/detail/-
/0471280542/qid=1066526194/sr=1-1/ref=sr_1_1/103-7895116-2553433?
v=glance&s=books]

---
---

Internet: see also:

---

Compiler: Grammar: Expression: Regular: Which grammar defines set of 
all regular expressions? [BNF]
http://www.faqts.com/knowledge_base/view.phtml/aid/25950/fid/1263

---

Datastructure: Queue: Dequeue: Definition: What is a dequeue?
http://www.faqts.com/knowledge_base/view.phtml/aid/25930/fid/1280

---

Delphi: Search: Regular expression: How to add regular expression 
searching to Delphi? [Systools]
http://www.faqts.com/knowledge_base/view.phtml/aid/25295/fid/175

---

TSE: Search/Replace:Regular Expression:Backus Naur Form:What is 
possible BNF for regular expression?
http://www.faqts.com/knowledge_base/view.phtml/aid/25714/fid/1236

---

PERL:Search/Replace:Regular Expression:Backus Naur Form:What is 
possible BNF for regular expression?
http://www.faqts.com/knowledge_base/view.phtml/aid/25718/fid/200

---

Compiler: Language: Overview: Hierarchy: Chomsky: Model: What is the 
Chomsky hierarchy?
http://www.faqts.com/knowledge_base/view.phtml/aid/25862/fid/1258

---

Integrating PowerGrep and RegExBuddy with your applications
http://www.regexbuddy.com/integration.html

---

Delphi and .NET regular expression integration
http://www.regexbuddy.com/delphi.html

----------------------------------------------------------------------