第二章笔记
高级语言及其语法描述
2.1 程序语言的定义
程序语言主要由语法和语义两方面定义
语法的三个基本概念：字母表、单词符号、语法单位
1.字母表：一个有限的字符集
2.单词符号：是语言中具有独立意义的最基本结构
3.语法单位：由单词符号构成的更大的结构
语义：对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义。
程序的层次结构：
2.2 高级语言的一般特性
高级语言的分类：
程序设计语言的一般特性：程序结构、数据类型与操作、语句、控制结构
表达式的相关概念：
1.表达式的形式（前缀，中缀，后缀）
2.表达式中的运算符（算数，关系，逻辑；优先级，结合性）
3.运算符的代数性质（交换律，结合律等等）
常见的算术表示形式:
前缀式： +abc
中缀式：a+bc
后缀式：abc*+
2.3 程序语言的语法描述
字母表：由若干元素组成的有限非空集合，用 Σ 表示，它的每个元素称为一个符号。
符号串： 由Σ中的符号所构成的有穷序列。
符号串的前缀和后缀及子串：设x是一个符号串，将x的尾（前）部删掉几个字符后形成的符号串，称为x的前（后）缀；从一个符号串中删去他的一个前缀和后缀后所剩下部分称为x的子串
空字：不包含符号的序列称为空字。
符号串的连接运算：设x和y是两个符号串，如果将y直接拼接在x之后，称这种操作为符号串的连接
符号串的方幂：一个符号串与其自身的n-1的任意连接称为次符号串的n次幂，记作：xⁿ
字符串集合的和(等价于集合的并运算)：设A、B是两个符号串的集合，则将集合A、B的和记为A+B或AUB,定义为：A UB={w|w∈A或w∈B}
符号串集合的连接： *的子集U和V中的（连接）积定义为:
UV={αβ∣α∈U & β∈V }
即集合UV中的符号串是由U和V的符号串连接而成的。
符号串集合V自身的n次（连接）积记为：
Vⁿ= V V…V (n个V)
规定 Vº = {ε}.
V的闭包：
令： V* = V0 U V1U V2…
称 V*是V的闭包。
V的正则包（正闭包，正则闭包）：
记V+ = VV*, 称 V+是V的正则包，即V+ =V1UV2UV3…。
上下文无关文法: 一个上下文无关文法G包括四个组成部分：一组
终结符号，一组非终结符，一个开始符号，以及一组产生式。
1.所谓终结符号乃是组成语言的基本符号，即在程序语言中以前屡次提到的单词符号，如基本字，标识符，常数，算符和界符等.
2.所谓非终结符号（也称语法变量）用来代表语法范畴。
3.开始符号是一个特殊的非终结符号，它代表所定义的语言中我们最感兴趣的语法范畴。
4.产生式（也称为产生规则或简称规则）是定义语法范畴的一种书写规则。
2.3.2 语法分析树与二义性
语法分析树：简称语法树。用来表示推导过程。
文法的二义性:如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法
是二义的。
2.3.3 形式语言鸟瞰
乔姆斯基把文法分为四种类型
0型,1型,2型,3型
0型强于1型，1型强于2型，2型强于3型。这几文法的差别在于对产生式施加不同的限制。
课后习题
令文法G为： N→D | ND
D→0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
（1）G6的语言L（G6）是什么？
0-9组成的数字串
（2）写出句子0127的最左和最右推导
最左推导： N =>ND =>NDD =>NDDD =>DDDD =>0DDD =>01DD=>012D=>0127
最右推导： N =>ND =>N7=>ND7=> N27=> ND27=> N127=> D127=>0127
令文法为： E→T | E + T | E - T
T→F | T * F | T / F
F→( E ) | i
给出 i + i + i、i + i * i 的语法树
把下面文法改成无二义的
S→ SS | ( S ) | ( )
改 ： S→TS | T
T→( S ) | ( )
给出下列语言的相应文法
（1） L1 = { aⁿ bⁿ ci | n>=0 ,i >=1}
G( S ) S→AC
A→aAb | ab
C→cC | ε
（2）L2 = { aⁿ bⁿ aⁿⁿ bⁿⁿ | n,m>=0 }
G( S ) S→AB
A→aAb | ε
B→aBb | ε
总结： 这一章概述了高级语言的结构和主要的共同特征，并介绍程序语言的语法描述方法，高级程序语言可分为强制式语言、作用式语言、基于规则的语言和面相对象语言。通过对这章的学习，让我对编译原理有了一定的了解，编译原理是一门理论性很强的学科，从文法的概念中，几乎都是对具体的高度抽象，感觉有些知识点还是很迷糊，需要反复研读课本