Mixing
How to find first set?
up vote
0
down vote
favorite
I am trying to list the First set of a given grammar with this function:
Note: char c - the character to find the first set;first_set - store elements of the corresponding first set;q1, q2 - the previous position;rule- store all the grammar rule line by line listed below;
for the first time the parameters are ('S', 0, 0).
void findfirst(char c, int q1, int q2){
if(!(isupper(c)) || c=='$'){
first_set[n++] = c;
}
for(int j=0;j<rule_number;j++){
if(rule[j][0]==c){
if(rule[j][2]==';'){
if(rule[q1][q2]=='')
first_set[n++] = ';';
else if(rule[q1][q2]!='' &&(q1!=0||q2!=0))
findfirst(rule[q1][q2], q1, (q2+1));
else
first_set[n++] = ';';
}
else if(!isupper(rule[j][2]) || rule[j][2]=='$')
first_set[n++] = rule[j][2];
else
findfirst(rule[j][2],j,3);
}
}
}
But found that if the given grammar looks like this:
S AC$
C c
C ;
A aBCd
A BQ
B bB
B ;
Q q
Q ;
(which the left hand side or any capital letters in the right hand side are non-terminal, and any small case letters are terminal)
the function couldn't correctly output the first set for S, since it will stop at finding the first set of Q and store ';' to the first set and won't go on to find C's first set.
Does anyone have a clue? Thanks in advance.
c++ compiler-construction
edited 2 days ago
Rhathin
5371313
asked 2 days ago
Lykas
357
add a comment |
up vote
0
down vote
favorite
I am trying to list the First set of a given grammar with this function:
Note: char c - the character to find the first set;first_set - store elements of the corresponding first set;q1, q2 - the previous position;rule- store all the grammar rule line by line listed below;
for the first time the parameters are ('S', 0, 0).
void findfirst(char c, int q1, int q2){
if(!(isupper(c)) || c=='$'){
first_set[n++] = c;
}
for(int j=0;j<rule_number;j++){
if(rule[j][0]==c){
if(rule[j][2]==';'){
if(rule[q1][q2]=='')
first_set[n++] = ';';
else if(rule[q1][q2]!='' &&(q1!=0||q2!=0))
findfirst(rule[q1][q2], q1, (q2+1));
else
first_set[n++] = ';';
}
else if(!isupper(rule[j][2]) || rule[j][2]=='$')
first_set[n++] = rule[j][2];
else
findfirst(rule[j][2],j,3);
}
}
}
But found that if the given grammar looks like this:
S AC$
C c
C ;
A aBCd
A BQ
B bB
B ;
Q q
Q ;
(which the left hand side or any capital letters in the right hand side are non-terminal, and any small case letters are terminal)
the function couldn't correctly output the first set for S, since it will stop at finding the first set of Q and store ';' to the first set and won't go on to find C's first set.
Does anyone have a clue? Thanks in advance.
c++ compiler-construction
edited 2 days ago
Rhathin
5371313
asked 2 days ago
Lykas
357
3
Get in the habit of documenting your code and using descriptive variable names.
– paddy
2 days ago
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I am trying to list the First set of a given grammar with this function:
Note: char c - the character to find the first set;first_set - store elements of the corresponding first set;q1, q2 - the previous position;rule- store all the grammar rule line by line listed below;
for the first time the parameters are ('S', 0, 0).
void findfirst(char c, int q1, int q2){
if(!(isupper(c)) || c=='$'){
first_set[n++] = c;
}
for(int j=0;j<rule_number;j++){
if(rule[j][0]==c){
if(rule[j][2]==';'){
if(rule[q1][q2]=='')
first_set[n++] = ';';
else if(rule[q1][q2]!='' &&(q1!=0||q2!=0))
findfirst(rule[q1][q2], q1, (q2+1));
else
first_set[n++] = ';';
}
else if(!isupper(rule[j][2]) || rule[j][2]=='$')
first_set[n++] = rule[j][2];
else
findfirst(rule[j][2],j,3);
}
}
}
But found that if the given grammar looks like this:
S AC$
C c
C ;
A aBCd
A BQ
B bB
B ;
Q q
Q ;
(which the left hand side or any capital letters in the right hand side are non-terminal, and any small case letters are terminal)
the function couldn't correctly output the first set for S, since it will stop at finding the first set of Q and store ';' to the first set and won't go on to find C's first set.
Does anyone have a clue? Thanks in advance.
c++ compiler-construction
edited 2 days ago
Rhathin
5371313
asked 2 days ago
Lykas
357
I am trying to list the First set of a given grammar with this function:
Note: char c - the character to find the first set;first_set - store elements of the corresponding first set;q1, q2 - the previous position;rule- store all the grammar rule line by line listed below;
for the first time the parameters are ('S', 0, 0).
void findfirst(char c, int q1, int q2){
if(!(isupper(c)) || c=='$'){
first_set[n++] = c;
}
for(int j=0;j<rule_number;j++){
if(rule[j][0]==c){
if(rule[j][2]==';'){
if(rule[q1][q2]=='')
first_set[n++] = ';';
else if(rule[q1][q2]!='' &&(q1!=0||q2!=0))
findfirst(rule[q1][q2], q1, (q2+1));
else
first_set[n++] = ';';
}
else if(!isupper(rule[j][2]) || rule[j][2]=='$')
first_set[n++] = rule[j][2];
else
findfirst(rule[j][2],j,3);
}
}
}
But found that if the given grammar looks like this:
S AC$
C c
C ;
A aBCd
A BQ
B bB
B ;
Q q
Q ;
(which the left hand side or any capital letters in the right hand side are non-terminal, and any small case letters are terminal)
the function couldn't correctly output the first set for S, since it will stop at finding the first set of Q and store ';' to the first set and won't go on to find C's first set.
Does anyone have a clue? Thanks in advance.
c++ compiler-construction
c++ compiler-construction
edited 2 days ago
Rhathin
5371313
asked 2 days ago
Lykas
357
edited 2 days ago
Rhathin
5371313
asked 2 days ago
Lykas
357
edited 2 days ago
Rhathin
5371313
edited 2 days ago
Rhathin
5371313
edited 2 days ago
Rhathin
5371313
5371313
asked 2 days ago
Lykas
357
asked 2 days ago
Lykas
357
asked 2 days ago
Lykas
357
357
3
Get in the habit of documenting your code and using descriptive variable names.
– paddy
2 days ago
add a comment |
3
Get in the habit of documenting your code and using descriptive variable names.
– paddy
2 days ago
3
3
Get in the habit of documenting your code and using descriptive variable names.
– paddy
2 days ago
Get in the habit of documenting your code and using descriptive variable names.
– paddy
2 days ago
add a comment |
2 Answers
2
active
oldest
votes
up vote
0
down vote
You could do like the following code:
used[i] means the rule[i] is used or not
The method is Depth-first search, see https://en.wikipedia.org/wiki/Depth-first_search
#include <iostream>
#define MAX_SIZE 1024
char rule[10] = {
"S AC$",
"C c",
"C ;",
"A aBCd",
"A BQ",
"B bB",
"B ;",
"Q q",
"Q ;"
};
constexpr int rule_number = sizeof(rule) / sizeof(rule[0]);
char first_set[MAX_SIZE];
bool findfirst(int row, int col, int *n, bool* used) {
for (;;) {
char ch = rule[row][col];
if (ch == '$' || ch == ';' || ch == '') {
first_set[*n] = '';
break;
}
if (islower(ch)) {
first_set[(*n)++] = ch;
++col;
continue;
}
int i;
for (i = 0; i != rule_number; ++i) {
if (used[i] == true || rule[i][0] != ch)
continue;
used[i] = true;
int k = *n;
if (findfirst(i, 2, n, used) == true)
break;
used[i] = false;
*n = k;
}
if (i == rule_number)
return false;
++col;
}
return true;
}
int main() {
bool used[rule_number];
int n = 0;
for (int i = 2; rule[0][i] != '$' && rule[0][i] != ''; ++i) {
for (int j = 0; j != rule_number; ++j)
used[j] = false;
used[0] = true;
findfirst(0, i, &n, used);
}
std::cout << first_set << std::endl;
return 0;
}
answered yesterday
Yunbin Liu
967211
add a comment |
up vote
0
down vote
It is extremely inefficient to compute FIRST sets one at a time, since they are interdependent. For example, in order to compute the FIRST set of A , you need to also compute the FIRST set of B, and then because B can derive the emoty string, you need the FIRST set of Q.
Most algorithms compute all of them in parallel, using some variation of a transitive closure algorithm. You can do this with a depth-first search, which seems to be what you are attempting, but it might be easier to implement the least fixed point algorithm described in the Dragon book (and Wikipedia.
Either way, you will probably find it easier to first compute NULLABLE (that is, which non-terminals derive the empty set). There is a simple linear-time algorithm for that (linear in the size of the grammar), which again is easy to find.
If you are doing this work as part of a class, you'll probably find the relevant algorithms in your course materials. Alternatively, you can look for a copy of the Dragon book or other similar text books.
answered yesterday
rici
149k19128192
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
You could do like the following code:
used[i] means the rule[i] is used or not
The method is Depth-first search, see https://en.wikipedia.org/wiki/Depth-first_search
#include <iostream>
#define MAX_SIZE 1024
char rule[10] = {
"S AC$",
"C c",
"C ;",
"A aBCd",
"A BQ",
"B bB",
"B ;",
"Q q",
"Q ;"
};
constexpr int rule_number = sizeof(rule) / sizeof(rule[0]);
char first_set[MAX_SIZE];
bool findfirst(int row, int col, int *n, bool* used) {
for (;;) {
char ch = rule[row][col];
if (ch == '$' || ch == ';' || ch == '') {
first_set[*n] = '';
break;
}
if (islower(ch)) {
first_set[(*n)++] = ch;
++col;
continue;
}
int i;
for (i = 0; i != rule_number; ++i) {
if (used[i] == true || rule[i][0] != ch)
continue;
used[i] = true;
int k = *n;
if (findfirst(i, 2, n, used) == true)
break;
used[i] = false;
*n = k;
}
if (i == rule_number)
return false;
++col;
}
return true;
}
int main() {
bool used[rule_number];
int n = 0;
for (int i = 2; rule[0][i] != '$' && rule[0][i] != ''; ++i) {
for (int j = 0; j != rule_number; ++j)
used[j] = false;
used[0] = true;
findfirst(0, i, &n, used);
}
std::cout << first_set << std::endl;
return 0;
}
answered yesterday
Yunbin Liu
967211
add a comment |
up vote
0
down vote
You could do like the following code:
used[i] means the rule[i] is used or not
The method is Depth-first search, see https://en.wikipedia.org/wiki/Depth-first_search
#include <iostream>
#define MAX_SIZE 1024
char rule[10] = {
"S AC$",
"C c",
"C ;",
"A aBCd",
"A BQ",
"B bB",
"B ;",
"Q q",
"Q ;"
};
constexpr int rule_number = sizeof(rule) / sizeof(rule[0]);
char first_set[MAX_SIZE];
bool findfirst(int row, int col, int *n, bool* used) {
for (;;) {
char ch = rule[row][col];
if (ch == '$' || ch == ';' || ch == '') {
first_set[*n] = '';
break;
}
if (islower(ch)) {
first_set[(*n)++] = ch;
++col;
continue;
}
int i;
for (i = 0; i != rule_number; ++i) {
if (used[i] == true || rule[i][0] != ch)
continue;
used[i] = true;
int k = *n;
if (findfirst(i, 2, n, used) == true)
break;
used[i] = false;
*n = k;
}
if (i == rule_number)
return false;
++col;
}
return true;
}
int main() {
bool used[rule_number];
int n = 0;
for (int i = 2; rule[0][i] != '$' && rule[0][i] != ''; ++i) {
for (int j = 0; j != rule_number; ++j)
used[j] = false;
used[0] = true;
findfirst(0, i, &n, used);
}
std::cout << first_set << std::endl;
return 0;
}
answered yesterday
Yunbin Liu
967211
add a comment |
up vote
0
down vote
up vote
0
down vote
You could do like the following code:
used[i] means the rule[i] is used or not
The method is Depth-first search, see https://en.wikipedia.org/wiki/Depth-first_search
#include <iostream>
#define MAX_SIZE 1024
char rule[10] = {
"S AC$",
"C c",
"C ;",
"A aBCd",
"A BQ",
"B bB",
"B ;",
"Q q",
"Q ;"
};
constexpr int rule_number = sizeof(rule) / sizeof(rule[0]);
char first_set[MAX_SIZE];
bool findfirst(int row, int col, int *n, bool* used) {
for (;;) {
char ch = rule[row][col];
if (ch == '$' || ch == ';' || ch == '') {
first_set[*n] = '';
break;
}
if (islower(ch)) {
first_set[(*n)++] = ch;
++col;
continue;
}
int i;
for (i = 0; i != rule_number; ++i) {
if (used[i] == true || rule[i][0] != ch)
continue;
used[i] = true;
int k = *n;
if (findfirst(i, 2, n, used) == true)
break;
used[i] = false;
*n = k;
}
if (i == rule_number)
return false;
++col;
}
return true;
}
int main() {
bool used[rule_number];
int n = 0;
for (int i = 2; rule[0][i] != '$' && rule[0][i] != ''; ++i) {
for (int j = 0; j != rule_number; ++j)
used[j] = false;
used[0] = true;
findfirst(0, i, &n, used);
}
std::cout << first_set << std::endl;
return 0;
}
answered yesterday
Yunbin Liu
967211
You could do like the following code:
used[i] means the rule[i] is used or not
The method is Depth-first search, see https://en.wikipedia.org/wiki/Depth-first_search
#include <iostream>
#define MAX_SIZE 1024
char rule[10] = {
"S AC$",
"C c",
"C ;",
"A aBCd",
"A BQ",
"B bB",
"B ;",
"Q q",
"Q ;"
};
constexpr int rule_number = sizeof(rule) / sizeof(rule[0]);
char first_set[MAX_SIZE];
bool findfirst(int row, int col, int *n, bool* used) {
for (;;) {
char ch = rule[row][col];
if (ch == '$' || ch == ';' || ch == '') {
first_set[*n] = '';
break;
}
if (islower(ch)) {
first_set[(*n)++] = ch;
++col;
continue;
}
int i;
for (i = 0; i != rule_number; ++i) {
if (used[i] == true || rule[i][0] != ch)
continue;
used[i] = true;
int k = *n;
if (findfirst(i, 2, n, used) == true)
break;
used[i] = false;
*n = k;
}
if (i == rule_number)
return false;
++col;
}
return true;
}
int main() {
bool used[rule_number];
int n = 0;
for (int i = 2; rule[0][i] != '$' && rule[0][i] != ''; ++i) {
for (int j = 0; j != rule_number; ++j)
used[j] = false;
used[0] = true;
findfirst(0, i, &n, used);
}
std::cout << first_set << std::endl;
return 0;
}
answered yesterday
Yunbin Liu
967211
answered yesterday
Yunbin Liu
967211
answered yesterday
Yunbin Liu
967211
answered yesterday
Yunbin Liu
967211
967211
add a comment |
add a comment |
up vote
0
down vote
It is extremely inefficient to compute FIRST sets one at a time, since they are interdependent. For example, in order to compute the FIRST set of A , you need to also compute the FIRST set of B, and then because B can derive the emoty string, you need the FIRST set of Q.
Most algorithms compute all of them in parallel, using some variation of a transitive closure algorithm. You can do this with a depth-first search, which seems to be what you are attempting, but it might be easier to implement the least fixed point algorithm described in the Dragon book (and Wikipedia.
Either way, you will probably find it easier to first compute NULLABLE (that is, which non-terminals derive the empty set). There is a simple linear-time algorithm for that (linear in the size of the grammar), which again is easy to find.
If you are doing this work as part of a class, you'll probably find the relevant algorithms in your course materials. Alternatively, you can look for a copy of the Dragon book or other similar text books.
answered yesterday
rici
149k19128192
add a comment |
up vote
0
down vote
It is extremely inefficient to compute FIRST sets one at a time, since they are interdependent. For example, in order to compute the FIRST set of A , you need to also compute the FIRST set of B, and then because B can derive the emoty string, you need the FIRST set of Q.
Most algorithms compute all of them in parallel, using some variation of a transitive closure algorithm. You can do this with a depth-first search, which seems to be what you are attempting, but it might be easier to implement the least fixed point algorithm described in the Dragon book (and Wikipedia.
Either way, you will probably find it easier to first compute NULLABLE (that is, which non-terminals derive the empty set). There is a simple linear-time algorithm for that (linear in the size of the grammar), which again is easy to find.
If you are doing this work as part of a class, you'll probably find the relevant algorithms in your course materials. Alternatively, you can look for a copy of the Dragon book or other similar text books.
answered yesterday
rici
149k19128192
add a comment |
up vote
0
down vote
up vote
0
down vote
It is extremely inefficient to compute FIRST sets one at a time, since they are interdependent. For example, in order to compute the FIRST set of A , you need to also compute the FIRST set of B, and then because B can derive the emoty string, you need the FIRST set of Q.
Most algorithms compute all of them in parallel, using some variation of a transitive closure algorithm. You can do this with a depth-first search, which seems to be what you are attempting, but it might be easier to implement the least fixed point algorithm described in the Dragon book (and Wikipedia.
Either way, you will probably find it easier to first compute NULLABLE (that is, which non-terminals derive the empty set). There is a simple linear-time algorithm for that (linear in the size of the grammar), which again is easy to find.
If you are doing this work as part of a class, you'll probably find the relevant algorithms in your course materials. Alternatively, you can look for a copy of the Dragon book or other similar text books.
answered yesterday
rici
149k19128192
It is extremely inefficient to compute FIRST sets one at a time, since they are interdependent. For example, in order to compute the FIRST set of A , you need to also compute the FIRST set of B, and then because B can derive the emoty string, you need the FIRST set of Q.
Most algorithms compute all of them in parallel, using some variation of a transitive closure algorithm. You can do this with a depth-first search, which seems to be what you are attempting, but it might be easier to implement the least fixed point algorithm described in the Dragon book (and Wikipedia.
Either way, you will probably find it easier to first compute NULLABLE (that is, which non-terminals derive the empty set). There is a simple linear-time algorithm for that (linear in the size of the grammar), which again is easy to find.
If you are doing this work as part of a class, you'll probably find the relevant algorithms in your course materials. Alternatively, you can look for a copy of the Dragon book or other similar text books.
answered yesterday
rici
149k19128192
edited yesterday
answered yesterday
rici
149k19128192
answered yesterday
rici
149k19128192
answered yesterday
rici
149k19128192
149k19128192
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53372838%2fhow-to-find-first-set%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
Get in the habit of documenting your code and using descriptive variable names.
– paddy
2 days ago