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

Groups > comp.compilers > #1808 > unrolled thread

Alternatives to Syntax Trees

Back to article view | Back to comp.compilers

Contents

  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

#1808 — Alternatives to Syntax Trees

Hi,

    Are there alternatives to syntax trees(i.e. the tree data structure)
    when compiling via yacc or yacc like  tools ?

Sincerely,
Seima Rao.
[There's quadruples, doubly linked lists of data structures.  They
make it easier to rearrange code, but harder to do just about anything
else.  There's also DAGs, which are trees that can have shared subtrees,
useful when you're doing common subexpressions or tail merging. -John]

[toc] | [next] | [standalone]

#1809

On 2017-01-15, Seima Rao <seimarao@gmail.com> wrote:
> Hi,
>
>     Are there alternatives to syntax trees(i.e. the tree data structure)
>     when compiling via yacc or yacc like  tools ?

If the language you are parsing has a context-free grammar suitable for
Yacc, then the parse corresponds to a tree. More precisely, a real-world
parse corresponds to a DAG: a tree in which some nodes are shared. For
instance if you're parsing Lisp, an input like (a a a) is converted to
DAG in which all three occurences of "a" point to the same symbol
object. This is because the symbols are "interned" as scanning takes
place.

Compilers do not use the tree data structure in all passes. Syntax
trees represent only the raw syntax. An intermediate representation
may be quite different: a graph containing chunks of instruction
sequences.

--
TXR Programming Lanuage: http://nongnu.org/txr
Music DIY Mailing List:  http://www.kylheku.com/diy
ADA MP-1 Mailing List:   http://www.kylheku.com/mp1

[toc] | [prev] | [next] | [standalone]

#1810

On Sun, 15 Jan 2017 16:52:15 -0500 (EST), Seima Rao
<seimarao@gmail.com> wrote:

>    Are there alternatives to syntax trees(i.e. the tree data structure)
>    when compiling via yacc or yacc like  tools ?

Parser tools don't limit the structure of the intermediate
representation.

>[There's quadruples, doubly linked lists of data structures.  They
>make it easier to rearrange code, but harder to do just about anything
>else.  There's also DAGs, which are trees that can have shared subtrees,
>useful when you're doing common subexpressions or tail merging. -John]

To add a bit to John's excellent response:

You can use a combined representation: e.g., a graph to represent
control - function defintions, loops, conditionals, etc. - and within
the graph use 3-address form to represent basic blocks (straight line
code).

Some analyses, e.g., determining dominance for EBB def/kill chains,
require both the basic blocks and the graph of their connectivity.


Also, "quadruples" are one form of 3-address representation.  There
are other forms of 3-address and you can implement them using either
lists or arrays.  Quadruples are the most commonly used because - as
John mentioned - they are the easiest to rearrange.

George

[toc] | [prev] | [next] | [standalone]

#1811

Seima Rao  <seimarao@gmail.com> wrote:
+---------------
|     Are there alternatives to syntax trees (i.e. the tree data
|     structure) when compiling via yacc or yacc like  tools ?
|
| [There's quadruples, doubly linked lists of data structures.  They
| make it easier to rearrange code, but harder to do just about anything
| else.  There's also DAGs, which are trees that can have shared subtrees,
| useful when you're doing common subexpressions or tail merging. -John]
+---------------

CMU Common Lisp (CMUCL) [circa 1990ff] used Implicit Continuation
Representation (ICR) as its first intermediate representation
(a.k.a. "IR1"). The key point w.r.t. Seima's question is that
IR1 is "represented as a flow-graph rather than a syntax tree":

    https://common-lisp.net/project/cmucl/doc/CMUCL-design.pdf
    Design of CMU Common Lisp
    Robert A. MacLachlan (ed)
    January 15, 2003
    ...
    Chapter 3
    Compiler Overview
    ...
    Two major intermediate representations are used in the compiler:

    * The Implicit Continuation Representation (ICR) represents
      the lisp-level semantics of the source code during the
      initial phases. Partial evaluation and semantic analysis are
      done on this representation. ICR is roughly equivalent to a
      subset of Common Lisp, but is represented as a flow-graph
      rather than a syntax tree. Phases which only manipulate ICR
      comprise the front end. It would be possible to use a
      different back end such as one that directly generated code
      for a stack machine.

    * The Virtual Machine Representation (VMR) [a.k.a. "IR2"]
      represents the implementation of the source code on a
      virtual machine. ...[trimmed]...

    Each phase is briefly described here. The phases from "local
    call analysis" to "constraint propagation" all interact; for
    maximum optimization, they are generally repeated until nothing
    new is discovered.
    ...[trimmed]...


-Rob

-----
Rob Warnock		<rpw3@rpw3.org>
627 26th Avenue		<http://rpw3.org/>
San Mateo, CA 94403

[toc] | [prev] | [next] | [standalone]

#1812

Thanks for your responses!

Your responses together with acm.org/dl(of which I
am currently not a member of) helped me mark
down the todos.

For those of you interested, I have some questions:

Specific

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

    You may or may not seek recourse to language-only domains.

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

General

    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?

--
Sincerely,
Seima Rao.
[To the first question, I suppose it might be useful if you're trying to reorganize
an expression to fit into a limited set of registers so each subtree is about the same
size, but it seems pretty marginal.  To the second, that's not a
meaningful question.  B-Trees are a way of organizing indexed data on disks, not
relevant to data structures a compiler might use in memory. -John]

[toc] | [prev] | [next] | [standalone]

#1813

On 2017-01-17, Seima Rao <seimarao@gmail.com> wrote:
> Thanks for your responses!
>
> Your responses together with acm.org/dl(of which I
> am currently not a member of) helped me mark
> down the todos.
>
> For those of you interested, I have some questions:
>
> Specific
>
>     Q: What happens when we balance a syntax tree ?

Something pretty obviously silly; why don't you try a toy example?

The structure of a syntax tree is of utmost significance; it
reflects the structure of the grammar rules to which
it corresponds.

Balancing operations wreck structure, preserving only
the inorder traversal.

If you wreck the structure, you wreck the syntax.

If this isn't clear, you will likely struggle later in the
course even though these answers will get you through the
current homework round.

[toc] | [prev] | [next] | [standalone]

#1814

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]

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web