I've written a simple top down parser using c#. It's a console application. I'd like the parser could save, at the end of the computation, an image file of the parse tree. I think I could use graphviz, but I'd like to know your opinion. Thanks.
+4
A:
You could use SVG as an alternative to DOT/Graphviz; both are probably equally good.
In either case, it should be pretty easy to walk the parse tree and produce output that will control the drawing of the graph. If the tree is constructed explicitly, a recursive walk should be easy to implement. If the tree isn't constructed, you'll need to generate the graph nodes on the fly as you parse.
For the DMS Software Reengineering Toolkit, which constructs explicit ASTs, we do something simpler: walk the tree, and simply print out the root noot on one line, and its children on idented seperate lines of text. We do this in a LISP style format (for historical reasons) and an XML style format (much requested). The effort to code this if you can do a recursive tree walk is probably about an hour.
It isn't a pretty as a graph drawing, but it doesn't suffer from the problem of drawing huge graphs... just from getting huge text outputs, but those you can navigate with less or perl.
Even a small AST can have lots of nodes, and thus swamp your ability to draw/comprehend with graphics. My experience is that an AST has roughly 5-8 nodes per source line.
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 a sample output, 180 tree nodes (note source position 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>
Ira Baxter
2010-06-14 20:01:15
A:
I think I'd generate XML (or make the tree XPath navigable somehow) and use an XSLT transform to generate any (text-based) format you like, especially SVG.
Lucero
2010-06-14 20:10:32