编译原理语法分析实验

语法分析是编译器的重要组成部分，它将源代码解析成抽象语法树（AST），以便进一步处理。下面是一个基本的语法分析实验，其中我们将使用自顶向下的递归下降分析方法。

1. 定义文法

首先，我们需要定义一种文法来描述我们要分析的语言。假设我们要分析的语言是一个简单的四则运算表达式语言，其中包含加、减、乘、除四种操作符，以及括号和整数常量。该语言的文法可以定义如下：

expr -> term (+|- term)*
term -> factor (*|/ factor)*
factor -> int | '(' expr ')'
int -> digit+
digit -> 0|1|2|3|4|5|6|7|8|9

2. 实现语法分析器

接下来，我们需要实现一个语法分析器来解析源代码并构建抽象语法树。我们可以使用递归下降分析方法，其中每个非终结符对应一个函数，该函数负责解析该非终结符的语法规则。

下面是一个简单的Python实现：

class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0
    
    def parse(self):
        return self.expr()
    
    def expr(self):
        left = self.term()
        while self.peek() in ('+', '-'):
            op = self.consume()
            right = self.term()
            left = ('+' if op == '+' else '-', left, right)
        return left
    
    def term(self):
        left = self.factor()
        while self.peek() in ('*', '/'):
            op = self.consume()
            right = self.factor()
            left = ('*' if op == '*' else '/', left, right)
        return left
    
    def factor(self):
        if self.peek() == '(':
            self.consume()
            expr = self.expr()
            self.consume(')')
            return expr
        else:
            return self.int()
    
    def int(self):
        return int(self.consume())
    
    def consume(self, expected=None):
        if expected and self.peek() != expected:
            raise ValueError(f"Expected {expected}, but got {self.peek()} at position {self.pos}")
        token = self.tokens[self.pos]
        self.pos += 1
        return token
    
    def peek(self):
        if self.pos >= len(self.tokens):
            return None
        return self.tokens[self.pos]

该语法分析器的主要逻辑在 `expr`、`term` 和 `factor` 函数中。每个函数都代表一个非终结符，它们会递归调用其他非终结符的函数来解析子表达式。

3. 测试

最后，我们可以使用一些测试用例来验证我们的语法分析器是否正确解析了源代码。下面是一些示例测试用例：

parser = Parser(['2', '+', '3', '*', '4'])
ast = parser.parse()
assert ast == ('+', 2, ('*', 3, 4))

parser = Parser(['(', '2', '+', '3', ')', '*', '4'])
ast = parser.parse()
assert ast == ('*', ('+', 2, 3), 4)

parser = Parser(['1', '+', '2', '+', '3', '+', '4'])
ast = parser.parse()
assert ast == ('+', ('+', ('+', 1, 2), 3), 4)

这些测试用例分别验证了加减乘除的优先级、括号的处理以及多个操作符连续出现的情况。如果我们的语法分析器能够正确解析这些表达式，那么我们可以认为它已经完成了任务。