1. 梳理第二章的内容，写一篇理解与总结。

       第二章 文法和语言

  1.文法:阐明语法的一个工具,也可以说是以有穷的集合刻画无穷的集合的一个工具。

   语言:程序设计语言。

  2.符号、字母表和符号串

  基本符号:可以相互区别的基本元素,如字母,数字,标点符号。

  字母表:基本符号的非空有穷集合,常用Z表示。例: 2={0,1), Z-{a, b, c, …, xy, z}

  符号串:由字母表中的符号构成的任何有穷序列称为符号串。符号串中的符号是有顺序的。

  3.产生式

  生成方式(文法) :语言中的每个句子可以用严格定义的规则来构造。

  4.推导

  用文法定义语言的中心思想是:从文法的开始符号出发,反复使用合适规则,对非终结符施行替换和展开。

  最左(最右)推导:在推导的任何一步a=>b，其中a、b是句型,都是对a中的最左(右)非终结符进行替换，最右推导被称为规范推导。

  5.文法类型

 （1）0型文法：无限制文法、短语文法，α->β，α中至少含一个非终结符。

 （2）1型文法（CSG）：上下文有关文法，α->β满足|α|<=|β|，对于产生式α1Aα2->α1βα2，用β替换A时，只能在上下文为α1和α2时才能进行。这里的|β|表示的是β的长度。同理|α|表示的是α的长度。

注意：虽然要求|β|>=|α|，但有一特例：α→ε也满足1型文法。

 （3）2型文法（CFG）：上下文无关文法，A->β，其中左边必须有且仅有一个非终结符，当用β替换A时，与A的上下文环境无关。

如Ab->Bab虽然符合1型文法要求,但不符合2型文法要求，因为其α=Ab，而Ab不是一个非终结符。

 （4）3型文法（RG）：也称为正则文法。它应该满足以下条件①左边必须只有一个字符，且必须是非终结符。②右边最多只能有两个字符，且当只有两个字符时必须是一个为终结符而另一个为非终极符；当右边只有一个字符时，此字符必须为终结符。

   上下文无关文法的句型推导直观工具：推导树–语法树。

  6.句型分析

  句型分析就是识别一个符号串是否为某文法的句型,是某个推导的构造过程。

  分析算法可分为:自上而下分析法：从文法的开始符号出发,反复使用文法的产生式，寻找与输入符号串匹配的推导。自下而上分析法：从输入符号串开始,逐步进行归约，直至归约到文法的开始符号。两种方法反映了两种不同的语法树的构造过程。

  语法树子树分析法:

  短语:任意一颗子树的叶子结点从左至右顺序排列的字符串(按给定句型排除) 。

  直接短语:只有父子两层的子树的叶子结点从左至右顺序排列的字符串。

  句柄:最左最下的只有父子两层的子树的叶子结点从左至右顺手排列的字符串。

  文法的二义性和语言的二义性：

　若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件文法的二义性和语言的二义性是不同的概念。

  通过这个月老师的授课，还有做练习和作业学习了编译原理的文法与语言，学习的概念：文法，推导，直接推导,最左(右)推导,产生式,句型,短语,直接短语,句柄语法树,规范推导,二义文法等 。熟悉4种文法的定义、文法的构造和文法的推导。掌握语法树的构造和最左(右)推导;熟悉二义文法、二义性的证明;掌握句型分析

2. 尝试写出PL/0 语言的文法。（或者你认为比较好的语言规则）

整数n  n :: =0| 1 | 2 | ….. | 9 

标识符i   i :: =a|b|c|……|y|z|A|B|C|……|Y|Z （<字母> | {<字母> | <数字 >}）

表达式e  e::= [+|-] <项> { <加减运算符> <项> }

条件语句  ::= if<条件>then<语句>

赋值语句  ::= <标识符id> := <表达式>

复合语句  ::= begin <语句> {;<语句>} end

函数  ::= <类型说明><函数名><复合语句>

程序  ::= [<常量说明部分>] [<变量说明部分>] [<过程说明部分>] <语句>

…