电子科技大学编译原理复习笔记（四）：程序语言的设计

目录

前言

重点一览

语言的定义

比较：生成观点与识别观点

语义又该怎么描述？

符号串

符号串集合

⭐文法（超重点）

定义

组成

表示

⭐分类（重点） 

文法产生的语言

⭐短语、直接短语和句柄（求它们目的是语法分析）

⭐语法树（推导树）

语言的设计

本章习题

本章小结

---

前言

本复习笔记基于张老师的课堂PPT，供自己期末复习与学弟学妹参考用。

---

重点一览

这一章开始正式进入编译原理的重点，文法部分。 

---

语言的定义

• 语言=语法（规则）+语义（规则）
• 语法：用以构造程序及其成分（语法单位）的规则的集合
• 语义：用以规定语法正确的语法单位的含义的规则的集合
• 程序设计语言是用来描述计算机所执行的算法的形式表示
• 词法规则：规定什么样的字符序列可以构成语言的有效符号
• 语法规则：确定一个符号序列是否为一个句子，并提供句子结构（判断是否合法）
• 生成的观点：每一行称为一条语法规则，语法就是所有句子的集合，可形成文法
• 识别的观点：用语法图来定义给定的语言，每一个非终结符连同相应的产生式对应一个语法图

识别观点下的语言：语法图能识别的所有终结符序列的集合

比较：生成观点与识别观点

语义又该怎么描述？

至今尚无一典型描述工具，许多语言仍采用自然语言描述语义。

符号串

符号串的概念需要介绍，它在后面的知识是一个基础，不然可能连题都看不懂。

基本概念

• 设x和y是符号串，x是abc，y是edf，那么xy就是abcdef，这个行为就叫作符号串的连接；
• 当符号串z是kk...kk时，记作z=k^n，即把k重复写n次
• 特殊地，当n=0时，z=ε（空船，无值符号）；当k=pq时，z=pqpq…pqpq

符号串集合

用一个例子简单说明：

特殊地，A^0={ε} ，并且串集的连接一定有顺序性。

---

⭐文法（超重点）

定义

文法是描述语言的我语法结构的形式规则

文法的重要特性：有限规则描述无限语言 

组成

很明显，文法包含：终结符、非终结符、开始符号、产生式四个元素，我们约定用大写字母表示非终结符，小写字母表示终结符，希腊小写字母表示串 

产生式是可以简写的，左侧相同时，右侧可以用 " | " 符号分开，表示或。

表示

想要描述文法，直接给出产生式的集合即可。

例：算术表达式文法G0：（第一条表达式第二项应该是E-T，老师写错了）

⭐分类（重点） 

① 0型文法（短语文法）

产生式形如α→β，α是一个至少含一个非终结符的串，而β是任意一个串。

② 1型文法（上下文有关文法）

1型文法在0型上加了限制，要求左边的长度必须小于右边的长度，也就是必然有非终结符要被替换成串，产生式形如αAβ→αγβ。

本质上是A→γ，但有前后的α和β的限制，所以只能在这两个串之间（上下文环境）中才能替换

③ 2型文法（上下文无关文法）

产生式形如A→α，容易看出2型文法解除了上下文的限制，只要有左边非终结符的出现就可以进行串的替换，由于这种文法对于程序基本可以描述，因此上下文无关文法常简称为文法

④ 3型文法（正则文法/右线性文法）

产生式形如A→α或A→αB（A、B是非终结符，α规定为终结符串），也就是替换了以后左边一定已经被终结符锁定，只有右边可以变。

文法产生的语言

推导与规约

• 直接推导：用产生式右边直接替换产生式左边
• 推导：，星号双箭头表示经过0次以上推导得到右边的串，加号双箭头表示经过至少1次的推导得到右边的串
• 归约：推导的逆过程 
• 最左/右推导：每次都替换最左/右边的非终结符，最右推导又叫规范推导

句型与句子

• 文法开始符号推出的一个串中包含非终结符，它就是一个句型；如果此串只含终结符，那它就是一个句子
• 只含终结符的句型就是句子
• 句子一定是句型，句型不一定是句子
• 文法G产生的所有句子的集合称为由文法产生的语言L(G)
• 如果两个文法产生的语言相同，则称这两个文法等价

例题：求语言（简答题）

 

 

⭐短语、直接短语和句柄（求它们目的是语法分析）

短语

 

直接短语

 

 

上述注意事项可用于判断某短语是否为直接短语，只需要找所有产生式右端即可。 

理解短语与直接短语

 

句柄 

一个句型的最左直接短语称为该句型的句柄，例题如下：

素短语 

含有终结符的短语，且它的真子串不具有这个特性（素短语的子串不是含终结符的短语）

⭐语法树（推导树）

• 语法树用图的方式来表示推导过程，语法树的本质是推导过程，所以文法的每个句型（句子）都有一颗对应的语法树
• 推导树的边缘（语法树所有叶结点的从左到右的连接）就是句型（句子）
• 当一个句子有两棵不同的语法树是，我们说这个文法具有二义性
• 我们还可以通过推导树确定短语/直接短语/句柄，语法树的子树和简单子树对应着短语和直接短语，而最左边的简单子树自然就是句柄
• 语法树有n个内部节点，就有n棵子树，就有n个短语；m棵直接子树（只有父子两代）就有m个直接短语。

例子：

 

---

语言的设计

在实验中体现，不会考察。

---

本章习题

 

 

---

本章小结

短语、直接短语与句柄、素短语

语法树概念、与短语的联系、绘制语法树