bowen@cs.Buffalo.EDU (Devon Bowen) (02/16/90)
I'm not sure how many of you are into the draft standard just released or
how many of the standards committee members read this, but I'd like to
point out some problems we have with it and see if anyone can contribute
to a fix or a better understanding of the problem.
Right now we're working on generating a parser for the code with YACC.
There are a few places that the grammar published is syntactically ambiguous.
Reading the semantics section helps clear up this ambiguity, but we
have had a hard time convincing YACC to read the draft. There are a
number of places that generate reduce/reduce errors in YACC. For non-
YACCers this means that the same string of tokens can be parsed by
two or more different blocks of BNF. These errors require that the BNF
be re-written to avoid the ambiguities.
The most obvious example of this behavior is in the value constructors
(section A.5.5). Here you may have array, record or set constructors and
a constructor is basically a type that describes the constructor followed
by a list of things surrounded by set braces. For example, the following
blocks of code are valid:
a := FIB { 1, 1, 2, 2, 3, 5 };
b := MONTHS { 3, 7 };
c := CONSTS { 3.14, 2.7 };
d := MONTHS { 3..7, 9 };
In this example a, b, c, and d must be of type FIB, MONTHS, CONSTS, and
MONTHS, respectively. What is in the braces afterword are values to be
assigned as a whole instance of that type. And these types might be sets,
arrays or records but in most cases we can't tell. For example, FIB may
be an array, set or record; MONTHS must be a set because our second usage
contains an interval but the first usage looks like it could be any of
the three; and CONSTS might be an array or record because it conatins
floating point numbers.
Now the problem here is that the only way to disambiguate the constructs
is when the types are defined and semantic checks can be run. But, each of
these are parsed and defined with different sections of the BNF code. On
seeing one of the above lines, the *parser* is asked to make a decision as
to which type it is parsing and there is not yet enough information available.
This leads to some real problems when implementing the code.
The best solution is to just combine all three types into one and worry
about distinguishing them after parsing when types are well known. This
would be relatively easy to do, but the way the draft standard is set up,
it describes the semantics according to them being separate. So not only
does the syntax need to be hacked but so do the semantics. We are not
yet qualified to do this type of re-write since we are still trying to dig
up a VDM tutorial somewhere.
The other solution is to not use one of the popular parser generators and
go from scratch. But this increases the probability of bugs and puts the
effort of writing a standard compiler out of the reach of many programmers.
Not to mention that it's really silly. This hardly seems the best goal for
a standard.
So we're pretty well stuck on how to implement this thing.
Any comments or suggestions?
Seems to me that the task of re-writing should be done by the standards
committee and not left to the implementor. If it is left to the implementor,
there is room for interpretation. And that works against the whole effort
of standardization.
Devonrsutc@CS.SFU.CA ("rsutc%cs.sfu.ca") (02/17/90)
I have forwarded these comments on the draft to sc22 for further discussion. Further comments are welcome. Rick Sutcliffe Associate Professor \ (89-90 only) Visitor Computing Science & Mathematics \ School of Computing Science Trinity Western University \ Simon Fraser University 7600 Glover Rd., \ Burnaby, B.C. Canada V5A 1S6 Langley B.C. Canada V3A 4R9 e-mail: Rick_Sutcliffe@cc.sfu.ca OR Compuserve 76475,3406 wg13 (Modula-2) chairman Canada
bowen@CS.BUFFALO.EDU (Devon Bowen) (02/17/90)
In article <INFO-M2%90021613400071@UCF1VM.BITNET> you write: > I have forwarded these comments on the draft to sc22 for further discussion. > Further comments are welcome. Any replies you get would be appreciated. Devon