Mfcttrf

Why are ambiguous grammars bad?

bash vs. zsh: What are the practical differences?

noalign caused by multirow and colors

Generate certain list from two lists

Do you have to have figures when playing D&D?

Should I refuse to be named as co-author of a low quality paper?

Are the guests in Westworld forbidden to tell the hosts that they are robots?

Why is Na5 not played in this line of the French Defense, Advance Variation?

Can there be absolute velocity?

As easy as Three, Two, One... How fast can you go from Five to Four?

Three questions

Do you really need a KDF when you have a PRF?

Extracting data from Plot

Does the Nuka-Cola bottler actually generate nuka cola?

How was the airlock installed on the Space Shuttle mid deck?

How can I remove material from this wood beam?

What should I be wary of when insurer is taking a lot of time to decide whether car is repairable or a total loss?

Should I put programming books I wrote a few years ago on my resume?

What plausible reason could I give for my FTL drive only working in space

What STL algorithm can determine if exactly one item in a container satisfies a predicate?

Increase speed altering column on large table to NON NULL

How do you play "tenth" chords on the guitar?

What should I discuss with my DM prior to my first game?

Why isn't Bash trap working if output is redirected to stdout?

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

8

1

$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

share|cite|improve this question

edited 24 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

8

1

$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

share|cite|improve this question

edited 24 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

share|cite|improve this question

edited 24 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$

share|cite|improve this question

edited 24 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.

share|cite|improve this question

edited 24 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 24 mins ago

user2357112

24717

edited 24 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.

asked 15 hours ago

HIRAK MONDALHIRAK MONDAL

414

2 Answers
2

active

oldest

votes

12

$begingroup$

Consider the following grammar for arithmetic expressions:
$$
X to X + X mid X - X mid X * X mid X / X mid textttvar mid textttconst
$$
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.

share|cite|improve this answer

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 | 

2

$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).

share|cite|improve this answer

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.

draft saved

draft discarded

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

Name

Email

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

Name

Email

Required, but never shown

12

$begingroup$

Consider the following grammar for arithmetic expressions:
$$
X to X + X mid X - X mid X * X mid X / X mid textttvar mid textttconst
$$
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.

share|cite|improve this answer

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 | 

12

$begingroup$

Consider the following grammar for arithmetic expressions:
$$
X to X + X mid X - X mid X * X mid X / X mid textttvar mid textttconst
$$
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.

share|cite|improve this answer

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 textttvar mid textttconst
$$
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.

share|cite|improve this answer

answered 14 hours ago

Yuval FilmusYuval Filmus

201k15195359

$endgroup$

share|cite|improve this answer

answered 14 hours ago

Yuval FilmusYuval Filmus

201k15195359

answered 14 hours ago

Yuval FilmusYuval Filmus

201k15195359

answered 14 hours ago

Yuval FilmusYuval Filmus

201k15195359

2

$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).

share|cite|improve this answer

answered 6 hours ago

DavislorDavislor

83348

$endgroup$

add a comment | 

2

$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).

share|cite|improve this answer

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).

share|cite|improve this answer

answered 6 hours ago

DavislorDavislor

83348

$endgroup$

share|cite|improve this answer

answered 6 hours ago

DavislorDavislor

83348

answered 6 hours ago

DavislorDavislor

83348

answered 6 hours ago

DavislorDavislor

83348