本章讲述目前广泛使用的上下文无关文法。即用上下文无关文法作为程序设计语言语法的描述工具。阐明语法的一个工具是文法。本章将介绍文法和语言的概念。
本章重点：上下文无关文法及其句型分析中的有关问题。
第一节文法的直观概念。
当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。
以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明（或者定义）句子的组成结构，比如：“我是大学生”。是汉语的一个句子。
汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用ebnf来表示这种句子的构成规则：
句子〉∷＝主语〉〈谓语〉
主语〉∷＝代词〉|〈名词〉
代词〉∷＝我|你|他。
名词〉∷＝王明|大学生|工人|英语。
谓语〉∷＝动词〉〈直接宾语〉
动词〉∷＝是|学习。
直接宾语〉∷＝代词〉|〈名词〉
我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据。
一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子。我们开始去找∷＝左端的带有〈句子〉的规则并把它表示成∷＝右端的符号串，这个动作表示成：〈句子〉〈主语〉〈谓语〉，然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应的规则∷＝右端代替之。
比如，选取了〈主语〉,并采用规则〈主语〉∷＝代词〉，那么得到：〈主语〉〈谓语〉〈代词〉〈谓语〉，重复做下去，我们得到句子：“我是大学生”的全部动作过程是：
句子〉〈主语〉〈谓语〉
代词〉〈谓语〉
我〈谓语〉我〈动词〉〈直接宾语〉
我是〈直接宾语〉
我是〈名词〉
我是大学生。
符号的含义是，使用一条规则，代替左边的某个符号，产生右端的符号串。
显然，按照上述办法，不仅生成“我是大学生”这样的句子，还可以生成“王明是大学生”，“王明学习英语”，“我学习英语”，“他学习英语”，“你是工人”，“你学习王明”等几十个句子。事实上，使用文法作为工具，不仅为了严格地定义句子的结构，也是为了用适当条数的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。
第二节符号和符号串。
符号和符号串，在形成语言中和编译技术中是很重要的概念。任何一种语言，都是由许多语言的基本符号组成的符号串的集合。如：
英语的基本符号有26个字母和一些标点符号，英语，就是由这些符号所组成的符号串的集合。
一）字母表和符号串。
字母表是元素的非空有穷集合，字母表中的元素称为符号。由字母表中的符号所组成的任何有穷序列称之为“符号串”。
例如： 00，01，10 是字母表σ＝上的符号串，又如ab，abc，bc 是字母表σ＝上的符号串。还允许有空符号串。
空符号串是不包含任何符号的符号串。用ε表示，其长度为0，即|ε|0。
二）符号串的运算。
相等 x＝y当且仅当组成x的诸符号与组成y的诸符号依次相等，σ＝
x＝abbc y＝abbc x＝y x＝ab y＝ba x≠y
1 符号串的长度，x是符号串，则其长度用|x|表示。其数值等于组成该符号串的符号个数。
如：x＝stv |x|＝3 而 |ε0
符号串s的前缀：移走符号串s尾部的零个或多于零个符号得到的符号串如： b是符号串banana的一个前缀。
符号串s的后缀：删去符号串s头部的零个或多于零个符号得到的符号串如：nana是符号串banana的一个后缀。
z＝abc，那么z的前缀。是ε，a，ab，abc
z的后缀。ε，c，bc，abc
符号串的联接，x和y是符号串，它们的联接xy是把y的符号写在x的符号之后，得到的符号串。
x＝st y＝abu xy＝stabu
x|＝2 |y|＝3 |xy|＝5 由于ε的含义。
显然有εx＝xε＝x
符号串的方幂，x是符号串，把x自身连接几次得到的符号串z，z＝xx……xx ， z＝xn
x0＝εx1＝x
x2＝xxx＝abc x0＝ε x1＝abc x2＝abcabc……
n＞0有xn＝xxn-1＝xn-1x
集合的乘积运算。
符号串的集合：若集合a中的一切元素都是某字母表上的符号串，则称a为该字母表上的符号串集合。
ab＝如：a＝ b＝ ab＝
对于任意符号串x总有εx＝xε＝x
a＝a＝a集合a的闭包a*和集合a的正闭包a+
a+＝a1∪a2∪a3……an∪……
a*＝a0∪a+a＝a+＝
a*＝第三节文法和语言的形式定义。
规则，也称重写规则、产生式，是形如α→β或α∷＝的（α，有序对，α是规则的左部，β是规则右部。
∈v+ βv* v为某字母表。
定义1 文法g定义为四元组（vn，vt，p，s）。
其中vn为非终结符号集。
vt终结符号集非空有穷集。
p产生式的集合。
s称为识别符号或开始符号，它是一个非终结符，它至少要在一条规则中作为左部出现。
vn∩vt＝φ v＝vn∪vt v称为文法g的字母表。
定义2，如α→β是文法g＝（vn，vt，p，s）的规则，γ和δ是v*中的任意符号，若有符号串v，w满足v＝γαw＝γβ
则说v（应用规则α→β直接产生w或说w是v的直接推导或说w直接归约到v记作vw
如，对于g[s] ：s→0s1，s→01
v＝0s1 w＝0011 直接推导：0s10011，使用的规则s→01 这里γ＝0 ，δ1
v＝s， w＝0s1 直接推导：s→0s1 使用的规则：s→0s1，这里γ＝ε
定义3，如果存在直接推导的序列：
v＝wow1w2……wn＝w（n＞0）
则称v推导出w或称w归约到v。记作vw。
定义4 若有vw，或v＝w，则记作vw
如，对于g[s] s→0s1，s→01存在直接推导序列。
v＝0s100s11000s11100001111＝w，即0s100001111也可记作0s100001111
定义5，设g[s]是一文法，如果符号串x是从识别符号推导出来的，即sx，则称x是文法g[s]的句型。若x仅由终结符号组成，即sx x∈vt* s：识别符号，则称x是文法g[s]的句子。
定义6，文法g所产生的语言l（g）=，即文法g[s]所产生的所有句子的集合。
形式语言理论可以证明如下两点：
a、 给定一个文法，就能从结构上唯一地确定其语言g→l（g）
b、 给定一种语言，能确定其文法，但这种文法不是唯一的l→g1或g2，……
在此我们用例子说明。
如文法g[z]：
1）z→azb
2）z→ab
由该文法所确定的语言为：
用规则（1）：za zba2zb2…an-1zbn-1
用规则（2）：anbn
所以，：l（g[z]）=
又如已知语言为：
l（g）= 可构造其文法g： g：z→ a b a b→ b b|b
对于上述语言，还可构造文法g′ g′：z→a b b→bb|b
很显然，g不同于g′。对上述语言还可以构造出其他文法。
定义7，若l（g1）＝l（g2）则称文法g1和g2是等价的。
第四节文法的类型。
乔姆斯基把文法分成四种类型，即0型、1型、2型和3型。这几类文法的差别在于对产生式施加不同的限制。
1、设g=（vn，vt，p，s），如果它的每个产生式α→β是这样一种结构：α∈vn∪vt) *且至少含有一个非终结符，而β∈(vn∪vt) *则g是一个0型文法。
0型文法也称短语方法。一个非常重要的理论结果是，0型文法的能力相当于图灵机（turing）。
2、设g=（vn，vt，p，s）为一文法，若p中的每一个产生式α→β均满足指符号串α的长度，仅仅s→ε除外，则文法g是1型或上下文有关的。
3、设g=（vn，vt，p，s），若p中的每一个产生式α→β满足：α是一非终结符，β∈vn∪vt) *则此文法称为2型的或上下文无关的。
例 g=（｛s，a，b｝，｛a, b｝，p，s），其中p由下列产生式组成：
s→aba→baa
s→bab→b
a→ab→bs
a→asb→abb
有时，为书写简洁，常把相同左部的生产式，形如。
a→α1a→α2
a→αn缩写为：
a→α1|α2|…|n
这里的元符号“|”读做“或”。
上例的p可写为：
s→ab | ba
a→a |as| baa
b→b |bs| abb
4、设g=（vn，vt，p，s），若p中的每一个产生式的形式都是a→ab或a→a，其中a和b是非终结符，a是终结符，则g是3型文法或正规文法。
例文法g=（｛s，a，b｝，｛0，1｝，p，s），其中p由下列产生式组成：
s→0aa→1b
s→1bb→1b
s→0b→1
a→0ab→0
a→0s显然g是正规文法。
四个文法类的定义是逐渐增加限制的，因此每一种正规文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是0型文法。
第五节上下文无关文法及其语法树。
上下文无关文法有足够能力描述现今程序设计语言的语法结构，如算术表达式，各种语句等。
一）语法树：上下文无关文法句型推导的**过程。
给定文法g＝（vn，vt，p，s）对于g的任何句型都能构造与之关联的语法树。
这棵树满足下列4个条件：
1、每个结点都有一个标记，此标记是v的一个符号。
2、根的标记是s
3、若一结点n至少有一个它自己除外的子孙，并且有标记a，则a肯定在vn中。
4、如果结点n的直接子孙，从左到右的次序是结点n1，n2，…，nk，其标记分别为a1，a2，…，ak，那么a→a1a2…ak一定是p中的一个产生式。
从一个例子来说明某语法树的构造。
例1 g[s] =s，a｝，｛a, b｝，p，s），其中p为：
1）s→aas
编译原理第二章作业
1.pl 0语言允许过程嵌套定义和递归调用，试问它的编译程序如何解决运行时的存储管理。pl 0 语言允许过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动态存储管理。数组 code 存放的只读目标程序，它在运行时不改变。运行时的数据区 s 是由解释程序定义的一维整型数组，解释执行时对数据空间 ...
编译原理答案第二章
第二章词法分析 2.1 完成下列选择题 1 词法分析器的输出结果是 c a.单词的种别编码 b.单词在符号表中的位置。c.单词的种别编码和自身值 d.单词自身值。2 正规式m1和m2等价是指 c a.m1和m2的状态数相等 b.m1和m2的有向边条数相等。c.m1和m2所识别的语言集相等 d.m1和...
编译原理第二章习题
第2章习题。1 文法g s 为 s ac ab a ab b bc 写出l g s 的全部元素。答案 s ac abc 或s ab abc 所以l g s 2 令文法g为 n d nd d 0 1 2 3 4 5 6 7 8 9 1 g的语言l g 是什么？2 给出句子0568的最左推导和最右推导。...