编译原理1

基本概念

• 字母表Σ是一个有穷符号集合

• 字母表上的运算（乘积、n次幂、正闭包、克林闭包、串）

• 串上的运算（连接、前后缀、幂运算）

文法定义

<动词> 语法成分 eat 语言的基本符号

文法的形式化定义：G=(VT、VN、P、S)

• VT={apple，boy，eat，little} 终结符，token
• VN非终结符，用来表示语法成分 VN={<句子>，<名词短语>，<动词短语>，...}
• VT∩VN=空集 VT∪VN：文法符号集
• P：产生式集合 α→β
• S：开始符号，表示的是该文法中最大的语法成分 S=<句子>

语言定义

推导（用产生式的右部替换产生式的左部） 归约与其相反

句型和句子

语言的形式化定义：

由文法G的开始符号S推导出的所有句子构成的集合称为文法G生成的语言L(G)

文法的分类

0型文法：无限制文法

1型文法：上下文有关文法 |α|≤|β|

2型文法：上下文无关文法 α∈VN CFG

3型文法：正则文法（右线性文法：A→wB 或 A→w 左线性文法：A→Bw 或 A→w）

四种文法之间的关系：逐级限制

CFG文法的分析树

分析树是推导的图形化表示

给定一个句型，其分析树中的每一颗子树的边缘称为该句型的一个短语

上述分析树短语：-（E+E）、（E+E）、E+E

如果子树只有父子两代节点，那么这颗子树的边缘称为该句型的一个直接短语：E+E

直接短语一定是某产生式的右部

但产生式的右部不一定是给定句型的直接短语

二义性文法

如果一个文法可以为某个句子生成多颗分析树，则称这个文法是二义性的

消歧规则：每个else和最近的尚未匹配的if匹配

对于任意一个上下文无关文法，不存在一个算法判定它是无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的