【第四章】语法分析

松鼠的窝 2017-11-30

第四章.语法分析

词法分析器的作用

词法分析器从语法分析器获得一个由词法单元组成的串,并验证串可以由源语言的文法生成,构造一棵语法分析树。

常见的方法可以分为自顶向下和自底向上方法。语法分析器的输入都是按照从左向右扫描的。

语法错误的处理

语法错误的处理有2中策略:

  • 恐慌模式
  • 短语层次恢复

程序中可能出现不同层次的错误

  • 词法错误:标识符、关键字、运算符拼写错误
  • 语法错误:{ },( )等的缺失
  • 语义错误:运算符和运算分量不匹配。void类型函数reture了个值
  • 逻辑错误:应该用==的时候,用成了=

语法分析器中错误处理程序的目标:

  • 发现并报告错误
  • 能从错误中恢复,继续后面的检查
  • 尽可能少的增加正确程序的开销

错误恢复-恐慌恢复模式

发现错误丢弃输入中的符号,直到找到同步词法单元(synchronizing token)。同步词法单元通常是界限符号,如 } ;

短词层次恢复

对于某错误,在余下的输入中进行局部校正,可能是将余下的某个前缀替换成另一个串,使语法分析器可以继续分析。如将逗号替换成分号,添加分号。

错误产生式

通过预测常见的错误,在文法添加中添加一个特殊的产生式,来处理错误结构。

上下文无关文法

上下文无关文法包含终结符,非终结符,一个开始符号和一组产生式组成。

  • 终结符号是组成串的基本符合,俗称"词法单元",如if,else
  • 非终结符号表示串集合,用于定义由文法生成的语言。
  • 某个非终结符被指为开始符号,这个符号表示的串集合就是这个文法生成的语言
  • 产生式描述了将终结符号和非终结符号组成串的方法。

通过推导构建语法分析树。

二义性:如果一个文法可以为某个句子生成多棵语法分析树,那么就有二义性。
加减乘除优先级就是用来实现消二义性规则的。

  • 文法是比正则表达式表达能力更强的表示方法。每个可以用正则表达式描述的构造,都可以使用文法描述,反之不成立。

设计文法

为什么使用正则表达式来定义一个语言的词法语法?

理由:

  • 将一个语言的语法结构分为词法和非词法,可以方便编译器前端模块化
  • 和文法相比,正则表达式更简洁更便于理解 表示词法单元的方法。
  • 正则表达式构造的词法分析器效率高于任意文法构造的分线器

设计文法需要消除二义性。如if else,在then和else之前添加语句,必须是"已匹配的"。

提取左公因子

提取左公因子是一种文法转换方法。通过改写产生式来退后这个决定,当输入足够多的时候,做出选择。

自顶向下的语法分析

本质上是为输入串构造语法分析树。从根节点按先序创建各个节点,可以看做寻找输入串的最左推导的过程。

对于有些文法,构造一个向前看k个字符的预测分析器,这类文法被称为LL(K)文法类,根据FIRST和FOLLOW集合,构造预测分析表

FIRST和FOLLOW

FIRST和FOLLOW是文法G相关的2个函数,可以根据下一个输入符号来选择应用哪个产生式。

  • first(a)定义为可从a推导得到的串的首符号的集合,a为任意的文法符号串。
  • FOLLOW(A)被定义为可能再某些句型中紧跟在A右边的终结符号的集合。

LL(1)文法

LL(1)文法,通过构造出预测分析器,既不需要回溯的递归下降语法分析器。

第一个L表示从左向右扫描输入,第二个L表示产生最左推导,1表示每次扫描一个字符

非递归的预测分析

构造一个非递归的预测分析器,显示的维护一个栈结构;递归是隐式的维护栈,这样的语法分析器可以模拟最左推导的过程。

自底向上的语法分析

从叶子节点向上到达根节点,通常方法使用移入-归约

LR文法类是最大的,可以构造出相应的移入-归约语法分析器的文法类。但是手工构造LR语法分析器的工作量特别大。

归约(reduction)

自底向上语法分析的过程看成将一个串w"归约"为文法开始符号的过程。

在归约过程中,一个与某产生式体匹配的特定子串被替换成该产生式的非终结符号。

归约就是推导步骤的反向操作。推导步骤是将句型中非终结符号替换成该符号的产生式的体。

移入-归约

使用一个栈来保存文法符号,用一个输入缓冲区存放将要进行语法分析的其它符号。

冲突问题:即使知道了栈中所有的内容,和接下来k个输入符号,仍然无法判断是应该移入还是归约操作,活着有多个归约的可能,无法正确选择。(如if if than else)

LR(k)语法分析技术

L表示从左向右扫描,R表示反向构造一个最右推导序列,k表示语法分析的时候向前看k个输入符号。

LR语法分析器是表格驱动的。

LR语法分析器包含:一个输入,一个输出,一个栈,一个语法分析表。

语法分析表包含:分析动作函数ACTION,和转换GOTO函数。

分析算法

输入:一个串w,一个LR语法分析表,这个表描述了文法G的ACTION函数和GOTO函数。

输出:如果w在L(G)中,输出w自底向上的语法分析过程中的归约步骤;否则error

方法:栈中的内容总是一个可行前缀,LR分析器首先构造各个可行前缀的有效项的项集(称为LR状态),有效项集合引导语法分析器做出移入-归约决定。

关键字

  • SLR:简单LR分析器。

  • 规范LR分析器,增加了一个向前看的符号集,可以避免SLR中出现的分析动作的冲突,状态会比同一文法的SLR状态更多。

  • LALR:向前看的LR分析器。

  • 二义性文法:使用二义性文法,添加附加信息,如算数符号的优先级,解决移入和归约的冲突。

相关推荐