1.梳理第二章内容，写一篇理解与总结。
一、文法和语言的形式与定义。
（1）什么是文法？文法是对语言结构的定义与描述，即从形式上描述和规定语言结构，也称为语法。任何一个文法都可以表示为一个四元组G=(VN,VT,P,S)。
VN是一个非空的有限集合，它的每个元素称为非终结符号。
VT是一个非空的有限集合，的每个元素称为终结符号。
P是一个非空的有限集合，它的每个元素称为产生式。
S是一个特殊的非终结符号，称为文法的开始符号。
（2）什么是语言？在某一确定字母表上的特定符号串的集合。
（3）语法规则。通过产生一组规则（产生式），来描述句子的语法结构。
（4）由产生式推导句子。推导方法：从一个要识别的符号开始推导，即用相应产生式的右部来代替产生式的左部，每次仅用一条产生式进行推导。
（5）句型。由起始符推导出来的符号串。
（6）句子。仅含有终结符合的句型。
（7）语言。句子的集合。
二、符号和符号串
（1）字母表. 符号的非空有限集合。典型的符号是字母、数字、各种标点和运算符等。
（2）符号串.定义在某一字母表上，由该字母表中的符号组成的有限符号序列。
（3）符号串有关的几个概念。
①长度。符号串a的长度是指a中出现的符号的个数，记作|α|。
②空串。长度为0的符号串，常用ε表示。|α|=0
③前缀(头）。符号串α的前缀是指从符号串α的末尾删除0个或多个符号后得到的符号串。如：univ 是 university 的前缀。
④后缀（尾）。符号串α的后缀是指从符号串α的开头删除0个或多个符号后得到的符号串。如：sity 是 university 的后缀。
⑤子串。符号串α的子串是指删除了α的前缀和/或后缀后得到的符号串。如：ver 是 university 的子串。
⑥真前缀、真后缀、真子串 。如果非空符号串β是α的前缀、后缀或子串，并且β不等于α，则称b是α的真前缀、真后缀、或真子串。
⑦子序列。符号串α的子序列是指从α中删除0个或多个符号(这些符号可以是不连续的)后得到的符号串。如：nvst。
（4）符号串运算。
①连接。符号串α和符号串β的连接αβ是把符号串β加在符号串α之后得到的符号串，若α=ab，β=cd，则αβ=abcd，βα=cdba。对任何符号串α来说，都有εα=αε=α。
②幂。若α是符号串，α的n次幂是αn 。当n=0时，α0是空串。e假如α=ab，则有：α0=ε、α1=ab、α2=abab、α3=...
三、文法类型和语法树。
（1）文法分类。
①0型文法/无限制文法：α->β，其中α∈(Vn∪Vt)且至少含有一个非终结符，β∈(Vn∪Vt)。
②1型文法/上下文有关文法：αAβ->αuβ，其中A∈Vn，α,β∈(Vn∪Vt)，u∈(Vn∪Vt)+。
③2型文法/上下文无关文法：A->β，其中A∈Vn，β∈(Vn∪Vt)。常用于句法分析。
④3型文法/正规文法：常用于词法分析。
右线性文法：只能对推出式的右边展开，A->αB|α，A,B∈Vn，α∈Vt。
左线性文法：只能对推出式的左边展开，A->Bα|α，A,B∈Vn，α∈Vt。
（2）语法树。
①短语。是句型中的某个非终结符所能推出的符号串。
②直接短语。不能再推导出其他式子的符号串
③句柄。最左的直接短语。
④最左推导。每个推导过程都是从最左边的非终结符号的替换开始。
⑤最右推导。每个推导过程都是从最右边的非终结符号的替换开始。
（3）文法的二义性。如果一个文法的某个句子有不止一棵分析树，则这个句子是二义性的句子。含有二义性句子的文法是二义性的文法。
2. 尝试写出PL/0 语言的文法。
整数n
n :: = 【-】{[span style="font-family: 宋体">非零数字数字
[span style="font-family: 宋体">非零数字
[span style="font-family: 宋体">数字
标识符i
i::=[span style="font-family: 宋体">字母字母数字
[span style="font-family: 宋体">字母
[span style="font-family: 宋体">数字
表达式e
e ::= 【+|-】[span style="font-family: 宋体">项加减运算符项
[span style="font-family: 宋体">项因子乘除运算符因子
[span style="font-family: 宋体">加减运符
[span style="font-family: 宋体">因子标识符无符号整数表达式
[span style="font-family: 宋体">乘除运算符
[span style="font-family: 宋体">标识符字母字母数字
[span style="font-family: 宋体">无符号整数数字数字
[span style="font-family: 宋体">数字
[span style="font-family: 宋体">字母
条件语句
[span //代码效果参考：http://www.jhylw.com.cn/212028435.html
style="font-family: 宋体">条件语句条件语句[span style="font-family: 宋体">条件表达式关系运算符表达式表达式
[span style="font-family: 宋体">表达式项加减运算符项
[span style="font-family: 宋体">项因子乘除运算符因子
[span style="font-family: 宋体">加减运符
[span style="font-family: 宋体">因子标识符无符号整数表达式
[span style="font-family: 宋体">乘除运算符
[span style="font-family: 宋体">标识符字母字母数字
[span style="font-family: 宋体">字母
[span style="font-family: 宋体">无符号整数数字数字
[span style="font-family: 宋体">数字
[span style="font-family: 宋体">关系运算符=
[span style="font-family: 宋体">语句赋值语句条件语句当型循环语句过程调用语句读语句写语句复合语句空语句
[span style="font-family: 宋体">赋值语句标识符表达式
[span style="font-family: 宋体">当型循环语句条件语句
[span style="font-family: 宋体">过程调用语句标识符
[span style="font-family: 宋体">读语句标识符标识符
[span style="font-family: 宋体">写语句表达式表达式
[span style="font-family: 宋体">复合语句语句语句
[span style="font-family: 宋体">空语句
赋值语句、复合语句如上所述。
函数
[span style="font-family: 宋体">函数类型说明函数名复合语句
程序
[span style="font-family: 宋体">程序分程序
[span style="font-family: 宋体">分程序常量说明部分变量说明部分过程说明部分语句
[span style="font-family: 宋体">常量说明部分常量定义常量定义
[span style="font-family: 宋体">常量定义标识符无符号整数
[span style="font-family: 宋体">变量说明部分标识符标识符
[span style="font-family: 宋体">过程说明部分::=[/span>过程首部分程序过程说明部分
[span style="font-family: 宋体">过程首部标识符
