5.5 Exercises

• Write a function IsPrefix taking 2 list arguments and returning true iff the first is a prefix of the second. Replace the definition of IsPrefix in the bottom-up parser with yours and test the parser.

• Write a function Drop which takes a list L as first argument and an integer N as second argument, ignores the first N elements of L and returns the remainder of the list. For example {Drop [a b c d] 0} should return [a b c d] and {Drop [a b c d] 2} should return [c d]. The Mozart library contains function List.drop: you should not use it in this exercise. Then use your Drop instead of List.drop in the bottom-up parser.

• Write a function Take which takes a list L as first argument and an integer N as second arguments and returns the first N elements of L. For example {Take [a b c d] 0} should return nil and {Take [a b c d] 2} should return [a b]. The Mozart library contains funtion List.take: you should not use it in this exercise.

• In addition to List.drop and List.take, the Mozart library contains List.takeDrop that combines the two functionalities:

  local Prefix Suffix in 
   {List.takeDrop [a b c d e] 2 Prefix Suffix}
   {Inspect Prefix}
   {Inspect Suffix}
end

  As brain teaser (but not a course exercise), see if you can figure out a way to do this by defining your own TakeDrop procedure. The library procedure achieves it in N steps (where N is its 2nd argument): can you do as well?

• Modify the bottom-up recognizer to discard conclusions which have already been derived before. Hint: it may be helpful to take advantage of the abstract datatype provided by NewBag.

• Modify the bottom-up recognizer into a parser which returns a list of parse trees rather than a list of recognized categories only. See Section 5.4.2 for hints. If possible, use your own Drop and Take functions, or your TakeDrop procedure if you were able to define it.