Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

The Wright Bothers weren't the first to fly. They were just the first not to crash.


devel / comp.compilers / Re: Graphical representations of syntax trees?

SubjectAuthor
* Graphical representations of syntax trees?Johann 'Myrkraverk' Oskarsson
+* Re: Graphical representations of syntax trees?gah4
|+- Re: Graphical representations of syntax trees?Hans-Peter Diettrich
|`- Re: Graphical representations of syntax trees?Steve Limb
+* Re: Graphical representations of syntax trees?Anton Ertl
|`* Re: Graphical representations of syntax trees?Johann 'Myrkraverk' Oskarsson
| +- Re: Graphical representations of syntax trees?Anton Ertl
| `* Re: Graphical representations of syntax trees?Jonathan Thornburg
|  `- Re: Graphical representations of syntax trees?Johann 'Myrkraverk' Oskarsson
`- Re: Graphical representations of syntax trees?Alexei A. Frounze

1
Graphical representations of syntax trees?

<22-02-004@comp.compilers>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=266&group=comp.compilers#266

 copy link   Newsgroups: comp.compilers
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: joh...@myrkraverk.com (Johann 'Myrkraverk' Oskarsson)
Newsgroups: comp.compilers
Subject: Graphical representations of syntax trees?
Date: Fri, 4 Feb 2022 20:20:00 +0000
Organization: Easynews - www.easynews.com
Lines: 14
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <22-02-004@comp.compilers>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970";
logging-data="68722"; mail-complaints-to="abuse@iecc.com"
Keywords: parse, question
Posted-Date: 06 Feb 2022 13:28:39 EST
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Content-Language: en-US
 by: Johann 'Myrkrav - Fri, 4 Feb 2022 20:20 UTC

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

Re: Graphical representations of syntax trees?

<22-02-005@comp.compilers>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=267&group=comp.compilers#267

 copy link   Newsgroups: comp.compilers
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: gah...@u.washington.edu (gah4)
Newsgroups: comp.compilers
Subject: Re: Graphical representations of syntax trees?
Date: Sun, 6 Feb 2022 13:07:00 -0800 (PST)
Organization: Compilers Central
Lines: 28
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <22-02-005@comp.compilers>
References: <22-02-004@comp.compilers>
Mime-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970";
logging-data="48766"; mail-complaints-to="abuse@iecc.com"
Keywords: parse, tools
Posted-Date: 06 Feb 2022 16:40:44 EST
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
In-Reply-To: <22-02-004@comp.compilers>
 by: gah4 - Sun, 6 Feb 2022 21:07 UTC

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.

Re: Graphical representations of syntax trees?

<22-02-006@comp.compilers>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=268&group=comp.compilers#268

 copy link   Newsgroups: comp.compilers
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: ant...@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.compilers
Subject: Re: Graphical representations of syntax trees?
Date: Sun, 06 Feb 2022 22:32:12 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 12
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <22-02-006@comp.compilers>
References: <22-02-004@comp.compilers>
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970";
logging-data="89814"; mail-complaints-to="abuse@iecc.com"
Keywords: parse, tools
Posted-Date: 06 Feb 2022 18:22:35 EST
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
 by: Anton Ertl - Sun, 6 Feb 2022 22:32 UTC

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/

Re: Graphical representations of syntax trees?

<22-02-007@comp.compilers>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=269&group=comp.compilers#269

 copy link   Newsgroups: comp.compilers
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: DrDiettr...@netscape.net (Hans-Peter Diettrich)
Newsgroups: comp.compilers
Subject: Re: Graphical representations of syntax trees?
Date: Sun, 6 Feb 2022 23:38:31 +0100
Organization: Compilers Central
Lines: 21
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <22-02-007@comp.compilers>
References: <22-02-004@comp.compilers> <22-02-005@comp.compilers>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970";
logging-data="90235"; mail-complaints-to="abuse@iecc.com"
Keywords: parse, tools
Posted-Date: 06 Feb 2022 18:23:06 EST
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
 by: Hans-Peter Diettrich - Sun, 6 Feb 2022 22:38 UTC

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

Re: Graphical representations of syntax trees?

<22-02-008@comp.compilers>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=270&group=comp.compilers#270

 copy link   Newsgroups: comp.compilers
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: joh...@myrkraverk.com (Johann 'Myrkraverk' Oskarsson)
Newsgroups: comp.compilers
Subject: Re: Graphical representations of syntax trees?
Date: Mon, 7 Feb 2022 10:49:30 +0000
Organization: Easynews - www.easynews.com
Lines: 24
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <22-02-008@comp.compilers>
References: <22-02-004@comp.compilers> <22-02-006@comp.compilers>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970";
logging-data="54608"; mail-complaints-to="abuse@iecc.com"
Keywords: parse, tools, comment
Posted-Date: 07 Feb 2022 13:01:12 EST
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Content-Language: en-US
In-Reply-To: <22-02-006@comp.compilers>
 by: Johann 'Myrkrav - Mon, 7 Feb 2022 10:49 UTC

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]

Re: Graphical representations of syntax trees?

<22-02-009@comp.compilers>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=271&group=comp.compilers#271

 copy link   Newsgroups: comp.compilers
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: ant...@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.compilers
Subject: Re: Graphical representations of syntax trees?
Date: Mon, 07 Feb 2022 18:33:57 GMT
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
Lines: 45
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <22-02-009@comp.compilers>
References: <22-02-004@comp.compilers> <22-02-006@comp.compilers> <22-02-008@comp.compilers>
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970";
logging-data="88498"; mail-complaints-to="abuse@iecc.com"
Keywords: parse, tools
Posted-Date: 07 Feb 2022 14:13:03 EST
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
 by: Anton Ertl - Mon, 7 Feb 2022 18:33 UTC

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/

Re: Graphical representations of syntax trees?

<22-02-011@comp.compilers>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=273&group=comp.compilers#273

 copy link   Newsgroups: comp.compilers
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: alexfrun...@gmail.com (Alexei A. Frounze)
Newsgroups: comp.compilers
Subject: Re: Graphical representations of syntax trees?
Date: Mon, 7 Feb 2022 18:17:07 -0800 (PST)
Organization: Compilers Central
Lines: 12
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <22-02-011@comp.compilers>
References: <22-02-004@comp.compilers>
Mime-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970";
logging-data="91006"; mail-complaints-to="abuse@iecc.com"
Keywords: tools, parse, comment
Posted-Date: 07 Feb 2022 21:54:46 EST
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
In-Reply-To: <22-02-004@comp.compilers>
 by: Alexei A. Frounze - Tue, 8 Feb 2022 02:17 UTC

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]

Re: Graphical representations of syntax trees?

<22-02-013@comp.compilers>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=275&group=comp.compilers#275

 copy link   Newsgroups: comp.compilers
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: stephenj...@gmail.com (Steve Limb)
Newsgroups: comp.compilers
Subject: Re: Graphical representations of syntax trees?
Date: Tue, 8 Feb 2022 09:14:41 +0000
Organization: Compilers Central
Lines: 13
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <22-02-013@comp.compilers>
References: <22-02-004@comp.compilers> <22-02-005@comp.compilers>
Mime-Version: 1.0 (Mac OS X Mail 15.0 \(3693.20.0.1.32\))
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970";
logging-data="85722"; mail-complaints-to="abuse@iecc.com"
Keywords: parse, tools
Posted-Date: 08 Feb 2022 09:49:17 EST
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
In-Reply-To: <22-02-005@comp.compilers>
 by: Steve Limb - Tue, 8 Feb 2022 09:14 UTC

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.

Re: Graphical representations of syntax trees?

<22-02-014@comp.compilers>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=276&group=comp.compilers#276

 copy link   Newsgroups: comp.compilers
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: jonat...@gold.bkis-orchard.net (Jonathan Thornburg)
Newsgroups: comp.compilers
Subject: Re: Graphical representations of syntax trees?
Date: 8 Feb 2022 21:34:56 GMT
Organization: Compilers Central
Lines: 21
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <22-02-014@comp.compilers>
References: <22-02-004@comp.compilers> <22-02-006@comp.compilers> <22-02-008@comp.compilers>
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970";
logging-data="15450"; mail-complaints-to="abuse@iecc.com"
Keywords: parse, tools
Posted-Date: 09 Feb 2022 18:18:55 EST
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
 by: Jonathan Thornburg - Tue, 8 Feb 2022 21:34 UTC

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?

Re: Graphical representations of syntax trees?

<22-02-017@comp.compilers>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=279&group=comp.compilers#279

 copy link   Newsgroups: comp.compilers
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: joh...@myrkraverk.invalid (Johann 'Myrkraverk' Oskarsson)
Newsgroups: comp.compilers
Subject: Re: Graphical representations of syntax trees?
Date: Fri, 11 Feb 2022 21:16:53 +0000
Organization: Easynews - www.easynews.com
Lines: 19
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <22-02-017@comp.compilers>
References: <22-02-004@comp.compilers> <22-02-006@comp.compilers> <22-02-008@comp.compilers> <22-02-014@comp.compilers>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970";
logging-data="70395"; mail-complaints-to="abuse@iecc.com"
Keywords: parse, tools
Posted-Date: 11 Feb 2022 16:43:05 EST
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Content-Language: en-US
In-Reply-To: <22-02-014@comp.compilers>
 by: Johann 'Myrkrav - Fri, 11 Feb 2022 21:16 UTC

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

1
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor