作业四——文法和语言总结与梳理

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

1、计算机的语言同中英文一样，都有自己独有的语法和规律，一定的规则可以判别句子结构合法与否，用这些规则描述句子的结构，这样的语言就是文法。是利用有限的集合（文法）来刻画无穷的集合（语种生成的句子）的一个工具。

　　正如汉语构成句子=主语+动词+谓语等汉字或者词组成语

　　程序设计语言句子=自己的符号+符号串

　　字母表是非空有限集合，所以字母表中的元素也成称为符号，字母表中的符号组成的任何有限序列称为符号串，符号串的顺序很重要，允许空符号串，用ε表示。符号串的运算一定要注意其顺序。

2、规则（重写规则、产生式、生成式）是形如A→B（A::=B）的（A,B）有序对。

　　文法G定义为四元组（Vn，VT，P,S）

　　V_N：为非终结符（语法实体，或变量）集，常用大写字母表示；

　　V_T：为终结符，常用小写字母表示；

　　P：为规则的集合，规则的左边属于V并且至少包含一个非终结符；

　　S：为识别符或是开始符，是一个非终结符，至少要在一条规则中作为左部出现。

　　推导是正向推导，归约是逆向推导。

3、文法的类型：

文法分为四种类型，0型、1型、2型、3型。

文法类型	又称	结构或定义		例子
0型文法	短语文法	α∈（V_N∪V_T），且至少含一个VN，而β∈（V_N∪V_T）	对产生式没有任何限制	S->A
1型文法	上下文有关文法	若任一产生式α→β，都有\|β\|≥\|α\|，仅仅S→ε除外，产生式的形式描述：α1Aα2→α1βα2，A必须出现在上下文中才允许用β替换。	产生式的左边不止一个符号，但必须至少有一个非终结符	aSb->aaSbb S->ab
2型文法	上下文无关文法	对任一产生式都有α∈V_N，β∈（V_N∪V_T）*	每个产生式左边只有一个终结符	G[S]: S→01 S→0S1
3型文法	正规文法	产生式的形式是A→aB或者是A→a	左边只有一个终结符，右边为一个非终结符或是一个非终结符加一个终结符	G[S]: S→a S→aB

4、语法树

　　给定文法G=(V_N,V_T,P,S)，语法树的根为S，每个结点都有一个标记，是V的一个符号。

　　在推导的任何一步α=>β,其中α、β是句型，都是对α最左非终结符进行替换，则为最左推导；若是对α最右非终结符进行替换，则为最右推导，也称之为规范推导。

　　如果一个文法存在某个句子对应两颗不同的语法数，则这个文法是二义的。

　　句型：语法树从左至右的一个序列；

　　句子：语法树从左至右终结符序列，是句型中的一个；

　　语言：由文法产生的所有句子的集合；

　　短语：某子树的末端节点按自左向右顺序为句型的符号串，该符号串为该句型相对于该子树跟的短语；

　　简单短语：语法树的简单子树的叶子结点从左到右排列构成一个简单短语；

　　句柄：最左的简单短语。

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

整数n

　　n->0|1|2|3|……|8|9

标识符i

　　i->a|b|c|……|y|z|A|B|C|……|Y|Z

表达式e

　　e->[+|-]<项>{<加减运算符><项>}

　　<项>-><因子>{<乘除运算符><因子>}

　　<因子>->i|n|’(‘e’)’

　　<加减运算符>->+|-

　　<乘除运算符>*|/

条件语句

　　stmt->if<条件>then<语句>

　　<条件>->e<关系运算符>e|odd e

　　<关系运算符>->==|#|<|<=|>|>=

赋值语句

　　i=e

复合语句

　　stmt->begin <语句>{;<语句>} end

函数

　　<函数>-><主函数><其他函数>|<主函数>

程序

　　<程序>-><分程序>

　　<分程序>-><常量说明部分><语句>|<变量说明部分><语句>|<过程说明部分><语句>

　　<常量说明部分>->const<常量定义>{，<常量定义>};

　　<变量说明部分>->var i{,i};

　　<过程说明部分>-><过程首部><分程序>{;<过程说明部分>};

　　<过程首部>->procedure i;

　　<过程循环语句>call i

　　<当型调用语句>->while<条件>do<语句>

　　<读语句>->write’(‘e{,e}’)’

　　<写语句>->read’(‘i{,i}’)’

　　<空语句>->ε