编译原理语法分析源程序

语法分析是编译原理中的一个重要环节，它的主要任务是根据给定的源程序，确定它是否符合语法规则，如果不符合，就报告错误。下面是一个简单的语法分析示例，使用的是自顶向下的递归下降分析方法。

假设我们要分析的是以下的简单的算术表达式：

a = b + c * d

首先，我们需要定义该算术表达式的语法规则，通常使用巴克斯范式（BNF）表示。假设我们的语法规则如下：

<expr> ::= <term> | <term> '+' <expr>
<term> ::= <factor> | <factor> '*' <term>
<factor> ::= 'id' | '(' <expr> ')'

其中，`<expr>` 表示表达式，`<term>` 表示项，`<factor>` 表示因子，`'+'` 表示加号，`'*'` 表示乘号，`'id'` 表示一个标识符。根据这些规则，我们可以把上述的算术表达式转换为以下的语法树：

<expr>
   |
 <term>
   |
 <factor>  'a'

其中，`'a'` 表示标识符 `a`。

现在，我们可以使用递归下降的方法，从上到下地分析这个表达式了。以 `expr()` 函数为例，代码如下：

def expr():
    term()
    while lookahead == '+':
        match('+')
        term()

def term():
    factor()
    while lookahead == '*':
        match('*')
        factor()

def factor():
    if lookahead == 'id':
        match('id')
    elif lookahead == '(':
        match('(')
        expr()
        match(')')
    else:
        raise SyntaxError('Expected id or (expr)')

def match(expected):
    if lookahead == expected:
        lookahead = get_token()
    else:
        raise SyntaxError('Expected ' + expected)

def get_token():
    # 从输入流中获取下一个 token

在这个代码中，我们使用了一个全局变量 `lookahead` 来表示当前的 token，它的初值是输入流的第一个 token。`match()` 函数用来比较当前的 token 是否符合预期，如果符合，则获取下一个 token；否则，就抛出一个语法错误。`get_token()` 函数用来从输入流中获取下一个 token。

我们从 `expr()` 函数开始分析，它首先调用 `term()` 函数，然后进入一个循环，每次循环都检查当前的 token 是否是一个加号，如果是，则调用 `match()` 函数获取下一个 token，并且再调用一次 `term()` 函数。这个循环的作用是处理所有的加号，直到没有加号为止。

`term()` 函数也类似，首先调用 `factor()` 函数，然后进入一个循环，每次循环都检查当前的 token 是否是一个乘号，如果是，则调用 `match()` 函数获取下一个 token，并且再调用一次 `factor()` 函数。这个循环的作用是处理所有的乘号，直到没有乘号为止。

`factor()` 函数则根据当前的 token 类型来决定下一步该做什么。如果当前的 token 是一个标识符，则调用 `match()` 函数获取下一个 token；否则，如果当前的 token 是一个左括号，则调用 `match()` 函数获取下一个 token，然后调用 `expr()` 函数分析括号内的表达式，并且再调用一次 `match()` 函数获取下一个 token，确保右括号的出现。

这样，我们就完成了一个简单的算术表达式的语法分析程序。当然，在实际的编译器中，语法规则要复杂得多，而且采用的分析方法也可能不同。但是，递归下降分析法作为一种简单而有效的语法分析方法，在编译原理中具有重要的地位。