What is the easiest and fastest way to draw a parse tree using .Net?

Question

I wrote a simple parser from top to bottom using C #. This is a console application. I would like the analyzer to be able to save the image file of the parsing tree at the end of the calculation. I think I could use graphviz, but I would like to know your opinion. Thanks.

Answer 1

You can use SVG as an alternative to DOT / Graphviz; both of them are probably equally good.

In any case, it should be fairly easy to go through the parse tree and produce a conclusion that will drive the chart. If the tree is built explicitly, recursive movement should be easily implemented. If the tree is not designed, you will need to generate graph nodes on the fly during analysis.

For the DMS Software Reengineering Toolkit , which builds explicit ASTs , we do something simpler: we will go through the tree and just print the noot root on one line and its children on selected separate lines of text. We do this in the LISP style format (for historical reasons) and in the XML style format (really asking). The coding effort for this, if you can take a recursive walk in the tree, is about an hour.

It is not beautiful, like a graphic drawing, but it does not suffer from the problem of drawing huge graphs ... just from getting huge text outputs, but those with which you can navigate with less or perl .

Even a small AST can have many nodes, and thus a swampy ability to draw / comprehend with graphics. My experience is that AST has about 5-8 nodes per source string.

For the following 22-line PLSQL code:

-- available online in file 'sample3' DECLARE x NUMBER := 0; counter NUMBER := 0; BEGIN FOR i IN 1..4 LOOP x := x + 1000; counter := counter + 1; INSERT INTO temp VALUES (x, counter, 'outer loop'); /* start an inner block */ DECLARE x NUMBER := 0; -- this is a local version of x BEGIN FOR i IN 1..4 LOOP x := x + 1; -- this increments the local x counter := counter + 1; INSERT INTO temp VALUES (x, counter, 'inner loop'); END LOOP; END; END LOOP; COMMIT; END; 

Here's an example output, 180 tree nodes (provide source location information for each node):

  C:\DMS\Domains\PLSQL\Tools\Parser\Source>run ../domainparser ++XML C:\DMS\Domains\PLSQL\Examples\sample.sql Domain Parser for PLSQL 2.3.2 Copyright (C) Semantic Designs 1996-2009; All Rights Reserved 180 tree nodes in tree. 2 ambiguity nodes in tree. <DMSForest> <tree node="root" type="1" domain="1" id="1ky2c" parents="0" line="3" column="1" file="1"> <tree node="plsql_block" type="458" domain="1" id="1ky1x" line="3" column="1" file="1"> <precomment child=" 1" index="1">-- available online in file 'sample3'</precomment> <tree node="block_body" type="463" domain="1" id="1ky28" line="4" column="4" file="1"> <tree node="optional_type_or_item_declaration_list" type="465" domain="1" id="1kxp9" line="4" column="4" file="1"> <tree node="optional_type_or_item_declaration_list" type="465" domain="1" id="1kxox" line="4" column="4" file="1"> <tree node="optional_type_or_item_declaration_list" type="464" domain="1" id="1kxnz" line="4" column="4" file="1"/> <tree node="item_declaration" type="139" domain="1" id="1kxoy" line="4" column="4" file="1"> <tree node="IDENTIFIER" type="1691" domain="1" id="1kxny" line="4" column="4" file="1"> <literal>x</literal> </tree> <tree node="datatype" type="47" domain="1" id="1kxo3" line="4" column="6" file="1"/> <tree node="not_null_option" type="126" domain="1" id="1kxo4" line="4" column="13" file="1"/> <tree node="initial_value" type="146" domain="1" id="1kxoq" line="4" column="13" file="1"> <tree node="logical_disjunction" type="330" domain="1" id="1kxon" line="4" column="16" file="1"> <tree node="logical_conjunction" type="332" domain="1" id="1kxol" line="4" column="16" file="1"> <tree node="sum" type="356" domain="1" id="1kxog" line="4" column="16" file="1"> <tree node="product" type="360" domain="1" id="1kxoe" line="4" column="16" file="1"> <tree node="power" type="367" domain="1" id="1kxo9" line="4" column="16" file="1"> <tree node="NATURAL" type="1422" domain="1" id="1kxo6" literal="0" line="4" column="16" file="1"/> </tree> </tree> </tree> </tree> </tree> </tree> </tree> </tree> <tree node="item_declaration" type="139" domain="1" id="1kxpa" line="5" column="4" file="1"> <tree node="IDENTIFIER" type="1691" domain="1" id="1kxow" line="5" column="4" file="1"> <literal>counter</literal> </tree> <tree node="datatype" type="47" domain="1" id="1kxp0" line="5" column="12" file="1"/> <tree node="not_null_option" type="126" domain="1" id="1kxp1" line="5" column="19" file="1"/> <tree node="initial_value" type="146" domain="1" id="1kxp8" line="5" column="19" file="1"> <tree node="logical_disjunction" type="330" domain="1" id="1kxp7" line="5" column="22" file="1"> <tree node="logical_conjunction" type="332" domain="1" id="1kxp6" line="5" column="22" file="1"> <tree node="sum" type="356" domain="1" id="1kxp5" line="5" column="22" file="1"> <tree node="product" type="360" domain="1" id="1kxp4" line="5" column="22" file="1"> <tree node="power" type="367" domain="1" id="1kxp3" line="5" column="22" file="1"> <tree node="NATURAL" type="1422" domain="1" id="1kxp2" literal="0" line="5" column="22" file="1"/> </tree> </tree> </tree> </tree> </tree> </tree> </tree> </tree> <tree node="optional_function_or_procedure_declaration_list" type="466" domain="1" id="1kxpc" line="6" column="1" file="1"/> <tree node="statement_list" type="473" domain="1" id="1kxrp" children="2" line="7" column="4" file="1"> <tree node="for_loop_statement" type="680" domain="1" id="1ky26" line="7" column="4" file="1"> <tree node="IDENTIFIER" type="1691" domain="1" id="1kxpd" line="7" column="8" file="1"> <literal>i</literal> </tree> <tree node="logical_disjunction" type="330" domain="1" id="1kxpj" line="7" column="13" file="1"> <tree node="logical_conjunction" type="332" domain="1" id="1kxpi" line="7" column="13" file="1"> <tree node="sum" type="356" domain="1" id="1kxph" line="7" column="13" file="1"> <tree node="product" type="360" domain="1" id="1kxpg" line="7" column="13" file="1"> <tree node="power" type="367" domain="1" id="1kxpf" line="7" column="13" file="1"> <tree node="NATURAL" type="1422" domain="1" id="1kxpe" literal="1" line="7" column="13" file="1"/> </tree> </tree> </tree> </tree> </tree> <tree node="logical_disjunction" type="330" domain="1" id="1kxpp" line="7" column="16" file="1"> <tree node="logical_conjunction" type="332" domain="1" id="1kxpo" line="7" column="16" file="1"> <tree node="sum" type="356" domain="1" id="1kxpn" line="7" column="16" file="1"> <tree node="product" type="360" domain="1" id="1kxpm" line="7" column="16" file="1"> <tree node="power" type="367" domain="1" id="1kxpl" line="7" column="16" file="1"> <tree node="NATURAL" type="1422" domain="1" id="1kxpk" literal="4" line="7" column="16" file="1"/> </tree> </tree> </tree> </tree> </tree> <tree node="statement_list" type="473" domain="1" id="1kxqh" children="4" line="8" column="7" file="1"> <tree node="assignment_statement" type="511" domain="1" id="1kxq1" line="8" column="7" file="1"> <tree node="IDENTIFIER" type="1691" domain="1" id="1kxpq" line="8" column="7" file="1"> <literal>x</literal> </tree> <tree node="logical_disjunction" type="330" domain="1" id="1kxpw" line="8" column="12" file="1"> <tree node="logical_conjunction" type="332" domain="1" id="1kxpu" line="8" column="12" file="1"> <tree node="sum" type="357" domain="1" id="1kxpt" line="8" column="12" file="1"> <tree node="sum" type="356" domain="1" id="1kxov" line="8" column="12" file="1"> <tree node="product" type="360" domain="1" id="1kxoc" line="8" column="12" file="1"> <tree node="power" type="367" domain="1" id="1kxo8" line="8" column="12" file="1"> <tree node="IDENTIFIER" type="1691" domain="1" id="1kxo0" line="8" column="12" file="1"> <literal>x</literal> </tree> </tree> </tree> </tree> <tree node="product" type="360" domain="1" id="1kxps" line="8" column="16" file="1"> <tree node="power" type="367" domain="1" id="1kxpr" line="8" column="16" file="1"> <tree node="NATURAL" type="1422" domain="1" id="1kxou" literal="1000" line="8" column="16" file="1"/> </tree> </tree> </tree> </tree> </tree> </tree> <tree node="assignment_statement" type="511" domain="1" id="1kxqg" line="9" column="7" file="1"> <tree node="IDENTIFIER" type="1691" domain="1" id="1kxq0" line="9" column="7" file="1"> <literal>counter</literal> </tree> <tree node="logical_disjunction" type="330" domain="1" id="1kxqd" line="9" column="18" file="1"> <tree node="logical_conjunction" type="332" domain="1" id="1kxqb" line="9" column="18" file="1"> <tree node="sum" type="357" domain="1" id="1kxqa" line="9" column="18" file="1"> <tree node="sum" type="356" domain="1" id="1kxq2" line="9" column="18" file="1"> <tree node="product" type="360" domain="1" id="1kxo7" line="9" column="18" file="1"> <tree node="power" type="367" domain="1" id="1kxos" line="9" column="18" file="1"> <tree node="IDENTIFIER" type="1691" domain="1" id="1kxor" line="9" column="18" file="1"> <literal>counter</literal> </tree> </tree> </tree> </tree> <tree node="product" type="360" domain="1" id="1kxq7" line="9" column="28" file="1"> <tree node="power" type="367" domain="1" id="1kxq4" line="9" column="28" file="1"> <tree node="NATURAL" type="1422" domain="1" id="1kxq3" literal="1" line="9" column="28" file="1"/> </tree> </tree> </tree> </tree> </tree> </tree> <tree node="unlabelled_statement" type="500" domain="1" id="1kxrj" line="10" column="7" file="1"> <tree node="subordinate_insert_statement" type="652" domain="1" id="1kxri" line="10" column="7" file="1"> <tree node="table_reference" type="920" domain="1" id="1kxqr" line="10" column="19" file="1"> <tree node="$NONTERMINALAMBIGUITY" type="1778" nonterminalname="query_table_expression" nonterminaltype="611" domain="1" id="1kxqf" children="2" line="10" column="19" file="1"> <tree node="query_table_expression" type="946" domain="1" id="1kxqn" line="10" column="19" file="1"> <tree node="IDENTIFIER" type="1691" domain="1" id="1kxqk" parents="2" line="10" column="19" file="1"> <literal>temp</literal> </tree> </tree> <tree node="query_table_expression" type="953" domain="1" id="1kxqq" line="10" column="19" file="1"> <tree node="IDENTIFIER" type="1691" domain="1" id="1kxqk" parents="2" alreadyprinted="true"/> </tree> </tree> </tree> <tree node="sql_expression_list" type="657" domain="1" id="1kxrg" line="10" column="32" file="1"> <tree node="sql_expression_list" type="657" domain="1" id="1kxr9" line="10" column="32" file="1"> <tree node="disjunction_condition" type="1188" domain="1" id="1kxqy" line="10" column="32" file="1"> <tree node="conjunction_condition" type="1190" domain="1" id="1kxqx" line="10" column="32" file="1"> <tree node="additive_expression" type="1243" domain="1" id="1kxqw" line="10" column="32" file="1"> <tree node="multiplicative_expression" type="1246" domain="1" id="1kxqv" line="10" column="32" file="1"> <tree node="IDENTIFIER" type="1691" domain="1" id="1kxqu" line="10" column="32" file="1"> <literal>x</literal> </tree> </tree> </tree> </tree> </tree> <tree node="disjunction_condition" type="1188" domain="1" id="1kxr8" line="10" column="35" file="1"> <tree node="conjunction_condition" type="1190" domain="1" id="1kxr7" line="10" column="35" file="1"> <tree node="additive_expression" type="1243" domain="1" id="1kxr6" line="10" column="35" file="1"> <tree node="multiplicative_expression" type="1246" domain="1" id="1kxr5" line="10" column="35" file="1"> <tree node="IDENTIFIER" type="1691" domain="1" id="1kxr4" line="10" column="35" file="1"> <literal>counter</literal> </tree> </tree> </tree> </tree> </tree> </tree> <tree node="disjunction_condition" type="1188" domain="1" id="1kxrf" line="10" column="44" file="1"> <tree node="conjunction_condition" type="1190" domain="1" id="1kxre" line="10" column="44" file="1"> <tree node="additive_expression" type="1243" domain="1" id="1kxrd" line="10" column="44" file="1"> <tree node="multiplicative_expression" type="1246" domain="1" id="1kxrc" line="10" column="44" file="1"> <tree node="STRING" type="1556" domain="1" id="1kxrb" line="10" column="44" file="1"> <literal>outer loop</literal> </tree> </tree> </tree> </tree> </tree> </tree> <tree node="optional_returning_clause" type="587" domain="1" id="1kxrh" line="10" column="57" file="1"/> </tree> </tree> <tree node="plsql_block" type="458" domain="1" id="1ky1u" line="12" column="7" file="1"> <precomment child=" 1" index="1">/* start an inner block */</precomment> <tree node="block_body" type="463" domain="1" id="1ky24" line="13" column="10" file="1"> <tree node="optional_type_or_item_declaration_list" type="465" domain="1" id="1kxz9" line="13" column="10" file="1"> <tree node="optional_type_or_item_declaration_list" type="464" domain="1" id="1kxrq" line="13" column="10" file="1"/> <tree node="item_declaration" type="139" domain="1" id="1kxza" line="13" column="10" file="1"> <postcomment child="5" index="1">-- this is a local version of x</postcomment> <tree node="IDENTIFIER" type="1691" domain="1" id="1kxrn" line="13" column="10" file="1"> <literal>x</literal> </tree> <tree node="datatype" type="47" domain="1" id="1kxrr" line="13" column="12" file="1"/> <tree node="not_null_option" type="126" domain="1" id="1kxrs" line="13" column="19" file="1"/> <tree node="initial_value" type="146" domain="1" id="1kxz5" line="13" column="19" file="1"> <tree node="logical_disjunction" type="330" domain="1" id="1kxz4" line="13" column="22" file="1"> <tree node="logical_conjunction" type="332" domain="1" id="1kxrz" line="13" column="22" file="1"> <tree node="sum" type="356" domain="1" id="1kxry" line="13" column="22" file="1"> <tree node="product" type="360" domain="1" id="1kxrx" line="13" column="22" file="1"> <tree node="power" type="367" domain="1" id="1kxrw" line="13" column="22" file="1"> <tree node="NATURAL" type="1422" domain="1" id="1kxrt" literal="0" line="13" column="22" file="1"/> </tree> </tree> </tree> </tree> </tree> </tree> </tree> </tree> <tree node="optional_function_or_procedure_declaration_list" type="466" domain="1" id="1kxze" line="14" column="7" file="1"/> <tree node="for_loop_statement" type="680" domain="1" id="1ky1y" line="15" column="10" file="1"> <tree node="IDENTIFIER" type="1691" domain="1" id="1kxzf" line="15" column="14" file="1"> <literal>i</literal> </tree> <tree node="logical_disjunction" type="330" domain="1" id="1kxzq" line="15" column="19" file="1"> <tree node="logical_conjunction" type="332" domain="1" id="1kxzn" line="15" column="19" file="1"> <tree node="sum" type="356" domain="1" id="1kxzk" line="15" column="19" file="1"> <tree node="product" type="360" domain="1" id="1kxzj" line="15" column="19" file="1"> <tree node="power" type="367" domain="1" id="1kxzi" line="15" column="19" file="1"> <tree node="NATURAL" type="1422" domain="1" id="1kxrv" literal="1" line="15" column="19" file="1"/> </tree> </tree> </tree> </tree> </tree> <tree node="logical_disjunction" type="330" domain="1" id="1kxzy" line="15" column="22" file="1"> <tree node="logical_conjunction" type="332" domain="1" id="1kxzx" line="15" column="22" file="1"> <tree node="sum" type="356" domain="1" id="1kxzw" line="15" column="22" file="1"> <tree node="product" type="360" domain="1" id="1kxzv" line="15" column="22" file="1"> <tree node="power" type="367" domain="1" id="1kxzu" line="15" column="22" file="1"> <tree node="NATURAL" type="1422" domain="1" id="1kxzt" literal="4" line="15" column="22" file="1"/> </tree> </tree> </tree> </tree> </tree> <tree node="statement_list" type="473" domain="1" id="1ky0t" children="3" line="16" column="13" file="1"> <tree node="assignment_statement" type="511" domain="1" id="1ky0g" line="16" column="13" file="1"> <postcomment child="4" index="1">-- this increments the local x</postcomment> <tree node="IDENTIFIER" type="1691" domain="1" id="1kxzz" line="16" column="13" file="1"> <literal>x</literal> </tree> <tree node="logical_disjunction" type="330" domain="1" id="1ky0c" line="16" column="18" file="1"> <tree node="logical_conjunction" type="332" domain="1" id="1ky07" line="16" column="18" file="1"> <tree node="sum" type="357" domain="1" id="1ky06" line="16" column="18" file="1"> <tree node="sum" type="356" domain="1" id="1ky00" line="16" column="18" file="1"> <tree node="product" type="360" domain="1" id="1kxz6" line="16" column="18" file="1"> <tree node="power" type="367" domain="1" id="1kxr3" line="16" column="18" file="1"> <tree node="IDENTIFIER" type="1691" domain="1" id="1kxop" line="16" column="18" file="1"> <literal>x</literal> </tree> </tree> </tree> </tree> <tree node="product" type="360" domain="1" id="1ky05" line="16" column="22" file="1"> <tree node="power" type="367" domain="1" id="1ky04" line="16" column="22" file="1"> <tree node="NATURAL" type="1422" domain="1" id="1ky01" literal="1" line="16" column="22" file="1"/> </tree> </tree> </tree> </tree> </tree> </tree> <tree node="assignment_statement" type="511" domain="1" id="1ky0s" line="17" column="13" file="1"> <tree node="IDENTIFIER" type="1691" domain="1" id="1ky0f" line="17" column="13" file="1"> <literal>counter</literal> </tree> <tree node="logical_disjunction" type="330" domain="1" id="1ky0o" line="17" column="24" file="1"> <tree node="logical_conjunction" type="332" domain="1" id="1ky0m" line="17" column="24" file="1"> <tree node="sum" type="357" domain="1" id="1ky03" line="17" column="24" file="1"> <tree node="sum" type="356" domain="1" id="1ky0h" line="17" column="24" file="1"> <tree node="product" type="360" domain="1" id="1kxz7" line="17" column="24" file="1"> <tree node="power" type="367" domain="1" id="1kxr0" line="17" column="24" file="1"> <tree node="IDENTIFIER" type="1691" domain="1" id="1kxpx" line="17" column="24" file="1"> <literal>counter</literal> </tree> </tree> </tree> </tree> <tree node="product" type="360" domain="1" id="1ky02" line="17" column="34" file="1"> <tree node="power" type="367" domain="1" id="1ky0l" line="17" column="34" file="1"> <tree node="NATURAL" type="1422" domain="1" id="1ky0k" literal="1" line="17" column="34" file="1"/> </tree> </tree> </tree> </tree> </tree> </tree> <tree node="unlabelled_statement" type="500" domain="1" id="1ky1t" line="18" column="13" file="1"> <tree node="subordinate_insert_statement" type="652" domain="1" id="1ky1s" line="18" column="13" file="1"> <tree node="table_reference" type="920" domain="1" id="1ky11" line="18" column="25" file="1"> <tree node="$NONTERMINALAMBIGUITY" type="1778" nonterminalname="query_table_expression" nonterminaltype="611" domain="1" id="1ky0q" children="2" line="18" column="25" file="1"> <tree node="query_table_expression" type="946" domain="1" id="1ky0x" line="18" column="25" file="1"> <tree node="IDENTIFIER" type="1691" domain="1" id="1ky0w" parents="2" line="18" column="25" file="1"> <literal>temp</literal> </tree> </tree> <tree node="query_table_expression" type="953" domain="1" id="1ky10" line="18" column="25" file="1"> <tree node="IDENTIFIER" type="1691" domain="1" id="1ky0w" parents="2" alreadyprinted="true"/> </tree> </tree> </tree> <tree node="sql_expression_list" type="657" domain="1" id="1ky1q" line="18" column="38" file="1"> <tree node="sql_expression_list" type="657" domain="1" id="1ky1j" line="18" column="38" file="1"> <tree node="disjunction_condition" type="1188" domain="1" id="1ky19" line="18" column="38" file="1"> <tree node="conjunction_condition" type="1190" domain="1" id="1ky18" line="18" column="38" file="1"> <tree node="additive_expression" type="1243" domain="1" id="1ky17" line="18" column="38" file="1"> <tree node="multiplicative_expression" type="1246" domain="1" id="1ky16" line="18" column="38" file="1"> <tree node="IDENTIFIER" type="1691" domain="1" id="1ky14" line="18" column="38" file="1"> <literal>x</literal> </tree> </tree> </tree> </tree> </tree> <tree node="disjunction_condition" type="1188" domain="1" id="1ky1i" line="18" column="41" file="1"> <tree node="conjunction_condition" type="1190" domain="1" id="1ky1h" line="18" column="41" file="1"> <tree node="additive_expression" type="1243" domain="1" id="1ky1g" line="18" column="41" file="1"> <tree node="multiplicative_expression" type="1246" domain="1" id="1ky1f" line="18" column="41" file="1"> <tree node="IDENTIFIER" type="1691" domain="1" id="1ky1c" line="18" column="41" file="1"> <literal>counter</literal> </tree> </tree> </tree> </tree> </tree> </tree> <tree node="disjunction_condition" type="1188" domain="1" id="1ky1p" line="18" column="50" file="1"> <tree node="conjunction_condition" type="1190" domain="1" id="1ky1o" line="18" column="50" file="1"> <tree node="additive_expression" type="1243" domain="1" id="1ky1n" line="18" column="50" file="1"> <tree node="multiplicative_expression" type="1246" domain="1" id="1ky1m" line="18" column="50" file="1"> <tree node="STRING" type="1556" domain="1" id="1ky1l" line="18" column="50" file="1"> <literal>inner loop</literal> </tree> </tree> </tree> </tree> </tree> </tree> <tree node="optional_returning_clause" type="587" domain="1" id="1ky1r" line="18" column="63" file="1"/> </tree> </tree> </tree> <tree node="end_loop" type="672" domain="1" id="1ky1v" line="19" column="10" file="1"/> </tree> <tree node="optional_exception_handlers" type="474" domain="1" id="1ky20" line="20" column="7" file="1"/> </tree> </tree> </tree> <tree node="end_loop" type="672" domain="1" id="1kxrm" line="21" column="4" file="1"/> </tree> <tree node="unlabelled_statement" type="500" domain="1" id="1kxro" line="22" column="4" file="1"> <tree node="subordinate_commit_statement" type="535" domain="1" id="1ky21" line="22" column="4" file="1"/> </tree> </tree> <tree node="optional_exception_handlers" type="474" domain="1" id="1ky1w" line="23" column="1" file="1"/> </tree> </tree> </tree> <FileIndex> <File index="1">C:/DMS/Domains/PLSQL/Examples/sample.sql</File> </FileIndex> <DomainIndex> <Domain index="1">PLSQL</Domain> </DomainIndex> </DMSForest> 

Answer 2

I think I would generate XML (or make the tree XPath-navigating in some way) and use the XSLT transform to create any (text) format you like, especially SVG.