0
$\begingroup$

When someone tries to formally describe the syntax of programming languages, they describe with context-free grammar, then for every program we can derive parse tree that would correspond to that program (if that program is derivable from that grammar), however if grammar is ambiguous, for a particular program, there may exist more than 1 parse tree, can this cause problems when someone tries to design compiler or some kind of parser for programming language, I thought checking types may decide this ambiguity, however shouldn't the syntax check and parse tree derivation be independent of checking types(assuming language is strongly typed). So, I think, formally, non-ambiguity of grammar is necessary when dealing with formal description of programming language, however I see no direct consequences of grammar being ambiguous, so can a formal grammar that describes syntax of programming language be ambiguous?

$\endgroup$
2
  • 1
    $\begingroup$ This may be relevant. $\endgroup$
    – Nathaniel
    Commented Apr 21 at 0:46
  • $\begingroup$ thanks, interesting reference, as I understand, they still fix it by making grammar non-ambiguous. I will wait for other answers. $\endgroup$
    – math boy
    Commented Apr 21 at 16:14

1 Answer 1

1
$\begingroup$

Grammars are just a tool. An ambiguous grammar is not a problem if the programming language demands that statements are to be parsed in a specific way, even though the grammar doesn't require it. In C, a simple situation is the "dangling else": "if (condition) statement1 else if (condition2) statement2 else statement3". Many grammars for this construction are ambiguous, but the C Standard which defines the C Programming Language requires that the second else goes with the second if, not with the first one.

Whatever makes life easier. The goal of a compiler writer is not to have a non-ambiguous grammar (that may be useful, but it isn't the goal), but a compiler that translates programs according to the rules of the programming language.

$\endgroup$
2
  • $\begingroup$ thanks for the answer, as I see C still decides dangling else problem by making grammar non-ambiguous. for compiler writer he has to take into account all possible parsing, but doesn't he have to choose single parse tree? $\endgroup$
    – math boy
    Commented Apr 23 at 20:36
  • 1
    $\begingroup$ Yes, the programmer has to choose a single parse tree. This can be achieved by having a non-ambiguous grammar and use a generic parsing method, or by having an ambiguous grammar that detects the ambiguity and uses some different mechanism to get the right parse tree. That will create a simpler grammar and a simpler parse tree. $\endgroup$
    – gnasher729
    Commented Apr 24 at 0:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.