1. 梳理第二章的内容,写一篇理解与总结。
答:在第二章中,我们学习了符号、符号串、句子、语法树、子树、短语、直接短语、句柄、文法、最左推导、最右推导、语言、二义性。
字母表:符号(元素)的非空有限集合(即字母表里的符号不能重复),典型的符号是字母、数字、各种标点和运算符等等。
符号串:由字母表中的符号组成的任何有穷序列;
若某符号串x中有m符号,则称其长度为m,表示为 |x|=m;
符号串包括了空符号串(即不包含任何符号的符号串),用 ε 表示,其长度为0,即 |ε|=0;
符号串的连接:设x和y是符号串,它们的连接xy是把y的符号写在x的符号之后得到的符号串;
符号串的方幂(自连接):设x是符号串,它的方幂是把x自身连接n次得到的符号串。
规则:也称重写规则、产生式或生成式,是形如α→β或α::=β的(α,β)有序对,其中α称为规则的左部,β称作规则的右部。这里使用的符号→(::=)读作“定义为”。
例如A→a读作“A定义为a”。也把它说成是一条关于A的规则(产生式)。
句子:仅含有终结符号的句型是文法的一个句子。
句型:对于文法G=(VT,VN,S,φ),如果S=>x,则称x是当前文法的一个句型。
语法树:推导的图形表示,又称推导树。一棵有序有向树,因此具有树的性质;分析树的特点:每一个结点都有标记。
根结点由文法的开始符号标记; 每个内部结点由非终结符号标记,它的子结点由这个非终结符号的这次推导所用产生式的右部各符号从左到右依次标记;
叶结点由非终结符号或终结符号标记,它们从左到右排列起来,构成句型。
子树:分析树中一个特有的结点、连同它的全部后裔结点、连接这些结点的边、以及这些结点的标记。
子树的根结点的标记可能不是文法的开始符号。 如果子树的根结点标记为非终结符号A,则可称该子树为A-子树。
短语:一棵子树的所有叶结点自左至右排列起来,形成此句型相对于该子树根的短语。
直接短语:分析树中只有父子两代的子树的所有叶结点自左至右排列起来,形成此句型相对于该子树根的直接短语。
句柄:分析树中最左边的那棵只有父子两代的子树的所有叶结点自左至右排列起来,就是该句型的句柄。
文法:语言中的每个句子可以用严格定义的规则来构造。通俗的讲就是:根据一些指定的规则,来确定编程语言的语法,从而实现编译器的功能。
任何一个文法都可以表示为一个四元组G=(VT,VN,S, φ)
VT是一个非空的有限集合,它的每个元素称为终结符号。
VN是一个非空的有限集合,它的每个元素称为非终结符号。 VT∩VN=φ
S是一个特殊的非终结符号,称为文法的开始符号。
φ是一个非空的有限集合,它的每个元素称为产生式。
如果两个文法产生的语言相同,则称这两个文法是等价的。
文法分类:0型文法、1型文法(上下文有关文法)、2型文法(上下文无关文法)、3型文法(正规文法)
最左推导:如果 a=>b,并且在每“一步推导”中,都替换a中最左边的非终结符号,则称这样的推导为最左推导。
最右推导:也称规范推导,如果 a=>b,并且在每“一步推导”中,都替换a中最右边的非终结符号,则称这样的推导为最右推导。
二义性:如果一个文法的某个句子有不止一棵分析树,则这个句子是二义性的句子。 含有二义性句子的文法是二义性的文法。
有些语言,根本就不存在无二义性的文法,这样的语言称为二义性的语言。
二义性问题是不可判定的。
语言:文法G产生的所有句子组成的集合是文法G所定义的语言。
2. 尝试写出PL/0 语言的文法。(或者你认为比较好的语言规则)
整数n:G(N):N->n | nN
n->0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
标识符i:G=(VN,VT,P,S),
VN={I(标识符),L(字母),D(数字)}
VT={a,b,c,...,x,y,z,0,1,2,...,9}
P={ <I>-><L>,
<I>-><I><L>,
<I>-><I><D>,
<L>->a,
<L>->b,
.
.
.
<L>->z,
<D>->0,
<D>->1,
.
.
.
<D>->9}
S=<I>
I->L|IL|ID
L->{a|b|c|...|z}
D->{0|1|2|...|9}
表达式e:G(e):e->e+T | e-T | T
T->T*F | T/F | F
F->(e) | i
条件语句:stmt->if expr then stmt | if expr then stmt else stmt | other
赋值语句:<赋值语句>-> <标识符> = <表达式>
<表达式>:G(e):e->e+T | e-T | T
T->T*F | T/F | F
F->(e) | i
复合语句:<复合语句>-><赋值语句> | <循环语句> | <条件语句>
<赋值语句>-> <标识符> = <表达式>
<循环语句>-><for语句>|<while语句>|<do while语句>
<条件语句>->if <条件> then <语句> | if <条件> then <语句> else <语句> | 其他
函数:<函数>-><返回值类型><标识符><形参><复合语句>
<返回值类型>->void | char | int | float
<标识符>-><字母> | <标识符><字母> | <标识符><数字>
<形参>-><数据类型><标识符>
<复合语句>-><赋值语句> | <循环语句> | <条件语句>
程序:<程序>-><外部声明> | <外部声明><函数>
<外部声明>-><头文件><函数声明> | <其他声明>
<函数>-><返回值类型><标识符><形参><复合语句>