(* CS 334 Assignment #3 Solutions *) (* 1 a) int * x[] is ambiguous as it could be parsed as either int (* x)[] or as int * (x{}) where the parentheses are not officially part of the language but suggest the way the parse trees look. b. Because * has lower precedence we set up a new non-terminal for the two different precendences: ::= '*' | ::= | '[' number ']' | '(' ')' | '(' ')' | name c. If the "*" moves to postfix from prefix then it is unambiguous for the same reasons that postfix arithmetic expressions are ambiguous. You can unambiguously build the parse tree by starting at the rightmost token and peel off the occurrences of *, "[..]", and "(...)" 2. "Time flies like an arrow" and "Fruit flies like a banana" cause confusion because "flies" is a verb in the first and noun in the second, while "like" is part of a prepositional phrase in the first, while it is a verb in the second. It is pretty straightforward to come up with a grammar which allows both parses. (Details omitted.) 3. *) (* Parses Article. If first token is the article "a" or "the", returns a tuple containing a true and the remaining tokens. Otherwise it return a tuple of a false and the remaining tokens. *) (* Article -> a | the *) fun parseArticle (fst::tokens) = if fst = "a" orelse fst = "the" then (true, tokens) else (false, tokens) (* Parses Noun. If first token is the noun "girl" or "dog", returns a tuple containing a true and the remaining tokens. Otherwise it return a tuple of a false and the remaining tokens. *) (* Noun -> girl | dog *) fun parseNoun (fst::tokens) = if fst = "girl" orelse fst = "dog" then (true, tokens) else (false, tokens) (* Parses verb. If first token is the verb "sees" or "pets", returns a tuple containing a true and the remaining tokens. Otherwise it return a tuple of a false and the remaining tokens. *) (* Verb -> sees | pets *) fun parseVerb (fst::tokens) = if fst = "sees" orelse fst = "pets" then (true, tokens) else (false, tokens); (* parses a NounPhrase. If the first two tokens represent an article and a noun then return the tuple consisting of true and the remaining tokens. Otherwise it returns false and the remaining tokens. *) (* NounPhrase -> Article Noun *) fun parseNounPhrase tokens = let val (OK,rest) = parseArticle tokens in if OK then parseNoun rest else (false, rest) end; (* parses a VerbPhrase. If we recognize a verb and then a NounPhrase then return the tuple consisting of true and the remaining tokens. Otherwise it returns false and the remaining tokens. *) (* VerbPhrase -> Verb NounPhrase *) fun parseVerbPhrase tokens = let val (OK, rest) = parseVerb tokens in if OK then parseNounPhrase rest else (false, tokens) end; (* Parses sentence. If an expression is found, returns a tuple containing a boolean indicating whether the tokens represent a sentence, and the input following the expression. *) (* Sentence -> NounPhrase VerbPhrase *) fun parseSentence tokens = let val (OK, rest) = parseNounPhrase tokens in if OK then parseVerbPhrase rest else (print (hd rest);(false, rest)) end; (* Return true if the tokens represent an English sentence. *) fun parse tokens = let val (OK, others) = parseSentence tokens; in OK andalso others = [] end; (* 4 *) use "parser.sml"; (* Substitute replaces every free occurrence of a variable within an expression with a value. The first argument is the expression in which the substituion occurs. The second argument is the variable name to substitute for. The third argument is the value to replace the variable with. It returns an equivalent abstract syntax tree term with the substitution performed. *) fun subst (id as AST_ID name) var value = (* Replace the identifier if the identifer name matches the variable. *) if name = var then value else id (* Recursively perform the substitution as long as the function paramete r name does not match the variable we are replacing. If they match, uses of the variable within the function body refer to the parameter, not the value we are currently substituing. *) | subst (AST_FUN (param, body)) var value = if (param = var) then AST_FUN (param, body) else AST_FUN (param, subst body var value) (* As with function declarations, we should stop the recursion if the variable matches the recursive function name. *) | subst (AST_REC (param, body)) var value = if (param = var) then AST_REC (param, body) else AST_REC (param, subst body var value) (* For function application and if expressions, recursively substitute in the component terms. *) | subst (AST_APP (func, arg)) var value = AST_APP (subst func var value, subst arg var value) | subst (AST_IF (cond, trueExp, falseExp)) var value = AST_IF (subst cond var value, subst trueExp var value, subst falseExp var value) (* Handles base cases involving no substitution: NUM, BOOL, SUCC, PRED, ISZERO *) | subst t _ _ = t; (* This function actually does the interpretation. It expects an abstract syntax tree term and returns another abstract syntax tree term that represents an evaluatation of the original AST. *) fun interp (AST_APP (func, arg)) = let (* Implement the predefined functions doing type checking and error propagation. *) fun apply AST_SUCC (AST_NUM (n)) = AST_NUM (n + 1) | apply AST_SUCC (e as AST_ERROR s) = e | apply AST_SUCC _ = AST_ERROR "succ needs integer arg" | apply AST_PRED (AST_NUM 0) = AST_NUM (0) | apply AST_PRED (AST_NUM n) = AST_NUM (n - 1) | apply AST_PRED (e as AST_ERROR s) = e | apply AST_PRED _ = AST_ERROR "pred needs integer arg" | apply AST_ISZERO (AST_NUM n) = AST_BOOL (n = 0) | apply AST_ISZERO (e as AST_ERROR s) = e | apply AST_ISZERO _ = AST_ERROR "iszero needs integer arg" (* If the parameter argument has an error, propagate the error *) | apply (AST_FUN (param, body)) (e as AST_ERROR _) = e (* Apply the function by substituting the evaluated argument in for the parameter throughout the function body. *) | apply (AST_FUN (param, body)) arg = interp (subst body param arg) (* The first argument turned out to not be a function! *) | apply _ _ = AST_ERROR "expecting a function to apply" val f = interp func val x = interp arg in (* Simplify the terms. Apply the simplified function to the simplified argument *) apply f x end (* Interpret an if expression by evaluating the condition and then interpreting at most one of the true or false expression based on the result. *) | interp (AST_IF (cond, trueExp, falseExp)) = let fun interpIf (AST_BOOL true) trueExp falseExp = interp trueExp | interpIf (AST_BOOL false) trueExp falseExp = interp falseExp | interpIf (e as AST_ERROR s) _ _ = e | interpIf _ _ _ = AST_ERROR "if needs a boolean condition" in interpIf (interp cond) trueExp falseExp end (* We should never attempt to interpret a variable. The substition performed during interpreting function application and recursion should eliminate all identifiers. If there are any left, it indicates that we attempted to use a variable without giving it a value. *) | interp (AST_ID x) = AST_ERROR (x ^ " not bound") (* Interpret a recursive function by unwinding the recursion one level. *) | interp (r as AST_REC (param, body)) = interp (subst body param r) (* Following captures int, bool, succ, pred, iszero, fun, and error which just return themselves. *) | interp t = t;