The parse tree of

program gcd (input, output); var i, j : integer; begin   read (i, j);   while i <> j do     if i > j then i := i - j     else j := j - i;   writeln (i) end. is

 \_<start>
         \_<Program>
                  |\_program
                  |\_gcd
                  |\_(
                  |\_input
                  |\_<More_ids>
                  |          |\_,
                  |          |\_output
                  |           \_<More_ids>
                  |                      \_empty
                  |\_)
                  |\_;
                  |\_<Block>
                  |       |\_<Variables>
                  |       |           |\_var
                  |       |           |\_i
                  |       |           |\_<More_ids>
                  |       |           |          |\_,
                  |       |           |          |\_j
                  |       |           |           \_<More_ids>
                  |       |           |                      \_empty
                  |       |           |\_:
                  |       |           |\_<Type>
                  |       |           |       \_integer
                  |       |           |\_;
                  |       |            \_<More_Variables>
                  |       |                             \_empty
                  |       |\_begin
                  |       |\_<Stmt>
                  |       |      |\_read
                  |       |      |\_(
                  |       |      |\_i
                  |       |      |\_<More_ids>
                  |       |      |          |\_,
                  |       |      |          |\_j
                  |       |      |           \_<More_ids>
                  |       |      |                      \_empty
                  |       |       \_)
                  |       |\_<More_Stmts>
                  |       |            |\_;
                  |       |            |\_<Stmt>
                  |       |            |      |\_while
                  |       |            |      |\_<Exp>
                  |       |            |      |     |\_<Simple>
                  |       |            |      |     |         \_<Term>
                  |       |            |      |     |                \_<Factor>
                  |       |            |      |     |                         \_i
                  |       |            |      |     |\_<Relop>
                  |       |            |      |     |       |\_<
                  |       |            |      |     |        \_>
                  |       |            |      |      \_<Simple>
                  |       |            |      |               \_<Term>
                  |       |            |      |                      \_<Factor>
                  |       |            |      |                               \_j
                  |       |            |      |\_do
                  |       |            |       \_<Stmt>
                  |       |            |             |\_if
                  |       |            |             |\_<Exp>
                  |       |            |             |     |\_<Simple>
                  |       |            |             |     |         \_<Term>
                  |       |            |             |     |                \_<Factor>
                  |       |            |             |     |                         \_i
                  |       |            |             |     |\_<Relop>
                  |       |            |             |     |        \_>
                  |       |            |             |      \_<Simple>
                  |       |            |             |               \_<Term>
                  |       |            |             |                      \_<Factor>
                  |       |            |             |                               \_j
                  |       |            |             |\_then
                  |       |            |             |\_<Stmt>
                  |       |            |             |      |\_i
                  |       |            |             |      |\_:
                  |       |            |             |      |\_=
                  |       |            |             |       \_<Exp>
                  |       |            |             |             \_<Simple>
                  |       |            |             |                     |\_<Term>
                  |       |            |             |                     |       \_<Factor>
                  |       |            |             |                     |                \_i
                  |       |            |             |                     |\_-
                  |       |            |             |                      \_<Term>
                  |       |            |             |                             \_<Factor>
                  |       |            |             |                                      \_j
                  |       |            |             |\_else
                  |       |            |              \_<Stmt>
                  |       |            |                    |\_j
                  |       |            |                    |\_:
                  |       |            |                    |\_=
                  |       |            |                     \_<Exp>
                  |       |            |                           \_<Simple>
                  |       |            |                                   |\_<Term>
                  |       |            |                                   |       \_<Factor>
                  |       |            |                                   |                \_j
                  |       |            |                                   |\_-
                  |       |            |                                    \_<Term>
                  |       |            |                                           \_<Factor>
                  |       |            |                                                    \_i
                  |       |             \_<More_Stmts>
                  |       |                         |\_;
                  |       |                         |\_<Stmt>
                  |       |                         |      |\_writeln
                  |       |                         |      |\_(
                  |       |                         |      |\_<Exp>
                  |       |                         |      |      \_<Simple>
                  |       |                         |      |               \_<Term>
                  |       |                         |      |                      \_<Factor>
                  |       |                         |      |                               \_i
                  |       |                         |      |\_<More_Exps>
                  |       |                         |      |            \_empty
                  |       |                         |       \_)
                  |       |                          \_<More_Stmts>
                  |       |                                       \_empty
                  |        \_end
                   \_.

The abstract syntax tree representation is

start(Program(More_ids(More_ids()),Block(Variables(More_ids(More_ids()),Type(),More_Variables()),Stmt(More_ids(More_ids())),More_Stmts(Stmt(Exp(Simple(Term(Factor())),Relop(),Simple(Term(Factor()))),Stmt(Exp(Simple(Term(Factor())),Relop(),Simple(Term(Factor()))),Stmt(Exp(Simple(Term(Factor()),Term(Factor())))),Stmt(Exp(Simple(Term(Factor()),Term(Factor())))))),More_Stmts(Stmt(Exp(Simple(Term(Factor()))),More_Exps()),More_Stmts())))))

Please, type a BNF grammar that is not left-recursive:

... and type a string to parse:


This page has been automatically generated by the Ctadel system on 2010/7/6 11:06am . Copyright Robert van Engelen