From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=unavailable autolearn_force=no version=3.4.4 X-Received: by 2002:a02:94e7:: with SMTP id x94mr16304525jah.5.1558397873233; Mon, 20 May 2019 17:17:53 -0700 (PDT) X-Received: by 2002:a9d:638f:: with SMTP id w15mr35151446otk.16.1558397873053; Mon, 20 May 2019 17:17:53 -0700 (PDT) Path: eternal-september.org!reader01.eternal-september.org!feeder.eternal-september.org!news.uzoreto.com!newsreader4.netcologne.de!news.netcologne.de!peer02.ams1!peer.ams1.xlned.com!news.xlned.com!peer02.am4!peer.am4.highwinds-media.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!u76no83913ita.0!news-out.google.com!p73ni107itp.0!nntp.google.com!i64no84110iti.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Mon, 20 May 2019 17:17:52 -0700 (PDT) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=47.185.234.171; posting-account=zwxLlwoAAAChLBU7oraRzNDnqQYkYbpo NNTP-Posting-Host: 47.185.234.171 References: <100ad407-090e-4316-9746-a4469568b53e@googlegroups.com> <64883feb-3e49-4c6a-855c-6673068e970c@googlegroups.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <3eb10021-ebc9-404c-8955-d9c7e8cc46e5@googlegroups.com> Subject: Re: Ada to Ada Translator ? From: Optikos Injection-Date: Tue, 21 May 2019 00:17:53 +0000 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Received-Bytes: 6196 X-Received-Body-CRC: 3503173782 Xref: reader01.eternal-september.org comp.lang.ada:56351 Date: 2019-05-20T17:17:52-07:00 List-Id: On Monday, May 20, 2019 at 6:19:55 PM UTC-5, Randy Brukardt wrote: > "Optikos" wrote in message=20 > news:64883feb-3e49-4c6a-855c-6673068e970c@googlegroups.com... > ... > >Conversely, if you utilize Yacc & Flex, it would be LR(k) bottom-up pars= er, > >which would be an admirable accomplishment in its own right. >=20 > Why? There are a number of such grammars out there, and Janus/Ada was=20 > designed from the beginning (in 1980!) using an LALR parser. (That was a= =20 > requirement of the class project at the University of Wisconsin that form= ed=20 > the basis of Janus/Ada, and we discovered that switching was impractical = as=20 > an LL parser was going to be several times larger than the 48K RAM availa= ble=20 > on CP/M-80. With some clever storage, we got the LR tables to fit with sp= ace=20 > to spare.) I said =E2=80=9Cadmirable=E2=80=9D, not unique. I was speaking in the cont= ext of an open-source Ada language-translator, not a closed-source one. > >It is purported to be more difficult to craft meaningful error messages = in=20 > >LR > >parsers, because LL parsers can explain in detail what was expected but, > >without care in crafting the grammar, LR parsers can lack the I meant here: easily-available-at-hand > >context -ual information > >to make "hmmm, it looks like you were trying to do /this/, but I found > >troublesome /that/ instead" type of error messages. >=20 > This is definitely not true and irrelevant at the same time. :-) An LR=20 > parser has plenty of context (there is always a state that contains a vas= t=20 > amount of information). The problem (to the extent that there is one) is= =20 > situations where you have already gone a long ways down an incorrect path= =20 > before finding out a problem You demonstrated what I was saying: in some LR reductions, the interesting= detail vis a vis interesting abstraction were a too far away from each oth= er to easily stitch back together in a meaningful way, such as for human-fr= iendly error message that isn't speaking in compiler-internal speak (or wor= se, LR clever-table-compaction-speak). > -- Ada luckily does not have many of these.=20 > (The worst one in Janus/Ada is an "is" following a subprogram in a packag= e=20 > specification; you've gone too far for an correction to fix the situation= .) >=20 > >Writing an LR-based (i.e., yacc-based) parser can create an awesome fast > >parser, but to do so requires a generous amount of expanding the base > >language's grammar to consider all the commonplace mistakes to build up > >enough context to emit that aforementioned type of useful error message. >=20 > Maybe for some languages, but there isn't much of that in Janus/Ada's=20 > grammar. Instead, error correction is based on the grammar tables=20 > themselves, and costs for insertion and deletions of tokens. That turns o= ut=20 > to be cheap, fast, and reliable -- the only issue is getting the costs ri= ght=20 > (and they aren't that critical, they're mainly used to break ties). >=20 > But I think that error messages for *syntax* in a compiler are pretty muc= h=20 > irrelevant these days; it's the IDE's job to check the syntax before call= ing=20 > the compiler, and in the IDE you only care about the first error anyway.= =20 > Presuming the check is fast enough (and it is on all but the largest file= s),=20 > you check, then fix, then check again until it is correct. I didn't say =E2=80=9Csyntax=E2=80=9D. My =E2=80=9C/this/=E2=80=9D and =E2= =80=9C/that/=E2=80=9D are wide-meaning enough to encompass semantic checks = as well. LR reductions are often abstracted enough at an index into a tabl= e to have (at the surface level without digging again) the easily-available= -at-hand contextual information to give good-human-friendly semantic error = messages of the category: I thought we were doing /this/ but then you gave= me conflicting /that/ semantically. Because they are human-crafted for hu= man consumption, LL parsers tend to not aggressively conflate abstractions = as much as LR parser tables try to conflate commonality to avoid combinator= ial or exponential explosion. With LR parsers, there is more digging & sif= ting through what just got successfully (fully-syntactically and partially-= semantically) parsed to analyze it. LL grammars do somewhat less of that r= ediscovery because LL parsers tended to preserve more implicit knowledge of= what has been accepted so far. All that I am saying is that LL parsers te= nd to have more interesting accumulated state implicitly laying around loca= lly that LR parsers need to overtly either accumulate via intentionally-cra= fted mementos a priori or go digging & sifting through a posteriori.