Re: Ayacc/Aflex "entropy" (P2Ada)

[Ray Blaak <blaak@infomatch.com>]

Gautier <Gautier.deMontmollin@Maths.UniNe.CH> writes:
> I've observed the phenomenon that most enhancements brought to Pascal.Y in my
> attempts to extend P2Ada for the Borland-ish Pascal language "nebula"
> increases the "Reduce/Reduce conflicts" (what does it mean? nothing good
> surely...)  and can confuse the translator in unexpected way.
> 
> - Is there a strategy to avoid it (I'm completely amateur in ayacc) ?

I have worked on a Delphi reverse engineering tool* for Rational Rose, and have
implemented a Delphi (Object Pascal) parser. Let's just say I feel your pain.

Delphi has many strange quirks that cause ambiguities in a straight forward
yacc-like grammar. Single token look ahead is very often not enough to decide
how to resolve to a rule.

The problems are related to the fact than many "keywords" are not in fact
reserved. All of the procedure directives, for example, are not (e.g. the
"virtual" in "procedure Method; virtual;". Semicolons are often optional, which
really makes life difficult for a parser (e.g. "procedure Method virtual;" is
also fine).

The Delphi compiler tolerates a fair bit of divergence from its official
description, which also makes life interesting.

The ways to resolve this are as follows:

- Use a better tool. Visual Parse, for example, supports n-token look ahead (at
  the cost of probable exponential explosion). This is not useful for a
  publicly available grammar file however (VP is a Windows proprietary parsing
  system).

- Use a completely different tool. Recursive descent? I don't know what freely
  available tools are out there.

- Bite the bullet and deal with each ambiguity explicitly by constructing
  precise descriptions of how things can be resolved. Avoid null rules at all
  costs. For example, a record type looks like:

  <record> = "record" <record_body> "end"
  <record_body> = | <field> | <record_body> <field>

  Note the empty choice that makes a record body optional. This kind of thing,
  however, tends to screw up parsers. Instead, make things explicit:

  <record> = "record" "end" | "record" <record_body> "end"
  <record_body> = <field> | <record_body> <field>

For what its worth, ayacc is probably as good as any other yacc tool. The real
work is to make the grammar rules unambiguous.


* See http://www.ensemble-systems.com if you are interested. It is called the
  Rose Delphi Link
-- 
Cheers,                                        The Rhythm is around me,
                                               The Rhythm has control.
Ray Blaak                                      The Rhythm is inside me,
blaak@infomatch.com                            The Rhythm has my soul.