Contents    Prev    Next    Page+10   

Every parsing based on a Context Free Grammar produces:

  • A: a linked list
  • B: a binary tree
  • C: a tree
  • D: a directed acyclic graph
  • E: a graph, possibly with cycles

    Answer:   C

    Since a Context Free language has a single nonterminal on the left-hand side, we can write the production as a subtree with the left-hand side as root and right-hand side symbols as children. Thus, any parsing of a sentence must be a tree (not necessarily binary).

    S -> X Y Z                S
                            / | \
                           X  Y  Z