编译原理[笔记] 第二章

文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称为“语法”）。 所谓文法是在 形式上 对句子结构的定义与描述，而未涉及语义问题。

我们通过建立一组规则，来描述句子的语法结构。规定用“::=”表示“由……组成”。 例如： ::= ::=| ::=你|我|他 ::= 王民|大学生|工人|英语 ::= ::=是|学习 ::=|

有了一组规则之后，可以按照一定的方式用它们去推导或产生句子。 推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。 => => …… …… 这种推导一直进行下去，直到所有带< >的符号都由终结符号替代为止。 说明： (1) 有若干语法成分同时存在时，我们总是从 最左的语法成 分进行推导，这称之为最左推导。类似地还有最右推导（一般推导、规范推导）。 (2) 除了最左和最右推导，还可能存在其它形式的推导。 (3) 从一组规则可推出不同的句子

我们用语法树来描述一个句子的语法结构。语法树的叶子节点是句子的单词，非叶子节点的是语法成分。

文法G =（Vn，Vt，P，Z） Vn：非终结符号集 Vt：终结符号集 P：产生式或规则的集合 Z：开始符号（识别符号） Z∈Vn 注： ①V＝Vn ∪ Vt 称为文法的字汇表 ②规则：规则是一个有序对(U, x), 通常写为 U ::= x 或U→x（其中U∈Vn, x∈V* 因此也有|U| = 1且|x| >= 0） ③给定一个文法，实际只需给出产生式集合，并指定识别符号。（识别符号一般约定为第一条规则的左部符号）

例：无符号整数的文法： G[]=（Vn，Vt，P，Z） Vn＝{,, } Vt = { 0, 1, 2, 3, … 9 } P = { → → → →0 →1 ………… →9 } Z =

一步推导： 注：当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在规则左部，所以将在规则左部出现的符号称为非终结符号。 多步推导： 任意步推导： 规范推导： 直观意义上：规范推导＝最右推导

对于文法G[Z]： （1）句型x：由开始符号Z经任意步推导得到x，且x∈V*； （2）句子x：由开始符合Z经1多步推导得到x，且x∈Vt* （3）语言L：所有根据该文法推到得到的句子组成的集合

形式语言理论可以证明以下两点： （1）G →L(G)：已知文法，求语言，通过推导； （2）L(G)→G1，G2，……，Gn：已知语言，构造文法，无形式化方法，更多是凭经验。

等价文法：G和G’是两个不同的文法，若 L(G) = L(G’) , 则G和G’为等价文法。

①递归规则：规则右部有与左部相同的符号 对于 U::= xUy 若x=ε,即U::= Uy，左递归； 若y=ε,即U::= xU，右递归。

②递归文法：文法G，存在U ∈Vn if U=+=>…U…, 则G为递归文法(自嵌入递归)； if U=+=>U…, 则G为左递归文法； if U=+=>…U, 则G为右递归文法。

③左递归文法的缺点：不能用自顶向下的方法来进行语法分析

④递归文法的优点：可用有穷条规则，定义无穷语言

给定文法G[Z], w::=xuy∈V+，为该文法的句型, 若 Z==> xUy, 且U=+=>u, 则u是句型w相对于U的短语； 若 Z==> xUy, 且U==>u, 则u是句型w相对于U的简单短语。 其中U ∈Vn，u ∈V+，x, y ∈V*

短语的直观理解：短语是前面句型中的某个非终结符所能推出 的符号串。 句柄：任一句型的最左简单短语称为该句型的句柄

给定句型找句柄的步骤： 短语-> 简单短语-> 句柄

注意：短语、简单短语是相对于句型而言。一个句型 可能有多个短语、简单短语，但句柄只能有一个。

1.判断二义性文法： 依据：文法所能产生的句子，可以用不同的推导原则（使用产生式顺序不同）将其推导出来。如果文法是非二义性文法，那么语法树的生成规律不同，但最终生成的语法树形状完全相同；如果文法是二义性文法，那么最终生成的语法树形状有可能不相同。 方法1：若对于一个文法的某一句子存在两棵不同的语法树（或两个不同的 规范推导）；或者自底向上看，对于同一个规范句型，存在两个不同的句柄。则该文法是二义性文法，否则是无二义性文法。 方法2：即不改变二义性文法，而是确定一种编译算法，使该算法满足无二义性充分条件。 文法二义性的判定？？：在理论上已经证明：文法的二义性是不可判定的，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。解决方法：提出一些限制条件，称为无二义性的充分条件。当文法满足这些条件时，就可以判定文法是无二义性的。 2.子树与短语 子树：子树由语法树中的某个结点（子树的根）连同它向下派生的部分所组成。 关系：某子树的末端结点按自左向右顺序为句型中的符号串，则该符号串为该句型的相对于该子树根的短语。 3.规约：自下而上地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次规约。 规范规约：对句型中最左简单短语（句柄）进行的规约称为规范规约。 注：规范规约与规范推导 互为逆过程。

规范句型：通过规范推导或规范规约所得到的句型称为规范句型。

句子的分析是词法分析和语法分析所要做的工作 任务：给定G[Z]: S ∈ Vt*, 判定是否有S ∈ L(G[E])

有害规则：若文法中有如U::=U的规则，则这就是有害规则，它会引起二义性。（我推我自己） 多余规则： （1）在推导文法的所有句子中，始终用不到的规则。即该规则的左部非终结符不出现在任何句型中。（用不到） （2）在推导句子的过程中，一旦使用了该规则，将推不出任何终结符号串。即该规则中含有推不出任何终结符号串的非终结符。（死胡同） 若某文法中无有害规则或多余规则，则称该文法是 压缩过的。

BNF的元符号： , ::=, | 扩充的BNF的元符号： , ::=, |, {, }, [, ] (, ) 1.{ t }：t可重复连接0到任意多次。如果有限制（上标m，下标n），则可重复连接n到m次。 2.[ t ]：t可有可无。 3.( )：元符号，注意不要与Vt混淆。

形式语言：用文法和自动机所描述的没有语义的语言。 语言定义： L(G[Z]) = { x | x∈Vt*, Z =+=> x } 文法定义：乔姆斯基将所有文法都定义为一个四元组： G=（Vn，Vt，P，Z） Vn：非终结符号集 Vt：终结符号集 P：产生式或规则的集合 Z：开始符号（识别符号） Z∈Vn 文法和语言分类 文法和语言分类：0型、1型、2型、3型 这几类文法的差别在于对产生式施加不同的限制。

注： （1）2型文法与BNF表示相等价。 （2）3型语言（L3）又称正则语言、正则集合 （3）四种语言的关系：