编译原理笔记1

编译原理1

基本概念

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

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

  • 串上的运算(连接、前后缀、幂运算)

文法定义

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

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

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

语言定义

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

编译原理笔记1

句型和句子

编译原理笔记1

语言的形式化定义:

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

编译原理笔记1

文法的分类

0型文法:无限制文法

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

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

3型文法:正则文法(右线性文法:A→wB 或 A→w 左线性文法:A→Bw 或 A→w)

编译原理笔记1

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

CFG文法的分析树

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

编译原理笔记1

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

上述分析树短语:-(E+E)、(E+E)、E+E

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

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

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

编译原理笔记1

二义性文法

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

编译原理笔记1

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

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

上一篇:常见的交易API接口介绍


下一篇:(转)3D中的OBJ文件格式详解