Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Christopher F Clark Newsgroups: comp.compilers Subject: syntax complexity Date: Tue, 21 Feb 2023 20:54:11 +0200 Organization: Compilers Central Sender: johnl@iecc.com Approved: comp.compilers@iecc.com Message-ID: <23-02-056@comp.compilers> References: <23-02-054@comp.compilers> References: <23-02-045@comp.compilers> <23-02-047@comp.compilers> <23-02-050@comp.compilers> MIME-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="15116"; mail-complaints-to="abuse@iecc.com" Keywords: syntax, design Posted-Date: 21 Feb 2023 14:10:52 EST X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:3395 I want to expand on what George Neuner wrote: > If you are restricted to BNF ... i.e. your tool does not allow > specifying precedence ... then recognizing even relatively simple > arithmetic expressions can (perhaps recursively) involve several > rules. Without precedence specifications, strict BNF does require nested rules to be created and named to implement the "natural" hierarchy of expression rules, e.g. that one does the multiplications before the additions. This was already recognized in 1973, when Steve Johnson et al, described how such specifications are implemented in yacc. See "Deterministic Parsing of Ambiguous Grammars". (https://dl.acm.org/doi/epdf/10.1145/360933.360969) Of course, the precedence parsing methods predate that paper, but it showed how one could easily annotate a BNF grammar to incorporate the idea. You can take the idea farther if you use numeric preferences for operators. That gives one a simple way of expressing the ordering of the operators and one "shifts" operators with higher or equal precedence and "reduces" when seeing an operator of lower precedence. (Note you can specify higher by either larger or smaller numbers. E.g. on a scale of 1 to 10, 1 can be highest, 1st place, or lowest, last place. One simply has to decide which way one wants it.) Similarly, in more recent times, the idea of ordering productions to specify precedence is used in Terence Parr's ANTLR4 to good effect. Again, the idea is not new. LEX used rule ordering to disambiguate which regular expression to use (and I suspect it was used before that). The same idea also is used in most Parsing Expression Grammar (PEG) implementations. Next, there was a paper in the 1980s or 90s whose title and author I have unfortunately forgotten, although I know it was published in TOPLAS, that suggested using examples to express preferences. And, that clearly goes back to the operators used in precedence parsing, e.g. ".<." which expressed which grouping had higher precedence and thus who should shift and who should reduce. But, no matter how one specifies it, the idea is the same. -- ****************************************************************************** Chris Clark email: christopher.f.clark@compiler-resources.com Compiler Resources, Inc. Web Site: http://world.std.com/~compres 23 Bailey Rd voice: (508) 435-5016 Berlin, MA 01503 USA twitter: @intel_chris ------------------------------------------------------------------------------"