Regular Expressions, Grammars & Parsing Flashcards
(36 cards)
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
