Re: precedences vs. hierarchy

On Monday, June 6, 2016 at 7:35:45 AM UTC-5, Andreas Schramm wrote:
> (i) by precedence and associativity declarations, and
> (ii) by a hierarchy of non-terminals.
> are they equally respected approaches?


The latter is strictly more powerful than the former. In particular,
hierarchies can be circular or out of sequence, like the expression syntax in
C! Levels "Ex13" and "Ex14" here
https://www.scribd.com/doc/235318907/Combined-Syntax-for-C-90-C-99-and-C-11


Fortran used a the same approach as classical philology textbooks on language
in the 1950's and 1966; then went over to a kind of precedence syntax in the
1977 standard. I think the latest standard uses non-terminal tagging.


Prolog's expression syntax is non-terminal tagged (the "term" is the only real
non-terminal in the language).


From the vantage point of a parser -- seen as a PDT -- the thing you actually
want is a way to do relative comparisons with a finite lookahead sequence (of
typically just one token) versus your current context. So in fact, neither
approach described is actually the best, but one which has an "Action Table"
that plots contexts versus lookaheads (subcategorizing each into groups to
avoid duplicate rows and columns). When a context is favored you reduce you
carry out the action predicated on it (usually a reduce), while when a
lookahead is favored you carry out the action predicated on it (normally a
shift).


If you diagram the table like a quilt or tapestry, so that a vertical line
(and broken horizontal line woven "underneath" it) favors the column header,
while a horizontal line (and broken vertical line woven "underneath" it)
favors the row header, then a linearly-ordered hierarchy will show up as a
regular pattern in the tapestry. with horizontal lines dominating on a side
toward one of the corners of the weave, while the vertical lines dominate on
the opposite end.


The hierarchy tacit in the action table need not be linearly ordered at all
but can be twisted and knotted, even transcending what can be described by a
labeling of non-terminals. So this way is strictly more powerful than either
of the two methods described.

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