编译原理复习2

先打一发广告，我这个博客一开始就是用于记录算法的学习过程的，后来干脆想着把课堂笔记也整理整理放上来。想想这学期快结束了，下学期开始又要开始学习算法啦。我是准备从0开始学习的，借助于高中生信息学竞赛的平台。欢迎各位各类同学加进来，笑着问我为什么刷那么慢，或者跟我一起从0开始。欢迎对照对边导航栏，对准“算法向”的“洛谷”查看进度，刷完这个之后会继续刷USACO。

群号是⑥⑥①⑨②2025，这是我设置的一道很低的门槛用来阻止广告的。入群的验证暗号是：我爱编译原理

---

高级语言及其语法描述

程序语言的定义

语法

语法：一组规则，用它可以形成和产生一个合式(well-formed)的程序

词法规则

单词符号的形成规则

• 单词符号是语言中具有独立意义的最基本结构
• 一般包括：常数、标识符、基本字、算符、界符
• 描述工具：有限自动机

语法规则

语法单位的形成规则

• 语法单位通常包括：表达式、语句、分程序、过程、函数、程序等
• 描述工具：上下文无关文法

语法规则和词法规则定义了程序的形式结构

语义

语义：一组规则，用它可以定义一个程序的意义

• 描述方法
  
  • 自然语言描述
  • 形式描述

高级语言的一般特性

高级语言的分类

程序结构

数据结构与操作

一个数据类型通常包括三种要素：

• 用于区别这种类型数据对象的属性
• 这种类型的数据对象可以具有的值
• 可以作用于这种类型的数据对象的操作

标识符与名字

• 标识符是语法概念
• 名字有确切的意义和属性

语句与控制结构

• 表达式
  
  • 前缀是说操作符在最前面

程序语言的语法描述

概念

字母表：考虑一个有穷字符集 Σ ，其中每一个元素成为一个字符

字符串： Σ 上的字（也叫做字符串），是指由 Σ 中的字符所构成的一个有穷序列

空字：不包含任何字符的序列称为空字，记做 ϵ

字的全体：用 Σ∗ 表示 Σ 上的所有字的全体，包括空字 ϵ

例如：设 Σ={a,b} ，则 Σ∗={ϵ,a,b,aa,ab,ba,bb,aaa,⋯}

连接(积)： Σ∗ 的子集 U 和 V 的连接(积)定义为 UV={αβ|α∈U&β∈V}

例：设 U={a,aa},V={b,bb} ，那么， UV={ab,abb,aab,aabb}

V 自身的 n 次积记为 Vn=VV⋯Vn个V

令 V∗=V0⋃V1⋃V2⋃V3⋃⋯ ，称 V∗ 是 V 的闭包

记 V+=VV∗ ，称 V+ 是 V 的正规闭包

上下文无关文法

文法：描述语言的语法结构的形式规则

一个上下文无关文法 G 是一个四元式， G=(VT,VN,S,P) ，其中

• VT ：终结符集合(非空)
• VN ：非终结符集合(非空)，且 VT⋂VN=∅
• S ：文法的开始集合， S∈VN
• P ：产生式集合(有限)，每个产生式形式为
  
  • P→α,P∈VN,α∈(VT⋃VN)∗
• 开始符 S 至少必须在某个产生式的左部出现一次

由语言构造文法

这是一个很大的专题，详情参考

参考文章1：由语言构造文法1

参考文章2：由语言构造文法2