Regex and BNF Flashcards
What is BNF
a notation used to define the grammar of a language. It describes how valid statements are structured using production rules.
Why do we need to use bnf
- some expressions cant be expressed with regEx or FSMs
- this class of languages called context free languages are more expressive than regular langs
::=
equals to
<>
surrounds category names and non terminal elements
what are terminal symbols
what are non terminal symbols
- terminal elements can be broken down
- non terminal cant be broken down
what is parsing
checking an input string against the set of BNF rules to see if its valid
parts of a syntax diagram and what are they used for
elipse - represents a terminal symbol
rectangle - a non terminal symbol
arrow above rectangle/circle(loop back) - non terminal element that may be used more than once
what is syntax
strict rules a program must follow regarding their structure
what does bnf consist of
- set of terminal symbols
- set of non terminal symbols
- set of production rules
what type of language is BNF
meta language
what are production rules
rules that define the syntax of a language by specifying how symbols can be expanded into other symbols or terminal values.
what is a subset
A set A is a subset of B (A ⊆ B) if every element in A is also in B.
what is a proper subset
A set A is a proper subset of B (A ⊂ B) if A ⊆ B and A ≠ B (A has fewer elements than B).
What is a countable set?
A set is countable if it has the same number of elements as some subset of the natural numbers ℕ.
What does ⊂ mean?
It means “proper subset” – A ⊂ B means A is contained in B, but B has extra elements not in A.
What is membership in set theory
If an element x belongs to a set A, we write x ∈ A.
What does ⊆ mean?
“subset” – A ⊆ B means A is contained in B, but A could be equal to B.
What is union (A ∪ B)
The union of A and B is a set containing all elements from both A and B.
What is intersection (A ∩ B)
The intersection of A and B is a set containing only elements that are in both A and B.
What is the difference between two sets (A \ B)?
A \ B (or A - B) is the set of elements that are in A but not in B.
what do these mean:
[01]
{2,4}
- (only 0 or 1 allowed)
- (length must be between 2 and 4)
Explain what this regex means: [a-zA-Z][a-zA-Z0-9]{5,9}
- First character must be a letter (uppercase or lowercase).
- The next 5 to 9 characters can be letters or numbers
Why can’t regular expressions describe nested structures like (()())
- Regular expressions lack recursion.
- They can’t track nested structures like parentheses, which require context-free grammar (BNF).
Why can FSMs recognize regular languages but not context-free ones?
FSMs lack memory (they can’t track nested structures), but context-free languages require a stack to keep track of recursion
