Regular Expressions, Grammars & Parsing Flashcards
Regular expressions
A sequence of characters that define a search pattern and a regular language
|symbol meaning
symbol meaning
Boolean OR
() symbol meaning
Grouping (equivalent to | symbol)
. symbol meaning
Wild card- can match any one character
[^a] symbol meaning
Negation
gray|grey
gray or grey
gr(a|e)y
gray|grey = gray or grey
gr.y
gray, grey, groy, grzy etc..
? symbol meaning
zero or one occurrences of the preceding element
- symbol meaning
zero or more occurrences of the preceding element
{n}
the preceding item is matched exactly n times
{min, }
the preceding item is matched min or more times
{min, max}
the preceding item is matched at least min times, but not more than max times
colou?r
color, colour
ab*c
ac, abc, abbc, abbbc etc..
ab+c
abc, abbc, abbbc etc..
N is a set of
non-terminals
What is a non-terminal symbol?
Those symbols that are in the generation of the sentence but not the component of the sentence
Non-terminal examples
capital letters
Grammar
A finite set of formal rules for generating correct sentences (N, T, P, S)
Σ (or E) is a set of
terminals
What is a terminal symbol?
The components of the sentences generated using a grammar
Terminal symbol examples
lowercase letters
What’s the relationship between N and Σ
They are disjoint meaning they have no members in common
P is a set of
production rules
What are production rules?
A rewrite rule specifying a symbol substitution than can recursively perform to generate new symbol sequences
S is a
starting non-terminal and is a member of N
Regular grammar
Is a mathematical object consisting of 4 components G = (N, E, P, S)
Right regular grammar
All the non-terminals on the right-hand side exist at the rightmost place
B -> a
B is a non-terminal in N and a is terminal in Σ
B -> aC
B and C are non-terminals in N and a is in Σ
B -> Ca
B and C are in N and a is in Σ
B -> ε
B is in N and ε is the empty string
Context free grammar
The syntax or structure of a formal language defined by (N, Σ, P, S)
CFG is defined where
an alphabet Σ of terminals, a set N of non-terminals, a finite set P of productions
::== meaning
may expand into or may get replaced with
