编译原理前端基础知识
自动机
文法
形式定义
对于一个文法
为终结符的集合 为非终结符的集合 为定义在 和 上的产生式的集合,有 为开始符号,对于自上而下分析法, 是解析的起点,对于自下而上分析,它是归约的终点
句型与句子
对于文法中的一个产生式
我们可以简记推导关系为
,若 可以通过0步或多步推导出 ,若 可以通过1步或多步推导出 ,若 可以通过 步推导出
对于一个文法
那么称
若对于一种程序语言
乔姆斯基谱系
当我们向文法中的产生式上施加限制,文法的表达能力将会下降,但解析将会更加容易。根据限制的不同,将文法大致分为以下几类:
0型文法:不对产生式施加任何限制
1型文法:上下文有关文法,需满足
注意该文法允许产生式的左侧附带上下文信息。例如保证某个非终结符只有跟在某个终结符后时才能被翻译
2型文法:上下文无关文法(表示大部分语言的语法规则,即单词之间如何连接)
上下文无关文法要求产生式的左侧只有一个非终结符。
3型文法:正则文法(表示大部分语言的词法规则,即字符如何构成单词)
或者
FIRST与FOLLOW
对于一个上下文无关文法
形式定义
FIRST集:
特别的,当
FOLLOW集:
自上而下分析
基本原理
例如文法(这里用_来代笔
1 |
|
自上而下分析即以文法符号为根结点构建分析树,自根结点往下进行,使最终叶子结点对应的字符串符号连接起来恰好是输入字符串。
假设有输入流abbb,那么有最左推导(总是替换产生式最左边的文法符号)
1 |
|
当输入流中的符号被耗尽时,解析完成,这暗示我们的算法最好能稳定的消耗输入流中的符号。
左递归消除
在一些坏情况下,我们可能会遇到下面的文法:
1 |
|
这时我们的分析程序可能会重复运用第一条产生式,产生死循环。这种情况称为左递归,因此为了分析算法可以停机,我们需要进行左递归消除。
左递归消除的基本思想是将产生左递归的文法符号替换为一个必然会消耗输入的文法符号,在本例中,E
可能以ident
开头,因此可以将其替换为
1 |
|
在一些更复杂的情况下,例如:
1 |
|
可以看到A -> AR
中右侧的A
产生了左递归,可以看到A
只以ident
开始,而且后面跟着的都是R
,对其进行推导,我们将会得到形如
1 |
|
因此我们可以将原式替换为
1 |
|