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

Groups > comp.compilers > #2883 > unrolled thread

Graphical representations of syntax trees?

Back to article view | Back to comp.compilers

Contents

  Graphical representations of syntax trees? Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.com> - 2022-02-04 20:20 +0000
    Re: Graphical representations of syntax trees? gah4 <gah4@u.washington.edu> - 2022-02-06 13:07 -0800
      Re: Graphical representations of syntax trees? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2022-02-06 23:38 +0100
      Re: Graphical representations of syntax trees? Steve Limb <stephenjohnlimb@gmail.com> - 2022-02-08 09:14 +0000
    Re: Graphical representations of syntax trees? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-02-06 22:32 +0000
      Re: Graphical representations of syntax trees? Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.com> - 2022-02-07 10:49 +0000
        Re: Graphical representations of syntax trees? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-02-07 18:33 +0000
        Re: Graphical representations of syntax trees? Jonathan Thornburg <jonathan@gold.bkis-orchard.net> - 2022-02-08 21:34 +0000
          Re: Graphical representations of syntax trees? Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2022-02-11 21:16 +0000
    Re: Graphical representations of syntax trees? "Alexei A. Frounze" <alexfrunews@gmail.com> - 2022-02-07 18:17 -0800

#2883 — Graphical representations of syntax trees?

Dear comp.compilers,

Are there any resources, or papers, about the subject of representing
syntax trees graphically?  Given the idea that a compiler reads syntax
and generates code, all I have to do to "print" it, is to generate post-
script.  Surely this has been done before.

My search-engine-fu did not result in any useful papers, or algorithms,
so I thought to ask here.

Thank you,
--
Johann | email: invalid -> com | www.myrkraverk.com/blog/
I'm not from the Internet, I just work there. | twitter: @myrkraverk

[toc] | [next] | [standalone]

#2884

On Sunday, February 6, 2022 at 10:28:41 AM UTC-8, Johann 'Myrkraverk' Oskarsson wrote:

> Are there any resources, or papers, about the subject of representing
> syntax trees graphically? Given the idea that a compiler reads syntax
> and generates code, all I have to do to "print" it, is to generate post-
> script. Surely this has been done before.

I think you mean what is sometimes called a parse tree.  It might be that
syntax tree sometimes has other meanings.

For an undergraduate linguistics class, I wrote a program to do parse trees
for English sentences. (Drawn on a Tektronix 4010, as that was before
Postscript.)  I believe at the same time I was taking the compilers class.

I added rules to the program, put some sentence into it, and printed out
the result.  Added more rules, and printed out more.  In the end, maybe
after I turned in the project, I found that it wouldn't correctly parse the
earlier ones. Note that there are many ambiguities in English, so one
should not be surprised when it finds the wrong tree.

The main complication with doing this, is positioning the items
on the page.  If you have unlimited page width, it isn't so bad, but often
they come out wider than you might like.  So you need extra logic to
make the page look nice to humans, which often isn't so natural.

I do remember knowing about programs to print out flow charts,
but that is different. But it also has the same problem of positioning
on the page.

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

#2886

On 2/6/22 10:07 PM, gah4 wrote:

> The main complication with doing this, is positioning the items
> on the page.

Right, that's a big problem. For my decompilers I wrote a flexible tree
representation of the parse tree with online navigation through the
tree. Source code for Atari ST in GfA Basic has gone long ago :-(

> I do remember knowing about programs to print out flow charts,
> but that is different. But it also has the same problem of positioning
> on the page.

That's not really different. A parse tree only includes more information
(nodes) than the original flow chart of the code.

Another solution may be a structure like used with source code. Blocks
or functions are not arranged LTR but top down. Subtrees are indented
and broken into multiple lines instead of nodes appended LTR.

DoDi

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

#2892

Antlr has a UI for parts of this. Not sure if you can print it though.
It tends to get a bit ‘deep’ for a more complete grammar.


> On 6 Feb 2022, at 21:07, gah4 <gah4@u.washington.edu> wrote:
>
> On Sunday, February 6, 2022 at 10:28:41 AM UTC-8, Johann 'Myrkraverk'
Oskarsson wrote:
>
>> Are there any resources, or papers, about the subject of representing
>> syntax trees graphically? Given the idea that a compiler reads syntax
>> and generates code, all I have to do to "print" it, is to generate post-
>> script. Surely this has been done before.

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

#2885

Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.com> writes:
>Are there any resources, or papers, about the subject of representing
>syntax trees graphically?

There are LaTeX modes for displaying trees.  There is also the
graphviz package for visualizing graphs.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

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

#2887

On 2/6/2022 10:32 PM, Anton Ertl wrote:
> Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.com> writes:
>> Are there any resources, or papers, about the subject of representing
>> syntax trees graphically?
>
> There are LaTeX modes for displaying trees.  There is also the
> graphviz package for visualizing graphs.

Sure, these are packages.  But no actual algorithms, or discussions of
how to do these things by myself.  Unless there's something in the latex
literature that I haven't found yet.

Between the time of sending this off to the moderation queue and
appearing, I found something about an Ada control flow graph making,
but all it does is offload the graphic bits to graphviz.

I was hoping, that if I did this by myself, I would not have to reinvent
the basics.  That's all.

--
Johann | email: invalid -> com | www.myrkraverk.com/blog/
I'm not from the Internet, I just work there. | twitter: @myrkraverk
[I suspect the practical problem is that for any but the tiniest programs
the parse tree will be so large and bushy as to be unreadable. -John]

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

#2888

Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.com> writes:
>On 2/6/2022 10:32 PM, Anton Ertl wrote:
>> Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.com> writes:
>>> Are there any resources, or papers, about the subject of representing
>>> syntax trees graphically?
>>
>> There are LaTeX modes for displaying trees.  There is also the
>> graphviz package for visualizing graphs.
>
>Sure, these are packages.  But no actual algorithms, or discussions of
>how to do these things by myself.

Seems pretty trivial to me.   If a rule

A: B C

is used for parsing a part of the input, you generate a node for this
rule (e.g., labeled "A"), with nodes for B and C as children.  If you
want it to look nice, you arrange for all the terminals to be at the
same (geometrical, not logical) level.  I think that's not very hard
with graphviz.  Then you get trees like:

    E
   /|\
  F |F
 /|\||
 1*2+3

A web search for "bison dot files" resulted in
<https://www.gnu.org/software/bison/manual/html_node/Graphviz.html>,
but this describes a visual representation of the parser, not the
parse tree.

>[I suspect the practical problem is that for any but the tiniest programs
>the parse tree will be so large and bushy as to be unreadable. -John]

IIRC (only read about that part, and a long time ago) graphviz
contains a tool that supports folding/unfolding parts of the graph
interactively, exactly because of this problem.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

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

#2893

Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.com> wrote:
> On 2/6/2022 10:32 PM, Anton Ertl wrote:
>> Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.com> writes:
>>> Are there any resources, or papers, about the subject of representing
>>> syntax trees graphically?
>>
>> There are LaTeX modes for displaying trees.  There is also the
>> graphviz package for visualizing graphs.
>
> Sure, these are packages.  But no actual algorithms, or discussions of
> how to do these things by myself.  Unless there's something in the latex
> literature that I haven't found yet.
[[...]]

There are many published papers and technical reports lined from
  https://www.graphviz.org/theory/

--
-- "Jonathan Thornburg [remove color- to reply]" <jthorn4242@pink-gmail.com>
   on the west coast of Canada, eh?

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

#2896

On 2/8/2022 9:34 PM, Jonathan Thornburg wrote:
> Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.com> wrote:
[snip]
>>
>> Sure, these are packages.  But no actual algorithms, or discussions of
>> how to do these things by myself.  Unless there's something in the latex
>> literature that I haven't found yet.
> [[...]]
>
> There are many published papers and technical reports lined from
>    https://www.graphviz.org/theory/

Thank you; that should keep my nightstand full of reading material for
months.

--
Johann | email: invalid -> com | www.myrkraverk.com/blog/
I'm not from the Internet, I just work there. | twitter: @myrkraverk

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

#2890

On Sunday, February 6, 2022 at 10:28:41 AM UTC-8, Johann 'Myrkraverk' Oskarsson wrote:
> Are there any resources, or papers, about the subject of representing
> syntax trees graphically? Given the idea that a compiler reads syntax
> and generates code, all I have to do to "print" it, is to generate post-
> script. Surely this has been done before.

Just how "graphically" do you need it represented?
S-expressions-like?
E.g. (+ a b) or +(a, b) or some such?

Alex
[From prior messages, I think we're talking about boxes and arrows. -John]

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web