syntax complexity

I want to expand on what
George Neuner <gneuner2@comcast.net> 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
------------------------------------------------------------------------------"

Return to the comp.compilers page.
Search the comp.compilers archives again.