<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 A Simple Parser for Term Rewriting
This file implements a parser for terms and equations.  It uses the parser generator Ply.  To install Ply, change the cell below into a code cell and execute it.  If the package ply is already installed, this command will only produce a message that the package is already installed.
!conda install -y -c anaconda ply
Specification of the Scanner
The scanner that is implemented below recognizes numbers, variable names, function names, and various operator symbols.  Variable names have to start with a lower case letter, while function names start with an uppercase letter.
Step1:  The token Number specifies a natural number.  Syntactically, numbers are treated a function symbols.
Step2:  Variables start with a letter, followed by letters, digits, and underscores. They must be followed by a character that is not an opening parenthesis (.
Step3:  Function names start with a letter, followed by letters, digits, and underscores. 
They have to be followed by an opening parenthesis (.
Step4:  Single line comments are supported and work as in C.
Step5:  The arithmetic operators and a few other symbols are supported.
Step6:  White space, i.e. space characters, tabulators, and carriage returns are ignored.
Step7:  Syntactically, newline characters are ignored. However, we still need to keep track of them in order to know which line we are in.  This information is needed later for error messages.
Step8:  Given a token, the function find_colum returns the column where token starts.
This is possible, because token.lexer.lexdata stores the string that is given to the scanner and token.lexpos is the number of characters that precede token.
Step9:  The function t_error is called for any token t that can not be scanned by the lexer.  In this case, t.value[0] is the first character that can not be recognized by the scanner.
Step10:  The next assignment is necessary to make the lexer think that the code given above is part of some file.
Step11:  for t in test_scanner('Examples/quasigroup.eqn')
Step12:  The start variable of our grammar is axioms.
Step13:  Setting the optional argument write_tables to False is required to prevent an obscure bug where the parser generator tries to read an empty parse table.  As we have used precedence declarations to resolve all shift/reduce conflicts, the action table should contain no conflict.
Step14:  !cat parser.out
The notebook AST-2-Dot.ipynb provides the function tuple2dot.  This function can be used to visualize the abstract syntax tree that is generated by the function yacc.parse.
Step15:  The function parse takes a file_name as its sole argument.  The file is read and parsed. 
The resulting parse tree is visualized using graphviz.  It is important to reset the
attribute lineno of the scanner, for otherwise error messages will not have the correct line numbers.
Step16:  !cat Examples/quasigroup.eqn
test_parse('Examples/quasigroup.eqn')
The function indent is used to indent the generated assembler commands by preceding them with 8 space characters.
Step17:  parse_file('Examples/group-theory.eqn')
Step18:  parse_equation('i(x) * x = 1')
Step19:  parse_term('i(x) * x')
<ASSISTANT_TASK:>
Python Code:
import ply.lex as lex
tokens = [ 'NUMBER', 'VAR', 'FCT', 'BACKSLASH' ]
Explanation: A Simple Parser for Term Rewriting
This file implements a parser for terms and equations.  It uses the parser generator Ply.  To install Ply, change the cell below into a code cell and execute it.  If the package ply is already installed, this command will only produce a message that the package is already installed.
!conda install -y -c anaconda ply
Specification of the Scanner
The scanner that is implemented below recognizes numbers, variable names, function names, and various operator symbols.  Variable names have to start with a lower case letter, while function names start with an uppercase letter.
End of explanation
def t_NUMBER(t):
    r'0|[1-9][0-9]*'
    return t
Explanation: The token Number specifies a natural number.  Syntactically, numbers are treated a function symbols.
End of explanation
def t_VAR(t):
    r'[a-zA-Z][a-zA-Z0-9_]*(?=[^(a-zA-Z0-9_])'
    return t
Explanation: Variables start with a letter, followed by letters, digits, and underscores. They must be followed by a character that is not an opening parenthesis (.
End of explanation
def t_FCT(t):
    r'[a-zA-Z][a-zA-Z0-9_]*(?=[(])'
    return t
def t_BACKSLASH(t):
    r'\\'
    return t
Explanation: Function names start with a letter, followed by letters, digits, and underscores. 
They have to be followed by an opening parenthesis (.
End of explanation
def t_COMMENT(t):
    r'//[^\n]*'
    t.lexer.lineno += t.value.count('\n')
    pass
Explanation: Single line comments are supported and work as in C.
End of explanation
literals = ['+', '-', '*', '/', '\\', '%', '^', '(', ')', ';', '=', ',']
Explanation: The arithmetic operators and a few other symbols are supported.
End of explanation
t_ignore  = ' \t\r'
Explanation: White space, i.e. space characters, tabulators, and carriage returns are ignored.
End of explanation
def t_newline(t):
    r'\n'
    t.lexer.lineno += 1
    return
Explanation: Syntactically, newline characters are ignored. However, we still need to keep track of them in order to know which line we are in.  This information is needed later for error messages.
End of explanation
def find_column(token):
    program    = token.lexer.lexdata
    line_start = program.rfind('\n', 0, token.lexpos) + 1
    return (token.lexpos - line_start) + 1
Explanation: Given a token, the function find_colum returns the column where token starts.
This is possible, because token.lexer.lexdata stores the string that is given to the scanner and token.lexpos is the number of characters that precede token.
End of explanation
def t_error(t):
    column = find_column(t)
    print(f"Illegal character '{t.value[0]}' in line {t.lineno}, column {column}.")
    t.lexer.skip(1)
Explanation: The function t_error is called for any token t that can not be scanned by the lexer.  In this case, t.value[0] is the first character that can not be recognized by the scanner.
End of explanation
__file__ = 'main'
lexer = lex.lex()
def test_scanner(file_name):
    with open(file_name, 'r') as handle:
        program = handle.read() 
    print(program)
    lexer.input(program)
    lexer.lineno = 1
    return [t for t in lexer]
Explanation: The next assignment is necessary to make the lexer think that the code given above is part of some file.
End of explanation
import ply.yacc as yacc
Explanation: for t in test_scanner('Examples/quasigroup.eqn'):
    print(t)
Specification of the Parser
We will use the following grammar to specify the language that our compiler can translate:
```
axioms
    : equation
    | axioms equation 
    ;
equation 
    : term '=' term
    ;
term: term '+'  term               
    | term '-' term             
    | term '*' term             
    | term '/' term 
    | term '\' term
    | term '%' term
    | term '^' term
    | '(' term ')' 
    | FCT '(' term_list ')'   
    | FCT                   
    | VAR
    ;
term_list
    : / epsilon /
    | term
    | term ',' ne_term_list
    ;
ne_term_list
    : term
    | term ',' ne_term_list
    ;
```
We will use precedence declarations to resolve the ambiguity that is inherent in this grammar.
End of explanation
start = 'axioms'
precedence = (
    ('nonassoc', '='),
    ('left', '+', '-'),
    ('left', '*', '/', 'BACKSLASH', '%'),
    ('right', '^')
)
def p_axioms_one(p):
    "axioms : equation"
    p[0] = ('axioms', p[1])
    
def p_axioms_more(p):
    "axioms : axioms equation"
    p[0] = p[1] + (p[2],)
def p_equation(p):
    "equation : term '=' term ';'"
    p[0] = ('=', p[1], p[3])
def p_term_plus(p):
    "term : term '+' term"
    p[0] = ('+', p[1], p[3])
    
def p_term_minus(p):
    "term : term '-' term"
    p[0] = ('-', p[1], p[3])
    
def p_term_times(p):
    "term : term '*' term"
    p[0] = ('*', p[1], p[3])
    
def p_term_divide(p):
    "term : term '/' term"
    p[0] = ('/', p[1], p[3])
    
def p_term_backslash(p):
    "term : term BACKSLASH term"
    p[0] = ('\\', p[1], p[3])
    
def p_term_modulo(p):
    "term : term '%' term"
    p[0] = ('%', p[1], p[3])
    
def p_term_power(p):
    "term : term '^' term"
    p[0] = ('^', p[1], p[3])
    
def p_term_group(p):
    "term : '(' term ')'"
    p[0] = p[2]
def p_term_fct_call(p):
    "term : FCT '(' term_list ')'"
    p[0] = (p[1],) + p[3][1:]
def p_term_number(p):
    "term : NUMBER"
    p[0] = (p[1],)
def p_term_id(p):
    "term : VAR"
    p[0] = ('$var', p[1])
def p_term_list_empty(p):
    "term_list :"
    p[0] = ('.',)
    
def p_term_list_one(p):
    "term_list : term"
    p[0] = ('.', p[1])     
def p_term_list_more(p):
    "term_list : term ',' ne_term_list"
    p[0] = ('.', p[1]) + p[3][1:]     
def p_ne_term_list_one(p):
    "ne_term_list : term"
    p[0] = ('.', p[1]) 
    
def p_ne_term_list_more(p):
    "ne_term_list : term ',' ne_term_list"
    p[0] = ('.', p[1]) + p[3][1:] 
def p_error(p):
    if p:
        column = find_column(p)
        print(f'Syntax error at token "{p.value}" in line {p.lineno}, column {column}.')
    else:
        print('Syntax error at end of input.')
Explanation: The start variable of our grammar is axioms.
End of explanation
parser = yacc.yacc(write_tables=False, debug=True)
Explanation: Setting the optional argument write_tables to False is required to prevent an obscure bug where the parser generator tries to read an empty parse table.  As we have used precedence declarations to resolve all shift/reduce conflicts, the action table should contain no conflict.
End of explanation
%run AST-2-Dot.ipynb
Explanation: !cat parser.out
The notebook AST-2-Dot.ipynb provides the function tuple2dot.  This function can be used to visualize the abstract syntax tree that is generated by the function yacc.parse.
End of explanation
def test_parse(file_name):
    lexer.lineno = 1
    with open(file_name, 'r') as handle:
        program = handle.read() 
    ast = yacc.parse(program)
    print(ast)
    return tuple2dot(ast)
Explanation: The function parse takes a file_name as its sole argument.  The file is read and parsed. 
The resulting parse tree is visualized using graphviz.  It is important to reset the
attribute lineno of the scanner, for otherwise error messages will not have the correct line numbers.
End of explanation
def parse_file(file_name):
    lexer.lineno = 1
    with open(file_name, 'r') as handle:
        program = handle.read() 
    AST = yacc.parse(program)
    if AST:
        _, *L = AST
        return L
    return None
Explanation: !cat Examples/quasigroup.eqn
test_parse('Examples/quasigroup.eqn')
The function indent is used to indent the generated assembler commands by preceding them with 8 space characters.
End of explanation
def parse_equation(s):
    lexer.lineno = 1
    AST = yacc.parse(s + ';')
    if AST:
        _, *L = AST
        return L[0]
    return None
Explanation: parse_file('Examples/group-theory.eqn')
End of explanation
def parse_term(s):
    lexer.lineno = 1
    AST = yacc.parse(s + '= 1;')
    if AST:
        _, *L = AST
        return L[0][1]
    return None
Explanation: parse_equation('i(x) * x = 1')
End of explanation
def to_str(t):
    if isinstance(t, set):
        return '{' + ', '.join({ f'{to_str(eq)}' for eq in t }) + '}'
    if isinstance(t, list):
        return '[' + ', '.join([ f'{to_str(eq)}' for eq in t ]) + ']'
    if isinstance(t, dict):
        return '{' + ', '.join({ f'{k}: {to_str(v)}' for k, v in t.items() }) + '}'
    if isinstance(t, str):
        return t
    if t[0] == '$var':
        return t[1]
    if len(t) == 3 and t[0] in ['=']:
        _, lhs, rhs = t
        return f'{to_str(lhs)} = {to_str(rhs)}'
    if t[0] == '\\':
        op, lhs, rhs = t
        return to_str_paren(lhs) + ' \\ ' + to_str_paren(rhs)
    if len(t) == 3 and t[0] in ['+', '-', '*', '/', '%', '^']:
        op, lhs, rhs = t
        return f'{to_str_paren(lhs)} {op} {to_str_paren(rhs)}'
    f, *Args = t
    if Args == []:
        return f
    return f'{f}({to_str_list(Args)})'
def to_str_paren(t):
    if isinstance(t, str):
        return t
    if t[0] == '$var':
        return t[1]
    if len(t) == 3:
        op, lhs, rhs = t
        return f'({to_str_paren(lhs)} {op} {to_str_paren(rhs)})'
    f, *Args = t
    if Args == []:
        return f
    return f'{f}({to_str_list(Args)})'
def to_str_list(TL):
    if TL == []:
        return ''
    t, *Ts = TL
    if Ts == []:
        return f'{to_str(t)}'
    return f'{to_str(t)}, {to_str_list(Ts)}'
Explanation: parse_term('i(x) * x')
End of explanation
<END_TASK>