Instructions: Download CFG.hs and Assignment06.hs from the course web- site into the same directory on your computer. The import line near the top of Assignment06.hs imports all of the denitions from CFG.hs, which you may then use in your assignment. You should familiarize yourself with everything in CFG.hs before beginning the assignment. Please submit your assignment as a modied version of Assignment06.hs.
points For warm-up practice with some of the relevant types, please code up the following
functions:
- () terminalsOnly, which tries to convert a mixed string of nonterminal and terminal symbols into a string of just terminal symbols. If the given string contains no nonterminal symbols, then the result should be a Just value with the list of whatever terminal symbols the given string contains. If the given string contains nonterminal symbols, then the result should be Nothing.
Example usage:
⇒∗
terminalsOnly [T “John”, T “saw”, NT “NP”] ⇒∗ Nothing - () leaves, which returns the list of terminal symbols that appear at the leaves of the given tree, in order.
Example usage:
⇒∗
leaves (NonLeaf 0 (Leaf 0 a) (NonLeaf 0 (Leaf 0 b) (Leaf 0 c)))
Ethan Poole : Comp. Ling. I Due: May
terminalsOnly [T "John", T "saw", T "Mary"]
leaves (NonLeaf "S" (Leaf "NP" "Mary") (Leaf "VP" "ran"))
Just [“John”, “saw”, “Mary”]
["Mary", "ran"]
⇒∗ “abc” Page of
points Please code up the following functions that convert between trees, rule lists, and
derivations:
() treeToRuleList, which returns the list of rules used in the leftmost derivation corresponding to the given tree, in the order in which they are used in that leftmost derivation.
Hint: All of the rewriting steps that construct parts of a node’s left daughter tree precede all of the rewriting steps that construct parts of that node’s right daughter tree . . .
treeToRuleList (NonLeaf “S” (Leaf “NP” “Mary”) (Leaf “VP” “ran”)) ⇒∗ [NonterminalRule “S” (“NP”, “VP”), TerminalRule “NP” “Mary”, TerminalRule “VP” “ran”]
treeToRuleList (NonLeaf 1 (NonLeaf 2 (Leaf 4 a) (Leaf 5 b)) (Leaf 3 c)) ⇒∗
[NonterminalRule 1 (2,3), NonterminalRule 2 (4,5), TerminalRule 4 a, TerminalRule 5 b, TerminalRule 3 c]
treeToRuleList (NonLeaf 1 (Leaf 2 a) (NonLeaf 3 (Leaf 4 b) (Leaf 5 c))) ⇒∗
[NonterminalRule 1 (2,3), TerminalRule 2 a, NonterminalRule 3 (4,5), TerminalRule 4 b, TerminalRule 5 c]
() ruleListToTree, which is, in eect, the reverse of treeToRuleList. If the given list of rules does not correspond to any leftmost derivation, then the result should be Nothing. If the given list of rules does correspond to a leftmost derivation, the result should be a Just value containing the appropriate tree.
What is intended by “leftmost derivation” is a sequence of steps from a single nonterminal symbol to a string containing only terminal symbols. As this is not relative to any particular grammar, it does not matter what nonterminal symbol the derivation starts from; this will just be whatever nonterminal symbol happens to appear on the left-hand side of the rst rule in the list.
Page of
Example usage:
Example usage:
⇒∗
ruleListToTree [NonterminalRule 1 (2,3), TerminalRule 2 a, NonterminalRule 3 (4,5), TerminalRule 4 b]
ruleListToTree [NonterminalRule "S" ("NP", "VP"), TerminalRule "NP" "Mary", TerminalRule "VP" "ran"]
Just (NonLeaf “S” (Leaf “NP” “Mary”) (Leaf “VP” “ran”))
⇒∗ Nothing
() treeToDerivation, which returns the leftmost derivation corresponding to the given tree, in the form of a list of mixed strings containing terminal and nonterminal symbols. Note that because this is a derivation, the order matters!
You must not execute this function by rst recovering the list of rules used in the derivation and then carrying out the rewriting steps one by one. There is a much more elegant and clever way to construct the necessary strings directly from the tree structure.
Example usage:
treeToDerivation (NonLeaf "S" (Leaf "NP" "Mary") (Leaf "VP" "ran"))
⇒∗
treeToDerivation (NonLeaf 1 (NonLeaf 2 (Leaf 4 a) (Leaf 5 b)) (Leaf 3 c))
[[NT "S"], [NT "NP", NT "VP"], [T "Mary", NT "VP"], [T "Mary", T "ran"]]
⇒∗ [[NT 1],[NT 2,NT 3],[NT 4,NT 5,NT 3],[T a,NT 5,NT 3],[T a,T b,NT 3],[T a,T b,T c]] points
The rewrite and splitAtNT functions provided in CFG.hs, which we discussed in class, capture the basic idea of what a rewriting step looks like. However, that particular rewrite function does not necessarily carry out the kinds of steps that appear in leftmost derivations. It rewrites, fairly arbitrarily, the leftmost occurrence (if there is one) of the particular nonterminal symbol to which the given rule can apply. This will not in general be the leftmost nonterminal symbol in the string.
Please code up the following functions that in eect, carry out all the leftmost derivations allowed by a grammar. Note that the rewrite and splitAtNT functions might be useful starting points to think about.
Page of
- () splitAtLeftmost, which splits a list of symbols at the leftmost occurrence of a nonterminal symbol. The idea is to use this function to pick out the position where the next rewriting step will happen in a leftmost derivation. If there are no nonterminal symbols in the list, then the result should be Nothing. Otherwise, it should be a Just value containing a triple, which has the leftmost nonterminal symbol itself as its second component, and has the preceding and following parts of the list as the rst and third components respectively.
Example usage:
⇒∗
splitAtLeftmost [T “apples”, T “and”, T “oranges”, T “or”, T “bananas”] - () rewriteLeftmost, which rewrites the leftmost nonterminal symbol in the given list of symbols, in all the ways possible according to the given list of rules. Each such possible rewriting step produces a new list of symbols. The result should be a list containing all of these resulting lists of symbols. In the following examples, snd is used to extract the second component of a pair, here, for the purposes of retrieving a CFG’s list of rules.
⇒∗
- () derivableFrom, which produces all the strings of terminals that can be derived from the given mixed string of terminals and nonterminals, using the given list of rules, in at most the given number of steps. The order in which the strings of terminals appear in the resulting list does not matter. However, you should only consider leftmost derivations. Therefore, a string of terminals should appear in the result list more than once if and only if there are multiple distinct leftmost derivations of that string.
splitAtLeftmost [T "apples", T "and", NT "NP", T "or", NT "NP"]
Just ([T “apples”, T “and”], “NP”, [T “or”, NT “NP”])
Example usage:
rewriteLeftmost (snd cfg1) [NT “NP”, NT “VP”] ⇒∗
[[NT “D”, NT “N”, NT “VP”], [T “John”, NT “VP”], [T “Mary”, NT “VP”]]
⇒∗ Nothing
rewriteLeftmost (snd cfg1) [T “John”, NT “VP”]
Hint: Remember terminalsOnly!
[[T "John", NT "V", NT "NP"]]
Page of
Example usage:
derivableFrom [NT “NP”] (snd cfg1) 0 ⇒∗ [] derivableFrom [NT “NP”] (snd cfg1) 3 ⇒∗
[[“the”,”cat”],[“the”,”dog”],[“a”,”cat”],[“a”,”dog”],[“John”],[“Mary”]] derivableFrom [T “Mary”, NT “VP”] (snd cfg1) 2 ⇒∗ []
⇒∗
From here, you could write the one-line function to nd all strings derivable via a
derivableFrom [T “Mary”, NT “VP”] (snd cfg1) 3
[["Mary","saw","John"],["Mary","saw","Mary"],
["Mary","likes","John"], ["Mary","likes","Mary"]]
given grammar, up to a maximum number of steps: ()
derivable :: (Eq nt, Eq t) => CFG nt t -> Int -> [[t]] derivable (start , rules) n =
derivableFrom [NT start] rules n
Page of
