Skip to content

Latest commit

 

History

History
249 lines (203 loc) · 14.8 KB

chapter4.md

File metadata and controls

249 lines (203 loc) · 14.8 KB

第四章 语法分析

[toc]

分析器的作用及错误处理

  • 接收词法分析器输出的记号串
  • 报告并尝试语法错误
    • 词法错误/语法错误/语义错误（算法作用于不相容的运算对象）/逻辑错误
    • 清楚准确报告错误，并从中恢复以诊断后文（抑制伪错误）
      • 紧急方式（恐慌模式）恢复（跳过部分错误，无死循环）
      • 短语层次恢复（需要避免死循环）
      • 出错产生式（常见错误）
      • 全局纠正（理论，开销大，作为评价标准）
  • 输出某种形式的分析树
  • 把记号信息收入符号表，类型检查，生成中间代码

上下文无关文法的分析和改造

  • 推导$\Rightarrow$
    • $\xRightarrow{Rule}$；$\xRightarrow{*}$；$\xRightarrow{+}$
    • 最左推导$\xRightarrow[lm]{}$；最右推导$\xRightarrow[rm]{}$（规范推导）
    • 每个语法树只有一个最右（左）推导。分析树构建过程对应一个推导过程，但分析树本身对应推导不唯一
  • 二义性
    • 某些情况下有便利性，但需要有消除的机制
  • 语法和语言等价的证明（两方向归纳）
  • 任何一个3型文法都是2型文法
  • 由NFA得到识别同样语言的2型文法

设计文法

  • 上下文无关文法适合描述循环和对称结构

去除二义性

  • 悬空二义性的处理（悬挂else）
  • 固有二义性语言：无论如何改写文法都无法消除二义性
  • 无关紧要的二义性（如结合律）

提取左公因子

  • 可能增大自上而下的回溯开销
  • 避免回溯
  • 引入新变量来提取左因子

消除左递归

  • 存在形如$A \Rightarrow A\alpha$的推导
  • 导致自顶向下的方法进入死循环
  • 可以用非左递归的产生式取代（引入中间变量）
  • 左递归的分类
    • 直接见诸产生式的左递归：把$A \rightarrow A\alpha | \beta$改写为$A \rightarrow \beta A^\prime,A^\prime \rightarrow \alpha A^\prime | \epsilon$
    • 一般的左递归（推导下的左递归）：用产生式替换出直接左递归，再消除

自顶向下的分析

基本概念

  • 一般策略：自上而下、从左到右的先根次序建立语法树的试探过程
  • 递归下降的语法分析
    • 每个过程联系到一个非终结符
    • 可能存在回溯（左递归）
    • 分析失败时难以得知错误的准确位置

构造无回溯自顶向下分析器的方法

  • 产生式右部由终结符开始，左部相同时右部首终结符
  • 不需要回溯的条件：任何非终结符能根据输入符号唯一确定执行任务
  • FIRST集（终结首符集合）：所有推导式中右部的终结首符。可能包括$\epsilon$
    • 任意两个FIRST集交集为空集时可以唯一指派
    • 终结符的FIRST只包含自身
    • 文法符号串的FIRST集计算方法类似
  • FOLLOW集（非终结符的后继符集合）：当非终结符是某个句型最右符号时，FOLLOW集包括$
    • 开始符的FOLLOW集包含输入结束符号$
    • 对产生式$A \rightarrow \alpha B$或$A \rightarrow \alpha B \beta$（$\epsilon \in FIRST(\beta)$），则$FOLLOW(A) \subset FOLLOW(B)$
    • $\epsilon$一定不属于FOLLOW集
  • 预测分析器的转换图
    • 消除左递归、提取左公因子
    • 对每个非终结符创建一个初始一个结束状态，对每个产生式创建一条路径，边的标号为终结符或词法单元（执行转换）或非终结符号（调用对应过程）
    • 可以进行消除尾递归的优化

LL(1)文法和非递归的预测分析

  • 定义：任意两个产生式$A\rightarrow \alpha | \beta$，满足$FIRST(\alpha) \cap FIRST(\beta) = \empty$，且$\alpha \rightarrow \epsilon$时$FIRST(\beta) \cap FOLLOW(A) = \empty$
  • 解释：从左向右扫描产生最左推导，每一步只向前看一个输入符号即确定语法分析动作
  • 性质：无二义性；不含左递归；无回溯
    • 不是所有文法都能变换为LL(1)文法
  • 非递归的预测分析：用状态栈取代递归调用
    • 包括输入缓冲、输出、预测分析表和状态栈（栈底为$）。状态栈中的内容通过不断展开增加，匹配输入流后出栈（栈顶符号匹配），每一刻的展开结果都应当与输入的剩余部分相匹配
  • 预测分析表M的构造
    • 对产生式$A \rightarrow \alpha$，对$FIRST{\alpha}$中的每个终结符$a$，把产生式加入$M[A,a]$。若$\epsilon \in FIRST(\alpha)$，则对$FOLLOW(A)$中的终结符$b$（包括$），把产生式加入$M[A,b]$
    • 对空的$M[A,a]$项，置为error（语法错误）
    • 适用于任何文法G
    • 对LL(1)文法，每个M条目至多有一个产生式
    • 左递归或二义性文法有至少一个多重定义的条件

自顶向下分析的错误恢复

  • 恐慌模式
    • 跳过一些输入符号，直到期望的同步记号出现
    • 效果依赖于同步记号集合选取
      • 将FOLLOW集中所有符号放入同步集合。跳过记号匹配到FOLLOW集元素时pop，继续分析
      • 把高层结构的开始符号加入底层结构的同步集合，如把语句开始关键字加入表达式非终结符的同步集合
      • 将FIRST集中所有符号放入同步集合（认为前面是冗余的）
      • 出错时把栈顶可以产生空串的非终结符视作产生空串弹出。导致延迟错误发现但不会遗漏，可减少恢复要考虑的非终结符
      • 直接弹出栈顶终结符
    • 短语级恢复
      • 可以修改、插入、删除输入符号，也可以弹出栈内符号，但不能替换或压入栈顶符号（保证恢复动作使剩余输入串缩短，避免无限循环）

自底向上的分析

  • 从叶结点逆序构建树
  • 对应于最右推导的逆过程（最右规约）
  • 移进-规约的语法分析，包括R分析和算符优先分析
  • 移进-归约分析的动作包括移进、规约、接受、出错
  • 可以处理左递归
  • 动作判断可使用栈中所有符号
  • 预测分析器模拟推导，自底向上分析描述规约过程，后者更复杂
  • 特定算法会影响分析程序检测错误位置的能力
  • 移进-规约冲突
    • 根据栈中所有内容和下一个输入符号不能决定移进和规约
    • 解决方法：移进优先原则解决一些二义性
  • 规约-规约冲突
    • 根据栈内所有内容和下一个输入符号无法确定用于规约的产生式
    • 解决方法：引入中间符号

句柄

  • 定义：若存在最右推导$S\Rightarrow \alpha A \omega \Rightarrow \alpha \beta \omega$，则$A\rightarrow \beta$是$\alpha \beta \omega$在$\alpha$后的句柄
  • 文法无二义性时句柄唯一，否则不一定唯一
  • 移进-规约分析器将终结符push入栈，直到能执行规约得到右句型；句柄对应产生式时下步归约中应用的产生式，且句柄最右位置与栈顶平齐
  • 句柄代表了最左边的由一个内部节点和后代组成的子树
  • 句柄右边的符号串只包括终结符
  • 活前缀（可行前缀）
    • 规范句型（右句型）中不含句柄后终结符的一个前缀
    • 已扫描部分若可规约成活前缀，则扫描部分没有错误

LR分析器

  • 从左向右扫描输入、构造最右推导的逆。LR(k)分析中k表示分析动作时向前看的符号个数，省略时默认为1。
  • 几乎所有可以表示为上下文无关文法的程序语言都可以被识别
  • 已知最一般的无回溯移进-规约方法
  • 最大可能地察觉语法错误，报告错误前不做任何无效规约
  • 项（item）对应一组分析的状态（位置+产生式）
  • LR(0)项目：产生式右部有n个项时，LR(0)项目有n+1个
  • 转移DFA构造
    • $A \rightarrow \beta . \gamma$表示$\beta$已在栈顶，下面输入符号可能获取$\gamma$
    • $A \rightarrow . \alpha$表示将用$A \rightarrow \alpha$识别A，称为初始项目
    • $A \rightarrow \alpha .$表示$\alpha$已在栈顶，且下一个规约使用此产生式时可能是句柄，称为完整项目
    • 首先构造增广文法（新的起始符号）
    • 需要增加CLOSURE函数和GOTO函数
    • 构造有限自动机时，对项目$A \rightarrow \alpha . X \eta$，若X为非终结符，则需要添加到每个以X为左部的产生式对应项目$X \rightarrow . \beta$的$\epsilon$转换
    • 初始文法时拓广文法开始符号的产生式
    • 可以没有接收状态，接受与否由编译器决定而非DFA
    • 子集构造法转换DFA的项目集规范族
    • 闭包计算：每次推移点，闭包=内核项（初始项目$S^\prime \rightarrow .S$和所有点不在左端的推移结果）+非内核项（后续非终结符点在最左展开项目）
    • 转换即为GOTO函数（对项目集和变元输出项目集）
    • 格局是栈的内容和剩余句子内容的二元组
    • 若将LR(0)的DFA每个状态都定为接收状态，则识别文法的活前缀（因为栈里的内容不能越过句柄）

LR文法

  • 定义：能构造出所有条目都唯一的LR分析表
  • 性质：当句柄出现在栈顶时，从左向右扫描的移进规约分析器能只通过栈顶信息进行识别
  • LR(k)文法：最多向前看k个文法符号就可以决定动作的LR分析器的文法
  • LL文法只要看右部推出的前k个符号，LR文法还看到了产生式右部推导出的所有东西（LR分析器构建过程中用到了所有产生式，雪崩时每一片雪花都在勇闯天涯）

LR分析算法

  • 规约分析表
    • 对所有终结符记录ACTION项，对所有非终结符记录GOTO项
    • ACTION项包括error和acc和si和ri，其中LR(0)分析若存在ri，则必定整行都是ri（因为缺少向前看的能力）
    • 对于完整项目进行规约
    • si时对stack和symbol压入栈，ri时对stack和symbol弹出栈产生式右部文法符号次数
  • 栈中存储的实际是文法符号和状态的二元组

LR(0)分析

  • LR(0)项目$A \rightarrow \beta_1 . \beta_2$对活前缀$\alpha \beta_1$有效，若存在推导序列$S \Rightarrow \alpha A \omega \Rightarrow \alpha \beta_1 \beta_2 \omega$
    • 这表明$\alpha \beta_1$在分析栈顶时，若$\beta_2 = \epsilon$则$A \rightarrow \beta$为句柄，是应选择的规约式；否则句柄未完全进栈，需要继续移进
    • 若活前缀的复数个有效项目对应了不同动作（相当于是有左公因子？），则需要向前看等方式解决冲突

SLR(1)分析

  • SLR(1)分析表
    • 针对需要考察FOLLOW集的冲突情况
    • 包含$[ S^\prime \rightarrow S. ]$的项目集读取$$$时转入acc
    • 包含$[ S^\prime \rightarrow .S ]$的项目集时初始状态
    • 若项目集$I_i$包含编号为$j$的$[ A \rightarrow \alpha. ]$，则对所有$FOLLOW(A)$中的$a$，置$ACTION(i,a)=rj$
    • 所有动作都无冲突时是SLR(1)文法
    • 无二义性是SLR(1)文法的必要非充分条件
    • 保证无规约-规约冲突：对$A \rightarrow \alpha .$和$B \rightarrow \gamma .$，$FOLLOW(A) \cap FOLLOW(B) = \empty$
    • 保证无移进-规约冲突：对终结符$X \in FOLLOW(B)$，任何状态不同时包含项目$A \rightarrow \alpha . X \beta$和$B \rightarrow \gamma .$
  • SLR(1)分析能力强于LR(0)，但仍有不足：活前缀的有效项目冲突（移进-规约冲突）
    • 有些规约存在发生条件，但SLR分析不足以记住这些条件

LR(1)规范分析

  • SLR(1)分析构造LR(0)项目的DFA时不考虑向前看的符号，构造完成后考虑；LR(1)在向前看符号的基础上进行DFA构造
  • LR(1)项目：$[ A \rightarrow \alpha . \beta, a ]$，其中终结符$a$可以是$$$
  • LR(1)的1即项目第二项（搜索符）的长度。在$\beta = \epsilon$时，表示只有下一个输入符号为搜索符时才能规约
  • LR(1)项目$A \rightarrow \alpha . \beta$对活前缀$\delta \alpha$有效，若存在推导序列$S \Rightarrow \delta A \omega \Rightarrow \delta \alpha \beta \omega$，其中$a$为$\omega$的首终结符（$\omega = \epsilon$时$a = $$）
  • 若对活前缀$\gamma$有效的项目集中包括项目$[A \rightarrow \alpha . B \beta, a]$，则对所有形如$B \rightarrow \eta$的产生式，$[B \rightarrow . \eta, b]$对$\gamma$也有效。其中$b = FIRST(\beta a)$
  • LR(1)分析表构造
    • 构造项目集规范族
    • 若$[ A \rightarrow \alpha . a \beta , b ] \in I_i$且$GOTO(I_i, a) = I_j$，则$ACTION(i, a) = sj$
    • 若$[ A \rightarrow \alpha . , a ] \in I_i$且$A \neq S$，则$ACTION(i, a) = r \alpha$
    • 若$[ S^\prime \rightarrow S . , $ ] \in I_i$，则$ACTION(i, $) = acc$
    • 若$GOTO(I_i, A) = I_j$，则$GOTO[i, A] = j$
    • 空白条目置error
    • 初始状态为包含$[ S^\prime \rightarrow .S , $ ]$的项目集

LALR(1)分析

  • lookahead-LR分析，为了减少状态数至SLR的水准，但保留部分特征
  • 构造同心的LR(1)项目集：第一个成分集合相同。具有相同核心的两个LR(1)项目DFA状态，必定对所有符号有相同的转换，且转换结果具有相同的核心
  • 构造方法一：先构建LR(1)分析表，再合并同心项。
    • 可能引入规约-规约冲突
    • 可以发现所有LR(1)发现的错误，但可能需要在报错前作虚假规约
  • 构造方法二：只使用内核项（$[ S^\prime \rightarrow .S]$和$[ S^\prime \rightarrow .S , $]$和所有点不在产生式右部左端的项）表示LR(0)或LR(1)项目集
    • 用$#$代替向前看符号，判断传播/自发。
    • 搜索符自发生成：对$[A \rightarrow \alpha . \beta , #]$的闭集$I$，若存在$[B \rightarrow \gamma . X \delta , a]$，则$GOTO(I,X)$中的项$B \rightarrow \gamma X . \delta$的向前看符号$a$是自发生成的
    • 搜索符传播生成：对$[A \rightarrow \alpha . \beta , #]$的闭集$I$，若存在$[B \rightarrow \gamma . X \delta , #]$，则$GOTO(I,X)$中的项$B \rightarrow \gamma X . \delta$的向前看符号$#$是传播生成的
    • 闭包构建初只包含自发生成的向前看符号，然后通过若干趟扫描获得传播生成的
    • 复杂度为$n^2$

二义文法应用

  • 二义性文法在一些情况下更简单
  • LR分析中消除二义性的规则
    • 优先级和结合规则分析动作冲突
      • 如明确规定左结合、优先级
    • 移进优先于规约的规则解决最长匹配问题
      • 如悬挂else
    • 按特殊情况产生式规约，解决特殊情况产生式二义性导致的规约-规约冲突

自底向上分析的错误处理

  • LR分析中访问转移表不会发现错误，检测到分析表中的空白项会报错
  • LR分析的紧急方式
    • 抛弃若干个输入符号，弹出栈顶若干个状态，直至找到能合法跟随当前非终结符的符号，再把GOTO状态压栈，恢复正常分析
    • 短语级回复：考察LR分析表的每个出错条目，并根据语言使用情况决定可能错误原因，编一个适当的错误恢复例程

语法分析器生成工具

  • Yacc：LALR(1)分析程序的生成器
  • 默认选择第一个规约式解决规约-规约冲突，移进优先解决移进-规约冲突
  • 优先级越下越优先
  • 错误纠正：错误产生式$A \rightarrow error \alpha$