Why are ambiguous grammars bad?Why is left recursion bad?Show that every grammar for an inherently ambiguous...
Use 1 9 6 2 in this order to make 75
What is the logic behind charging tax _in the form of money_ for owning property when the property does not produce money?
That's not my X, its Y is too Z
Is it okay to have a sequel start immediately after the end of the first book?
Is there a DSLR/mirorless camera with minimal options like a classic, simple SLR?
How to avoid typing 'git' at the begining of every Git command
Why are ambiguous grammars bad?
Remove border lines of SRTM tiles rendered as hillshade
The significance of kelvin as a unit of absolute temperature
Does the Nuka-Cola bottler actually generate nuka cola?
How (un)safe is it to ride barefoot?
What should I be wary of when insurer is taking a lot of time to decide whether car is repairable or a total loss?
Rail-to-rail op-amp only reaches 90% of VCC, works sometimes, not everytime
Trying to get (more) accurate readings from thermistor (electronics, math, and code inside)
Print "N NE E SE S SW W NW"
Multiband vertical antenna not working as expected
Flight compensation with agent
How durable are silver inlays on a blade?
What are the unintended or dangerous consequences of allowing spells that target and damage creatures to also target and damage objects?
Is it safe to remove python 2.7.15rc1 from Ubuntu 18.04?
What would be the way to say "just saying" in German? (Not the literal translation)
Was Self-modifying-code possible just using BASIC?
A Salute to Poetry
Why do radiation hardened IC packages often have long leads?
Why are ambiguous grammars bad?
Why is left recursion bad?Show that every grammar for an inherently ambiguous CFL has infinitely many ambiguitiesAmbiguous Grammar and SLR parsing table : No conflicts?Find unambiguous grammar for an ambiguous grammarHow to find whether a grammar is ambiguous?Converting Ambiguous Grammar G to LL(1)unambiguous grammar but it's not LR(1)LR parsers and ambiguous and non deterministic grammarsIs there any relationship between grammar being ambiguous and the language itself?Whether it's necessary for a grammar to be ambiguous when it is both left recursive and right recursive
$begingroup$
I understand that if there exist 2 or more left or right derivation trees, then the grammar is ambiguous, but I am unable to understand why it is so bad that everyone wants to get rid of it.
compilers ambiguity
edited 22 mins ago
user2357112
24717
asked 15 hours ago
HIRAK MONDALHIRAK MONDAL
414
New contributor
HIRAK MONDAL is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
|
show 2 more comments
$begingroup$
I understand that if there exist 2 or more left or right derivation trees, then the grammar is ambiguous, but I am unable to understand why it is so bad that everyone wants to get rid of it.
compilers ambiguity
edited 22 mins ago
user2357112
24717
asked 15 hours ago
HIRAK MONDALHIRAK MONDAL
414
New contributor
HIRAK MONDAL is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
Do you want a computer program to have ambiguous semantics?
$endgroup$
– Yuval Filmus
15 hours ago
$begingroup$
well thats naive question, do you like to read text what sentences is ambigious ? And its not about "bad" its about what task you have
$endgroup$
– user8426627
15 hours ago
$begingroup$
@user8426627 say we have 2 parse trees for a grammar what is the problem with it?
$endgroup$
– HIRAK MONDAL
15 hours ago
$begingroup$
@YuvalFilmus Please elaborate..
$endgroup$
– HIRAK MONDAL
15 hours ago
$begingroup$
say we have 1000 parce trees, what you will further do with those?
$endgroup$
– user8426627
15 hours ago
|
show 2 more comments
$begingroup$
I understand that if there exist 2 or more left or right derivation trees, then the grammar is ambiguous, but I am unable to understand why it is so bad that everyone wants to get rid of it.
compilers ambiguity
edited 22 mins ago
user2357112
24717
asked 15 hours ago
HIRAK MONDALHIRAK MONDAL
414
New contributor
HIRAK MONDAL is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I understand that if there exist 2 or more left or right derivation trees, then the grammar is ambiguous, but I am unable to understand why it is so bad that everyone wants to get rid of it.
compilers ambiguity
compilers ambiguity
edited 22 mins ago
user2357112
24717
asked 15 hours ago
HIRAK MONDALHIRAK MONDAL
414
New contributor
HIRAK MONDAL is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 22 mins ago
user2357112
24717
asked 15 hours ago
HIRAK MONDALHIRAK MONDAL
414
New contributor
HIRAK MONDAL is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 22 mins ago
user2357112
24717
edited 22 mins ago
user2357112
24717
edited 22 mins ago
user2357112
24717
24717
asked 15 hours ago
HIRAK MONDALHIRAK MONDAL
414
New contributor
HIRAK MONDAL is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 15 hours ago
HIRAK MONDALHIRAK MONDAL
414
asked 15 hours ago
HIRAK MONDALHIRAK MONDAL
414
414
New contributor
HIRAK MONDAL is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
HIRAK MONDAL is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$begingroup$
Do you want a computer program to have ambiguous semantics?
$endgroup$
– Yuval Filmus
15 hours ago
$begingroup$
well thats naive question, do you like to read text what sentences is ambigious ? And its not about "bad" its about what task you have
$endgroup$
– user8426627
15 hours ago
$begingroup$
@user8426627 say we have 2 parse trees for a grammar what is the problem with it?
$endgroup$
– HIRAK MONDAL
15 hours ago
$begingroup$
@YuvalFilmus Please elaborate..
$endgroup$
– HIRAK MONDAL
15 hours ago
$begingroup$
say we have 1000 parce trees, what you will further do with those?
$endgroup$
– user8426627
15 hours ago
|
show 2 more comments
$begingroup$
Do you want a computer program to have ambiguous semantics?
$endgroup$
– Yuval Filmus
15 hours ago
$begingroup$
well thats naive question, do you like to read text what sentences is ambigious ? And its not about "bad" its about what task you have
$endgroup$
– user8426627
15 hours ago
$begingroup$
@user8426627 say we have 2 parse trees for a grammar what is the problem with it?
$endgroup$
– HIRAK MONDAL
15 hours ago
$begingroup$
@YuvalFilmus Please elaborate..
$endgroup$
– HIRAK MONDAL
15 hours ago
$begingroup$
say we have 1000 parce trees, what you will further do with those?
$endgroup$
– user8426627
15 hours ago
$begingroup$
Do you want a computer program to have ambiguous semantics?
$endgroup$
– Yuval Filmus
15 hours ago
$begingroup$
Do you want a computer program to have ambiguous semantics?
$endgroup$
– Yuval Filmus
15 hours ago
$begingroup$
well thats naive question, do you like to read text what sentences is ambigious ? And its not about "bad" its about what task you have
$endgroup$
– user8426627
15 hours ago
$begingroup$
well thats naive question, do you like to read text what sentences is ambigious ? And its not about "bad" its about what task you have
$endgroup$
– user8426627
15 hours ago
$begingroup$
@user8426627 say we have 2 parse trees for a grammar what is the problem with it?
$endgroup$
– HIRAK MONDAL
15 hours ago
$begingroup$
@user8426627 say we have 2 parse trees for a grammar what is the problem with it?
$endgroup$
– HIRAK MONDAL
15 hours ago
$begingroup$
@YuvalFilmus Please elaborate..
$endgroup$
– HIRAK MONDAL
15 hours ago
$begingroup$
@YuvalFilmus Please elaborate..
$endgroup$
– HIRAK MONDAL
15 hours ago
$begingroup$
say we have 1000 parce trees, what you will further do with those?
$endgroup$
– user8426627
15 hours ago
$begingroup$
say we have 1000 parce trees, what you will further do with those?
$endgroup$
– user8426627
15 hours ago
|
show 2 more comments
2 Answers
2
active
oldest
votes
$begingroup$
Consider the following grammar for arithmetic expressions:
$$
X to X + X mid X - X mid X * X mid X / X mid texttt{var} mid texttt{const}
$$
Consider the following expression:
$$
a - b - c
$$
What is its value? Here are two possible parse trees:
According to the one on the left, we should interpret $a-b-c$ as $(a-b)-c$, which is the usual interpretation. According to the one on the right, we should interpret it as $a-(b-c) = a-b+c$, which is probably not what was intended.
When compiling a program, we want the interpretation of the syntax to be unambiguous. The easiest way to enforce this is using an unambiguous grammar. If the grammar is ambiguous, we can provide tie-breaking rules, like operator precedence and associativity. These rules can equivalently be expressed by making the grammar unambiguous in a particular way.
Parse trees generated using syntax tree generator.
answered 14 hours ago
Yuval FilmusYuval Filmus
201k15195359
$endgroup$
$begingroup$
Thanks a ton.. :) Now got it.. :)
$endgroup$
– HIRAK MONDAL
14 hours ago
$begingroup$
upvotes are not working as i have less than 15 reputation.. :(
$endgroup$
– HIRAK MONDAL
14 hours ago
$begingroup$
Hopefully the question will be upvoted enough for you to cross the threshold. You can also get some reputation points by accepting the answer.
$endgroup$
– Yuval Filmus
14 hours ago
3
$begingroup$
@HIRAKMONDAL The fact that the syntax is ambiguous is not real issue. the problem is that the two different parse trees have different behaviour. If your language has an ambiguous grammar but all parse trees for an expression are semantically equivalent then that wouldn't be a problem (e.g. take Yuval example and consider the case where your only operator+).
$endgroup$
– Bakuriu
6 hours ago
$begingroup$
@Bakuriu What you said is true, but "semantically equivalent" is a tall order. For example, floating point arithmetic is actually not associative (so the two "+" trees would not be equivalent). Additionally even if the answer came out the same way, undefined evaluation order matters a lot in languages where expressions can have side effects. So what you said is technically true but in practice it would be very unusual for a grammar's ambiguity to have no repercussions to the use of that grammar.
$endgroup$
– Richard Rast
2 hours ago
add a comment |
$begingroup$
Even if there’s a well-defined way to handle ambiguity (ambiguous expressions are syntax errors, for example), these grammars still cause trouble. As soon as you introduce ambiguity into a grammar, a parser can no longer be sure that the first match it gets is definitive. It needs to keep trying all the other ways to parse a statement, to rule out any ambiguity. You’re also not dealing with something simple like a LL(1) language, so you can’t use a simple, small, fast parser. Your grammar has symbols that can be read multiple ways, so you have to be prepared to backtrack a lot.
In some restricted domains, you might be able to get away with proving that all possible ways to parse an expression are equivalent (for example, because they represent an associative operation). (a+b) + c = a + (b+c).
answered 6 hours ago
DavislorDavislor
83348
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
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',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
});
}
});
HIRAK MONDAL is a new contributor. Be nice, and check out our Code of Conduct.
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%2fcs.stackexchange.com%2fquestions%2f110402%2fwhy-are-ambiguous-grammars-bad%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
$begingroup$
Consider the following grammar for arithmetic expressions:
$$
X to X + X mid X - X mid X * X mid X / X mid texttt{var} mid texttt{const}
$$
Consider the following expression:
$$
a - b - c
$$
What is its value? Here are two possible parse trees:
According to the one on the left, we should interpret $a-b-c$ as $(a-b)-c$, which is the usual interpretation. According to the one on the right, we should interpret it as $a-(b-c) = a-b+c$, which is probably not what was intended.
When compiling a program, we want the interpretation of the syntax to be unambiguous. The easiest way to enforce this is using an unambiguous grammar. If the grammar is ambiguous, we can provide tie-breaking rules, like operator precedence and associativity. These rules can equivalently be expressed by making the grammar unambiguous in a particular way.
Parse trees generated using syntax tree generator.
answered 14 hours ago
Yuval FilmusYuval Filmus
201k15195359
$endgroup$
$begingroup$
Thanks a ton.. :) Now got it.. :)
$endgroup$
– HIRAK MONDAL
14 hours ago
$begingroup$
upvotes are not working as i have less than 15 reputation.. :(
$endgroup$
– HIRAK MONDAL
14 hours ago
$begingroup$
Hopefully the question will be upvoted enough for you to cross the threshold. You can also get some reputation points by accepting the answer.
$endgroup$
– Yuval Filmus
14 hours ago
3
$begingroup$
@HIRAKMONDAL The fact that the syntax is ambiguous is not real issue. the problem is that the two different parse trees have different behaviour. If your language has an ambiguous grammar but all parse trees for an expression are semantically equivalent then that wouldn't be a problem (e.g. take Yuval example and consider the case where your only operator+).
$endgroup$
– Bakuriu
6 hours ago
$begingroup$
@Bakuriu What you said is true, but "semantically equivalent" is a tall order. For example, floating point arithmetic is actually not associative (so the two "+" trees would not be equivalent). Additionally even if the answer came out the same way, undefined evaluation order matters a lot in languages where expressions can have side effects. So what you said is technically true but in practice it would be very unusual for a grammar's ambiguity to have no repercussions to the use of that grammar.
$endgroup$
– Richard Rast
2 hours ago
add a comment |
$begingroup$
Consider the following grammar for arithmetic expressions:
$$
X to X + X mid X - X mid X * X mid X / X mid texttt{var} mid texttt{const}
$$
Consider the following expression:
$$
a - b - c
$$
What is its value? Here are two possible parse trees:
According to the one on the left, we should interpret $a-b-c$ as $(a-b)-c$, which is the usual interpretation. According to the one on the right, we should interpret it as $a-(b-c) = a-b+c$, which is probably not what was intended.
When compiling a program, we want the interpretation of the syntax to be unambiguous. The easiest way to enforce this is using an unambiguous grammar. If the grammar is ambiguous, we can provide tie-breaking rules, like operator precedence and associativity. These rules can equivalently be expressed by making the grammar unambiguous in a particular way.
Parse trees generated using syntax tree generator.
answered 14 hours ago
Yuval FilmusYuval Filmus
201k15195359
$endgroup$
$begingroup$
Thanks a ton.. :) Now got it.. :)
$endgroup$
– HIRAK MONDAL
14 hours ago
$begingroup$
upvotes are not working as i have less than 15 reputation.. :(
$endgroup$
– HIRAK MONDAL
14 hours ago
$begingroup$
Hopefully the question will be upvoted enough for you to cross the threshold. You can also get some reputation points by accepting the answer.
$endgroup$
– Yuval Filmus
14 hours ago
3
$begingroup$
@HIRAKMONDAL The fact that the syntax is ambiguous is not real issue. the problem is that the two different parse trees have different behaviour. If your language has an ambiguous grammar but all parse trees for an expression are semantically equivalent then that wouldn't be a problem (e.g. take Yuval example and consider the case where your only operator+).
$endgroup$
– Bakuriu
6 hours ago
$begingroup$
@Bakuriu What you said is true, but "semantically equivalent" is a tall order. For example, floating point arithmetic is actually not associative (so the two "+" trees would not be equivalent). Additionally even if the answer came out the same way, undefined evaluation order matters a lot in languages where expressions can have side effects. So what you said is technically true but in practice it would be very unusual for a grammar's ambiguity to have no repercussions to the use of that grammar.
$endgroup$
– Richard Rast
2 hours ago
add a comment |
$begingroup$
Consider the following grammar for arithmetic expressions:
$$
X to X + X mid X - X mid X * X mid X / X mid texttt{var} mid texttt{const}
$$
Consider the following expression:
$$
a - b - c
$$
What is its value? Here are two possible parse trees:
According to the one on the left, we should interpret $a-b-c$ as $(a-b)-c$, which is the usual interpretation. According to the one on the right, we should interpret it as $a-(b-c) = a-b+c$, which is probably not what was intended.
When compiling a program, we want the interpretation of the syntax to be unambiguous. The easiest way to enforce this is using an unambiguous grammar. If the grammar is ambiguous, we can provide tie-breaking rules, like operator precedence and associativity. These rules can equivalently be expressed by making the grammar unambiguous in a particular way.
Parse trees generated using syntax tree generator.
answered 14 hours ago
Yuval FilmusYuval Filmus
201k15195359
$endgroup$
Consider the following grammar for arithmetic expressions:
$$
X to X + X mid X - X mid X * X mid X / X mid texttt{var} mid texttt{const}
$$
Consider the following expression:
$$
a - b - c
$$
What is its value? Here are two possible parse trees:
According to the one on the left, we should interpret $a-b-c$ as $(a-b)-c$, which is the usual interpretation. According to the one on the right, we should interpret it as $a-(b-c) = a-b+c$, which is probably not what was intended.
When compiling a program, we want the interpretation of the syntax to be unambiguous. The easiest way to enforce this is using an unambiguous grammar. If the grammar is ambiguous, we can provide tie-breaking rules, like operator precedence and associativity. These rules can equivalently be expressed by making the grammar unambiguous in a particular way.
Parse trees generated using syntax tree generator.
answered 14 hours ago
Yuval FilmusYuval Filmus
201k15195359
answered 14 hours ago
Yuval FilmusYuval Filmus
201k15195359
answered 14 hours ago
Yuval FilmusYuval Filmus
201k15195359
answered 14 hours ago
Yuval FilmusYuval Filmus
201k15195359
201k15195359
$begingroup$
Thanks a ton.. :) Now got it.. :)
$endgroup$
– HIRAK MONDAL
14 hours ago
$begingroup$
upvotes are not working as i have less than 15 reputation.. :(
$endgroup$
– HIRAK MONDAL
14 hours ago
$begingroup$
Hopefully the question will be upvoted enough for you to cross the threshold. You can also get some reputation points by accepting the answer.
$endgroup$
– Yuval Filmus
14 hours ago
3
$begingroup$
@HIRAKMONDAL The fact that the syntax is ambiguous is not real issue. the problem is that the two different parse trees have different behaviour. If your language has an ambiguous grammar but all parse trees for an expression are semantically equivalent then that wouldn't be a problem (e.g. take Yuval example and consider the case where your only operator+).
$endgroup$
– Bakuriu
6 hours ago
$begingroup$
@Bakuriu What you said is true, but "semantically equivalent" is a tall order. For example, floating point arithmetic is actually not associative (so the two "+" trees would not be equivalent). Additionally even if the answer came out the same way, undefined evaluation order matters a lot in languages where expressions can have side effects. So what you said is technically true but in practice it would be very unusual for a grammar's ambiguity to have no repercussions to the use of that grammar.
$endgroup$
– Richard Rast
2 hours ago
add a comment |
$begingroup$
Thanks a ton.. :) Now got it.. :)
$endgroup$
– HIRAK MONDAL
14 hours ago
$begingroup$
upvotes are not working as i have less than 15 reputation.. :(
$endgroup$
– HIRAK MONDAL
14 hours ago
$begingroup$
Hopefully the question will be upvoted enough for you to cross the threshold. You can also get some reputation points by accepting the answer.
$endgroup$
– Yuval Filmus
14 hours ago
3
$begingroup$
@HIRAKMONDAL The fact that the syntax is ambiguous is not real issue. the problem is that the two different parse trees have different behaviour. If your language has an ambiguous grammar but all parse trees for an expression are semantically equivalent then that wouldn't be a problem (e.g. take Yuval example and consider the case where your only operator+).
$endgroup$
– Bakuriu
6 hours ago
$begingroup$
@Bakuriu What you said is true, but "semantically equivalent" is a tall order. For example, floating point arithmetic is actually not associative (so the two "+" trees would not be equivalent). Additionally even if the answer came out the same way, undefined evaluation order matters a lot in languages where expressions can have side effects. So what you said is technically true but in practice it would be very unusual for a grammar's ambiguity to have no repercussions to the use of that grammar.
$endgroup$
– Richard Rast
2 hours ago
$begingroup$
Thanks a ton.. :) Now got it.. :)
$endgroup$
– HIRAK MONDAL
14 hours ago
$begingroup$
Thanks a ton.. :) Now got it.. :)
$endgroup$
– HIRAK MONDAL
14 hours ago
$begingroup$
upvotes are not working as i have less than 15 reputation.. :(
$endgroup$
– HIRAK MONDAL
14 hours ago
$begingroup$
upvotes are not working as i have less than 15 reputation.. :(
$endgroup$
– HIRAK MONDAL
14 hours ago
$begingroup$
Hopefully the question will be upvoted enough for you to cross the threshold. You can also get some reputation points by accepting the answer.
$endgroup$
– Yuval Filmus
14 hours ago
$begingroup$
Hopefully the question will be upvoted enough for you to cross the threshold. You can also get some reputation points by accepting the answer.
$endgroup$
– Yuval Filmus
14 hours ago
3
3
$begingroup$
@HIRAKMONDAL The fact that the syntax is ambiguous is not real issue. the problem is that the two different parse trees have different behaviour. If your language has an ambiguous grammar but all parse trees for an expression are semantically equivalent then that wouldn't be a problem (e.g. take Yuval example and consider the case where your only operator
+).$endgroup$
– Bakuriu
6 hours ago
$begingroup$
@HIRAKMONDAL The fact that the syntax is ambiguous is not real issue. the problem is that the two different parse trees have different behaviour. If your language has an ambiguous grammar but all parse trees for an expression are semantically equivalent then that wouldn't be a problem (e.g. take Yuval example and consider the case where your only operator
+).$endgroup$
– Bakuriu
6 hours ago
$begingroup$
@Bakuriu What you said is true, but "semantically equivalent" is a tall order. For example, floating point arithmetic is actually not associative (so the two "+" trees would not be equivalent). Additionally even if the answer came out the same way, undefined evaluation order matters a lot in languages where expressions can have side effects. So what you said is technically true but in practice it would be very unusual for a grammar's ambiguity to have no repercussions to the use of that grammar.
$endgroup$
– Richard Rast
2 hours ago
$begingroup$
@Bakuriu What you said is true, but "semantically equivalent" is a tall order. For example, floating point arithmetic is actually not associative (so the two "+" trees would not be equivalent). Additionally even if the answer came out the same way, undefined evaluation order matters a lot in languages where expressions can have side effects. So what you said is technically true but in practice it would be very unusual for a grammar's ambiguity to have no repercussions to the use of that grammar.
$endgroup$
– Richard Rast
2 hours ago
add a comment |
$begingroup$
Even if there’s a well-defined way to handle ambiguity (ambiguous expressions are syntax errors, for example), these grammars still cause trouble. As soon as you introduce ambiguity into a grammar, a parser can no longer be sure that the first match it gets is definitive. It needs to keep trying all the other ways to parse a statement, to rule out any ambiguity. You’re also not dealing with something simple like a LL(1) language, so you can’t use a simple, small, fast parser. Your grammar has symbols that can be read multiple ways, so you have to be prepared to backtrack a lot.
In some restricted domains, you might be able to get away with proving that all possible ways to parse an expression are equivalent (for example, because they represent an associative operation). (a+b) + c = a + (b+c).
answered 6 hours ago
DavislorDavislor
83348
$endgroup$
add a comment |
$begingroup$
Even if there’s a well-defined way to handle ambiguity (ambiguous expressions are syntax errors, for example), these grammars still cause trouble. As soon as you introduce ambiguity into a grammar, a parser can no longer be sure that the first match it gets is definitive. It needs to keep trying all the other ways to parse a statement, to rule out any ambiguity. You’re also not dealing with something simple like a LL(1) language, so you can’t use a simple, small, fast parser. Your grammar has symbols that can be read multiple ways, so you have to be prepared to backtrack a lot.
In some restricted domains, you might be able to get away with proving that all possible ways to parse an expression are equivalent (for example, because they represent an associative operation). (a+b) + c = a + (b+c).
answered 6 hours ago
DavislorDavislor
83348
$endgroup$
add a comment |
$begingroup$
Even if there’s a well-defined way to handle ambiguity (ambiguous expressions are syntax errors, for example), these grammars still cause trouble. As soon as you introduce ambiguity into a grammar, a parser can no longer be sure that the first match it gets is definitive. It needs to keep trying all the other ways to parse a statement, to rule out any ambiguity. You’re also not dealing with something simple like a LL(1) language, so you can’t use a simple, small, fast parser. Your grammar has symbols that can be read multiple ways, so you have to be prepared to backtrack a lot.
In some restricted domains, you might be able to get away with proving that all possible ways to parse an expression are equivalent (for example, because they represent an associative operation). (a+b) + c = a + (b+c).
answered 6 hours ago
DavislorDavislor
83348
$endgroup$
Even if there’s a well-defined way to handle ambiguity (ambiguous expressions are syntax errors, for example), these grammars still cause trouble. As soon as you introduce ambiguity into a grammar, a parser can no longer be sure that the first match it gets is definitive. It needs to keep trying all the other ways to parse a statement, to rule out any ambiguity. You’re also not dealing with something simple like a LL(1) language, so you can’t use a simple, small, fast parser. Your grammar has symbols that can be read multiple ways, so you have to be prepared to backtrack a lot.
In some restricted domains, you might be able to get away with proving that all possible ways to parse an expression are equivalent (for example, because they represent an associative operation). (a+b) + c = a + (b+c).
answered 6 hours ago
DavislorDavislor
83348
answered 6 hours ago
DavislorDavislor
83348
answered 6 hours ago
DavislorDavislor
83348
answered 6 hours ago
DavislorDavislor
83348
83348
add a comment |
add a comment |
HIRAK MONDAL is a new contributor. Be nice, and check out our Code of Conduct.
HIRAK MONDAL is a new contributor. Be nice, and check out our Code of Conduct.
HIRAK MONDAL is a new contributor. Be nice, and check out our Code of Conduct.
HIRAK MONDAL is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Computer Science Stack Exchange!
- 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.
Use MathJax to format equations. MathJax reference.
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%2fcs.stackexchange.com%2fquestions%2f110402%2fwhy-are-ambiguous-grammars-bad%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
$begingroup$
Do you want a computer program to have ambiguous semantics?
$endgroup$
– Yuval Filmus
15 hours ago
$begingroup$
well thats naive question, do you like to read text what sentences is ambigious ? And its not about "bad" its about what task you have
$endgroup$
– user8426627
15 hours ago
$begingroup$
@user8426627 say we have 2 parse trees for a grammar what is the problem with it?
$endgroup$
– HIRAK MONDAL
15 hours ago
$begingroup$
@YuvalFilmus Please elaborate..
$endgroup$
– HIRAK MONDAL
15 hours ago
$begingroup$
say we have 1000 parce trees, what you will further do with those?
$endgroup$
– user8426627
15 hours ago