1. Forum
  2. Usenet
  3. COMP.COMPILERS

  • Graphical representations of syntax trees?

    From Johann 'Myrkraverk' Oskarsson@21:1/5 to All on Fri Feb 4 20:20:00 2022
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From gah4@21:1/5 to Johann 'Myrkraverk' Oskarsson on Sun Feb 6 13:07:00 2022
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Hans-Peter Diettrich@21:1/5 to All on Sun Feb 6 23:38:31 2022
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Anton Ertl@21:1/5 to Johann 'Myrkraverk' Oskarsson on Sun Feb 6 22:32:12 2022
    Johann 'Myrkraverk' Oskarsson <[email protected]> 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
    [email protected]
    http://www.complang.tuwien.ac.at/anton/

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Johann 'Myrkraverk' Oskarsson@21:1/5 to Anton Ertl on Mon Feb 7 10:49:30 2022
    On 2/6/2022 10:32 PM, Anton Ertl wrote:
    Johann 'Myrkraverk' Oskarsson <[email protected]> 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]

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Anton Ertl@21:1/5 to Johann 'Myrkraverk' Oskarsson on Mon Feb 7 18:33:57 2022
    Johann 'Myrkraverk' Oskarsson <[email protected]> writes:
    On 2/6/2022 10:32 PM, Anton Ertl wrote:
    Johann 'Myrkraverk' Oskarsson <[email protected]> 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
    [email protected]
    http://www.complang.tuwien.ac.at/anton/

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Christopher F Clark@21:1/5 to All on Mon Feb 7 22:04:28 2022
    There is a "good" reason why you don't see lots of work on outputting
    pretty pictures of syntax trees. That is because Graphviz has a
    reasonable implementation of drawing graphs with a variety of
    algorithms that draw it to different preferences. And, Graphviz is
    open source, so the code is there for you to use. However, most
    compiler people realize that our talents are better used elsewhere
    than trying to do a "better" Graphviz. So, we all just use it rather
    than re-inventing the wheel.

    And, as our wise moderator said, beyond very very simple syntax trees,
    nothing works. There is simply way too much information. In fact, in
    that way, the railroad diagrams in the original book about Pascal are impressive, because they figured out that you want to break them down
    to roughly one rule each (and simple rules at that) and not try to do
    the whole graph as a single graph.

    Similarly, there was a site (beatgraphs, if I recall the name
    correctly) that used Graphviz to draw the pictures of how the teams in
    the NFL ranked week by week based upon who beat who (and how to
    resolve cycles). Graphviz managed to draw all 32 teams and their
    rankings in a single graph. Some weeks it wouldn't fit on the screen,
    but most of the time it did. That shows a rough upper bound of how
    much info you can reliably draw a picture for.

    So, unless you have a real desire to write drawing algorithms
    yourself, you are better off just writing a "dot" file and feeding it
    to Graphviz. And, with the options it has, I would be surprised if you
    couldn't get it to draw the syntax tree to your liking. And, if you do
    want to write layout algorithms, why not add them to Graphviz?

    -- ****************************************************************************** Chris Clark email: [email protected] Compiler Resources, Inc. Web Site: http://world.std.com/~compres
    23 Bailey Rd voice: (508) 435-5016
    Berlin, MA 01503 USA twitter: @intel_chris ------------------------------------------------------------------------------

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Alexei A. Frounze@21:1/5 to Johann 'Myrkraverk' Oskarsson on Mon Feb 7 18:17:07 2022
    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]

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Steve Limb@21:1/5 to Oskarsson on Tue Feb 8 09:14:41 2022
    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 <[email protected]> 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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Jonathan Thornburg@21:1/5 to Johann 'Myrkraverk' Oskarsson on Tue Feb 8 21:34:56 2022
    Johann 'Myrkraverk' Oskarsson <[email protected]> wrote:
    On 2/6/2022 10:32 PM, Anton Ertl wrote:
    Johann 'Myrkraverk' Oskarsson <[email protected]> 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]" <[email protected]>
    on the west coast of Canada, eh?

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Johann 'Myrkraverk' Oskarsson@21:1/5 to Jonathan Thornburg on Fri Feb 11 21:16:53 2022
    On 2/8/2022 9:34 PM, Jonathan Thornburg wrote:
    Johann 'Myrkraverk' Oskarsson <[email protected]> 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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)