编译复习:自底向上语法分析

Posted by Sz Zheng on 2019-04-01

编译复习:自底向上语法分析

本学期做编译助教,需要复习一下。LR文法分析之前的内容都跳过了,对于自底向上的语法分析内容需要详细复习一下,在此记录

  • 资料:龙书第2版4.5节, 4.6节

一、初步知识

  • 自底向上语法分析本质上是为输入串构造语法分析树的过程
  • LR文法类是最大的、可以构造相应的移入-归约语法分析器的文法类
  • 当今构造LR语法分析器可以借助自动生成工具
  • LR(k)文法中的L是自左向右扫描,R是用最右推导,k是指向前看k个字符,k=1时省略标出。

二、正文

1. 归约

  • 归约就是将串恢复成文法开始符号的过程,方法为将串中与某产生式体相匹配的子串替换为该生成式的头部。
  • 将归约过程反过来对应着一个最右推导。
  • 最右推导是每次替换掉最右边的非终结符号的推导过程。

2. 句柄

  • 句柄是进行一步最右推导后,生成的串中与刚刚使用的生成式体相匹配的那个子串。但要注意这不等价于串中左边与某生成式体匹配的字串。

例子: $T$ * $id_2$ 这个串的句柄是$id_2$而不是$T$,因为将$T$归约后得到$E$ * $id_2$将无法继续归约。事实上,正常的最右推导过程是$E \rightarrow T \rightarrow T * F \rightarrow T * id_2$, 正确的句柄是$id_2$,对应的生成式是$F \rightarrow id_2$。

  • 句柄是一个生成式,但为了简便,常用生成式体代替。
  • 无二义的文法,那么其每个最右句型都有唯一的句柄。
  • 归约的关键就在于找到句柄然后替换。

3. 移入-归约语法分析技术

采用四个动作:移入,归约,接受,报错

  • 用两个栈结构完成算法,过程中将w串的字符移入左侧栈,当达到可规约条件时,在左侧栈中完成规约,当右侧已空且左侧只剩下文法开始符号,则为接受,否则报错。
    栈1   栈2
    $__  _w$
  • 性质:句柄总是会出现在左侧栈的栈顶
  • 两种冲突:移入归约冲突和归约归约冲突。

4. 项和LR(0)自动机

  • 项: 生成式的右侧中含有一个点,如$A \rightarrow .XYZ$。
  • LR(0)自动机,每个状态代表规范LR(0)项集族的一个项集。

(1) 构造规范LR(0)项集族:

定义增广文法和两个函数:CLOSURE, GOTO

  • 增广文法: 为开始符号S增加$S’ \rightarrow S$。这个增加的生成式是用来确定何时采取接受动作的。
  • CLOSURE(I):最开始I的项都在其中,如果$A \rightarrow \alpha . B \beta$在其中且项$B \rightarrow .\gamma$不在其中,那么将其加入闭包。这样直到闭包不再变大为止。
  • 内核项:这些项定义了整个项集的结构,它们是那些点不在生成式体最左边的项,以及$S’ \rightarrow S$。
  • 非内核项:除了$S’ \rightarrow S$以外的所有点在生成式体最左边的项。
  • GOTO(I, X),对项集I遇到文法符号X时应到达的项集的闭包

(2) LR语法分析算法:

  • 有两个表:ACTION和GOTO

(3) SLR语法分析:

  • SLR语法分析是用LR(0)自动机进行的语法分析
  • 构造ACTION表和GOTO表:移入看GOTO函数,归约看FOLLOW集,有$S’ \rightarrow S.$时对符号$接受,这些构成ACTION表,对于GOTO表则是对应非终结符号的GOTO函数结果。

(4) 可行前缀:

最右推导的某个句型中不越过句柄的前缀。