编译原理-文法和语言

文法的直接概念

文法是阐述语法的一个工具，语句是语法的实例 。

语言的构成：组成语言的基本形式是句子，句子是由单词序列构成的，单词是由语言基本符号（字母或单字）组成的。

语言既包含单词和句子这样的语言成分，又包含将这些成分组织起来的语言规则，如词法规则、句法规则等。

• 语法：是一组规则，定义符号如何排列，排列与符号含义无关。
• 语句：是一组规则，定义符号如何排列，排列与符号含义无关。
• 语义：研究语法的含义

约定（1）:符号”::=”表示“···是由···组成的”

约定（2):符号”|”表示“或者”的意义

约定（3):符号”=>”表示“推导”

eg：

<句子> ∷＝<主语> <谓语> <宾语>
<主语> ∷＝<名词>
<主语> ∷＝<代词>
<谓语> ∷＝<动词>
<宾语> ∷＝<名词>
<宾语> ∷＝<代词>
<代词> ∷＝ 我
<代词> ∷＝ 你
<动词> ∷＝ 吃
<动词> ∷＝ 做
<名词> ∷＝ 饭
<名词> ∷＝ 菜

<句子> => <主语> <谓语> <宾语>
=> <代词> <谓语> <宾语>
=> 我 <谓语> <宾语>
=> 我<动词> <宾语>
=> 我吃<宾语>
=> 我吃<名词>
=> 我吃饭

1、推导过程不唯一

2、推导起点的不同，导致语法意义上差异的推导结果

语法形式化方法要点：

• 语法规则的形式化
• 语法规则含有语法单位符号
• 语法规则含有构成语句的单词符号
• 特殊的语法单位符号——开始符号

语法形式化的最终目的在于将语法分析的问题将装换成形式化的推导过程。

符号和符号串

基本概念

• 字母表：字母表∑是非空有穷集合，其元素称为符号。
• 符号串 由字母表∑中的符号组成的有穷序列称为 (字母表∑上的)符号串。特别地，不含任何符号的有穷序列称为空串，记为ε。单词和源程序都是符号串！

eg

设字母表∑＝｛0，1｝，则

​ 101是∑上的符号串，201不是∑上的符号串。

• 符号串长度：符号串α的长度是指符号串α中含有符号的个数，记为︱α︱。特别约定，空串ε为零，即︱α︱＝0。
• 符号串集合：如果集合A的元素都是字母表∑上的符号串，则称集合A为∑上的符号串集合，简称串集。

eg

设字母表∑＝｛a，b，c｝，A＝｛ε，a，ba，cab｝，B＝｛a1，ba，cab｝，则

A是∑上的符号串集合，B不是∑上的符号串集合。

基本运算

• 符号串连接运算：设x和y是字母表∑上的符号串，在符号串x的最后一个符号之后顺序接上符号串y的符号得到的新符号串z，则称符号串z是由符号串x和符号串y经过连接运算的结果，记为z＝x·y，其中，·是连接运算符。

设字母表∑＝｛a，b，c，0，1｝，x＝abc，y＝01cba，则 z＝x·y＝ abc01cba

• 符号串方幂运算 设x是字母表∑上的符号串，z是由n(≥0)个x自身连接得到的符号串，则称符号串z是由符号串x的n次方幂运算的结果，记为z ＝ x^n^ 。特别约定，x^0^ ＝ε, x^1^＝x 。

• 符号串集连接运算 设A，B是字母表∑上的符号串集，·是符号串集连接运算，则C＝A·B＝｛x·y︱x∈A ，y∈B｝。 笛卡尔积

• 符号串集方幂运算 设A是字母表∑上的符号串集，则C是由n(≥0)个A自身连接得到的符号串集，则称符号串集C是由符号串A的n次方幂运算的结果，记为C ＝ A^n^ 。特别约定，A^0^ ＝｛ε｝,A^1^＝A 。

• 符号串集正闭包运算 设A是字母表∑上的符号串集， A+是A的正闭包，则: A+＝A^1^∪A^2^∪A^3^∪···∪A^n^··· 。

• 符号串集闭包运算 设A是字母表∑上的符号串集， A*是A的闭包，则 : A* ＝A0∪A+ ，

  ​ 即：A* ＝A^0^∪A^1^∪A^2^∪A^3^∪···∪A^n^··· 。

文法和语言的形式定义

规则是字母表V上形如 a∷＝b的式子，可以简写成a→b。其中，符号串a∈V^+^称为规则的左部，符号串b∈V*称为规则的右部。规则也称为重写规则、产生式或生成式。

特别地，a∷＝ε（ε空串）称为a的空规则。

对于相同左部的多个规则，可以使用符号∣简写。如，规则a∷＝b和a∷＝δ，简写成a∷＝b∣δ。 简写为a → b∣δ

文法

文法G定义为一个四元组（VN，VT，P，S），记为G＝（VN，VT，P，S）。其中，

① VN是非空有穷集合，称为非终结符集，其元素称为非终结符；

② VT是有穷集合，称为终结符集，其元素称为终结符；

③ P是非空有穷集合，称为规则集，其元素是字母表VN∪VT上的规则，VN∪VT称为文法的字母表V，且VN∩VT＝空集；

④ S∈VN，称为开始符。

直接推导、直接归约

设文法G＝（VN，VT，P，S），如果α→β∈P，则称γ α δ推导出γ β δ，记为γ α δ=>γ β δ，其中,γ,δ∈V。

γ α δ=>γ β δ也称为直接推导或一步推导。

如果γ α δ=>γ β δ，则也称为γ β δ归约到γ α δ，也称为直接归约或一步归约。

例如，例3.1 定义的文法G1＝({S}，{a，b}，{S→aSb，S→ab}，S)，推导例子有：

（1）S=> aSb (α＝S，β＝aSb，γ＝ε，δ＝ε)【ε是空集】

（2）aSb => aaSbb (α＝S，β＝aSb，γ＝a，δ＝b)

（3）aSb => aabb (α＝S，β＝ab，γ＝a，δ＝b)

（4）aSbSb => aaSbbSb (α＝S，β＝aSb，γ＝a，δ＝bSb )

多步推导、多步归约

设文法G＝（VN，VT，P，S），α,β∈（VN∪VT）*， 如果α,β之间存在推导序列：

α＝ W0 => W1 => W2 ··· => Wn ＝β（n≥1）,

则称α经过n步推导出β，记为α=>^+^β。其中，Wi∈(VN∪VT)*

(1≤i≤n)。α=>^+^β也称n步推导或多步推导。

如果α=>^+^β，也称为β归约到α，也称为n步归约或多步归约。

例如，例3.1 定义的文法G1＝({S}，{a，b}，{S→aSb，S→ab}，S) ，多步推导(Þ)例子有：

（1）S=>^+^ ab (∵S=> ab)

（2）S=>^+^ aabb (∵ S=> aSb=> aabb)

（3）S=>^+^ aaaSbbb (∵ S=> aSb=> aaSbb=> aaaSbbb)

（4）aSb =>^+^ aaabbb (∵ aSb=> aaSbb=> aaabbb)

0步或0步以上推导与归约

设文法G＝（VN，VT，P，S），α,β∈（VN∪VT ) ^*^，如果有α→β或α=>^+^β，则称α经过0步或0步以上推导出β，记为α=>*β。亦称β经过0步或0步以上归约到α。

例如，例3.1 定义的文法G1＝({S}，{a，b}，{S→aSb，S→ab}，S) ， 0步或0步以上推导(Þ)例子有：

（1）S=>* ab，因为有S=>^+^ ab

（2）S=>* aabb， 因为有S=>^+^aabb

（3）S=>* aaabbb，因为有S=>^+^aaabbb

（4）aSb =>* aaabbb，因为有aSb=>^+^ aaabbb

（5）aSbSb =>*aSbSb，因为有aSbSb =>^+^ aSbSb

句型、句子

设文法G＝（VN，VT，P，S），如果有S=>* β，则称β是文法G的句型。如果有S=>* β，且β∈VT*，则称β是文法G的句子。

例如，例3.1 定义的文法G1＝({S}，{a，b}，{S→aSb，S→ab}，S) ，句型和句子例子有：

（1）ab是G的句子，因为有S=>* ab ，ab∈VT*

（2）aabb是G的句子，因为有S=>* aabb，aabb∈VT*

（3）aaaSbbb是G的句型，因为有S=>* aaaSbbb(aaaSbbb ∉ VT*)

语言

文法G＝（VN，VT，P，S）的产生语言定义为文法G的句子集合，记为L(G)。即：

L(G)＝｛β︱S=>^^β，β∈VT^^｝。

文法等价

设G1和G2是两个文法，如果L(G1)＝L(G2)，则称文法G1和G2是等价的。

例如，下列文法G2和G3是等价的。因为它们产生的语言都是以字母a开头、字母a和b构成的符号串的集合。即L(G2)＝L(G2）＝{a}{a，b}*。

G2＝(｛S，C｝，｛a，b｝，P，S），

其中，P＝｛S→aC，C→aC ，C→bC, C→ε｝。

G3＝(｛S｝，｛a，b｝，P，S），

其中，P＝｛S→Sa，S→Sb ，S→a｝。

文法类型

0型文法

设文法G＝（VN，VT，P，S），如果任意α→β∈P，α中至少含有一个非终结符，则称文法G属于0型文法。0型文法，也称为短语文法。

1型文法

设文法G＝（VN，VT，P，S），如果任意α→β∈P，α中至少含有一个非终结符，且除空规则之外，α的长度不大于β的长度，即︱α︱≤︱β︱，则称文法G属于1型文法。1型文法，也称为上下文有关文法。

文法G5定义如下，显然G5是1型文法。

​ L(G5）＝｛a^n^b^n^c^n^︱n≥1｝。

G5 ＝（VN，VT，P，S），

其中，VN＝｛S，B，C｝，

VT＝｛a，b，c｝，

P ＝｛S→aSBC︱aBC，CB→BC，

​ aB→ab，bB→bb，

​ bC→bc，cC→cc｝

2型文法

设文法G＝（VN，VT，P，S），如果任意α→β∈ P，α∈VN ，则称文法G属于2型文法。2型文法，也称为上下文无关文法。

例3.6 文法G6定义如下，显然G6是2型文法。

L(G6）＝｛w$w^R^︱n≥0, w^R^ 为w之逆，w∈{0，1}*｝

G6 ＝（VN，VT，P，S），

其中，VN＝｛S｝，

​ VT ＝｛$，0，1｝，

​ P ＝｛S→0S0︱1S1︱$ ｝

3型文法

文法 设文法G＝（VN，VT，P，S），如果任意α→β∈ P，α∈ VN ，且β只能是aB或a（除空规则之外），则称文法G属于右线性3型文法。【B是非终结符】

设文法G＝（VN，VT，P，S），如果任意α→β∈ P，α∈ VN ，且β只能是Ba或a（除空规则之外），则称文法G属于左线性3型文法。

左线性3型文法和右线性3型文法，统称3型文法，也称为正规文法。

例2.7 文法G7定义如下。显然G7是3型文法。

​ L(G7）＝｛00，01，10，11｝。

G7 ＝（VN，VT，P，S），

其中，VN＝｛S，A，B｝，

VT＝｛0，1｝，

P ＝｛S→A0︱B1，A→0︱1，B→0︱1｝

文法分类是对规则形式逐步加以限制而得。换言之，从0型文法到1型文法、2型文法和3型文法，其规则形式逐步简单。自然，其表达力也随之逐步减弱。

如果L0、L1、L2和L3分别是0型文法、1型文法、2型文法和3型文法能产生的语言之集，则有如下关系：

L0 ⊋ L1 ⊋ L2 ⊋ L3。

上下无关文法及其语法树

上下无关文法一个显著特征是规则左部一定有且仅有一个非终结符。利用这个特征，可以不列出VN和VT ，给出一个上下无关文法的简洁描述方法：①文法名G改写成G[S]，其中，S表示开始符；②规则集P，仅书写其具体规则。

最左推导、最右推导

如果在推导的每一步总是选择当前句型的最左（最右）边非终结符进行推导，则称这种推导过程为最左（最右）推导。最右推导，也叫规范推导。由规范推导所得的句型，叫做规范句型。规范推导的逆过程，叫做规范归约。

G[S]：S→aAS︱a

A→SbA︱SS︱ba

最左推导：S => aAS => aSbAS => aabAS => aabbaS => aabbaa

最右推导：S => aAS => aAa => aSbAa => aSbbaa => aabbaa

一般推导：S => aAS => aSbAS => aSbAa => aabAa => aabbaa

语法树

假设文法G＝（VN，VT，P，S），则文法G的语法树是一个满足下列条件的多叉树：

（1）以文法开始符S做为树根；

（2）以终结符号或非终结符号做为树的其他结点，且子树根和其孩子结点分别是某规则的左部和右部。

推论： ①非叶子结点一定是非终结符

           **②全部叶子结点组成的符号串是文法的句子**

语义二义性

如果一个文法G，某个句子存在对应的至少两棵不同的语法树，则称文法G是二义性的。

推论：

① 如果文法是无二义性的，一个句子的语法树反映了该句子的全部推导过程；

② 如果文法是无二义性的，一个句子的最左（最右）推导是唯一的。

语义的先天二义性

文法的二义性，并不等同于语言的二义性，尽管两者之间可能存在非必然的联系。

因为二义性文法G，可能存在与之等价的无二义性的文法G′，即L(G)＝L(G′）。

如果一个语言不存在无二义性的文法，则称该语言是先天二义性的。

例如，语言L＝{a^i^b^j^c^k^︱(i＝j 或i＝k)，(i，j，k≥1)}不存在无二义性的文法，是先天二义性的语言。

已经证明：文法的二义性判定问题是递归不可解的。即不存在这个判定问题的算法。

句型分析

假设文法G[S]是语言L之文法，即L(G)＝L，则“符号串α是否符合语言L的语法问题”被等价地转化成“推导或归约问题”，即：

【从起始符推导出α，并且α是非终结符组成的串，也就是α不能再细分】

【归约和推导可以视作是一个相反的过程】

这样，自然地形成了推导法和归约法两大类分析方法。推导法和归约法，也分别称为自上而下的分析方法和自下而上的分析方法。

自上而下的分析方法

从文法开始符号出发，反复使用规则，寻找匹配符号串（推导）的句型，直到推导出句子或规则用遍。进行每步推导时，存在两个选择问题：

⑴ 选择句型中哪一个非终结符进行推导

⑵ 选择非终结符的哪一个规则进行推导

问题⑴可以采用最左推导解决。问题⑵通常需要穷举每一个规则的可能推导。

成功：在推到过程中一旦出现个符号串α，便结束穷举过程，断定符号串α是句子。

失败：当穷举全部可能的推导，而不存在一个符号串α之推导过程的时候，才可以断定符号串α不是句子。

自下而上的分析方法

从输入符号串α开始，逐步进行“归约”，直至归约出文法的开始符号 S，则输入串α是文法G定义的语言的句子。否则不是。

这种分析方法在进行每步归约时，存在两个如何选择句型α的子串β进行归约的问题(α=β δ)。

如果文法规则没有相同的右部，则在语法分析的过程中，一旦出现子串β与某条规则的右部相同，就可以使用这条规则进行归约,简单优先分析法就是采用此方法进行归约。

但这种限制，实际上也限制了文法的表达能力，所以通常是通过在句型中寻找所谓的“句柄”的途径解决的。

短语、直接短语、句柄

设G[S]是一文法，αβδ是文法G的句型，如果有S=>^*^αAδ且A=>^+^β，则称β是句型αβδ的、相对于非终结符A的短语。

特别地，当A=>^+^β实际是A=>β即一步推导时，则又称β是句型αβδ的、相对于非终结符A的直接短语（或简单短语）。

句型的最左直接短语，称为该句型的句柄。

短语的理解：

“αβδ是文法G的句型”，即S =>^*^αβδ

“S=>^*^αAδ且A=>^+^β”，即S=> … =>αAδ=> … =>αβδ

这表明，如果β是句型αβδ的、相对于A的短语，则至少存在一个推导，使得αAδ =>^+^ αβδ，或者αβδ<=^+^ αAδ。

特别地，如果β是直接短语，则αAδ => αβδ，或者αβδ<=αAδ。

【直接短语、短语都是某一个句型的子串】

在语法树中，短语是子树的叶子的组合；直接短语是两层子树的末端【i3和F1是两层子树】

文法在实用中的一些说明

在实际应用中，对于文法规则提出了一些限制条件，但这些并没有限制文法的语言描述能力。限制下列 3种规则的使用：

（1）有害规则 形如U→U的规则，称为有害规则。

（2）不可达规则 不在任何规则右部出现的非终结符对应的规则，称为不可达规则。

（3）不可终止规则 如果从某非终结符开始，不可能推导出任意终结串来，则该非终结符对应的规则称为不可终止规则。

不含有多余规则的文法，称为压缩过的文法。在后面讨论的文法时，都假设是压缩过的的文法。

ε规则问题

在文法设计中，使用ε规则有时会带来方便，但会导致文法讨论和证明的复杂。

一个上下文无关文法G是否必须使用ε规则，完全取决于文法G产生的语言L(G[S])中是否含有ε语句。

可以证明，如果ε不属于L(G[S]),则存在一个等价的文法G’[S’] ，且G’ 不含ε规则。

如果ε∈ L(G[S]),则存在一个等价的文法G’[S’] ，且G’ 仅含S’ →ε的一个空规则。

提示：使用“代入法”，即可得到等价的文法G’(S’)