Choice Conflict Involving Two Expansions:











up vote
3
down vote

favorite
1












I'm trying to create my own analyser/parser.



I have a problem which I understand why it doesn't work but I'm unsure of how to solve it.



This is the code for the problem part of my parser.



void Expression() : {}{
Term() ((<PLUS> | <MINUS>) Term())*
}

void Term() : {}{
Factor()((<MULTIPLY> | <DIVIDE>) Factor())*
}

void Factor() : {}{
(<ID> | <NUMBER> | ((<PLUS> | <MINUS>)?<OPEN_PARENTHESIS> Expression() <CLOSE_PARENTHESIS>))
}

void Condition() : {}{
(
(<NOT> Condition()) |
(<OPEN_PARENTHESIS> Condition() (<AND> | <OR>) Condition() <CLOSE_PARENTHESIS>) |
(Expression() (<EQUAL_CHECK> | <NOT_EQUAL> | <LESS> | <LESS_EQUAL> | <GREATER> | <GREATER_EQUAL>) Expression())
)
}


As you can see, the problem comes within the Condition() method from the last two of the three options in the OR section. This is because Expression() can eventually become "( Expression() )" therefore both the third and second option can begin with a open parenthesis token.



However, I'm unsure how I would solve this problem. I solved a similar problem earlier in the parser however I can't employ the same logic here without it being extremely messy because of the way Expression() --> Term() --> Factor() and the problem code being all the way down in the Factor() method.



Any advice would be greatly appreciated.



Thanks,



Thomas.



EDIT:



For more info, I'll provide to code examples that should work with this parser but will not due to the bug explained above.



fun succesful_method()
start
var i = 1;
if(i > 0 and i < 2)
do
i = 2;
stop
stop

start
successful_method()
stop


The above method would run successfully as it uses the second alternative of the Condition() method.



fun succesful_method()
start
var i = 1;
if(i > 0)
do
i = 2;
stop
stop

start
successful_method()
stop


The above method would fail, as it requires use of the third alternative, however it cannot access this due to the '(' causing the parser to call the second alternative.










share|improve this question
























  • Many languages (e.g. Java, C, C++, Python, Haskell, ML) take the approach of not syntactically distinguishing between conditions and expressions. One reason for this is that Boolean variables are really useful. Once you have Boolean variables you'll want to have if statements like this if q do ... stop and assignment statements like this q = a < b ;. At this point keeping Boolean expressions and other expressions syntactically separate gets to be futile. So you should give some consideration to @1010's answer.
    – Theodore Norvell
    May 1 '15 at 0:24















up vote
3
down vote

favorite
1












I'm trying to create my own analyser/parser.



I have a problem which I understand why it doesn't work but I'm unsure of how to solve it.



This is the code for the problem part of my parser.



void Expression() : {}{
Term() ((<PLUS> | <MINUS>) Term())*
}

void Term() : {}{
Factor()((<MULTIPLY> | <DIVIDE>) Factor())*
}

void Factor() : {}{
(<ID> | <NUMBER> | ((<PLUS> | <MINUS>)?<OPEN_PARENTHESIS> Expression() <CLOSE_PARENTHESIS>))
}

void Condition() : {}{
(
(<NOT> Condition()) |
(<OPEN_PARENTHESIS> Condition() (<AND> | <OR>) Condition() <CLOSE_PARENTHESIS>) |
(Expression() (<EQUAL_CHECK> | <NOT_EQUAL> | <LESS> | <LESS_EQUAL> | <GREATER> | <GREATER_EQUAL>) Expression())
)
}


As you can see, the problem comes within the Condition() method from the last two of the three options in the OR section. This is because Expression() can eventually become "( Expression() )" therefore both the third and second option can begin with a open parenthesis token.



However, I'm unsure how I would solve this problem. I solved a similar problem earlier in the parser however I can't employ the same logic here without it being extremely messy because of the way Expression() --> Term() --> Factor() and the problem code being all the way down in the Factor() method.



Any advice would be greatly appreciated.



Thanks,



Thomas.



EDIT:



For more info, I'll provide to code examples that should work with this parser but will not due to the bug explained above.



fun succesful_method()
start
var i = 1;
if(i > 0 and i < 2)
do
i = 2;
stop
stop

start
successful_method()
stop


The above method would run successfully as it uses the second alternative of the Condition() method.



fun succesful_method()
start
var i = 1;
if(i > 0)
do
i = 2;
stop
stop

start
successful_method()
stop


The above method would fail, as it requires use of the third alternative, however it cannot access this due to the '(' causing the parser to call the second alternative.










share|improve this question
























  • Many languages (e.g. Java, C, C++, Python, Haskell, ML) take the approach of not syntactically distinguishing between conditions and expressions. One reason for this is that Boolean variables are really useful. Once you have Boolean variables you'll want to have if statements like this if q do ... stop and assignment statements like this q = a < b ;. At this point keeping Boolean expressions and other expressions syntactically separate gets to be futile. So you should give some consideration to @1010's answer.
    – Theodore Norvell
    May 1 '15 at 0:24













up vote
3
down vote

favorite
1









up vote
3
down vote

favorite
1






1





I'm trying to create my own analyser/parser.



I have a problem which I understand why it doesn't work but I'm unsure of how to solve it.



This is the code for the problem part of my parser.



void Expression() : {}{
Term() ((<PLUS> | <MINUS>) Term())*
}

void Term() : {}{
Factor()((<MULTIPLY> | <DIVIDE>) Factor())*
}

void Factor() : {}{
(<ID> | <NUMBER> | ((<PLUS> | <MINUS>)?<OPEN_PARENTHESIS> Expression() <CLOSE_PARENTHESIS>))
}

void Condition() : {}{
(
(<NOT> Condition()) |
(<OPEN_PARENTHESIS> Condition() (<AND> | <OR>) Condition() <CLOSE_PARENTHESIS>) |
(Expression() (<EQUAL_CHECK> | <NOT_EQUAL> | <LESS> | <LESS_EQUAL> | <GREATER> | <GREATER_EQUAL>) Expression())
)
}


As you can see, the problem comes within the Condition() method from the last two of the three options in the OR section. This is because Expression() can eventually become "( Expression() )" therefore both the third and second option can begin with a open parenthesis token.



However, I'm unsure how I would solve this problem. I solved a similar problem earlier in the parser however I can't employ the same logic here without it being extremely messy because of the way Expression() --> Term() --> Factor() and the problem code being all the way down in the Factor() method.



Any advice would be greatly appreciated.



Thanks,



Thomas.



EDIT:



For more info, I'll provide to code examples that should work with this parser but will not due to the bug explained above.



fun succesful_method()
start
var i = 1;
if(i > 0 and i < 2)
do
i = 2;
stop
stop

start
successful_method()
stop


The above method would run successfully as it uses the second alternative of the Condition() method.



fun succesful_method()
start
var i = 1;
if(i > 0)
do
i = 2;
stop
stop

start
successful_method()
stop


The above method would fail, as it requires use of the third alternative, however it cannot access this due to the '(' causing the parser to call the second alternative.










share|improve this question















I'm trying to create my own analyser/parser.



I have a problem which I understand why it doesn't work but I'm unsure of how to solve it.



This is the code for the problem part of my parser.



void Expression() : {}{
Term() ((<PLUS> | <MINUS>) Term())*
}

void Term() : {}{
Factor()((<MULTIPLY> | <DIVIDE>) Factor())*
}

void Factor() : {}{
(<ID> | <NUMBER> | ((<PLUS> | <MINUS>)?<OPEN_PARENTHESIS> Expression() <CLOSE_PARENTHESIS>))
}

void Condition() : {}{
(
(<NOT> Condition()) |
(<OPEN_PARENTHESIS> Condition() (<AND> | <OR>) Condition() <CLOSE_PARENTHESIS>) |
(Expression() (<EQUAL_CHECK> | <NOT_EQUAL> | <LESS> | <LESS_EQUAL> | <GREATER> | <GREATER_EQUAL>) Expression())
)
}


As you can see, the problem comes within the Condition() method from the last two of the three options in the OR section. This is because Expression() can eventually become "( Expression() )" therefore both the third and second option can begin with a open parenthesis token.



However, I'm unsure how I would solve this problem. I solved a similar problem earlier in the parser however I can't employ the same logic here without it being extremely messy because of the way Expression() --> Term() --> Factor() and the problem code being all the way down in the Factor() method.



Any advice would be greatly appreciated.



Thanks,



Thomas.



EDIT:



For more info, I'll provide to code examples that should work with this parser but will not due to the bug explained above.



fun succesful_method()
start
var i = 1;
if(i > 0 and i < 2)
do
i = 2;
stop
stop

start
successful_method()
stop


The above method would run successfully as it uses the second alternative of the Condition() method.



fun succesful_method()
start
var i = 1;
if(i > 0)
do
i = 2;
stop
stop

start
successful_method()
stop


The above method would fail, as it requires use of the third alternative, however it cannot access this due to the '(' causing the parser to call the second alternative.







java parsing javacc left-recursion






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Apr 30 '15 at 18:19









jww

52.5k38220481




52.5k38220481










asked Apr 30 '15 at 17:18









Feint

375




375












  • Many languages (e.g. Java, C, C++, Python, Haskell, ML) take the approach of not syntactically distinguishing between conditions and expressions. One reason for this is that Boolean variables are really useful. Once you have Boolean variables you'll want to have if statements like this if q do ... stop and assignment statements like this q = a < b ;. At this point keeping Boolean expressions and other expressions syntactically separate gets to be futile. So you should give some consideration to @1010's answer.
    – Theodore Norvell
    May 1 '15 at 0:24


















  • Many languages (e.g. Java, C, C++, Python, Haskell, ML) take the approach of not syntactically distinguishing between conditions and expressions. One reason for this is that Boolean variables are really useful. Once you have Boolean variables you'll want to have if statements like this if q do ... stop and assignment statements like this q = a < b ;. At this point keeping Boolean expressions and other expressions syntactically separate gets to be futile. So you should give some consideration to @1010's answer.
    – Theodore Norvell
    May 1 '15 at 0:24
















Many languages (e.g. Java, C, C++, Python, Haskell, ML) take the approach of not syntactically distinguishing between conditions and expressions. One reason for this is that Boolean variables are really useful. Once you have Boolean variables you'll want to have if statements like this if q do ... stop and assignment statements like this q = a < b ;. At this point keeping Boolean expressions and other expressions syntactically separate gets to be futile. So you should give some consideration to @1010's answer.
– Theodore Norvell
May 1 '15 at 0:24




Many languages (e.g. Java, C, C++, Python, Haskell, ML) take the approach of not syntactically distinguishing between conditions and expressions. One reason for this is that Boolean variables are really useful. Once you have Boolean variables you'll want to have if statements like this if q do ... stop and assignment statements like this q = a < b ;. At this point keeping Boolean expressions and other expressions syntactically separate gets to be futile. So you should give some consideration to @1010's answer.
– Theodore Norvell
May 1 '15 at 0:24












2 Answers
2






active

oldest

votes

















up vote
1
down vote



accepted










You can solve this with syntactic look ahead.



void CompOp() : {} { <EQUAL_CHECK> | <NOT_EQUAL> | <LESS> | <LESS_EQUAL> | <GREATER> | <GREATER_EQUAL> }

void Condition() : {}{
<NOT> Condition()
|
LOOKAHEAD(Expression() CompOp())
Expression()
CompOp()
Expression()
|
<OPEN_PARENTHESIS>
Condition()
(<AND> | <OR>)
Condition()
<CLOSE_PARENTHESIS>
}




Slightly more efficient is to only lookahead when there is a (.



void Condition() : {}{
<NOT> Condition()
| LOOKAHEAD( <OPEN_PARENTHESIS> )
(
LOOKAHEAD(Expression() CompOp())
Expression()
CompOp()
Expression()
|
<OPEN_PARENTHESIS>
Condition()
(<AND> | <OR>)
Condition()
<CLOSE_PARENTHESIS>
)
|
Expression()
CompOp()
Expression()
}





share|improve this answer























  • Great solution, worked perfectly - really appreciated. Is the "LOOKAHEAD" function efficient?
    – Feint
    Apr 30 '15 at 23:35










  • It should be reasonably efficient.
    – Theodore Norvell
    May 1 '15 at 0:14


















up vote
1
down vote













Using a single grammar for all expressions and defining precedence for all operators should solve your problem, at the expense of adding semantic checks for the type of expressions.



Expr -> AndExpr (<OR> AndExpr)*
AndExpr -> NotExpr (<AND> NotExpr)*
NotExpr -> <NOT>* RelExpr
RelExpr -> NumExpr () (<RELOP> NumExpr)?

NumExpr -> Term ((<PLUS>|<MINUS>) Term)*
Term -> Factor ((<MULTIPLY>|<DIVIDE>) Factor)*
Factor -> (<PLUS>|<MINUS>)* Atom
Atom -> <ID> | <NUMBER> | <OPEN_PARENTHESIS> Expr <CLOSE_PARENTHESIS>


The token <RELOP>represents your relational operators.



Note that this grammar let's you mix boolean and numerical expressions, so you should check for errors.



For example for Expr -> AndExpr the type returned would be the type of AndExpr. But for AndExpr <OR> AndExpr you should check that both AndExprs are boolean expressions and the type returned by Expr would be Boolean.






share|improve this answer





















  • Interesting solution! Thanks a lot. Is there an advantage to this solution over the "Look Ahead" solution provided above in terms of efficiency?
    – Feint
    Apr 30 '15 at 23:35










  • as @TheodoreNorvell pointed out, this way it would be easier to add boolean variabes to your language. I don't think you'll notice a difference in performance parsing normal programs.
    – 1010
    May 1 '15 at 1:41










  • You can make this approach highly efficient by using precedence climbing. engr.mun.ca/~theo/Misc/exp_parsing.htm
    – Theodore Norvell
    May 1 '15 at 10:36











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
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f29973988%2fchoice-conflict-involving-two-expansions%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
1
down vote



accepted










You can solve this with syntactic look ahead.



void CompOp() : {} { <EQUAL_CHECK> | <NOT_EQUAL> | <LESS> | <LESS_EQUAL> | <GREATER> | <GREATER_EQUAL> }

void Condition() : {}{
<NOT> Condition()
|
LOOKAHEAD(Expression() CompOp())
Expression()
CompOp()
Expression()
|
<OPEN_PARENTHESIS>
Condition()
(<AND> | <OR>)
Condition()
<CLOSE_PARENTHESIS>
}




Slightly more efficient is to only lookahead when there is a (.



void Condition() : {}{
<NOT> Condition()
| LOOKAHEAD( <OPEN_PARENTHESIS> )
(
LOOKAHEAD(Expression() CompOp())
Expression()
CompOp()
Expression()
|
<OPEN_PARENTHESIS>
Condition()
(<AND> | <OR>)
Condition()
<CLOSE_PARENTHESIS>
)
|
Expression()
CompOp()
Expression()
}





share|improve this answer























  • Great solution, worked perfectly - really appreciated. Is the "LOOKAHEAD" function efficient?
    – Feint
    Apr 30 '15 at 23:35










  • It should be reasonably efficient.
    – Theodore Norvell
    May 1 '15 at 0:14















up vote
1
down vote



accepted










You can solve this with syntactic look ahead.



void CompOp() : {} { <EQUAL_CHECK> | <NOT_EQUAL> | <LESS> | <LESS_EQUAL> | <GREATER> | <GREATER_EQUAL> }

void Condition() : {}{
<NOT> Condition()
|
LOOKAHEAD(Expression() CompOp())
Expression()
CompOp()
Expression()
|
<OPEN_PARENTHESIS>
Condition()
(<AND> | <OR>)
Condition()
<CLOSE_PARENTHESIS>
}




Slightly more efficient is to only lookahead when there is a (.



void Condition() : {}{
<NOT> Condition()
| LOOKAHEAD( <OPEN_PARENTHESIS> )
(
LOOKAHEAD(Expression() CompOp())
Expression()
CompOp()
Expression()
|
<OPEN_PARENTHESIS>
Condition()
(<AND> | <OR>)
Condition()
<CLOSE_PARENTHESIS>
)
|
Expression()
CompOp()
Expression()
}





share|improve this answer























  • Great solution, worked perfectly - really appreciated. Is the "LOOKAHEAD" function efficient?
    – Feint
    Apr 30 '15 at 23:35










  • It should be reasonably efficient.
    – Theodore Norvell
    May 1 '15 at 0:14













up vote
1
down vote



accepted







up vote
1
down vote



accepted






You can solve this with syntactic look ahead.



void CompOp() : {} { <EQUAL_CHECK> | <NOT_EQUAL> | <LESS> | <LESS_EQUAL> | <GREATER> | <GREATER_EQUAL> }

void Condition() : {}{
<NOT> Condition()
|
LOOKAHEAD(Expression() CompOp())
Expression()
CompOp()
Expression()
|
<OPEN_PARENTHESIS>
Condition()
(<AND> | <OR>)
Condition()
<CLOSE_PARENTHESIS>
}




Slightly more efficient is to only lookahead when there is a (.



void Condition() : {}{
<NOT> Condition()
| LOOKAHEAD( <OPEN_PARENTHESIS> )
(
LOOKAHEAD(Expression() CompOp())
Expression()
CompOp()
Expression()
|
<OPEN_PARENTHESIS>
Condition()
(<AND> | <OR>)
Condition()
<CLOSE_PARENTHESIS>
)
|
Expression()
CompOp()
Expression()
}





share|improve this answer














You can solve this with syntactic look ahead.



void CompOp() : {} { <EQUAL_CHECK> | <NOT_EQUAL> | <LESS> | <LESS_EQUAL> | <GREATER> | <GREATER_EQUAL> }

void Condition() : {}{
<NOT> Condition()
|
LOOKAHEAD(Expression() CompOp())
Expression()
CompOp()
Expression()
|
<OPEN_PARENTHESIS>
Condition()
(<AND> | <OR>)
Condition()
<CLOSE_PARENTHESIS>
}




Slightly more efficient is to only lookahead when there is a (.



void Condition() : {}{
<NOT> Condition()
| LOOKAHEAD( <OPEN_PARENTHESIS> )
(
LOOKAHEAD(Expression() CompOp())
Expression()
CompOp()
Expression()
|
<OPEN_PARENTHESIS>
Condition()
(<AND> | <OR>)
Condition()
<CLOSE_PARENTHESIS>
)
|
Expression()
CompOp()
Expression()
}






share|improve this answer














share|improve this answer



share|improve this answer








edited Nov 9 at 18:12

























answered Apr 30 '15 at 18:50









Theodore Norvell

7,11541637




7,11541637












  • Great solution, worked perfectly - really appreciated. Is the "LOOKAHEAD" function efficient?
    – Feint
    Apr 30 '15 at 23:35










  • It should be reasonably efficient.
    – Theodore Norvell
    May 1 '15 at 0:14


















  • Great solution, worked perfectly - really appreciated. Is the "LOOKAHEAD" function efficient?
    – Feint
    Apr 30 '15 at 23:35










  • It should be reasonably efficient.
    – Theodore Norvell
    May 1 '15 at 0:14
















Great solution, worked perfectly - really appreciated. Is the "LOOKAHEAD" function efficient?
– Feint
Apr 30 '15 at 23:35




Great solution, worked perfectly - really appreciated. Is the "LOOKAHEAD" function efficient?
– Feint
Apr 30 '15 at 23:35












It should be reasonably efficient.
– Theodore Norvell
May 1 '15 at 0:14




It should be reasonably efficient.
– Theodore Norvell
May 1 '15 at 0:14












up vote
1
down vote













Using a single grammar for all expressions and defining precedence for all operators should solve your problem, at the expense of adding semantic checks for the type of expressions.



Expr -> AndExpr (<OR> AndExpr)*
AndExpr -> NotExpr (<AND> NotExpr)*
NotExpr -> <NOT>* RelExpr
RelExpr -> NumExpr () (<RELOP> NumExpr)?

NumExpr -> Term ((<PLUS>|<MINUS>) Term)*
Term -> Factor ((<MULTIPLY>|<DIVIDE>) Factor)*
Factor -> (<PLUS>|<MINUS>)* Atom
Atom -> <ID> | <NUMBER> | <OPEN_PARENTHESIS> Expr <CLOSE_PARENTHESIS>


The token <RELOP>represents your relational operators.



Note that this grammar let's you mix boolean and numerical expressions, so you should check for errors.



For example for Expr -> AndExpr the type returned would be the type of AndExpr. But for AndExpr <OR> AndExpr you should check that both AndExprs are boolean expressions and the type returned by Expr would be Boolean.






share|improve this answer





















  • Interesting solution! Thanks a lot. Is there an advantage to this solution over the "Look Ahead" solution provided above in terms of efficiency?
    – Feint
    Apr 30 '15 at 23:35










  • as @TheodoreNorvell pointed out, this way it would be easier to add boolean variabes to your language. I don't think you'll notice a difference in performance parsing normal programs.
    – 1010
    May 1 '15 at 1:41










  • You can make this approach highly efficient by using precedence climbing. engr.mun.ca/~theo/Misc/exp_parsing.htm
    – Theodore Norvell
    May 1 '15 at 10:36















up vote
1
down vote













Using a single grammar for all expressions and defining precedence for all operators should solve your problem, at the expense of adding semantic checks for the type of expressions.



Expr -> AndExpr (<OR> AndExpr)*
AndExpr -> NotExpr (<AND> NotExpr)*
NotExpr -> <NOT>* RelExpr
RelExpr -> NumExpr () (<RELOP> NumExpr)?

NumExpr -> Term ((<PLUS>|<MINUS>) Term)*
Term -> Factor ((<MULTIPLY>|<DIVIDE>) Factor)*
Factor -> (<PLUS>|<MINUS>)* Atom
Atom -> <ID> | <NUMBER> | <OPEN_PARENTHESIS> Expr <CLOSE_PARENTHESIS>


The token <RELOP>represents your relational operators.



Note that this grammar let's you mix boolean and numerical expressions, so you should check for errors.



For example for Expr -> AndExpr the type returned would be the type of AndExpr. But for AndExpr <OR> AndExpr you should check that both AndExprs are boolean expressions and the type returned by Expr would be Boolean.






share|improve this answer





















  • Interesting solution! Thanks a lot. Is there an advantage to this solution over the "Look Ahead" solution provided above in terms of efficiency?
    – Feint
    Apr 30 '15 at 23:35










  • as @TheodoreNorvell pointed out, this way it would be easier to add boolean variabes to your language. I don't think you'll notice a difference in performance parsing normal programs.
    – 1010
    May 1 '15 at 1:41










  • You can make this approach highly efficient by using precedence climbing. engr.mun.ca/~theo/Misc/exp_parsing.htm
    – Theodore Norvell
    May 1 '15 at 10:36













up vote
1
down vote










up vote
1
down vote









Using a single grammar for all expressions and defining precedence for all operators should solve your problem, at the expense of adding semantic checks for the type of expressions.



Expr -> AndExpr (<OR> AndExpr)*
AndExpr -> NotExpr (<AND> NotExpr)*
NotExpr -> <NOT>* RelExpr
RelExpr -> NumExpr () (<RELOP> NumExpr)?

NumExpr -> Term ((<PLUS>|<MINUS>) Term)*
Term -> Factor ((<MULTIPLY>|<DIVIDE>) Factor)*
Factor -> (<PLUS>|<MINUS>)* Atom
Atom -> <ID> | <NUMBER> | <OPEN_PARENTHESIS> Expr <CLOSE_PARENTHESIS>


The token <RELOP>represents your relational operators.



Note that this grammar let's you mix boolean and numerical expressions, so you should check for errors.



For example for Expr -> AndExpr the type returned would be the type of AndExpr. But for AndExpr <OR> AndExpr you should check that both AndExprs are boolean expressions and the type returned by Expr would be Boolean.






share|improve this answer












Using a single grammar for all expressions and defining precedence for all operators should solve your problem, at the expense of adding semantic checks for the type of expressions.



Expr -> AndExpr (<OR> AndExpr)*
AndExpr -> NotExpr (<AND> NotExpr)*
NotExpr -> <NOT>* RelExpr
RelExpr -> NumExpr () (<RELOP> NumExpr)?

NumExpr -> Term ((<PLUS>|<MINUS>) Term)*
Term -> Factor ((<MULTIPLY>|<DIVIDE>) Factor)*
Factor -> (<PLUS>|<MINUS>)* Atom
Atom -> <ID> | <NUMBER> | <OPEN_PARENTHESIS> Expr <CLOSE_PARENTHESIS>


The token <RELOP>represents your relational operators.



Note that this grammar let's you mix boolean and numerical expressions, so you should check for errors.



For example for Expr -> AndExpr the type returned would be the type of AndExpr. But for AndExpr <OR> AndExpr you should check that both AndExprs are boolean expressions and the type returned by Expr would be Boolean.







share|improve this answer












share|improve this answer



share|improve this answer










answered Apr 30 '15 at 18:47









1010

1,4351124




1,4351124












  • Interesting solution! Thanks a lot. Is there an advantage to this solution over the "Look Ahead" solution provided above in terms of efficiency?
    – Feint
    Apr 30 '15 at 23:35










  • as @TheodoreNorvell pointed out, this way it would be easier to add boolean variabes to your language. I don't think you'll notice a difference in performance parsing normal programs.
    – 1010
    May 1 '15 at 1:41










  • You can make this approach highly efficient by using precedence climbing. engr.mun.ca/~theo/Misc/exp_parsing.htm
    – Theodore Norvell
    May 1 '15 at 10:36


















  • Interesting solution! Thanks a lot. Is there an advantage to this solution over the "Look Ahead" solution provided above in terms of efficiency?
    – Feint
    Apr 30 '15 at 23:35










  • as @TheodoreNorvell pointed out, this way it would be easier to add boolean variabes to your language. I don't think you'll notice a difference in performance parsing normal programs.
    – 1010
    May 1 '15 at 1:41










  • You can make this approach highly efficient by using precedence climbing. engr.mun.ca/~theo/Misc/exp_parsing.htm
    – Theodore Norvell
    May 1 '15 at 10:36
















Interesting solution! Thanks a lot. Is there an advantage to this solution over the "Look Ahead" solution provided above in terms of efficiency?
– Feint
Apr 30 '15 at 23:35




Interesting solution! Thanks a lot. Is there an advantage to this solution over the "Look Ahead" solution provided above in terms of efficiency?
– Feint
Apr 30 '15 at 23:35












as @TheodoreNorvell pointed out, this way it would be easier to add boolean variabes to your language. I don't think you'll notice a difference in performance parsing normal programs.
– 1010
May 1 '15 at 1:41




as @TheodoreNorvell pointed out, this way it would be easier to add boolean variabes to your language. I don't think you'll notice a difference in performance parsing normal programs.
– 1010
May 1 '15 at 1:41












You can make this approach highly efficient by using precedence climbing. engr.mun.ca/~theo/Misc/exp_parsing.htm
– Theodore Norvell
May 1 '15 at 10:36




You can make this approach highly efficient by using precedence climbing. engr.mun.ca/~theo/Misc/exp_parsing.htm
– Theodore Norvell
May 1 '15 at 10:36


















draft saved

draft discarded




















































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.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f29973988%2fchoice-conflict-involving-two-expansions%23new-answer', 'question_page');
}
);

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







這個網誌中的熱門文章

Xamarin.form Move up view when keyboard appear

Post-Redirect-Get with Spring WebFlux and Thymeleaf

Anylogic : not able to use stopDelay()