Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2772

Re: Why are ambiguous grammars usually a bad idea? Why are languages usually defined and implemented with ambiguous grammars?

Show all headers | View raw

On Monday, December 27, 2021 at 4:19:08 AM UTC+1, Roger L Costello wrote:
> Question: Opine about why languages are usually defined and implemented with
> ambiguous grammars.
>
> My answer: Writing a grammar that completely avoids ambiguities might result
> in a grammar that is nightmarishly complex. It is easier/better to create a
> simple grammar and then add rules/descriptions which explain and resolve the
> ambiguities.

Another issue is that creating an unambiguous grammar (without extending the
parser generator with new features) would require inventing new abstract names
in grammar rules to handle cases resolved by compilation passes executed after
the parsing phase - but inventing new abstract names is very hard.

For example, in C/C++ the meaning of the statement "a*b;" depends on the code
parsed before the statement. If the code-before is "int a" then "a*b;" is a
statement containing an expression - if the code-before is "typedef int a;"
then "a*b;" is a variable declaration.

Another C/C++ example: "(a)+1.23" is a binary expression if "a" is an integer
variable - but it is a type conversion if "a" has been defined as "typedef
double a;".

In order to handle the above examples, the left-hand side of the [bison]
grammar rules might want to use names such as STMT__MUL_EXP_OR_VAR_DECL and
EXP__ADD_OR_CONVERT.

In some languages derived from C/C++ but different from C/C++, declarations in
the top-level scope and the package-level scope are order-independent. The
meaning of the statement "a*b;" might depend on the code parsed before the
statement or parsed after the statement.

The other option (that is: extending the parser generator with new features,
and thus avoiding abstract names in the rules of the grammar, and thus
avoiding a nightmarishly complex grammar) means that the parser
postpones the resolution of ambiguities until information computed in a
subsequent compilation phase resolves the ambiguity. This basically requires
both [the code generated by the parser generator] and [the programming
language used to implement the compiler] to be concurrent programming
languages.

In summary: In my opinion, the answer to the question "Why languages are
usually defined and implemented with ambiguous grammars?" translates to how
well the parser generator integrates with compilation stages executed after
the parsing stage.

-atom

Back to comp.compilers | Previous | Next | Find similar

Thread

Re: Why are ambiguous grammars usually a bad idea? Why are languages usually defined and implemented with ambiguous grammars? Jan Ziak <0xe2.0x9a.0x9b@gmail.com> - 2021-12-28 09:39 -0800

csiph-web