Consider the language of forests of labelled trees represented as parenthesized lists of trees separated by commas. Each tree that is not just a leaf is represented by a pair of elements, separated by comma and enclosed in square brackets. The first of these elements is the label of the root; the second element is the forest of trees that are the children of the root. Trees that are composed of only one node (leaf) are represented by just the label of the node. The alphabet of the labels is {A, B, C, D, E}. An example of a sentence belonging to the language is

$$ ([A,(B,[C,(D)]],[D,(A,E,B,C)]) $$

which represents the following forest

Your tasks are:

1. Give a grammar for the language
2. Give an Syntax Directed Definition suitable to be implemented during top-down parsing that computes, for each non-leaf node, an attribute that is the parse tree derived from the node. For the construction of the tree the following operations can be used:
   1. MkT:: Label x TreeList -> Tree /* MkT(a,f) creates a tree with a root labelled “a” and whose children are the trees in “f”, in the order in which they occur */
   2. MkE:: -> TreeList /* creates an empty list of trees */
   3. Add:: Tree x TreeList -> TreeList /* Add(t,f) adds the tree “t” to “f” as first element */
3. Give an SDD suitable to be implemented during top-down parsing that computes, as an attribute of the start symbol, the derived forest of trees. Use the operations above; in particular use list of trees for forests.
4. Give an SDD suitable to be implemented during top-down parsing that computes, as an attribute of the start symbol, the depth of the forest represented by the parsed string (i.e., the maximum height of the trees in the forest).
5. Give an SDD suitable to be implemented during top-down parsing that computes, as an attribute of the start symbol, the width of the forest represented by the parsed string (i.e., the maximum number of children of a node in the trees of the forest).
6. Give an SDD suitable to be implemented during top-down parsing that computes, as an attribute of the start symbol, the number of nodes in the forest that are labelled with “A”.
7. Give an SDD suitable to be implemented during top-down parsing that computes, as an attribute of the start symbol, the maximum depth of the trees (and subtrees) in the forest whose root is labelled with “A”.
8. Give an SDD suitable to be implemented during top-down parsing that computes, as an attribute of the start symbol, the maximum width of the trees (and subtrees) in the forest whose root is labelled with “A”.

• Hints
• Soluzione

Consider the language of sequences of symbols on the alphabet {&, A, B, C}. The character '&' is used as a quote character to indicate that the next symbol, if different from '&', must be interpreted as a command. The sequence '&&' is used to denote the symbol '&' itself. Reply to the following questions:

1. Give a grammar for the language
2. Give a Syntax Directed Translation Scheme, suitable for being implemented during top-down parsing, that computes as an attribute of the start symbol the sequence that is obtained resolving the commands and the quoting. For instance, for the input sequence &&&A&&B the computed attribute must be: &Cmd(A)&B where Cmd is the operator to encapsulate commands.
3. Give a Syntax Directed Translation Scheme, suitable for being implemented during bottom-up parsing, that computes the same attribute of step 2)