编译原理陈火旺版第五章习题

### 编译原理陈火旺第五章习题解析

#### 5.1 关于文法和语言的定义
在编译原理中，文法用于描述编程语言的语法结构。对于给定的语言L，其对应的上下文无关文法G由四元组(V_N, V_T, P, S)组成，其中V_N是非终结符集合，V_T是终结符集合，P是一系列产生式规则，S是起始符号[^3]。

#### 5.2 文法类型的分类及其特点
根据乔姆斯基体系，可以将形式文法分为四种类型：0型（无限制）、1型（上下文有关）、2型（上下文无关）以及3型（正则）。每种类型的表达能力依次减弱，但识别效率逐渐提高。例如，正则文法能够被有限状态自动机接受，而上下文无关文法则对应着下推自动机[^3]。

#### 5.3 自顶向下分析方法概述
自顶向下的句法分析是从根节点出发逐步构建子树的过程，主要技术包括预测分析表驱动方式、递归下降分析器等。为了确保算法的有效执行，通常要求输入文法满足LL(k)条件，即通过查看k个向前看记号就能唯一确定当前应使用的产生式[^3]。

#### 5.4 LL(1)文法判定准则
判断一个给定的上下文无关文法是否属于LL(1)，需验证它不存在左递归现象，并且任意两个不同候选串之间不会发生FIRST集交叠；当存在公共前缀时，则要检查FOLLOW集中是否有冲突情况出现[^3]。

def is_LL1(grammar):
    """简单模拟LL(1)文法检测逻辑"""
    has_left_recursion = check_for_left_recursion(grammar)
    first_set_conflicts = find_first_set_conflicts(grammar)
    follow_set_conflicts = find_follow_set_conflicts(grammar)

    return not(has_left_recursion or first_set_conflicts or follow_set_conflicts)