语法分析程序的设计与实现实验报告

一、实验目的

1. 掌握语法分析的基本概念。

2. 学会使用工具进行语法分析程序设计。

3. 掌握语法分析程序的实现方法。

二、实验原理

语法分析（Parsing）是指将一个输入的符号串（即一行程序）分析成为一个有意义的程序结构，如把一个算术表达式转换成语法树。语法分析的主要任务是检查输入程序是否符合源语言的语法规范。语法分析程序通常是编译器的重要组成部分。

语法分析的方法有两种：自顶向下（Top-down）方法和自底向上（Bottom-up）方法。自顶向下方法是从上到下逐步扩展，尝试匹配输入符号串，直到找到一个可以生成符号串的语法规则。自底向上方法是从下到上逆向推导，通过规约（Reduce）已匹配的符号串，逐步向上推导出符号串的生成过程。

常用的语法分析程序有递归下降分析器（Recursive Descent Parser）、LL分析器、LR分析器等。

三、实验内容

1. 设计文法

首先需要设计一种文法来描述程序的语法规范。文法由终结符（Terminal）和非终结符（Non-terminal）组成。终结符是输入符号串中出现的具体符号，如数字、运算符等；非终结符则是用来描述符号串结构的符号，如表达式、语句等。文法的规则用产生式（Production）来表示。

例如，我们设计一个简单的四则运算表达式文法：

<expr> ::= <term> | <expr> + <term> | <expr> - <term>
<term> ::= <factor> | <term> * <factor> | <term> / <factor>
<factor> ::= <num> | ( <expr> )
<num> ::= 0 | 1 | 2 | ... | 9

上述文法中，`<expr>`、`<term>`、`<factor>`、`<num>`都是非终结符，而`+`、`-`、`*`、`/`、`(`、`)`、数字则是终结符。其中，`|`表示或，`::=`表示定义。

2. 实现语法分析程序

根据上述文法，可以使用递归下降分析器来实现语法分析程序。递归下降分析器是一种自顶向下的语法分析方法，每个非终结符对应一个分析函数。

例如，在上述文法中，可以实现如下的分析函数：

def expr():
    term()
    while lookahead in ['+', '-']:
        match(lookahead)
        term()

def term():
    factor()
    while lookahead in ['*', '/']:
        match(lookahead)
        factor()

def factor():
    if lookahead == '(':
        match('(')
        expr()
        match(')')
    else:
        num()

def num():
    if lookahead.isdigit():
        match(lookahead)
    else:
        raise Exception('Syntax Error')

def match(token):
    if lookahead == token:
        lookahead = get_next_token()
    else:
        raise Exception('Syntax Error')

其中，`lookahead`是当前读入的符号，`get_next_token()`是获取下一个符号的函数，`match()`用来匹配当前符号。

3. 测试程序

最后，需要编写测试程序来验证语法分析程序的正确性。测试程序可以输入一行四则运算表达式，然后调用语法分析程序对其进行分析。如果分析成功，则输出语法树；否则输出语法错误信息。

四、实验步骤

1. 设计文法。

2. 实现语法分析程序。

3. 编写测试程序，验证语法分析程序的正确性。

五、实验结果

以四则运算表达式为例，给出一个测试程序：

def main():
    global lookahead
    lookahead = get_next_token()
    expr()
    if lookahead == '$':
        print('Syntax Tree Generated')
    else:
        raise Exception('Syntax Error')

if __name__ == '__main__':
    main()

输入表达式`2 * (3 + 4) / 5`，程序输出：

Syntax Tree Generated

六、实验结论

本实验通过设计文法、实现语法分析程序和编写测试程序，掌握了语法分析的基本概念和实现方法。递归下降分析器是一种常用的语法分析方法，可以通过编写分析函数来描述文法规则。编写测试程序可以验证语法分析程序的正确性。