Question 10

The input consists of a context-free grammar followed by a derivation, encoded as CFG and DERIVATION components.

• There will only be one CFG component and one DERIVATION component in the input.
• No error checking is required for the input. It will be correctly formatted.

There are two output formats allowed for this question. Marmoset will accept both and there is no difference in terms of marks or tests.

The Unicode Format uses Unicode characters for cleaner-looking output. If the software you are using doesn't display these Unicode characters properly, you can instead use the ASCII Format, which only uses ASCII characters. In either case, the output is a representation of the parse tree for the derivation, as illustrated below.

.CFG
expr expr MINUS term
expr term
term factor
factor ID
factor LPAREN expr RPAREN
.DERIVATION
expr expr MINUS term
  expr term
    term factor
      factor ID
  term factor
    factor LPAREN expr RPAREN
      expr expr MINUS term
        expr term
          term factor
            factor ID
        term factor
          factor ID

expr
├─expr
│ ╰─term
│   ╰─factor
│     ╰─ID
├─MINUS
╰─term
  ╰─factor
    ├─LPAREN
    ├─expr
    │ ├─expr
    │ │ ╰─term
    │ │   ╰─factor
    │ │     ╰─ID
    │ ├─MINUS
    │ ╰─term
    │   ╰─factor
    │     ╰─ID
    ╰─RPAREN

expr
|-expr
| '-term
|   '-factor
|     '-ID
|-MINUS
'-term
  '-factor
    |-LPAREN
    |-expr
    | |-expr
    | | '-term
    | |   '-factor
    | |     '-ID
    | |-MINUS
    | '-term
    |   '-factor
    |     '-ID
    '-RPAREN

The tree-building algorithm requires you to know which symbols are terminals or nonterminals. This is the only information you need from the CFG. Thus, you should read the CFG and construct a set containing all the nonterminals. You can then check whether a symbol is a terminal or a nonterminal by checking whether it is in this set.

Read one line to skip the .CFG header of the CFG component. Then, read the contents of the CFG component line by line. Each line is a single CFG rule.

• Read the first string on the line (up to the first space).
  • If the string you read is .DERIVATION, you've reached the end of the CFG component and you can move on to building the tree.
  • Otherwise, this string is the left-hand side of a rule and therefore must be a nonterminal. Add it to your set.
• The rest of the line can be skipped because the information is not needed. Anything which doesn't appear on the left-hand side of a rule is a terminal.

You will need to create your own data structure to store the tree. An example in C++ might look like:

struct Node {
  // data stored at the node
  std::string data;
  // vector of pointers to child subtrees; could also use smart pointers
  std::vector<Node*> children;
  // constructor for a leaf node
  Node(std::string data) : data(data) {}
  Node(std::istream &in = std::cin) {
    // constructor that builds a tree as it reads input
  }
  // explicit destructor; could also use smart pointers
  ~Node() {
    for( auto &c : children ) { delete c; }
  }
  void print(std::string prefix, std::ostream &out = std::cout) {
    // prints a representation of the tree, with each line indented by the given prefix
  }
};

(Allowing the Node constructor to read input from any input stream, and allowing the print function to write to any output stream, will make it more flexible if you want to use it for debugging purposes later.)

In Racket, you could just create a tree struct with fields for the data and a list of children, and write a function that reads standard input and builds a tree struct, and another function that prints a tree struct.

(struct node (data children) #:transparent)
(define (build-tree [in (current-input-port)]) ...)
(define (print-tree tree prefix [out (current-output-port)]) ...)

Make sure that you have consumed the entire CFG component from standard input, as well as the .DERIVATION header line. That is, the next line you read from standard input should be the first rule in the DERIVATION component.

To build the tree, use the following recursive algorithm:

1. Read one line from standard input. This line represents the production rule used to expand the root of the tree.
2. Store the left-hand side of the rule at the root node of the tree.
3. Loop over the symbols on the right-hand side of the rule, and add one child to the root for each symbol.
   • If the symbol is a terminal, the child should be a leaf node storing the terminal.
   • If the symbol is a nonterminal, construct the child by recursively calling this algorithm.

To print the tree, use the following recursive algorithm. This algorithm takes a parameter called the "indentation prefix", which is printed before printing each child node of the tree. The initial call to the algorithm should pass an empty string as the indentation prefix.

1. Print the data at the tree root, followed by a newline.
2. If the root has children, then recursively print each child subtree.
   • For every child except the last, print the current indentation prefix, then a Joint, then recursively print the child subtree with a Bar added to the end of the indentation prefix.
   • For the last child, print the current indentation prefix, then a Corner, then recursively print the child subtree with a Spacer added to the end of the indentation prefix.

The algorithm refers to the following two-character strings. Note that the Bar string is different between Unicode and ASCII, even though it looks similar, so make sure to copy the appropriate string directly into your code.