Javacc - Eliminating choice conflict by using left factoring instead of lookahead
up vote
0
down vote
favorite
I am writing a JAVACC program for a simple language and I am running into 1 conflict which is fixable by using a LOOKAHEAD(2).Would I be able to overcome this issue by left-factoring the code rather than using a look-ahead and if not, why?
GRAMMAR
void expression() : {}
{
simple_expression() (addition_or_substraction() | {})
}
void simple_expression() : {}
{
<NUMBER>
| <LBRAC> expression() <RBRAC>
}
void condition() : {}
{
simple_condition() (compare_condition() | {})
}
void prime_condition() : {}
{
expression_comparison()
|<NOT_OPERATOR> condition()
| LOOKAHEAD(2) <LBRAC> condition() <RBRAC> // Choice conflict for "("
}
void expression_comparison() : {}
{
expression()
(
<EQUAL> expression()
<LESS_THAN> expression()
<GREATER_THAN> expression()
)
}
void compare_condition() : {}
{
<AND> condition() | <OR> condition()
}
regex parsing compiler-construction stringtokenizer javacc
asked Nov 11 at 18:44
Samuel_143
6
|
show 2 more comments
up vote
0
down vote
favorite
I am writing a JAVACC program for a simple language and I am running into 1 conflict which is fixable by using a LOOKAHEAD(2).Would I be able to overcome this issue by left-factoring the code rather than using a look-ahead and if not, why?
GRAMMAR
void expression() : {}
{
simple_expression() (addition_or_substraction() | {})
}
void simple_expression() : {}
{
<NUMBER>
| <LBRAC> expression() <RBRAC>
}
void condition() : {}
{
simple_condition() (compare_condition() | {})
}
void prime_condition() : {}
{
expression_comparison()
|<NOT_OPERATOR> condition()
| LOOKAHEAD(2) <LBRAC> condition() <RBRAC> // Choice conflict for "("
}
void expression_comparison() : {}
{
expression()
(
<EQUAL> expression()
<LESS_THAN> expression()
<GREATER_THAN> expression()
)
}
void compare_condition() : {}
{
<AND> condition() | <OR> condition()
}
regex parsing compiler-construction stringtokenizer javacc
asked Nov 11 at 18:44
Samuel_143
6
What is the final regex that you're considering factoring ?
– sln
Nov 11 at 18:59
@sln prime_condition
– Samuel_143
Nov 11 at 20:55
Yeah, I'd just use(?(condition)yes_regex|no_regex)
– sln
Nov 12 at 18:49
Put together a complete substitution rather than a series of function calls. Or, post the overall regex that would be used to parse your source. Then I can tell you what to do. To me it looks like an endless loop.
– sln
Nov 12 at 18:56
The premise of the question is wrong. The LOOKAHEAD(2) does not fix the conflict. It does shut off the warning. See the FAQ regarding LOOKAHEADs and warnings.
– Theodore Norvell
Nov 14 at 20:36
|
show 2 more comments
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I am writing a JAVACC program for a simple language and I am running into 1 conflict which is fixable by using a LOOKAHEAD(2).Would I be able to overcome this issue by left-factoring the code rather than using a look-ahead and if not, why?
GRAMMAR
void expression() : {}
{
simple_expression() (addition_or_substraction() | {})
}
void simple_expression() : {}
{
<NUMBER>
| <LBRAC> expression() <RBRAC>
}
void condition() : {}
{
simple_condition() (compare_condition() | {})
}
void prime_condition() : {}
{
expression_comparison()
|<NOT_OPERATOR> condition()
| LOOKAHEAD(2) <LBRAC> condition() <RBRAC> // Choice conflict for "("
}
void expression_comparison() : {}
{
expression()
(
<EQUAL> expression()
<LESS_THAN> expression()
<GREATER_THAN> expression()
)
}
void compare_condition() : {}
{
<AND> condition() | <OR> condition()
}
regex parsing compiler-construction stringtokenizer javacc
asked Nov 11 at 18:44
Samuel_143
6
I am writing a JAVACC program for a simple language and I am running into 1 conflict which is fixable by using a LOOKAHEAD(2).Would I be able to overcome this issue by left-factoring the code rather than using a look-ahead and if not, why?
GRAMMAR
void expression() : {}
{
simple_expression() (addition_or_substraction() | {})
}
void simple_expression() : {}
{
<NUMBER>
| <LBRAC> expression() <RBRAC>
}
void condition() : {}
{
simple_condition() (compare_condition() | {})
}
void prime_condition() : {}
{
expression_comparison()
|<NOT_OPERATOR> condition()
| LOOKAHEAD(2) <LBRAC> condition() <RBRAC> // Choice conflict for "("
}
void expression_comparison() : {}
{
expression()
(
<EQUAL> expression()
<LESS_THAN> expression()
<GREATER_THAN> expression()
)
}
void compare_condition() : {}
{
<AND> condition() | <OR> condition()
}
regex parsing compiler-construction stringtokenizer javacc
regex parsing compiler-construction stringtokenizer javacc
asked Nov 11 at 18:44
Samuel_143
6
asked Nov 11 at 18:44
Samuel_143
6
asked Nov 11 at 18:44
Samuel_143
6
asked Nov 11 at 18:44
Samuel_143
6
asked Nov 11 at 18:44
Samuel_143
6
6
What is the final regex that you're considering factoring ?
– sln
Nov 11 at 18:59
@sln prime_condition
– Samuel_143
Nov 11 at 20:55
Yeah, I'd just use(?(condition)yes_regex|no_regex)
– sln
Nov 12 at 18:49
Put together a complete substitution rather than a series of function calls. Or, post the overall regex that would be used to parse your source. Then I can tell you what to do. To me it looks like an endless loop.
– sln
Nov 12 at 18:56
The premise of the question is wrong. The LOOKAHEAD(2) does not fix the conflict. It does shut off the warning. See the FAQ regarding LOOKAHEADs and warnings.
– Theodore Norvell
Nov 14 at 20:36
|
show 2 more comments
What is the final regex that you're considering factoring ?
– sln
Nov 11 at 18:59
@sln prime_condition
– Samuel_143
Nov 11 at 20:55
Yeah, I'd just use(?(condition)yes_regex|no_regex)
– sln
Nov 12 at 18:49
Put together a complete substitution rather than a series of function calls. Or, post the overall regex that would be used to parse your source. Then I can tell you what to do. To me it looks like an endless loop.
– sln
Nov 12 at 18:56
The premise of the question is wrong. The LOOKAHEAD(2) does not fix the conflict. It does shut off the warning. See the FAQ regarding LOOKAHEADs and warnings.
– Theodore Norvell
Nov 14 at 20:36
What is the final regex that you're considering factoring ?
– sln
Nov 11 at 18:59
What is the final regex that you're considering factoring ?
– sln
Nov 11 at 18:59
@sln prime_condition
– Samuel_143
Nov 11 at 20:55
@sln prime_condition
– Samuel_143
Nov 11 at 20:55
Yeah, I'd just use
(?(condition)yes_regex|no_regex)– sln
Nov 12 at 18:49
Yeah, I'd just use
(?(condition)yes_regex|no_regex)– sln
Nov 12 at 18:49
Put together a complete substitution rather than a series of function calls. Or, post the overall regex that would be used to parse your source. Then I can tell you what to do. To me it looks like an endless loop.
– sln
Nov 12 at 18:56
Put together a complete substitution rather than a series of function calls. Or, post the overall regex that would be used to parse your source. Then I can tell you what to do. To me it looks like an endless loop.
– sln
Nov 12 at 18:56
The premise of the question is wrong. The LOOKAHEAD(2) does not fix the conflict. It does shut off the warning. See the FAQ regarding LOOKAHEADs and warnings.
– Theodore Norvell
Nov 14 at 20:36
The premise of the question is wrong. The LOOKAHEAD(2) does not fix the conflict. It does shut off the warning. See the FAQ regarding LOOKAHEADs and warnings.
– Theodore Norvell
Nov 14 at 20:36
|
show 2 more comments
1 Answer
1
active
oldest
votes
up vote
0
down vote
I really don't think that you can left-factor your way out of the problem. I suspect (but haven't proved) that the language generated from condition does not have an LL(1) grammar.
Anyway, let's try left factoring. Let's work on a simpler --but similar-- grammar that contains the essentials of your problem. Terminals are number, =, [, and ].
C --> EXP = EXP | [ C ]
EXP --> number | [ EXP ]
Now, I'm not going to do more because you should do it your self. I'm fairly sure this is a homework problem, so if I do it here, I will be depriving you of the educational opportunity of doing it your self, not to mention the fun.
The first step is to expand the first occurrence of EXP in C. Be sure not to stop until your grammar is LL(1) or you are sure that this is a fruitless task.
answered Nov 14 at 21:21
Theodore Norvell
7,12541637
BTW, if you find this or any other answer useful, be sure to cite the answers in your homework submission, so as to avoid academic dishonesty.
– Theodore Norvell
Nov 14 at 21:23
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f53251986%2fjavacc-eliminating-choice-conflict-by-using-left-factoring-instead-of-lookahea%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
I really don't think that you can left-factor your way out of the problem. I suspect (but haven't proved) that the language generated from condition does not have an LL(1) grammar.
Anyway, let's try left factoring. Let's work on a simpler --but similar-- grammar that contains the essentials of your problem. Terminals are number, =, [, and ].
C --> EXP = EXP | [ C ]
EXP --> number | [ EXP ]
Now, I'm not going to do more because you should do it your self. I'm fairly sure this is a homework problem, so if I do it here, I will be depriving you of the educational opportunity of doing it your self, not to mention the fun.
The first step is to expand the first occurrence of EXP in C. Be sure not to stop until your grammar is LL(1) or you are sure that this is a fruitless task.
answered Nov 14 at 21:21
Theodore Norvell
7,12541637
BTW, if you find this or any other answer useful, be sure to cite the answers in your homework submission, so as to avoid academic dishonesty.
– Theodore Norvell
Nov 14 at 21:23
add a comment |
up vote
0
down vote
I really don't think that you can left-factor your way out of the problem. I suspect (but haven't proved) that the language generated from condition does not have an LL(1) grammar.
Anyway, let's try left factoring. Let's work on a simpler --but similar-- grammar that contains the essentials of your problem. Terminals are number, =, [, and ].
C --> EXP = EXP | [ C ]
EXP --> number | [ EXP ]
Now, I'm not going to do more because you should do it your self. I'm fairly sure this is a homework problem, so if I do it here, I will be depriving you of the educational opportunity of doing it your self, not to mention the fun.
The first step is to expand the first occurrence of EXP in C. Be sure not to stop until your grammar is LL(1) or you are sure that this is a fruitless task.
answered Nov 14 at 21:21
Theodore Norvell
7,12541637
BTW, if you find this or any other answer useful, be sure to cite the answers in your homework submission, so as to avoid academic dishonesty.
– Theodore Norvell
Nov 14 at 21:23
add a comment |
up vote
0
down vote
up vote
0
down vote
I really don't think that you can left-factor your way out of the problem. I suspect (but haven't proved) that the language generated from condition does not have an LL(1) grammar.
Anyway, let's try left factoring. Let's work on a simpler --but similar-- grammar that contains the essentials of your problem. Terminals are number, =, [, and ].
C --> EXP = EXP | [ C ]
EXP --> number | [ EXP ]
Now, I'm not going to do more because you should do it your self. I'm fairly sure this is a homework problem, so if I do it here, I will be depriving you of the educational opportunity of doing it your self, not to mention the fun.
The first step is to expand the first occurrence of EXP in C. Be sure not to stop until your grammar is LL(1) or you are sure that this is a fruitless task.
answered Nov 14 at 21:21
Theodore Norvell
7,12541637
I really don't think that you can left-factor your way out of the problem. I suspect (but haven't proved) that the language generated from condition does not have an LL(1) grammar.
Anyway, let's try left factoring. Let's work on a simpler --but similar-- grammar that contains the essentials of your problem. Terminals are number, =, [, and ].
C --> EXP = EXP | [ C ]
EXP --> number | [ EXP ]
Now, I'm not going to do more because you should do it your self. I'm fairly sure this is a homework problem, so if I do it here, I will be depriving you of the educational opportunity of doing it your self, not to mention the fun.
The first step is to expand the first occurrence of EXP in C. Be sure not to stop until your grammar is LL(1) or you are sure that this is a fruitless task.
answered Nov 14 at 21:21
Theodore Norvell
7,12541637
edited Nov 18 at 13:52
answered Nov 14 at 21:21
Theodore Norvell
7,12541637
answered Nov 14 at 21:21
Theodore Norvell
7,12541637
answered Nov 14 at 21:21
Theodore Norvell
7,12541637
7,12541637
BTW, if you find this or any other answer useful, be sure to cite the answers in your homework submission, so as to avoid academic dishonesty.
– Theodore Norvell
Nov 14 at 21:23
add a comment |
BTW, if you find this or any other answer useful, be sure to cite the answers in your homework submission, so as to avoid academic dishonesty.
– Theodore Norvell
Nov 14 at 21:23
BTW, if you find this or any other answer useful, be sure to cite the answers in your homework submission, so as to avoid academic dishonesty.
– Theodore Norvell
Nov 14 at 21:23
BTW, if you find this or any other answer useful, be sure to cite the answers in your homework submission, so as to avoid academic dishonesty.
– Theodore Norvell
Nov 14 at 21:23
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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%2f53251986%2fjavacc-eliminating-choice-conflict-by-using-left-factoring-instead-of-lookahea%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
What is the final regex that you're considering factoring ?
– sln
Nov 11 at 18:59
@sln prime_condition
– Samuel_143
Nov 11 at 20:55
Yeah, I'd just use
(?(condition)yes_regex|no_regex)– sln
Nov 12 at 18:49
Put together a complete substitution rather than a series of function calls. Or, post the overall regex that would be used to parse your source. Then I can tell you what to do. To me it looks like an endless loop.
– sln
Nov 12 at 18:56
The premise of the question is wrong. The LOOKAHEAD(2) does not fix the conflict. It does shut off the warning. See the FAQ regarding LOOKAHEADs and warnings.
– Theodore Norvell
Nov 14 at 20:36