Module 1: Regular Expressions Flashcards
What does a lexer do in programming languages?
The lexer is used to check the syntax of the code in a particular programming language.
It separates the nouns and verbs in a programming language.
What is the input into a lexer?
Inputs that go into a lexer are a series of bytes. (Just the program as bytes)
What are tokens in a programming language and what are they made of?
Tokens are meaningful words in a programming language. Tokens are made up of a series of strings.
What does a compiler writers do?
The compiler writers can understand and enforce the syntax
What is the output of a lexer?
It is a series of strings that make up tokens.
What is a string and how do we define a string over an alphabet ∑ (sigma)?
A string is alphabet symbols together.
A string over an alphabet ∑ (sigma) is a finite sequence of symbols from ∑ (sigma)
How is an ɛ (empty string) defined?
It is a string that is an ɛ empty sequence of symbols.
What happens if you concat a string with an ɛ empty string?
i.e. ɛs = s ɛ
When you concat a string with an ɛ you will get the string back. This does not matter the order of the operation at this point, the empty string can come first or last in the arithmetic operation.
ɛs = s ɛ = s
What does ∑* stand for?
The star operator contains all of the possible possibilities of combinations given a set.
So ∑* contains all of the strings that can be created by combining the alphabet symbols into a string.
Is language L a subset of ∑*?
Yes, language L is a subset of ∑*
Which of the following are infinite?
a. ∑
b. ∑*
c. L
b. ∑* is infinite
c. L can be both finite and infinite
Why do we need regular expressions?
We need regular expressions because tokens are typically specified using regular expressions.
Which of the following apply to regular expressions?
a. Compact
b. Expressive
c. Declarative
d. Vague
e. Precise
f. Widely used
g Hard to generate
h. Easy to generate
a. Compact
b. Expressive (expandable)
e. Precise (not ambiguous, will not match two specific defs)
f. Widely used
h. Easy to generate
What does compact mean in mathematics?
Compact means a set with no holes in it.
Which of the following are rules that a regular expression will follow:
a. Ø
b. ɛ
c. a, where a is not an element in the alphabet
d. a, where a is an element in the alphabet
e. R1 * R2, where R1 and R2 are regular expressions
f. R1 | R2, where R1 and R2 are regular expressions
g. R1 . R2, where R1 and R2 are regular expressions
h. (R), where R is a regular expression
i. R*, where R is a regular expression
a. Ø (null set)
b. ɛ
d. a, where a is an element in the alphabet
f. R1 | R2, where R1 and R2 are regular expressions
g. R1 . R2, where R1 and R2 are regular expressions
h. (R), where R is a regular expression
i. R*, where R is a regular expression
What is the cardinality of an empty string?
a. 0
b. 1
c. -1
d. 2
b. 1
Which of the following are true:
a. L(Ø) = 0
b. L(Ø) = Ø
c. L(ɛ) = { }
d. L(a) = { }
e. L(R1 | R2) = L(R1) U L(R2)
f. L(R1 . R2) = L(R1) . L(R2)
b. L(Ø) = Ø
c. L(ɛ) = { }
d. L(a) = { }
e. L(R1 | R2) = L(R1) U L(R2)
f. L(R1 . R2) = L(R1) . L(R2)
What does L(a | b) equal?
a. L(a) | L(b)
b. L(a) U L(b)
c. {a} U {b}
d. {a,b}
b. L(a) U L(b)
c. {a} U {b}
d. {a,b}
What does (a | b | c) equal?
a. L(a|b) U L(c)
b. L(a) | L(b) | L(c)
c. {a,b} U {c}
d. {a,b,c}
a. L(a|b) U L(c)
c. {a,b} U {c}
d. {a,b,c}
What does L(a | ɛ) equal?
a. L(a)
b. L(ɛ)
c. L(a) U L(ɛ)
d. {a}
e. {a} U {ɛ}
f. {a,ɛ}
c. L(a) U L(ɛ)
e. {a} U {ɛ}
f. {a,ɛ}
What does L(ɛ|ɛ) equal?
a. Null
b. {ɛ}
b. {ɛ}
What does the A . B equal given:
A = {aa, b}
B = {a,b}
a. {aa,a,b}
b. {aab,b,a,b}
c. {aaa,aab,ba,bb}
d. {aaa,ba,baa,bb}
c. {aaa,aab,ba,bb}
What does the A . B equal given:
A = {aa, b, ɛ}
B = {a,b}
a. {aaa,aab,ba,bb}
b. {ɛ}
c. {aaa,aab,ba,bb,a,b}
d. {aaa,ab,a,baa,bb,b}
c. {aaa,aab,ba,bb,a,b}
In order of operations what comes first in the following:
L(a | b .c)
a. a | b
b. b . c
b. b . c
What does L(a | b . c) evaluate to?
a. {a , bc}
b. {abc}
c. {b, ac}
d. {ab, c}
a. {a , bc}
L(a) U L(b . c) = {a} U {bc} = {a, bc}
What is the Kleene Star operator?
The kleene star operator is the * symbol that is used to indicate an infinite set.
What is the definition of L(R*)?
a. L^(i-1) . L(R)
b. U(subset i>=0) L^(i)(R)
b. U(subset i>=0) L^(i)(R)
What does L(a | b*) equal?
a. {b,bb,bbb,bbbb,…}
b. {a,b,bb,bbb,bbbb,…}
c. {a, ɛ,b,bb,bbb,bbbb,…}
c. {a, ɛ,b,bb,bbb,bbbb,…}
What does L((a | b)*) equal?
a. {ɛ}
b. {ɛ} U {a,b}
c. {a,b} U {aa,ab,ba,bb} U {aaa,aab,aba,baa,bab,bba,bbb} U …
d. {ɛ} U {a,b} U {aa,ab,ba,bb} U {aaa,aab,aba,baa,bab,bba,bbb} U …
d. {ɛ} U {a,b} U {aa,ab,ba,bb} U {aaa,aab,aba,baa,bab,bba,bbb} U …
The third is found by concating {a,b} . {a,b}.
The forth is found by concating {aa,ab,ba,bb} . {a,b}
Which of the following are valid ID’s given the following:
letter = a | b | c | d | e | ... | A | B | C | D | ... digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ID = letter(letter | digit | _ )*
a. a891_jksdbed
b. 12ajkdfjb
a. a891_jksdbed
How do we define a number given:
digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
pdigit = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
a. NUM = digit*
b. NUM = digit(digit)*
c. NUM = pdigit(digit)*
d. NUM = pdigit(digit)* | 0
d. NUM = pdigit(digit)* | 0
What is the longest matching prefix rule?
a. Starting from the next input symbol, find the longest string that matches a token.
b. Starting from the first input symbol, find the longest string that matches a token.
a. Starting from the next input symbol, find the longest string that matches a token.
What happens when you have a tie in the longest matching prefix rule?
If there is a tie between two prefix rules, then you use whichever rule was defined first in the rule list.
