Regular Expressions, Grammars & Parsing Flashcards
What is an alphabet in regex?
- Alphabet = finite set of fundamental units
- Unit = Symbols, letters and tokens
What is a language in regex?
Language = alphabet + (exhaustive list of valid words/ a set of rules defining acceptable words)
What are words in regex?
- Words = finite strings that are permissible in the language
What is ε in regex
- ε = Empty/null string
How do you represent concatentation?
How do you represent choice
How do you represent none or more?
How do you represent one or more?
What is regex?
Regular Expressions (Regex)
Sequence of characters that define a search pattern AND defines a regular language
Set of regex = rules that define a language
Give an example of regex
Give a general example of regex
Search & Find Processes
- Given a regular expression
- Search through set of strings
- To find all matching instances
- Report back what has been found (Can include locations)
Give an example of search and find
These are commands to run in the OSs terminal
Win11 = findstr /r [REGEX GOES HERE] filename
Linux = egrep [REGEX GOES HERE] filename
Limitation - this doesn’t work if there are line breaks in the string you want to find because it wont fit the requested string in the regex
What are read inputs in grammar?
- A particular form of an input for grammar
- Formatted document = webpage
- Source code
- Arithmetical expression or mathematical formular
What are rule description in grammar?
- Defines the input format
- Used to recognise/accept the input
- Includes error checking
- Start to process a correctly formatted input
Explain the tuples to describe grammar
What is right grammar?
What is left grammar?
How do you use | in regular grammar?
How do you describe Context Free Grammars?
What is BNF
How do you write production rules in BNF?
What is option in BNF?
What is repetition in BNF?
What is grouping in BNF?
What is the chomsky hierarchy of languages?
