编译原理自顶向下语法分析

### 编译原理中的自顶向下语法分析方法

#### 自顶向下解析的概念
自顶向下解析是一种基于预测的解析策略，通常用于处理LL(k)文法。这种解析方式从起始符号出发逐步匹配输入字符串，直到整个输入被成功识别或遇到错误为止[^1]。

#### LL(1) 文法的特点
为了使自顶向下解析有效工作，所使用的文法应当满足某些条件，特别是对于LL(1)文法而言，它要求任何两个不同生产规则左侧相同的非终结符对应的右侧首符号集之间无交集，并且不存在左递归现象。此外，在实际编程环境中可能需要用特定字符代替特殊符号（如用`$`表示空串），以便更好地适应开发工具的要求[^3]。

#### Python 中实现简单的 LL(1) 解析器示例
下面是一个简化版的Python代码片段来展示如何构建一个基本的LL(1)解析器：

class Parser:
    def __init__(self, tokens):
        self.tokens = iter(tokens)
        self.current_token = None
        next(self)

    def parse(self):
        try:
            self.program()
            if self.current_token is not None:
                raise Exception('Unexpected token at end of input')
        except StopIteration:
            pass
    
    def program(self):
        while self.current_token != 'EOF':
            self.statement()

    def statement(self):
        if self.current_token == "if":
            self.match("if")
            self.expression()
            self.match("then")
            self.statement()
            if self.current_token == "else":
                self.match("else")
                self.statement()
        elif self.current_token.isdigit():
            self.match(self.current_token)
        else:
            raise Exception(f'Invalid syntax near {self.current_token}')

    def expression(self):
        self.term()
        while self.current_token in ('+', '-'):
            op = self.current_token
            self.match(op)
            self.term()

    def term(self):
        self.factor()
        while self.current_token in ('*', '/'):
            op = self.current_token
            self.match(op)
            self.factor()

    def factor(self):
        if self.current_token.lstrip('-').isdigit():  # Handle negative numbers as well
            value = int(self.current_token)
            self.match(str(value))
        elif self.current_token == '(':
            self.match('(')
            self.expression()
            self.match(')')
        else:
            raise Exception(f'Expected number or (expr), found {self.current_token}')
    
    def match(self, expected):
        if str(self.current_token).strip() == str(expected).strip():
            next(self)
        else:
            raise Exception(f'Mismatched token: Expected "{expected}", but got "{self.current_token}"')

def next(parser_instance):
    parser_instance.current_token = next(parser_instance.tokens, 'EOF')


# Example usage with a list of string tokens representing the source code.
tokens_example = ["if", "(", "-", "42", "<", "0", ")", "then", "print", "(", '"', "negative", '"', ")"]
parser = Parser(iter(tokens_example))
parser.parse()

这段代码定义了一个名为 `Parser` 的类，该类实现了对简单表达式的解析逻辑。通过调用不同的函数模拟了语法规则的应用过程，从而完成了对给定标记序列的有效性验证以及相应的结构化解释[^2]。