Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1814

Re: Alternatives to Syntax Trees

Show key headers only | View raw

On Tue, 17 Jan 2017 14:16:27 +0530, Seima Rao <seimarao@gmail.com>
wrote:

>    Q: What happens when we balance a syntax tree ?

Nothing, because you don't ever balance a syntax tree.  Doing so would
destroy the structure of the program and make it incomprehensible.

Syntax graphs (trees or DAGs) necessarily must reflect the structure
of the program.  Transformations made to the graph may affect local
structure, but the gross (overall) structure must remain.


>    Q: What happens when we use a B-tree (say) ?

A syntax graph is *not* a search tree in the conventional sense.  A
balanced tree would be a very *poor* choice of representation.

When a compiler uses a graph representation, typically the nodes will
be heterogenous: there will be unique node types for each different
language construct that needs to be represented.  Code walking the
graph will ignore nodes it does not understand.


>   (some might want to discuss structural analysis aka Muchnick)

Structural analyses are the very reasons a syntax tree can't be
balanced.


>   (some might want to discuss dbms)

What for?


>    Q: Yacc(and likewise tools) make use of a set of rules in helping
>         ,make progress in computing.
>
>        Are there approaches other then AI that use rule based computing?

"AI" is not synonymous with "rules".  Rule based decision systems - so
called "expert" systems - generally are no longer considered to be
"AI".  Attempts to model intelligent behavior using rule systems
failed miserably.  Expert systems are very important and have many
uses - they just aren't "AI".

Generally yacc is considered to be finite automata.  The (E)BNF
"rules" specify the structure of the automata and direct its behavior.
I suppose that an argument /could/ be made that is a "decision"
system, although I think such an argument would have to severely
stretch definitions.

At some level, all forms of computing that are based on Turing's
hypothesis can be considered to be "rule based".  The rules may be
explicit: a list of steps to follow, or implicit in the behavior of
the "processor" that executes the steps.

Things which are not rule based are out of the ordinary: analog
[continous signal] computing, neural networks, quantum [annealing]
computing, etc.  However, digital emulations/simulations of these
things *are* rule based.

George
[I can think of one place where one might balance a syntax tree -- an expression
like a+b+c+d would parse as a+(b+(c+d)) and for some kinds of code
generation you might know that + is associative so you could rewrite it to
(a+b)+(c+d).  But that's a very narrow and special case.  In general
I agree that compiler syntax trees and database B-trees have nothing in common
beyond the word "trees". -John]

Back to comp.compilers | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Alternatives to Syntax Trees Seima Rao <seimarao@gmail.com> - 2017-01-15 16:52 -0500
  Re: Alternatives to Syntax Trees Kaz Kylheku <221-501-9011@kylheku.com> - 2017-01-15 22:31 +0000
  Re: Alternatives to Syntax Trees George Neuner <gneuner2@comcast.net> - 2017-01-16 06:11 -0500
  Re: Alternatives to Syntax Trees rpw3@rpw3.org (Rob Warnock) - 2017-01-16 12:12 +0000
    Alternatives to Syntax Trees Seima Rao <seimarao@gmail.com> - 2017-01-17 14:16 +0530
      Re: Alternatives to Syntax Trees Kaz Kylheku <221-501-9011@kylheku.com> - 2017-01-17 22:39 +0000
      Re: Alternatives to Syntax Trees George Neuner <gneuner2@comcast.net> - 2017-01-17 22:08 -0500

csiph-web