"""
 recdesent.py

 An implementation of a simple recursive descent parser
 implementing "grammar 2" at cs.marlboro.college/courses/
 fall2016/formal_languages/notes/programming_language_parsers

 See for example https://en.wikipedia.org/wiki/Recursive_descent_parser

 I've modified the grammar to remove the left recursion
 in grammar 2, in a way that's similar to the discussion at
 https://en.wikipedia.org/wiki/Left_recursion . The problem
 is that with left recursion, the recursive definition 
 expr=expr+term will expand into expr(expr(expr(....) infinitely.

 The right recursive modified version expr=term+expr avoids this
 problem by expending into expr(term(expr(term(...)))) which
 needs to find the "+" for each continued level of recursion,
 and which will therefore stop at the appropriate depth.

 This modification does change the structure of the resulting parse tree.
 However, the language is still the same, and the arithmetic calculation
 is also still the same ... so maybe that's good enough. :)

 The difference can be seen by looking at the parse tree for "1+2+3". 
 The original grammar 2 would give the tree (expr (expr 1 + 2) + 3),
 while the modified grammar (avoiding left recursion) 

 Using a lisp notation to represent the tree, the original grammar 
 turns "1+2+3" into the tree  while the modified
 grammar will give (+ 1 (+ 2 3)). 

 Anyway, here's the modified grammar that is implemented below.

    -- lexer handles these --
    addop       ::=   "+" | "-"
    mulop       ::=   "*" | "/"
    number      ::=   digit+
    identifier  ::=   letter+
    digit       ::=   "0" | "1" | ... | "8" | "9"
    letter      ::=   "a" | "b" | ... | "y" | "z"

    -- parser handles these  --              kids    lisp_template
                                             ----    --------------
    expr        ::=   term                   1       singlet kid term
                      term addop expr        3       ( op left right )
    term        ::=   factor                 1       singlet kid factor
                      factor mulop term      3       ( op left right )
    factor      ::=   id                     0       its value
                      number                 0       its value
                      "-" factor             2       (- fact)
                      "(" expr ")"           3       kid expr


 The processing is 

     input_string --> lexer ------> parser -----> compiler --> output_string
     symbols                tokens         tree                lisp

 I'm storing the tokens as a sequence of Token objects,
 then reusing them as nodes in a parse tree.

 The lexer does regular expression matching.

 The parser uses a "recursive descent" method,
 with a function call (e.g. expression()) for 
 the left hand side of each production rule, 
 which tries to find the right hand side recursively.

 The lisp compilation step is just a few string templates,
 for example "term addop expr" turns into "({op} {term} {expr})".

 So there you go.

 Running it :

   $ python --version
   Python 3.7.3
   $ python recdescent.py > recdescent_output.txt

 Jim Mahoney | cs.marlboro.college | Sep 2019 | MIT License
"""

import re
DEBUG = False

import pprint
pp = pprint.PrettyPrinter(indent=4)

def print_debug(name, value):
    if DEBUG:
        print(f" *DEBUG* {name} is '{value}'")

class Token:
    """ A Token is both 
           (a) what the lexer finds in the input and
           (b) a node in the parse tree.
    """

    def __init__(self, kind='', value='', children=[]):
        self.kind = kind
        self.value = value
        self.children = children

    def __str__(self):
        return "Token(kind='"  + self.kind  + "'," + \
                     "value='" + self.value + "'," + \
                     "children=[" + ','.join(map(str, self.children)) + "])"

    def as_tree(self):
        return [self.kind, self.value,
                list(map(lambda x: x.as_tree(), self.children))]
    
    def as_lisp(self):
        if len(self.children) == 0:                  # identifier or number
            return str(self.value)
        elif len(self.children) == 1:                # singlet <term> or <expr>
            return self.children[0].as_lisp()
        elif len(self.children) == 2:                # (- stuff)
            return '(- ' + self.children[1].as_lisp() + ')'
        elif self.children[0].kind == 'LEFTPAREN':   # just output interior
            return self.children[1].as_lisp()
        elif len(self.children) == 3:                # (op thing thing)
            return '(' + self.children[1].value \
                       + ' ' + self.children[0].as_lisp() \
                       + ' ' + self.children[2].as_lisp() + ')'
        else:
            return f'OOPS:{str(self)}'
        
lexer_kind = { r'([0-9]+)([^0-9]|$)' : 'NUMBER',
               r'([a-z]+)([^a-z]|$)' : 'IDENTIFIER',
               r'(\+|\-)'            : 'ADDOP',
               r'(\*|\/)'            : 'MULOP',
               r'(\()'               : 'LEFTPAREN',
               r'(\))'               : 'RIGHTPAREN' }

def next_token(symbols):
    """ Search the start of the symbols for the next token.
        Return (token, remaining_symbols).
        If a legal token cannot be found, throw an exception. """
    print_debug('start next_token symbols', symbols)
    symbols = symbols.lstrip()
    for regex in lexer_kind:
        search = re.match(regex, symbols)
        if search:
            found = search.groups()[0]
            token = Token(kind=lexer_kind[regex], value=found)
            print_debug('in next_token token is ', token)
            return (token, symbols[len(found):])
    raise Exception('Token not found.')

def lexer(symbols):
    """ Convert a string of symbols to a list of (childless) tokens """
    tokens = []
    while len(symbols) > 0:
        (token, symbols) = next_token(symbols)
        tokens.append(token)
    return tokens

def parse(tokens):
    """ Convert a sequence of tokens to a parse tree,
        that is, a single root token and its ancestors. """
    (tree, leftover_tokens) = expression(tokens)
    if leftover_tokens:
        raise Exception("OOPS - extra symbols in input")
    return tree

def expression(tokens):
    """ Search for an <expression> within a sequence of tokens.
        Return (tree, remaining_tokens). """
    print_debug(f'<expression> from {len(tokens)} tokens ',
                (str(tokens[0]), str(tokens[-1])))
    (left_side, tokens) = term(tokens)
    if tokens and tokens[0].kind == 'ADDOP':
        addop = tokens.pop(0)
        (right_side, tokens) = expression(tokens)
        its_children = [left_side, addop, right_side]
    else:
        its_children = [left_side]
    return (Token(kind = 'EXPRESSION',
                  value = '',
                  children = its_children),
            tokens)

def term(tokens):
    """ Search for a <term> within a sequence of tokens.
        Return (tree, remaining_tokens). """
    print_debug(f'<term> from {len(tokens)} tokens ',
                (str(tokens[0]), str(tokens[-1])))
    (left_side, tokens) = factor(tokens)
    if tokens and tokens[0].kind == 'MULOP':
        mulop = tokens.pop(0)
        (right_side, tokens) = term(tokens)
        its_children = [left_side, mulop, right_side]
    else:
        its_children = [left_side]
    return (Token(kind = 'TERM',
                  value = '',
                  children = its_children),
            tokens)

def factor(tokens):
    """ Search for a <factor> with a sequence of tokens.
        Return (tree, remaining_tokens) """
    print_debug(f'<factor> from {len(tokens)} tokens ',
                (str(tokens[0]), str(tokens[-1])))
    if tokens[0].kind in ('IDENTIFIER', 'NUMBER'):
        singlet = tokens.pop(0)
        return (Token(kind='FACTOR',
                      value='',
                      children=[singlet]),
                tokens)
    elif tokens[0].kind == 'ADDOP' and tokens[0].value == '-':
        negate = tokens.pop(0)
        (fact, tokens) = factor(tokens)
        return (Token(kind='FACTOR',
                      value='',
                      children=[Token(kind='NEGATE'), fact]),
                tokens)
    elif tokens[0].kind == 'LEFTPAREN':
        leftparen = tokens.pop(0)
        (expr, tokens) = expression(tokens)
        rightparen = tokens.pop(0)
        if rightparen.kind != 'RIGHTPAREN':
            raise Exception('OOPS - mismatched parens')
        return (Token(kind='FACTOR',
                      value='',
                      children=[leftparen, expr, rightparen]),
                tokens)
    else:
        raise Exception('OOPS - failed to find factor')

def test():
    tests = ['123',
             'a*b',
             'a + 2 * b',
             '1*c*2*d',
             'a*b+c*d',
             '123 + abc + z * ( 3 + x )'
            ]
    for symbols in tests:
        print('='*40)
        print('-- input : ', symbols)

        print('-- lexer :')
        tokens = lexer(symbols)
        for token in tokens:
            print(token)

        print('-- parser : ')
        tree = parse(tokens)
        pp.pprint(tree.as_tree())

        print('-- output : ', tree.as_lisp())

if __name__ == '__main__':
    test()