用python写一个递归下降的语法分析器，要求如下：（1）写出Sample语言（或你所选定的语言）的算术表达式的文法，利用递归下降的方法编写判定给定的单词串能否构成一个正确的算术表达式的函数，写一个主函数读入一个单词串，进行测试。（2）利用上一步的方法，编写对赋值表达式、布尔表达式和关系表达式的分析。（3）编写对if语句语法结构的分析。（4）编写对程序的语法结构的分析，完成一个完整的Sample语言程序的分析。

Sample语言的算术表达式文法：

<expression> → <term> | <expression> + <term> | <expression> - <term>
<term> → <factor> | <term> * <factor> | <term> / <factor>
<factor> → <number> | (<expression>)

<number>表示一个数字，可以是整数或小数。

实现代码如下：

def expression(tokens):
if len(tokens) == 0:
return False
if term(tokens):
if len(tokens) == 0:
return True
if tokens[0] == '+' or tokens[0] == '-':
return expression(tokens[1:])
else:
return False
else:
return False

def term(tokens):
if len(tokens) == 0:
return False
if factor(tokens):
if len(tokens) == 0:
return True
if tokens[0] == '*' or tokens[0] == '/':
return term(tokens[1:])
else:
return False
else:
return False

def factor(tokens):
if len(tokens) == 0:
return False
if tokens[0] == '(':
if expression(tokens[1:]):
if len(tokens) > 1 and tokens[1] == ')':
return True
else:
return False
else:
return False
else:
return number(tokens)

def number(tokens):
if len(tokens) == 0:
return False
if tokens[0].isdigit():
if len(tokens) == 1:
return True
if tokens[1].isdigit() or tokens[1] == '.':
return number(tokens[1:])
else:
return True
elif tokens[0] == '-':
return number(tokens[1:])
else:
return False

主函数可以这样实现：

def test_expression():
while True:
s = input('Input an expression (press q to quit): ')
if s == 'q':
break
tokens = s.split()
if expression(tokens):
print('Valid expression')
else:
print('Invalid expression')

if __name__ == '__main__':
test_expression()

对于赋值表达式、布尔表达式和关系表达式的分析，可以类似地实现递归下降的函数。例如，布尔表达式的文法：

<boolean> → <boolean> or <boolean> | <boolean> and <boolean> | not <boolean> | <relation>
<relation> → <expression> < <expression> | <expression> <= <expression> | <expression> == <expression> | <expression> >= <expression> | <expression> > <expression> | <expression> != <expression>

实现代码如下：

def boolean(tokens):
if len(tokens) == 0:
return False
if tokens[0] == 'not':
return boolean(tokens[1:])
if relation(tokens):
return True
if len(tokens) > 2 and (tokens[1] == 'and' or tokens[1] == 'or'):
if boolean(tokens[:2]) and boolean(tokens[2:]):
return True
else:
return False
else:
return False

def relation(tokens):
if len(tokens) == 0:
return False
if expression(tokens):
if len(tokens) > 1 and tokens[1] in ['<', '<=', '==', '>=', '>', '!=']:
if expression(tokens[2:]):
return True
else:
return False
else:
return True
else:
return False

赋值表达式和if语句的文法可以类似地定义和实现。对于程序的语法结构的分析，可以先实现对函数定义和函数调用的分析，然后再实现对程序的顶层结构的分析。具体实现略。