1. Do not use any external libraries/functions 2. The code must be compiled with gcc & in linux environment 3. The zip folder has 2 PDFs, Project 2 & Project 2 presentation. The 2nd one is basically...

36952/CSE340S19-Project2-Presentation.pdf
PROJECT 2: Useless Symbols,
FIRST and FOLLOW sets, and
Predictive Parsing
CSE 340 Spring 2019
Rida A. Bazzi
Project 2 Goals
▪ I have introduced in class predictive parsing and FIRST and FOLLOW
sets
▪ The goal of this project is to show you how the process of building a
predictive parser can be automated
▪ Another important goal of the project is to give you experience in
writing a substantial program which is non-trivial conceptually
– This will make you a better programmer
– You will have a better understanding of the power of abstraction in building code
– You will have a better appreciation of the material covered so far
Outline
▪ Set representation
▪ Grammar representation
▪ Calculating useless symbols
▪ Calculating FIRST sets
▪ Calculating FOLLOW sets
▪ Determining if a grammar has a predictive parser
Bit-vector representation of Sets
▪ In these slides I show a bit-vector representation of sets which can be
much more efficient when the total number of elements that can
belong to a set is known ahead of time and is not very large
▪ The bit vector representation is not as efficient if we want to initialize
sets often
▪ You do not have to use this representation. You can use any set
representation you want.
Bit-vector representation of Sets
▪ We can assign an index to each element that can be part of a set. Here we have:
“a” has index 0
“b” has index 1
“c” has index 2
...
“a” “b” “c” “d” “e”
0 1 2 3 4
Bit-vector representation
▪ We can assign an index to each element that can be part of a set. Here we have:
“a” has index 0
“b” has index 1
“c” has index 2
...
▪ A set is a bit vector (or Boolean vector) indicating which elements are in the set and
which elements are not in the set
“a” “b” “c” “d” “e”
0 1 2 3 4
Bit-vector representation
▪ We can assign an index to each element that can be part of a set. Here we have:
▪ A set is a bit vector (or Boolean vector) indicating which elements are in the set
and which elements are not in the set
EXAMPLES
{ “a”, “b” }
“a” “b” “c” “d” “e”
0 1 2 3 4
T T F F F
0 1 2 3 4
{ “a”, “b”, “c”, “d”, “e” }
Bit-vector representation
▪ We can assign an index to each element that can be part of a set. Here we have:
▪ A set is a bit vector (or Boolean vector) indicating which elements are in the set
and which elements are not in the set
EXAMPLES
{ “a”, “b” }
“a” “b” “c” “d” “e”
0 1 2 3 4
T T F F F
0 1 2 3 4
{ “a”, “b”, “c”, “d”, “e” }
✓ ✓
✘ ✘ ✘
Bit-vector representation
▪ We can assign an index to each element that can be part of a set. Here we have:
▪ A set is a bit vector (or Boolean vector) indicating which elements are in the set and
which elements are not in the set
EXAMPLES
{ “a”, “b” , “e”}
“a” “b” “c” “d” “e”
0 1 2 3 4
T T F F T
0 1 2 3 4
{ “a”, “b”, “c”, “d”, “e” }
✓ ✓ ✓
✘ ✘
Operations on sets: Union
Example: { “a”, “c” } ∪ { “a”, “e” }
T F F F T
0 1 2 3 4
{ “a”, “c” }
{ “a”, “e” }
T F T F T
0 1 2 3 4
{ “a”, “c”, “e” }
In general
S1, S2, S3
for i = 0 to universe_size - 1
S3[i] = S1[i] or S2[i]
T F T F F
0 1 2 3 4
Operations on sets: Membership
boolean is_element(S : set, i : integer)
{
if ( (i > = 0) && (i < universe_size – 1) )
return S[i];
else
return false;
}
Operations on sets: Printing a set
boolean print_set(S : set)
{
for ( i = 0 to universe_size – 1 )
if S[i] then
print universe[i]; // this does not print commas
// or parentheses
}
“a” “b” “c” “d” “e”
0 1 2 3 4
universe
Summary
▪ Universe array contains the actual names of the elements
▪ For all set manipulations, an element is simply an index
▪ An element is in a set if the array entry corresponding to the element
is true
▪ To print an element, print the corresponding entry in the universe
array
Grammar Representation
Universe for FIRST and FOLLOW sets
All Symbols
Rule 1
LHS 6
RHS 7 8 9
RHS_size: 3
S ➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e”
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Grammar Representation
Universe for FIRST and FOLLOW sets
All Symbols
Rule 2
LHS 7
RHS 10 11
RHS_size: 2
S ➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e”
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Grammar Representation
Universe for FIRST and FOLLOW sets
All Symbols
Rule 2
LHS 8
RHS 2 8
RHS_size: 2
S ➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e”
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Grammar Representation
Universe for FIRST and FOLLOW sets
All Symbols
Rule 2
LHS 8
RHS 0
RHS_size: 1
S ➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e”
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Grammar Representation
▪ You need a list of all the rules: this can simply be a vector of rules
▪ Every rules has a LHS which is an integer index
▪ Every rule has a RHS which is a vector of integers, one integer for
every symbol on the RHS
▪ To put the LHS and RHS together you can declare a structure with
two fields, one for the LHS and one for the RHS
Grammar Representation Example
All Symbols
S ➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e”
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
LHS: 6 RHS: 7, 8, 9
LHS: 7 RHS 10, 11
LHS: 8 RHS 2 , 8
Universe for FIRST and FOLLOW sets
LHS: 8 RHS 0
LHS: 9 RHS 3, 9
LHS: 9 RHS 0
LHS: 10 RHS 4, 10
LHS: 10 RHS 0
LHS: 11 RHS 5, 11
LHS: 11 RHS 0 Rules
Grammar Representation
▪ Once you have a vector of rules, you can easily iterate over all the
rules
▪ Also, for a given rule, you can easily iterate over the RHS
▪ For calculating FIRST sets (see later also), you will need to be
referring to FIRST[rule.LHS] or FIRST[rule.RHS[j]]
▪ Having all entries as integer indices makes the code easier to work
with
▪ The strings (names of various symbols) are only needed when the
output is produced
Useless Symbols
A symbol is useless if it does not appear in the derivation of a string of
terminals or in the derivation of the empty string
A symbol is not useless if it appears in the derivation of a string of
terminals or in a derivation of the empty string
* *
S ⇒ x A y ⇒ w ∈ T*
Calculating Useless Symbols
▪ We start by calculating generating symbols
– A symbol is generating if it can derive a string in T* (zero or more sequence of
terminals)
▪ Then we determine reachable symbols
– A symbol A is reachable if S can derive a sentential form containing the symbol:
*
S ⇒ x A y
Calculating generating symbols
1. Initialization
▪ all terminals are generating
▪ ɛ is generating
2. If A ➝A1 A2 ... Ak is a grammar rule and
▪ A1 generating and
▪ A2 generating and
▪ ... and
▪ ...
▪ Ak generating
A is
generating
Iterative approach to calculating
generating symbols
S ➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
F
F
F
F
F
F
F
F
F
F
F
F
Symbols 0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Generating
array
Iterative approach to calculating
generating symbols: Initialization
S ➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
T
F
T
T
T
T
F
F
F
F
F
F
Symbols 0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Generating
array
Iterative approach to calculating
generating symbols: Iteration
▪ No change
S➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
T
F
T
T
T
T
F
F
F
F
F
F
Symbols 0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Generating
array
S ➝A B C (1)
A➝D E (2)
B ➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
Iterative approach to calculating
generating symbols: Iteration
▪ No change
T
F
T
T
T
T
F
F
F
F
F
F
Symbols 0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Generating
array
S ➝A B C (1)
A ➝D E (2)
B➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
Iterative approach to calculating
generating symbols: Iteration
▪ No change
T
F
T
T
T
T
F
F
F
F
F
F
Symbols 0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Generating
array
S ➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
Iterative approach to calculating
generating symbols: Iteration
▪ B is generating
T
F
T
T
T
T
F
F
F
F
F
F
Symbols 0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Generating
array
S ➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
Iterative approach to calculating
generating symbols: Iteration
▪ B’s entry changes to true
T
F
T
T
T
T
F
F
T
F
F
F
Symbols 0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Generating
array
S ➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
Iterative approach to calculating
generating symbols: Iteration
▪ No change
T
F
T
T
T
T
F
F
T
F
F
F
Symbols 0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Generating
array
S ➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
Iterative approach to calculating
generating symbols: Iteration
▪ C is generating
T
F
T
T
T
T
F
F
T
F
F
F
Symbols 0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Generating
array
S ➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
Iterative approach to calculating
generating symbols: Iteration
▪ C’s entry changes to true
T
F
T
T
T
T
F
F
T
T
F
F
Symbols 0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Generating
array
S ➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
Iterative approach to calculating
generating symbols: Iteration
▪ At the end of the first round (going over
all rules), we get the array on the right
▪ Since some entries have changed, we
need to do another round
T
F
T
T
T
T
F
F
T
T
T
T
Symbols 0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Generating
array
S ➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
Iterative approach to calculating
generating symbols: Iteration
▪ We examine the first rule again, but we
cannot tell that S is generating because
A is not generating
T
F
T
T
T
T
F
F
T
T
T
T
Symbols 0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Generating
array
S ➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
Iterative approach to calculating
generating symbols: Iteration
▪ We examine the second rule and now we
can tell that A is generating
T
F
T
T
T
T
F
F
T
T
T
T
Symbols 0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Generating
array
S ➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
Iterative approach to calculating
generating symbols: Iteration
▪ So we change A’s entry to true
T
F
T
T
T
T
F
T
T
T
T
T
Symbols 0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Generating
array
S ➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
Iterative approach to calculating
generating symbols: Iteration
▪ The remaining rules do not result in any
change
▪ But since some entries have changed in
the second round, we need to do a third
round
T
F
T
T
T
T
F
T
T
T
T
T
Symbols 0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Generating
array
S ➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
Iterative approach to calculating
generating symbols: Iteration
▪ In the third round, we determine that S is
generating
▪ Since some entries changed in the third
round, we need to do a fourth round
T
F
T
T
T
T
T
T
T
T
T
T
Symbols 0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Generating
array
S ➝A B C (1)
A ➝D E (2)
B ➝ b B (3)
B ➝ ɛ (4)
C ➝ c C (5)
C ➝ ɛ (6)
D ➝ d D (7)
D ➝ ɛ (8)
E ➝ e E (9)
E ➝ ɛ (10)
Iterative approach to calculating
generating symbols: Iteration
▪ In the fourth round nothing changes and
we have our answer
T
F
T
T
T
T
T
T
T
T
T
T
Symbols 0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Generating
array
Updating the grammar
▪ After we calculate generating symbols, we remove all rules that have
a symbol that is not generating
▪ We do not have to explicitly delete any rules
– We can use a boolean array to indicate which rules are eliminated and which are
not eliminated
Calculating Useless Symbols
▪ We start by calculating generating symbols
– A symbol is generating if it can derive a string in T* (zero or more sequence of
terminals)
▪ Then we remove all rules that have a symbol that is not generating
▪ Then we determine reachable symbols
– A symbol A is reachable if S can derive a sentential form containing the symbol:
*
S ⇒ x A y
Calculating reachable symbols
1. S is reachable
2. If A ➝A1 A2 ... Ak is a grammar rule
and A is reachable
A1 and A2 and
... and Ak
are reachable
Calculating reachable symbols
▪ Calculation can be done in a way that is similar to how we did
generating symbols
▪ We only consider rules that have not been eliminated in our
calculation
▪ At the end, we have a boolean array indicating which symbols are
reachable
FIRST sets Initialization
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e”
0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”
Symbols
FIRST and FOLLOW universe
T F F F F F
F F F F F F
F F T F F F
F F F T F F
F F F F T F
F F F F F T
F F F F F F
F F F F F F
F F F F F F
F F F F F F
F F F F F F
F F F F F F
FIRST sets Initialization
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e”
0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”Symbols
FIRST(“#”) = { “#” }T F F F F F
F F F F F F
F F T F F F
F F F T F F
F F F F T F
F F F F F T
F F F F F F
F F F F F F
F F F F F F
F F F F F F
F F F F F F
F F F F F F
FIRST and FOLLOW
universe
FIRST(“$”) = { }
FIRST(“b”) = { “b” }
FIRST(“c”) = { “c” }
FIRST(“d”) = { “d” }
FIRST(“e”) = { “e” }
FIRST sets Initialization
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e”
0
1
2
3
4
5
6
7
8
9
10
11
“#” “$” “b” “c” “d”
0 1 2 3 4 5
“e” “S” “A” “B” “C” “D”
6 7 8 9 10 11
“E”Symbols
T F F F F F
F F F F F F
F F T F F F
F F F T F F
F F F F T F
F F F F F T
F F F F F F
F F F F F F
F F F F F F
F F F F F F
F F F F F F
F F F F F F
FIRST and FOLLOW
universe
FIRST(“S”) = { }
FIRST(“A”) = { }
FIRST(“B”) = { }
FIRST(“C”) = { }
FIRST(“D”) = { }
FIRST(“E”) = { }
Things to think about
▪ You should decide on the data structures you will be using. Things
you need to represent are
– initial list of non-terminals
– initial list of terminals
– you should think about how these lists will be used for the various tasks and if
they need to be combined into a larger list of symbols
– grammar rules: LHS, RHS
– Set representation. You should think about the operation you will need to be
doing on sets
▪ Before you start coding, you should have any outline of how you will
be using your data structures to implement the various tasks
▪ Before you start coding, make you you have a correct understanding
of the requirements
36952/CSE340S19_Project2.pdf
CSE340 Spring 2019 Project 2
Due: March 1st 2019 by 11:59pm MST
1 Note
You should read the description carefully. Multiple readings are recommended. You will not be able to understand everything on
a first reading. Give yourself time by starting early and taking breaks between readings. You will digest the requirements better.
• The answers to many of your questions can be found in the description.
• Do no start coding until you have a complete understanding of the requirements
• Ask for help early.
• Have fun!
2 Overview
In this project, you are asked to write a C++ program that reads a description of a context free grammar, then, depending on
the command line argument passed to the program, performs one of the following tasks:
1. print the list of non-terminals followed by the list of terminals in the order in which they appear in the grammar rules,
2. find useless symbols in the grammar and remove rules with useless symbols,
3. calculate FIRST sets,
4. calculate FOLLOW sets , or
5. determine if the grammar has a predictive parser.
We provide you code to read the command line argument into a integer variable. Depending on the value of the variable, your
program will invoke the appropriate functionality.
3 Input Format
The following context-free grammar specifies the input format:
Rule-list → Rule Rule-list | Rule
Id-list → ID Id-list | ID
Rule → ID ARROW Right-hand-side HASH
Right-hand-side → Id-list | �
The tokens used in the above grammar description are defined by the following regular expressions:
1
ID = letter (letter + digit)*
HASH = #
DOUBLEHASH = ##
ARROW = ->
Where digit is the digits from 0 through 9 and letter is the upper and lower case letters a through z and A through Z.
Tokens are case-sensitive. Tokens are space separated and there is at least one whitespace character between any two successive
tokens. We provide a lexer with a geToken() function to recognize these tokens. You should use the provided lexer in you solution.
4 Semantics
Each grammar Rule starts with a non-terminal symbol (the left-hand side of the rule) followed by ARROW, then followed by a
sequence of zero or more terminals and non-terminals, which represent the right-hand side of the rule. If the sequence of terminals
and non-terminals in the right-hand side is empty, then the right hand side represents �.
The set of non-terminals for the grammar is the set of symbols that appear to the left of an arrow. Grammar symbols that do
not appear to the left of an arrow are terminal symbols. The start symbol of the grammar is the left hand side of the first rule of
the grammar.
Note that the convention of using upper-case letters for non-terminals and lower-case letters for terminals that I typically
followed in class does not apply in this project.
4.1 Example
Here is an example input:
decl -> idList colon ID #
idList -> ID...