编译原理 4

第四章: 语法分析

语法分析器

• 基本作用
  • 从词法分析器获得词法单元序列, 判断能否由该语言的文法生成
  • 错误, 则报错
  • 正确, 则生成语法树
• 分类
  • 自顶向下分析器: 根部开始构造(LL文法)
  • 自底向上分析器: 从叶开始构造(LR文法)
  • 总是从左到右扫描, 只处理特定类型的文法

上下文无关文法

• 终结符号: 组成串的基本符号
• 非终结符号: 表示串集合的语法变量
• 开始符号: 某个被指定的非终结符号(其对应的集合, 就是文法的语言)
• 产生式: 描述终结符号和非终结符号组成串的方法
  • 形式: 头部(左部)->体部(右部)
  • 头部是非终结符, 体部是符号串
• 元符号: 文法描述用的符号

推导

• 将待处理的串中的某个非终结符号替换为这个符号某个产生式的体
• 不断替换, 就能得到文法的不同句型
• 正则定义
  • 如果$A\to\gamma$是一个产生式, 那么$\alpha A\beta\Rightarrow \alpha\gamma\beta$
  • 最左(右)推导: $\alpha(\beta)$中不包含非终结符号
    • 含有多个非终结符, 始终坚持替换最左侧的非终结符
    • $\xRightarrow[lm]{}$ $\xRightarrow[rm]{}$
  • 零步或多步: $\xRightarrow{*}$
  • 一步或多步: $\xRightarrow{+}$, 等价于$\alpha\xRightarrow{*}\beta\wedge \alpha\ne\beta$

句型句子语言

• 句型: $S\xRightarrow{*}\alpha$, $S$为开始符号
• 句子: 不包含非终结符号的句型
• 语言: 文法$G$的语言, 是$G$句子的集合, $L(G)$. $w\in G\Leftrightarrow S\xRightarrow{*}w$

语法分析树

• 根结点的标号是文法的开始符号
• 叶子结点的标号是非终结符号, 终结符号或空字符
• 内部结点的标号是非终结符号
• 每个内部结点代表了某个产生式的一次应用
  • 结点标号为产生式头, 其子节点从左到右为产生式的体
• 叶子的序列是一个句型
• 一个语法分析树, 可对应多个推导序列
  • 但只有唯一的最左推导和最右推导

二义性

• 一个文法可以为某个句子生成多课语法分析树, 则这个文法就是二义的

上下文无关文法与正则表达式

• 上下文无关文法更强
• 正则表达式不足以表达
  • 直观例子: 有穷自动机不能计数
• 上下文无关文法能表达任意正则语言
  • 对于NFA, 构造上下上下文无关文法
  • 状态$i$, 构造非终结符$A_i$
  • 输入$a$的转换, 则$A_i\yo aA_j$
  • 空输入转换, 则$A_i\to A_j$
  • 接受状态, 则$A_i\to\epsilon$
  • 开始状态, 为开始符号

文法及其生成的语言

• 证明$G$生成的每个串都在$L$中
• 证明$L$中每个串都能被$G$生成

设计文法

• 消除二义性
• 消除左递归: $A\xRightarrow{+}A\alpha$
  • 左递归的定义: 存在非终结符号$A\xRightarrow{+}A\alpha$, 则它是左递归的
  • 立即左递归: 存在形如$A\to A\alpha$的规则
  • 自顶向下: 不能处理左递归
• 消除立即左递归
  • $$A\to A\alpha|\beta \equiv \begin{cases}
    A&\to\beta A’\\
    A’&\to\alpha A’|\epsilon\\
    \end{cases}$$
• 消除多步左递归
  • 算法: 消除所有左递归
  • 所有非终结符排序
  • 对每一个原有的$A_i\to A_j\gamma, j < i$的产生式, 换成一系列$A_i\to \sigma_k\gamma$, 其中$\sigma_k$来自$A_j\to \sigma_k$的产生式
  • 完成对一个$A_i$的转化后, 消除其立即左递归
• 预测分析法: 试图从开始符号推导出输入符号串
  • 两个产生式有相同前缀时, 无法预测
  • 消除相同前缀: 提取左公因子

语法分析技术

自顶向下

• 从分析树根节点开始, 按照先根次序, 深度优先, 创建节点
• 对应于最左推导
• 步骤
  • 确定最左边的非终结符应当应用那个产生式
  • 用产生式去匹配
  • 关键: 选择合适的 产生式
• 递归下降
  • 搜索回溯
    • 回溯: 遇到错误, 退回之前的扫描结果
    • 错误: 可能是输入的不是句子, 也可能选错产生式
    • 改进选择产生式: 做记录, 一个产生式选一次, 都不行, 则输入不是句子
  • 问题
    • 回溯需要来回扫描, 甚至撤销已完成的语义动作
    • 有可能明明是句子, 却不能被回溯出来
  • 预测分析法
    • 向前看几个符号, 确定产生式(通常只看1个), 若可能的产生式仅有一个, 则避免回溯. 对于句型$xA\beta$和输入$xa…$, 选择$A\to\alpha$可能性有:
      • $\alpha\xRightarrow{*}a$
      • $\alpha\xRightarrow{}\epsilon$, 且$\beta\xRightarrow{}a$
    • FIRST和FOLLOW
      • FIRST
        • $\mathrm{FIRST}(\alpha)$: 可以从$a$推导得到串的首符号的集合
        • 例: $A\to \alpha | \beta$, 且$\mathrm{FIRST}(\alpha)$与$\mathrm{FIRST}(\beta)$不相交, 输入属于哪个, 就选哪个产生式
        • 计算
          • $\mathrm{FIRST}(X_1X_2\cdots X_n)$
            • 加入$X_1$中所有非$\epsilon$符号
            • 若$\epsilon$在$\mathrm{FIRST}(X_1)$中, 则加入$\mathrm{FIRST}(X_2)$中所有非$\epsilon$符号, 对每一个都是其前面的都含有$\epsilon$
            • $X_i$都含有$\epsilon$, 也加入$\epsilon$
      • FOLLOW
        • $\mathrm{FOLLOW}(A)$: 可能在某些句型中紧跟在$A$右边的终结符号的集合
        • 计算
          • 右端结束标记$$$加入$\mathrm{FOLLOW}(S)$
          • 按照以下两个规则迭代, 直到不再增长
            • 存在产生式$A\to\alpha B\beta$, 那么$\mathrm{FIRST}(\beta)$中的所有非$\epsilon$符号加入$\mathrm{FOLLOW}(B)$
            • 存在产生式$A\to\alpha B$, 或者$A\to\alpha B\beta$且$\mathrm{FIRST}(\beta)$中包含$\epsilon$, 那么$\mathrm{FOLLOW}(A)$中的所有符号加入$\mathrm{FOLLOW}(B)$

LL(1)文法

• 对于文法的任意两个产生式$A\to\alpha|\beta$
  • 不存在终结符$a$, 使得$\alpha$和$\beta$都推导出以$a$开头的串
  • $\alpha$和$\beta$至多一个可推出空串
  • 如果$\beta$可推导出空串, 那么$\alpha$不能推导出以$\mathrm{FOLLOW}(A)$中任何终结符号开头的串
• 等价于
  • $\mathrm{FIRST}(\alpha)\cap\mathrm{FIRST}(\beta) =\emptyset$
  • 若$\epsilon\in\mathrm{FIRST}(\beta)$, 那么$\mathrm{FIRST}(\alpha)\cap\mathrm{FOLLOW}(A)=\emptyset$, 反之亦然
• 预测分析表构造算法
  • 输入: 文法G
  • 输出: 预测分析表M
  • 方法:
    • 对于文法$G$的每个产生式$A\to \alpha$
      • 对于$\mathrm{FIRST}(\alpha)$中的每个终结符号$a$, 将$A\to \alpha$加入到$M[A,a]$
      • 如果$\epsilon\in\mathrm{FIRST}(\alpha)$, 那么对于$\mathrm{FOLLOW}(A)$中的每个符号$b$, 将$A\to \alpha$加入到$M[A,b]$
    • 剩下的空白条目填写error
  • 一格内仅有一个产生式, 否则二义性
• LL(1)文法的递归下降分析
  • 构造预测分析表后, 可以用当前的输入符号选择唯一的产生式
• 非递归的预测分析
  • 总是匹配掉句型左边的所有终结符号
  • 接下来的动作均发生于左边, 用栈完成
  • 处理过程
    • 初始化时, 栈中仅有开始符号$S$(和$)
    • 若栈顶是终结符号, 那么进行匹配
    • 若是非终结符号, 用分析表选择产生式, 并用它的右部替换栈顶的左部(选不出来, 报错)
  • 算法
    • 输入: 串w, 预测分析表M
    • 输出: w是句子, 则输出最左推导, 否则报错
    • 初始化: 栈中S$, 输入缓冲区w$, ip指向w第一个符号
    • 令X=栈顶符号, ip指向输入符号a
      • if(X==a), X出栈, ip移动—>匹配到终结符号
      • else if(X是终结符号) error—>失配
      • else if(M[X,a]是报错条目) error—>没有产生式
      • else if(M[X,a]=$X\to Y_1Y_2\cdots Y_k$)
        • 输出产生式$X\to Y_1Y_2\cdots Y_k$
        • 弹出栈顶符号$X$, 并将$Y_1Y_2\cdots Y_k$放入(左边的在顶部)
    • 不断执行, 直到栈空或报错

自底向上

• 为一个输入串构造语法分析树的过程
  • 从叶子开始向上到达根节点
  • 移入-归约 框架
  • 简单LR技术(SLR), LR技术(LR)
• 归约: 右部换成左部(何时归约, 归约成什么符号串)
• 句柄
  • 对输入从左到右扫描, 自底向上分析, 可反向构造出最右推导
  • 句柄：最右句型中和某个产生式体相匹配的字串, 对他的归约代表了该最右句型的最右推导的最后一步
  • 句柄右边只有终结符号
  • 如果文法是无二义的, 每个句型有且仅有一个句柄
  • 正则定义: $S\xRightarrow[rm]{*}\alpha A w\xRightarrow[rm] \alpha\beta w$, 那么紧跟在$\alpha$后的$\beta$是$A\to \beta$的一个句柄
• 移入-归约
  • 使用一个栈: 栈中符号描述了一个最右句型
  • 开始: 栈中只有$, 输入为w$
  • 结束时刻: 栈中S$, 输入为$
  • 不断移入符号, 识别到句柄就归约
  • 分析动作
    • 移入: 将下一个输入符号移到栈顶
    • 归约: 将句柄归约为对应的非终结符
      • 句柄总在栈顶
      • 具体操作时, 弹出句柄, 压入被归约到的非终结符号
    • 接受: 宣布分析成功完成
    • 报错: 发现语法错误, 调用错误恢复子程序
  • 冲突
    • 移入-归约冲突: 不知道是否应该继续移入, 因为移不移都能归约
    • 归约-归约冲突: 多个产生式, 右部相同
• LR(k)分析: 向前看k个, k一般不超过1
  • 优点
    • 表格驱动, 通用方法, 无回溯移入-归约分析, 能分析的文法多
  • LR(0)项
    • 文法的产生式, 在右部加一个点, 每个空位都可能加
    • 点: 代表阶段性成果: 其前部已经被扫描, 后部是期望扫描到的东西
  • LR(0)项集规范族的构造
    • 增广文法: 原文法加新开始符号S’, 并添加产生式$S’\to S$
    • 项集闭包: CLOSURE(I): 根据以下规则构造, I为文法G的一个顶集
      • I中各项加入CLOSURE(I)
      • 如果$A\to\alpha \cdot B\beta$在CLOSURE(I), 而$B\to\cdot\gamma$不在, 则加入其中, 并不断迭代
    • GOTO函数:
      • GOTO(I,X): I中所有形如$[A\to \alpha\cdot X\beta]$对应的项$[A\to \alpha X\cdot\beta]$的集合的闭包
    • 求规范族
      • 从初始项集开始, 不断计算各种可能的后继, 直到生成所有可能的项集
      • 对C中每个项集I, 对每个文法符号X, 如果GOTO(I,X)非空且不在C中, 将GOTO(I,X)加入C
      • 直到某一轮没有新的项集被加入
  • LR(0)自动机的构造
    • 构造方法
      • 根据项集族构造
      • 每个项集族的顶集对应于自动机的一个状态
      • 状态转换: GOTO(I,X)=J, 则从I到J有标号X的转换
      • 开始状态为CLOSURE({$S’\to \cdot S$})
    • 作用
      • 假设输入$\gamma$使自动机从开始状态运行到状态j
      • 如果j中存在项$A\to\alpha\cdot$
        • $\gamma$后添加一些终结符可以得到一个最右句型
        • $\alpha$是$\gamma$的后缀, 且是句型的句柄
        • 表示可能找到了当前最右句型的句柄, 可以归约
      • 如果j中存在项$B\to \alpha\cdot X\beta$, 那么
        • 在$\gamma$后添加$X\beta$和一些终结符号, 可得到一个最右句型
        • 该句型中$\alpha X \beta$是句柄, 但还没找到, 应当移入
      • 如果能给出明确的移入-归约建议, 则可以用来分析句型
        • 已得到的文法符号序列对应于自动机的一条路径
  • LR语法分析器的结构
    • 输入, 栈, 分析程序, 输出
    • 栈中存放状态序列, 可求出符号序列
    • 分析表确定动作: ACTION和GOTO
    • LR分析表的结构
      • ACTION: 参数: 状态i, 终结符号a
        • 移入j: j是新状态, 将j压入栈, 同时移入a
        • 归约$A\to \beta$: 栈顶的$\beta$归约成A, 因此根据GOTO表项压入新状态
        • 接受
        • 报错
      • GOTO: 如果GOTO($I_i$,A) = $I_j$(函数), 则GOTO[$i$,A] = $j$(表项)
  • 语法分析器的格局
    • 栈中内容和余下输入
    • 每一个状态都对应一个文法符号(进入该状态的边的标号), 除了$s_0$
    • 动作与格局
      • 移入: 输入拿掉一个, 栈增加一个
      • 归约: 输入不变, 栈拿掉r个(右部长度), 加上1个(左部)
      • 接受
      • 报错
    • ACTION表
      • s5: 表示移入, 并压入状态5
      • r8: 表示用8号产生式归约
    • GOTO表: 3表示弹出之后的栈顶, 根据归约产生式左部 , 应当压入状态3
• SLR语法分析表
  • 构造
    • 以自动机为基础, 构造规范族
    • 状态$i$对应项集$I_i$, 相关的ACTION和GOTO如下
      • $[A\to\alpha\cdot a\beta]$在$I_i$中, 且GOTO($I_i$,a) = $I_j$, 则ACTION[i,a]=移入j
      • $[A\to\alpha\cdot]$在$I_i$中, 那么对FOLLOW(S)中的所有a, ACTION[$I_i$, a]
      • =按$A\to\alpha$归约
      • 如果$[S’\to S\cdot]$在$I_i$中, 那么将ACTION[$I_i$,$]设为接受
      • 如果GOTO($I_i$, A)=$I_j$, 那么在GOTO表中, GOTO[i,A]=j
      • 空白的是error
    • SLR表无冲突, 则该文法是SLR的
  • 弱点
    • 项集包含$[A\to\alpha\cdot]$, 按照$A\to \alpha$归约的条件是, 下一个输入符号$a$在某个句型中可以跟在$A$后
    • 假设此时栈中的符号串为$\beta\alpha$, 如果$\beta Aa$不是任何最右句型的前缀, 那么即使a满足FOLLOW这个条件, 依然不应当按照$A\to\alpha$归约
  • 改进
    • $[A\to\alpha\cdot]$在顶集中的条件是, $[A\to \cdot\alpha]$出现在某个顶集中, 而这个的条件是, $B\to\beta\cdot A\gamma$出现在项中
    • 据此, 按此归约, 需要下一个输入符号是$\gamma$的第一个符号, 但LR(0)项集中不能确定这个信息
  • 更强大的分析器
    • 规范LR方法: LR(1)顶集, 把期望的向前看符号也加入项, 状态很多
    • 向前看LR方法: LALR方法, 基于LR(0)项集族, 但每个项都带有向前看符号, 强于SLR, 但表一样大

LR(1)

• LR(1)项
  • $[A\to \alpha\cdot\beta, a]$: 向前看符号为$a$
  • 按照该产生式归约, 则下一个输入必须是$a$, 同一产生式可以配上不同的向前看符号, 有更多状态
  • $\beta$非空, 则移入动作不考虑$a$
• 构造项
  • 增广文法
    • $[S’\to S, $]$
    • $[A\to \alpha\cdot B\beta, a]$对于可行前缀$\gamma$有效, 那么$[B\to\cdot\theta, b]$有效的条件$b$是什么
    • $S\xRightarrow[rm]{}\delta Aw\xRightarrow[rm]{}\delta\alpha B \beta w\xRightarrow[rm]{}\delta\alpha B x w\xRightarrow[rm]{}\delta\alpha \theta x w$
    • $b$应当是FIRST(xw), 或$xw$为空时, $b=$$
    • 若$[A\to \alpha\cdot X\beta, a]$对于可行前缀$\gamma$有效, $[A\to \alpha X\cdot \beta, a]$对$\gamma X$有效
  • 项集
    • CLOSURE中, $[A\to \alpha\cdot B\beta, a]$生成$[B\to\cdot\theta, b]$时, $b$必须在FIRST($\beta a$)
    • 总有$a$在FOLLOW($A$)中
• 构造分析表
  • 做修改: 按照产生式归约的条件, 从FOLLOW(A)改为: 项集的向前看符号a, ACTION[i,a]=按照….归约

LALR语法分析表

• LR(1)语法分析表的合并
  • 寻找相同核心(不考虑向前看符号)的LR(1)项集(项的第一分量相同, 向前看符号可能不同), 合并为1个项集
  • GOTO(I,X)也可合并, 因GOTO(I,X)的核心只由I的核心决定
• 合并引起的冲突
  • 不会导致移入归约冲突, 若原来无冲突
    • 若有, 则合并前, 这两个项也冲突, 于是原来的LR(1)已经存在冲突
  • 归约归约冲突
• 分析表构造算法
  • 先构造LR(1)项集规范族
  • 对于每个核心, 找出有该核心的项集, 用并集代替他们
  • 按照LR分析表的方法得到ACTION, 注意检查冲突
  • GOTO表, 原目标是项集, 替换为该项集在新的项集规范族中对应的项集(即替换为并集)
• 比较
  • 处理正确的输入, LALR与LR的动作相同
  • 错误的输入, LALR可能进行额外的归约, 但不会额外移入
  • LALR与SLR状态相同, 拥有LR(1)的向前看符号

语法错误的处理

• 错误处理的目标: 报错, 指出位置, 错误恢复
• 错误恢复
  • 出错后继续进行处理
  • 可能恢复的不成功
  • 可用信息: 栈中的符号, 待分析的符号
  • 恢复方法
    • 恐慌模式(跳过当前结构, 通用)
      • 忽略输入中的一些符号, 直到出现由设计者选定的某个同步词法单元
      • 同步词法单元
        • 将FOLLOW(A)中的所有符号放入A的同步集合中
        • 高层次开始符号集合, 加入低层次同步集合
        • 多了: FIRST(A)加入A的同步集合
        • 漏了: 栈顶终结符错误, 可直接弹出该符号, 并发出消息称, 已经插入了该符号
    • 短语层次的恢复(专用)
  • LR语法分析中的错误恢复
    • 报错: 栈顶符号串$\alpha$, 输入$a$, 不存在终结符号$x$, 使得$\alpha a x$是最右句型
    • 恢复(恐慌恢复)
      • 栈顶向下扫描, 找到状态s, s有一对应于终结符号A的GOTO目标(s之上的状态被丢弃)
      • 输入中丢弃一些符号, 直到一个可以跟在A后的符号b(不丢弃b), 并将GOTO(s,A)压栈, 继续分析
      • 总结: 设法(扔掉一些状态和输入)扫描完带错的A字串, 假装找到了A的实例
      • 短语恢复: 不详细讲

二义性文法的使用

• 对于某些二义性文法, 可通过消除二义性规则, 保证每个句子只有一颗语法树

优先级/结合性消除冲突

• 优先级: 不同时判断顺序(高低)
• 结合性: 相同优先级, 判断顺序(左右)

语法分析器生成工具