"""parser.py --- A small scheme parser. Danny Yoo (dyoo@hkn.eecs.berkeley.edu) This parser might be useful if we wanted to grab information from the user using Schemeish lists. It might also be nice if one is planning to write a Scheme interpreter in Python. *cough* The main functions to use in this module are parse(s): parse string s, and return a either an atomic value (symbol or number) or a pair. If anything bad happens during the parsing, we'll raise a ParserError. Some special notes: this module should behave well even under unusual input: there should be no possibility of hitting the recursion limit, since we are using trampolined style. """ __license__ = "MIT License" from lex import tokenize from symbol import symbol from pair import cons, NIL, list import unittest class ParserError(Exception): """Our personalized exception class.""" pass def peek(tokens): """Take a quick glance at the first token in our tokens list.""" if len(tokens) == 0: raise ParserError, "While peeking: ran out of tokens." return tokens[0] def eat(tokens, tokenType): """Digest the first token in our tokens list, making sure that we're biting on the right tokenType of thing.""" if len(tokens) == 0: raise ParserError, "While trying to eat %s: ran out of tokens." % \ (repr(tokenType),) if tokens[0][0] != tokenType: raise ParserError, "While trying to eat %s: got token %s instead." % \ (repr(tokenType), repr(tokens[0])) return tokens.pop(0) ###################################################################### """Below is our parser for symbol-lists. We'll use a recursive descent parsing technique, since Scheme's syntax is so well suited for it. Actually, it's a bit more complicated than this. There is one major problem with a naive rec-descent approach: with unusual input, we can run into Python's recursion stack limit. To get around this, we first wrote the parser normally, and then attacked the recursion using CPS and trampolining style. The result is that the parser works, even with evil input, but it's a bit harder to read. """ def parseSingleExpression(tokens): """Returns a single Expression, given a sequence of tokens. Raises a ParserException if our tokens haven't been exhausted.""" exp = parseExpression(tokens) if eat(tokens, None): return exp else: raise ParserError, "extra stuff after expression: %s." % tokens def parseExpression(tokens): """Returns an Expression, given a sequence of tokens. An expression is made up of one of the following things: o A quoted expression o An atom (like a number or symbol or string) o A list. This procedure tries to take care of all these potentials.""" look_ahead_type = peek(tokens)[0] if look_ahead_type == '\'': eat(tokens, '\'') return cons(symbol('quote'), cons(parseExpression(tokens), NIL)) if look_ahead_type == '`': eat(tokens, '`') return cons(symbol('quasiquote'), cons(parseExpression(tokens), NIL)) elif look_ahead_type == ',': eat(tokens, ',') return cons(symbol('unquote'), cons(parseExpression(tokens), NIL)) elif look_ahead_type == '(': return parse_list(tokens) elif look_ahead_type in ('number', 'symbol', 'string'): return parse_atom(tokens) else: raise ParserError, "While parsing Expression: no alternatives." def parse_atom(tokens): """Returns an Atom, given a sequence of tokens. An atom is either a number, a symbol, or a string.""" next_type = peek(tokens)[0] if next_type == 'number': return to_number(eat(tokens, 'number')[1]) elif next_type == 'symbol': return symbol(eat(tokens, 'symbol')[1]) elif next_type == 'string': return eat(tokens, 'string')[1] else: raise ParserError, "While parsing Atom: no alternatives." def to_number(s): """Tries to convert string 's' into a number.""" try: return int(s) except ValueError: return float(s) def parse_list(tokens): """Parses a parenthesized list expression.""" eat(tokens, "(") return parse_list_members(tokens) def parse_list_members(tokens): """Tries to eat as many expressions as it can see.""" START_EXPR_SET = ('\'', '`', ',', '(', 'number', 'symbol', 'string') # Dotted pairs if peek(tokens) == ('symbol', '.'): eat(tokens, 'symbol') final = parseExpression(tokens) eat(tokens, ')') return final if peek(tokens)[0] in START_EXPR_SET: next = parseExpression(tokens) return cons(next, parse_list_members(tokens)) if peek(tokens)[0] == ')': eat(tokens, ')') return NIL raise ParserError, "Can't finish list: %s." % tokens def parse(s): """Parse a single string. This is just a convenience function.""" return parseSingleExpression(tokenize(s)) ###################################################################### class ParserTests(unittest.TestCase): def testAtomParsing(self): self.assertEquals(42, parse("42")) self.assertEquals("particle-man", parse('"particle-man"')) def testBrokenNegativeExampleFromBaypiggies(self): ## embarassing case that didn't work during the Baypiggies meeting ## on September 9, 2004. Doh! self.assertEquals(-42, parse("-42")) def testLists(self): self.assertEquals(list(1, 2), parse("(1 2)")) self.assertEquals(list(1, 2, list(3), 4), parse("(1 2 (3) 4)")) self.assertEquals(list(list(list())), parse("((()))")) def testQuotation(self): self.assertEquals(list(symbol("quote"), symbol("atom-man")), parse("'atom-man")) self.assertEquals(list(symbol("quasiquote"), symbol("istanbul")), parse("`istanbul")) self.assertEquals(list(symbol("unquote"), symbol("constantinople")), parse(",constantinople")) def testDottedPair(self): self.assertEquals(cons(symbol("alpha"), symbol("beta")), parse("(alpha . beta)")) self.assertEquals(cons(symbol("a"), cons(symbol("b"), cons(cons(symbol("c"), symbol("d")), NIL))), parse("(a b (c . d))")) def testQuotedList(self): self.assertEquals(list(symbol("quote"), list(symbol("foo"), symbol("bar"))), parse("'(foo bar)")) def testEmptyList(self): self.assertEquals(NIL, parse("()")) def testStressWithSuperNesting(self): ## An evil test to see if this raises bad errors. N = 1000 bigNestedList = list() for ignored in xrange(N-1): bigNestedList = list(bigNestedList) try: self.assertEquals(bigNestedList, parse( "(" * N + ")" * N)) except RuntimeError, e: self.fail(e) if __name__ == '__main__': unittest.main()