Regular Expressions - Kutztown University of Pennsylvania

Regular Expressions - Kutztown University of Pennsylvania

Syntax Specification Regular Expressions 1 Phases of Compilation 2 Syntax Analysis Syntax: Websters definition: 1 a : the way in which linguistic elements (as words) are put together to form constituents (as phrases or clauses)

The syntax of a programming language Describes its form i.e. Organization of tokens (elements) Formal notation Context Free Grammars (CFGs) 3 Review: Formal definition of tokens A set of tokens is a set of strings over an alphabet {read, write, +, -, *, /, :=, 1, 2, , 10, , 3.45e-3, }

A set of tokens is a regular set that can be defined by comprehension using a regular expression For every regular set, there is a deterministic finite automaton (DFA) that can recognize it i.e. determine whether a string belongs to the set or not Scanners extract tokens from source code in the same way DFAs determine membership 4 Regular Expressions A regular expression (RE) is: A single character

The empty string, The concatenation of two regular expressions Notation: RE1 RE2 (i.e. RE1 followed by RE2) The union of two regular expressions Notation: RE1 | RE2 The closure of a regular expression Notation: RE* * is known as the Kleene star

* represents the concatenation of 0 or more strings Non-null enumeration Notation: RE+ represents all non-null concatenations of RE (1 or more times) 5 Regular Expressions Basics Let alphabet ={a,b} (means a and b are its only letters) a*=(, a, aa, aaa, ...} (ab)*=(, ab, abab, ababab, ...} a b=(a, , b, bb, bb, ...} (a b)*= all strings containing as and bs

(a*b*)*=(ab*)*= all strings containing as and bs a*b*={aibj| i >=0, j>=0) 6 Building Regular Expressions Regular Expressions as Language * while loop iterates 0 or more times concatenation uv sequential; first u, then v uv OR select from one or the other or both

7 Description Regular Expression Let ={a,b} all expressions over this alphabet Strings with exactly one a b*ab* exactly two as one or more as even number of as b*ab*ab* (b*ab*)* or (a b)*a (a b)*

(b*ab*ab*)* even number of as and exactly one b (aa)*b(aa)* (aa)*ab(aa)*a odd number of as (b*ab*ab*)*b*ab* that dont contain aa (b ab)*( a) 8 Regular Expression Description Same alphabet

(aa)* even number of as (a b) (a b) (a b) (a b) all strings of length 4 ((a b) (a b) (a b) (a b))* strings of length divisible by 4 (aa)* ((a b) (a b) (a b) (a b))* strings of as of length divisible by 4 9 Token Definition Example

Numeric literals in Pascal Definition of the token unsigned_number digit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 unsigned_integer digit digit* | digit+ unsigned_number unsigned_integer ( ( . unsigned_integer ) | ) ( ( e ( + | | ) unsigned_integer ) | ) Recursion is not allowed in Regular Expressions! 10 Exercise digit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 unsigned_integer digit digit*

unsigned_number unsigned_integer ( ( . unsigned_integer ) | ) ( ( e ( + | | ) unsigned_integer ) | ) Regular expression for Decimal numbers number 11 Exercise digit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 unsigned_integer digit digit* unsigned_number unsigned_integer ( ( . unsigned_integer ) | ) ( ( e ( + | | ) unsigned_integer ) | )

Regular expression for Decimal numbers number ( + | | ) unsigned_integer ( ( unsigned_integer ) | ) 12 Exercise digit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 unsigned_integer digit digit* unsigned_number unsigned_integer ( ( . unsigned_integer ) | ) ( ( e ( + | | ) unsigned_integer ) | ) Regular expression for

Identifiers identifier 13 Exercise digit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 unsigned_integer digit digit* unsigned_number unsigned_integer ( ( . unsigned_integer ) | ) ( ( e ( + | | ) unsigned_integer ) | ) Regular expression for Identifiers identifier letter ( letter | digit | )*

letter a | b | c | | z 14

Recently Viewed Presentations

  • Ring, Ring… Whose there? The Law!?!? - Texas Real Estate

    Ring, Ring… Whose there? The Law!?!? - Texas Real Estate

    Examples. 1) Grandmother and father of murdered children who brought suit under 18 USCS § 2511 because their private prayers and conversations were recorded at outdoor grave site memorial service by electronic surveillance microphone placed in funeral urn did not...
  • Chapter 1

    Chapter 1

    Chapter 7 Motivation and Emotion Motivation and Emotion What Is Motivation? The driving force within individuals that impels them to action It is produced by a state of arousal or tension, which exists as the result of an unfulfilled need...
  • Ch. 8: Quantities in Chemical Reactions

    Ch. 8: Quantities in Chemical Reactions

    3H2(g) + N2(g) 2NH3(g) IV. Real-life Reactions In reality, we cannot have complete conversion to products. Even if there was complete conversion, difficult to actually collect all of the product. IV. Reaction Yields Stoichiometry gives us theoretical yield. What is...
  • Department of Defense Combating Trafficking in Persons Investigative

    Department of Defense Combating Trafficking in Persons Investigative

    The Petty Officer who pandered the victim pleaded guilty at a trial in the Eastern District of California to five counts of Pimping a Minor, one count of Possession of Child Pornography, one count of Use of a Minor for...
  • 2006-2007 High School Planning Packet

    2006-2007 High School Planning Packet

    Naviance. account . to find updated high school information and applications (check Team News for Naviance information) Get familiar with the school websites you are applying to for next year - you can learn a lot by searching these sites...
  • Assessor  Mr. Douglas Wolf How to Ruffle Ridges

    Assessor Mr. Douglas Wolf How to Ruffle Ridges

    Founded in 1979, TMA is the leader in assisting state and local governments with their revenue enhancement initiatives, with over 150 professionals who are recognized as experts in their filed and multiple national offices. ... B 19 19 18 18...
  • Cukr - Rvp

    Cukr - Rvp

    Autorem materiálu a všech jeho částí, není-li uvedeno jinak, je Bc. Lada Marholdová. Dostupné z Metodického portálu www.rvp.cz, ISSN: 1802-4785. Provozuje Národní ústav pro vzdělávání, školské poradenské zařízení a zařízení pro další vzdělávání pedagogických pracovníků (NÚV).
  • The Math Lecture - Kennesaw State University

    The Math Lecture - Kennesaw State University

    The Math Lecture(boiled down, yet lightly salted) Overview. For 2D games, ... Trig functions are defined by the relationships of the sides of a triangle. Commonly used: sine, cosine, tangent and cotangent ... How can we determine how much light...