上下文无关文法的基本概念
定义：上下文无关文法G是一个四元组G = (N，T，P，S)，其中
N是非终结符的有限集合；
T是终结符或单词的有限集合，它与N不相交；
P是形如A →α的产生式的有限集合，其中A∈N,α∈V﹡,V=T∪N
S是N中的区分符号，称为开始符号或句子符号。V中的符号称为文法符号，包括终结符和非终结符。
特殊情况：A →ε空产生式
例如，if语句结构的文法产生式表示：
stmt →if expr then stmt else stmt
Backus - Naur范式（Backus-Naur form）或BNF文法
符号的使用约定：
符号是终结符：
字母表中比较靠前的小写字母，如a，b，c等。
操作符，如+、-等。
标点符号，如括号、逗号等。
数字0，1， (9)
黑体串，如id、if等。
符号的使用约定：
下列符号是非终结符：
字母表中比较靠前的大写字母，如A、B、C等。
字母S，它常常代表开始符号。
小写斜体名字，如expr、stmt等。
字母表中比较靠后的大写字母，如X、Y、Z等，表示文法符号，也就是说，可以是非终结符也可以是终结符。
符号的使用约定：
字母表中比较靠后的小写字母，如u，v，…，z等，表示终结符号的串。
小写希腊字母，如α、β、γ等，表示文法符号的串。因此，一个通用产生式可以写作A →α，箭头左边（产生式左部）是一个非终结符A，箭头右边是文法符号串（产生式右部）。
符号的使用约定：
如果A →α1、A →α2、…、A →αk 是所有以A为左部的产生式（称为A产生式），则可以把它们写成A →α1|α2|…|αk，我们将α1、α2、…、αk称为A的候选式。除非另有说明，否则第一个产生式左部的符号是开始符号。
例1考虑下面的关于简单算术表达式的文法，非终结符为<表达式>和<运算符>，终结符有ID,+,-,*,/,↑,(,)。产生式有
<表达式> → <表达式> <运算符> <表达式>
<表达式> → (<表达式>)
<表达式> → - <表达式>
<表达式> →ID
<运算符> → +
<运算符> → -
<运算符> → *
<运算符> → /
<运算符> →↑
正规表达式和上下文无关文法的关系：
正规表达式所描述的每一种语言结构都可以用上下文无关文法来描述。
NFA转换成一个等价CFG(上下文无关文法)
对NFA的每个状态i，创建一个非终结符Ai。
如果在状态i输入符号a转换到状态j,则引入产生式Ai →a Aj 。
如果在状态i输入符号ε转换到状态j, 则引入产生式Ai →Aj。
如果状态i是接受状态，则引入产生式Ai →ε。
如果状态i是开始状态，则Ai 是文法的开始符号。
分析和推导
文法是用来定义一个语言的，那么，它是如何定义的？
分析树的建立过程
推导，其核心思想是把产生式看成重写规则，即用产生式右部的串来代替左部的非终结符，实际上也可以看成是从上而下推导分析树的精确描述
表达式(52-6) * 32的推导过程：
E?E op E[E→E op E]
?( E)op E[E→(E)]
?( E) op number[E→number]
?( E)* number[op →*]
?(E op E) * number[E→E op E]
?(E op number) * number[E→number]
?(E– number) * number[op →-]
?(number – number) * number[E→number]
如果α1 ?α2 ?α3 ?α4 ?α5 ?α6…?αn ,则说α1推导出αn。一般，符号?表示“一步推导”，通常我们用?*表示“零步或多步推导”，用?+表示“一步或多步推导”
由推导从E 符号中得到的所有记号符号的串集是被表达式的文法定义的语言。这个语言包括了所有合乎语法的表达式。由上下文无关文法产生的语言称为上下文无关语言，如果两个文法产生同样的语言，则称这两个文法等价。
可将它用符号表示为：
L (G) = {s | E ?* s }
其中G代表表达式文法，s 代表记号符号的任意数组串。
文法生成的语言示例：
例考虑带有单个文法规则的文法G E →(E )|a
例考虑带有单个文法规则文法G: E →(E)
例考虑带有单个文法规则E → E + a | a的文法G
例考虑下面语句的极为简化的文法：
statement →if-stmt|other
if-stmt →if (exp) statement
| if (exp) statement else statement
exp →0|1
other
if ( 0 ) other
if ( 1 ) other
if ( 0 ) other else other
if ( 1 ) other else other
if ( 0 ) if ( 0 ) other
if ( 0 ) if ( 1 ) other else other
if ( 1 ) other else if ( 0 ) other else other
...
两种推导的主要方法：
?最左推导：每一步都替代最左非终结符的推导。
?最右推导：每一步推导都替代最右非终结符的推导
分析树
分析树是抽去了代换顺序的推导图表示。分析树中每棵子树的根，也就是树的内部节点，都是文法的非终结符，子树本身是被代换的符号的产生式的右部。文法开始符号总是整棵分析树的根。分析树的叶节点，即树中无子树的节点，或为非终结符，或为终结符，从左至右读，就构成了一个句型。句子的分析树的叶节点就得到了该句子的串。
二义文法
给定一个文法G，如果L（G）中存在一个具有两棵或两棵以上分析树的句子，则称G是二义性的。针对句子3+5*7，该文法就有两棵不同的语法树。
文法的设计
对输入进行语法分析的过程基本上是为其建立分析树或建立最左（最右）推导的过程。一般，每种分析方法只能处理某种形式的文法。因此，虽然语言的设计者给出了定义程序设计语言的文法，但是，为了适应所选择的分析方法，还需常常改写初始文法。如适合于表达式的文法常常用结合律和优先级的信息来构造。
如何设计好文法，使其能够更好适应分析方法，包括消除二义性、消去左递归等等。
验证由文法产生的语言
从给定的文法定义，推导出它所生成的语言。验证给定的文法或产生式集合是否产生指定的语言是非常重要的。可以从两方面进行，
为语言设计精确的抽象的文法；
推导文法所生成的语言。
对“文法G产生语言L”的证明包括两部分：
证明由G产生的每个字符串都在L中。
证明L中的每个字符串都能有G产生。
消除二义性
必要性
有两个解决二义性的基本方法：
设置一个规则，该规则可在每个二义性情况下指出哪一个分析树（或语法树）是正确的。这样的规则称作消除二义性规则。
将文法改变成一个强制正确分析树的构造的格式，这样就可以解决二义性了。
优缺点比较：
消除二义性
重写规则后使得所有的运算都是左结合：
E →E addop term | term
addop →+ | -
term →term mulop factor | factor
mulop →*
factor →( E ) | number
消除二义性－“悬挂else”的问题
stmt →if expr then stmt
| if expr then stmt else stmt
| other
消除二义性－“悬挂else”的问题
每个else 都同其前面最近的未匹配的then 相匹配
改写后的文法如下：
stmt →matched_stmt | unmatched_stmt
matched_stmt →if expr then matched_stmt else matched_stmt
| other
unmatched_stmt →if expr then stmt
| if expr then matched_stmt else unmatched_stmt 消除左递归
递归定义
自顶向下语法分析法不能处理左递归文法
左递归的情况分三种：
简单直接左递归
普遍直接左递归
间接左递归
消除左递归－简单直接左递归
左递归只出现在如下文法规则中
A →A α | β
其中α和β是终结符和非终结符的串，而且β不以A 开头。
重写为两个规则：
A →βAˊ
Aˊ→αAˊ| ?
消除左递归－普遍直接左递归
如下格式的产生式：
A →A α1 | A α2 | . . . | A αn | β1 | β2 | . . . |βm
其中β1, . . . , βm均不以A 开头。
重写为两个规则：
A →β1 Aˊ| β2 Aˊ| . . . |βm Aˊ
Aˊ→α1Aˊ| α2Aˊ| . . . |αn Aˊ|ε
消除左递归－间接左递归
至少有一步是以相同的非终结符：
A?α?* A 开始和结束的推导
该算法的方法是：为语言的所有非终结符选择任意
顺序，如A1 , . . . , A m，接着它消除所有A i→A j γ，
其中j≤i 形式的文法规则的左递归。如果按这样操
作从1 到m的每一个i，则由于这样的循环的每个步
骤只增加索引，且不能再次到达原始索引，因此就
不会留下任何递归循环了。
例考虑下面的算术表达式文法：
E→E + T |T
T→T * F |F
F→( E ) | id
消除E和T的直接左递归，可以得到
E →T Eˊ
Eˊ→+ T Eˊ|ε
T →F Tˊ
Tˊ→* F Tˊ|ε
F→( E )|id
例考虑下面的文法：
A →
B a | A a | c
B →B b | A b | d
令A1 = A，且A2 = B，当i = 1时，得到的文法是：
A →
B a Aˊ| c Aˊ
Aˊ→a Aˊ|ε
B →B b | A b| d
当i = 2得到了文法：
A →
B a Aˊ| c Aˊ
Aˊ→a Aˊ|ε
B →B b | B a Aˊb | c Aˊb | d
最后消除B 的直接左递归后得到
A →
B a Aˊ| c Aˊ
Aˊ→a Aˊ|ε
B →c Aˊb Bˊ| d Bˊ
Bˊ→b Bˊ| a Aˊb Bˊ|ε
提取左因子
当两个或更多文法规则选择共享一个通用前缀串时，需要提取左因子。Why?
提取左因子
提取方法：
A →?αβ|αγ?
将左边的α分解出来，把用哪个产生式展开的决定推迟到可以看到足够的输入信息才作。并将该规则重写为两个规则
A →αAˊ?
Aˊ→β |γ?
提取左因子
一般提取方法：
A →?αβ1 | αβ2|……| αβn
将左边的α分解出来，把用哪个产生式展开的决定推迟到可以看到足够的输入信息才作。并将该规则重写为两个规则
A →α Aˊ
Aˊ→β1 | β2|……| βn
提取左因子
例：S →i E t S | i E t S e S | a
E →b
提取左因子后，该文法变为：
S →i E t S S’ | a
S’ →e S | ε
E →b
上下文无关文法的局限
4种文法——非限制的、上下文有关的、上下文无关的和正则的，分别被称为0型、1型、2型和3型文法。它们构成的语言类称为以乔姆斯基命名的乔姆斯基层次（Chomsky hierarchy）。
乔姆斯基层次及
语言文法模型
正则语言右线性文法有穷自动机
上下文无关语言上下文无关文法下推自动机
上下文有关语言上下文有关文法线性有界自动机
递归可枚举语言非限制文法图灵机
课后习题
Page 80：3，9
_
第三部分上下文无关语言和下推自动机 前面介绍的有限自动机是计算的初级模型，它所接受的正规语言不太关心字符串自身的结构。上下文无关文法（CFL）是一种简单的描述语法规则的递归方法，语言中的字符串由这些规则产生。所有的正规语言都能用上下文无关文法描述，它也可以描述非正规语言。上下文无关文法描述的语法规则更复杂多变，可以在相当大的程度上，描述高级程序设计语言的语法和其他一些形式语言。 类似正则语言对应的抽象机模型是有限自动机，CFL也有对应的抽象机模型。CFL对应的计算模型是在有限自动机的基础上增加存储空间得到，并被设想成无限空间（对应有限自动机的有限空间），采用了一种简单的管理模式，栈（stack），这种新的计算模型（或抽象机）称为下推自动机（pushdown automata），下推是栈最典型的操作。有必要在下推自动机中保留非确定性，确定型下推自动机不能接受所有的CFL，但给定一个CFG，容易构造一个相应的非确定型下推自动机，它在识别字符串过程中的移动模拟了文法的推导过程，这个过程称为分析（parse）。分析不是一定需要下推自动机来完成。 CFL仍然不够通用，不能包括所有有意义的、或有用的形式语言。采用类似第五章的技术，我们将给出一些不是CFL的简单例子，这些技术也用于解决与CFL相关的判定问题。 6 上下文无关文法 6.1 上下文无关文法的定义 为了描述我们在第二部分考察的各种语言，包括一些非正则语言，我们引入一种语言的递归定义方法，称为文法。文法与我们熟悉的语言的语法描述相近，是描述语言和分析语言的有力工具。 问题：文法的形式化定义似乎可以模仿有限自动机，比如5元组或6元组之类。 例子6.1 正如我们在例子2.16中所见，字母表{a, b}上的回文语言pal可以用下面的递归方法描述： 1.Λ, a, b∈pal 2.对每个S∈pal，aSa和bSb也属于pal 3.pal中不包含其他字符串 如果将上面的符号S看成一个变量，代表了所有我们希望计算（比如某种递归算法）的pal 的元素，那么上面的规则1和规则2可以非正式地重新表述如下： 1.S的值可以是Λ, a, b 2.每个S可以写成aSa或bSb的形式 如果我们用→表示“可以取值为”，则可以写出下面的式子： S→aSa→abSba→abΛba=abba 上面的产生过程可以总结成下面的两组产生式（或称规则）： S→a | b | Λ S→aSa | bSb 符号“|”表示“或”的含义。上式的含义是aSa或bSb，而不是a或b，即连接运算的优先级高于“|”。我们使用的这套术语中，小写字母a和b表示终结符，大写字母S表示非终结符，或称变量。总共有5条规则，或产生式（production）。符号S是非终结符，也是起始终结
作 业 一、选择题 1.、程序中出现的错误常数 3.14.15属于__(A)__。 (A) 语法错误 (B) 词法错误 (C) 语义错误 (D) 警告错误 2、表达式α0 αn 代表____(B)____ 。 (A) 直接推导 (B) 广义推导 (C) 推导 (D) 间接推导 3、文法),},,,{)},(,,*,,({2P +=E F T E i G 其中：产生式P 为： i E F F F T T T T E E |)(|*|→→+→ 则句型T+T*i+F 中的句柄是__(A)___。 (A) T (B) i (C) T*i (D) i+F 4、文法b B a aA A AS AB S →→→,|,|与下列哪个正规式等价__(B)___。 (A)+b aa * (B)b aa * (C)*)(ab (D) *)(ab a ； 第二题：（清华大学年考研试题）已知文法G[S]为： S → dAB A → aA | a B → Bb | ε G[S]产生的语言是什么？（请用自然语言或表达式描述语言特征） 答案：da +b * 第三题：（1） 构造一个文法G ，使得：L(G)={a 2m b m |m>0} （2） 构造一个文法G ，使得：L(G)={a n #b n | n>0} （3） 写出以0开头的8进制无符号整数的文法。
答案：(1) S→aaSb | aab (2) S→aSb | a#b (3) S→0 N N→DN | D D→0|1|2|3|4|5|6|7 四、有文法G[S]： S → a | ( T ) |ε T →T，S | S （1）请给出句子(a，(a，a))的最左、最右推导。 （2）请给出句子(a，(a，a))的短语、直接短语和句柄。答案：（1）最左推导： S=>（T） =>（T,S） =>（S，S） =>（a，S） =>（a，（T）） =>（a，（T，S）） =>（a，（S，S）） =>（a，（a，S）） =>（a，（a，a）） 最右推导： S=>（T） =>（T，S） =>（T，（T）） =>（T，（T，S）） =>（T，（T，a）） =>（T，（S，a）） =>（T，（a，a）） =>（S，（a，a）） =>（a，（a，a））
HUNAN UNIVERSITY 计算理论导引实验报告 题目：上下文无关文法（CFG）学生姓名： 学生学号： 专业班级：计算机科学与技术2班 上课老师： 实验日期：2014-1-5
一、实验目的 (2) 二、实验内容.......................................................................................... 错误！未定义书签。 三、实验代码.......................................................................................... 错误！未定义书签。 四、测试数据以及运行结果 (9) 五、实验感想 (13)
一、实验目的 1、掌握上下文无关文法概念。 2、掌握用动态规划算法验证某个字符串w是否属于某上下文无关文法。 二、实验内容 对于任意给定的一个上下文无关文法，并对任意字符串w, 用动态规划算法判断是否有w∈L(G)。 编写一个算法/程序，对于给定的输入
第2章习题解答 1.文法G[S]为： S->Ac|aB A->ab B->bc 写出L(G[S])的全部元素。 [答案] S=>Ac=>abc 或S=>aB=>abc 所以L(G[S])={abc} ============================================== 2. 文法G[N]为： N->D|ND D->0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？ [答案] G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD.... =>NDDDD...D=>D......D =============================================== 3.已知文法G[S]： S→dAB A→aA|a B→ε|bB 问：相应的正规式是什么？G[S]能否改写成为等价的正规文法？[答案] 正规式是daa*b*；
相应的正规文法为(由自动机化简来)： G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b 也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε ===================================================================== ========== 4.已知文法G[Z]： Z->aZb|ab 写出L(G[Z])的全部元素。 [答案] Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb L(G[Z])={a n b n|n>=1} ===================================================================== ========= 5.给出语言{a n b n c m|n>=1,m>=0}的上下文无关文法。 [分析] 本题难度不大，主要是考上下文无关文法的基本概念。上下文无关文法的基本定义是：A->β,A∈Vn，β∈（Vn∪Vt）*，注意关键问题是保证a n b n的成立，即“a与b的个数要相等”，为此，可以用一条形如A->aAb|ab的产生式即可解决。 [答案] 构造上下文无关文法如下： S->AB|A A->aAb|ab B->Bc|c [扩展]
1 引言 几乎所有程序设计语言都是通过上下文无关文法来定义的。一个原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法,而且从另外一方面，上下文无关文法又足够简单，使得我们可以构造有效的分析算法来检验一个给定字符串是否是由某个上下文无关文法产生的。具体的例子可以参见LR分析器和LL分析器. 2 定义 上下文无关文法（英语：context-free grammar，缩写为CFG），在计算机科学中，若 一个形式文法G = (V, Σ, P, S) 的产生式规则都取如下的形式：A -> α，则谓之。其中A∈V ，α∈(V∪Σ)*。上下文无关文法取名为“上下文无关”的原因就是因为字符 A 总可以被字符串α自由替换，而无需考虑字符 A 出现的上下文。一个形式语言是上下文无关的，如果它是由上下文无关文法生成的. 正则语言和正则表达式，一个正则表达式可以用来表示一个句子集合（正则语言），且每个正则表达式都可以构造出有限状态自动机来判断任意的句子是否属于这个句子集合。因此，用正则表达式来表示正则语言是精确的、可操作的。 那么，可以用正则表达式来表示程序语言（比如 C 语言）所代表的句子集合吗？ 很遗憾，答案是否定的。正则表达式毕竟太简单了，无法来表示程序语言这样复杂级别的句子集合。 为了表示程序语言的句子集合，需要采用表达能力更强大的工具——上下文无关语 法（context-free grammar）。 下面以一个简单的例子来说明什么是上下文无关语法，假设有一种非常非常原始的语言，我们把它成为 X 语言，它的句子只有：主语谓语宾语这样一种结构，主语中 只有我、你、他三个词，谓语中只有吃一个词.宾语中只有饭、菜两个词。我们 把它的语法写出下面这样的形式： 语句 -> 主语谓语宾语 主语 -> 我 主语 -> 你 主语 -> 他 谓语 -> 吃 宾语 -> 饭 宾语 -> 菜 可以看出， X 语言总共只有 6 个句子： { 我吃饭, 我吃菜, ..., 他吃菜 }。也就是说，我们可以用上面这个语法来表示 X 语言这个集合，我们可以从第一行的“语句 -> 主语谓语宾语” 开始，分别将主、谓、宾替换成可用的词，从而将所有满足语法的句子都推导出来。对于任意一个句子，我们也可以将句子和此语法来对比，判断它是否属于满足 X 语言。 上面这个语法中的每一行形如“语句 -> 主语谓语宾语” 的式子称为产生式（production）。 产生式左侧的符号（语句、主语、谓语和宾语）称为非终结符（nonterminal）， 代表可以继续扩展或产生的符号，也就是说，当在某条产生式的右边遇到了此非终结符的时候，总是可以用本产生式的右边来替换这个非终结符。 而“我、你、他、吃、饭、菜” 这些符号是 X 语言中的词，无法再产生新的符号了，称为终结符（terminal）。终结符只能出现在产生式的右边，非终结符则左边和右边都可以出现。
8 上下文无关语言和非上下文无关语言 8.1 上下文无关语言的泵引理 从第6章到第7章，我们给出了两种描述CFL的模型，CFG和PDA。这两种模型都没有提供直接、明确的方法来判断一个形式语言不是CFL。然而，正如例子6.7对自然语言的一个简单考察，我们发现CFG存在描述能力的局限。本节中，我们精确定义和讨论CFL的一个性质，它类似于正则语言的泵引理。利用这个性质能够发现许多不是CFL的语言。 正则语言的泵引理基于这样的事实，如果一个足够长的输入字符串x导致FA在状态转移中，到达某个状态超过一次，即接受路径上存在回路，根据回路容易将x分成三部分，u是回路之前的字符串，v是回路的字符串，w是回路后的字符串，那么在回路上的多次重复，得到的新的字符串也应该被FA接受，即对任意的m>=0，uv m w被FA接受。如果我们用CFG生成（而不是PDA移动）CFL，容易得到类似的观察。设CFG G的一个推导出现同一个非终结符的嵌套重复，如下面的形式， S?*vAz?*vwAyz?*vwxyz 其中，v, w, x, y, z∈∑*。推导过程中，出现了A?*wAy，我们可以多次重复这个推导过程，如 S?*vAz?*vwAyz?*vw2Ay2z?*vw3Ay3z?*...?*vw m Ay m z 又由于A?*x，因此所有这类字符串vxz, vwxyz, vw2xy2z, ..., vw m xy m z都输入语言L(G)。 为了将上面的观察总结成CFL的泵引理，我们必须说明对于足够长的字符串的推导过程中都会出现非终结符的嵌套重复。同时我们也尽量发现分解得到的5个子串：v, w, x, y, z，的一些性质。这类似于我们处理正则语言的泵引理。 在6.6节，我们证明了所有的CFG产生式都可以改写成Chomsky范式，而不会影响CFG 接受语言的能力（唯一的影响是不能接受空字符，由于此处仅仅关心足够长的字符串，因此这个影响可以忽略）。因此我们的讨论可以局限在Chomsky范式（CNF）表示的CFG，显然这类文法得到的推导树都是二叉树，即每个父节点至多有两个子节点。 我们先定义几个与二叉树相关的概念。路径是一串节点组成的序列，前后节点之间有父子关系；路径的长度是路径包含的节点的个数；二叉树的高度是最长路径的长度。由于非终结符数目有限，如果推导树足够高，那么存在一个路径，某个非终结符在该路径上出现了两次，即出现了前面提到的嵌套重复现象。 引理8.1 任给h>=1，如果二叉树的叶结点个数>2h-1，那么该二叉树的高度>h。 证明：这是一个数学问题。我们用数学归纳法证明它的逆反命题：如果二叉树的高度<=h，那么二叉树的叶节点个数<=2h-1。 1.归纳基础，h=1，此时二叉树只有一个根节点，它也是唯一的叶结点，命题成立。 2.归纳推理，设k>=1时，命题成立。要证明k+1时，命题也成立。设二叉树T的高度为 k+1，则它的根节点的两个子树（以子节点为跟的二叉树）的叶节点数都<=2k-1，因此T 的叶节点数<=2k-1+2k-1=2k。得证。 定理8.1 G=(V, ∑, S, P)是形式为CNF的CFG，共有p个非终结符，则对每个长度>=2p+1的属于L(G)的字符串，都能找到5个字符串v, w, x, y, z满足下面的条件： u=vwxyz |wy|>0 |wxy|<=2p+1 vw m xy m z∈L(G), ?m>=0 证明：根据引理8.1，任何一个生成u的推导树高度>=p+2，即至少存在一个长度>=p+2的路径，不妨设d是其中的一个，显然d的最底部是一个终结符，其上的符号都是非终结符，共
第3章、上下文无关语言习题解答 - 练习 3.1 回忆一下例3.3中给出的CFG G 4。为方便起见，用一个字母重新命名它的变元如下： E →E ＋T|T T →T ×E|F F →（E ）|a 给出下述字符串的语法分析树和派生。 a. a b. a+a c. a+a+a d. ((a)) 答： a. E T F a ??? b. E E T T F F a a a ?+?+?+?+ c. E E T E T F T F a F a a a a a ?+?++?++?++?++ d. ()()()(())(())(())(())E T F E T F E T F a ????????? 3.2 a. 利用语言A={a m b n c n | m,n ≥0}和B={a n b n c m | m,n ≥0}以及例3.20(语言B={a n b n c n | n ≥0}不是上下文无关的)，证明上下文无关语言在交的运算下不封闭。 b. 利用(a)和DeMorgan 律(定理1.10)，证明上下文无关语言在补运算下不封闭。 证明： a.先说明A,B 均为上下文无关文法，对A 构造CFG C 1 S →aS|T|ε T →bTc|ε //生成b n c n 对B,构造CFG C 2 S →Sc|R|ε R →aRb |ε //生成a n b n 由此知 A,B 均为上下文无关语言。 由例3.20, A ∩B={a n b n c n |n ≥0}（假设m ≤n ）不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。
b. 用反证法。 假设CFL 在补运算下封闭，则对于(a)中上下文无关语言A,B ，A ,B 也为CFL 。因为CFL 对并运算封闭，所以A B U 也为CFL ，进而知道A B U 为CFL 。由DeMorgan 定律A B A B =U I ，得出A B I 是CFL 。 这与(a)的结论矛盾，所以CFL 对补运算不封闭。 3.3 设上下文无关文法G ： R →XRX|S S →aTb|bTa T →XTX|X|ε X →a|b 回答下述问题： a. G 的变元和终结符是什么？起始变元是哪个？ 答：变元是：R ，X ，S ，T ；起始变元是R 。终结符是：a ，b ，ε b. 给出L(G)中的三个字符串。答：ab ，ba ，aab 。 c. 给出不在L(G)中的三个字符串。答：a ，b ，ε。 d. 是真是假：T aba ?。答：假 e. 是真是假：* T aba ?。答：真 f. 是真是假：T T ?。答：假 g. 是真是假：* T T ?。答：假 h. 是真是假：* XXX aba ?。答：真 i. 是真是假：* X aba ?。答：假 j. 是真是假：* T XX ?。答：真 k. 是真是假：* T XXX ?。答：真 l. 是真是假：*X ε?。答：假 m. 用普通的语言描述L(G)：
第 5 章上下文无关文法及语言 现在我们把注意力从正则语言转移到另外一大类语言上来，它们叫做“上下文无关语言”。这个语言类有着自然、递归的表示方法，这种表示方法叫做“上下文无关文法”。从1960年以来，上下文无关文法一直在编译技术中扮演着重要的角色。它们能够把分析器（一类用来在编译过程中发掘源程序结构的程序）的实现从一种费时的、不通用方式的设计工作转变成为一种能够很快完成的工作。近年来，上下文无关文法也被用来描述文档格式：XML（eXtensible Markup Language 可扩展标记语言）中使用的DTD（Document-Type Definition 文档类型定义）就是用来描述Web上的信息交换格式的。 在本章中，我们将首先介绍上下文无关文法的表示方法，然后将介绍怎样用文法来定义语言。我们将会讨论到“语法分析树”──对一个文法处在它所表示的语言的字符串中结构的图形描述。语法分析树是对一个编程语言的语法分析器的产物，也是通常用来获得程序结构的途径。 上下文无关语言还有另外一种等价的自动机表示叫做“下推自动机”。我们将在第6章介绍下推自动机。虽然它不如有穷自动机重要，但仍然要介绍它，原因是作为一种语言的定义机制来说，它跟上下文无关文法具有等价性，后面在第7章研究如何判定上下文无关语言以及研究上下文无关语言的封闭性时，这种等价性是非常有用的。 5.1 上下文无关文法 这一章的内容将从非形式化地介绍上下文无关文法的表示法开始。形式化的定义会在读者了解到这些文法的一些重要的能力之后给出。届时我们将会说明怎样形式地定义一个文法，并将介绍一种叫作“推导”的过程：它能够决定在一个文法的语言中到底有哪些串。 5.1.1一个非形式化的例子 下面来考虑一个“回文（palindrome）”的语言。“回文”是指正向和反向读起来都一样的串，比如otto或者madamimadam（“Madam, I’m Adam,”引自Eve在Eden的花园里听到的第一句话）。换句话说，串w是一个回文当且仅当w = w R。考虑简单些的情况——只需要描述字母表{0, 1}上的回文，这个语言包括像0110，11011这样的串，也包括空串ε，但不包括像011或0101这样的串。 很容易验证这个0,1上的回文语言L pal不是正则语言，要做到这点只需要使用泵引理即可：假设L pal是一个正则语言，令n是与其相关的常数，考虑回文串w = 0n10n，如果L pal 是正则的，那么我们就能够把w写为w = xyz，其中y由第一组0中的若干个（但至少一个）构成。接下来，如果L pal是正则的话那么xz也应该在L pal里。然而由于xz的两端的0的个数不同，进而可知它不可能是回文串，由此得出的矛盾可以推翻前面关于L pal是正则语言的假设。 对于什么样的0,1串在L pal里，有一个自然的、递归的定义，它从一个最基本的显然属于L pal中的串开始，接着利用一个最直观的思想：如果一个串在L pal里，那么它开头和结尾
上下文无关文法 形式语言理论中一种重要的变换文法，用来描述上下文无关语言，在乔姆斯基分层中称为2型文法。由于程序设计语言的语法基本上都是上下文无关文法，因此应用十分广泛。 简介 上下文无关文法（Context-Free Grammar, CFG） 在计算机科学中，G = (N, Σ, P, S) 的产生式规则都取如下的形式：V -> w，则称之为上下文无关的，其中V∈N ，w∈(N∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符V 总可以被字串w 自由替换，而无需考虑字符V 出现的上下文。一个形式语言是上下文无关的，如果它是由上下文无关文法生成的﹙条目上下文无关语言﹚。 来定义的。另一方面，上下文无关文法又足够简单，使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。例子可以参见LR 分析器和LL 分析器。
BNF ﹙巴克斯-诺尔范式﹚经常用来表达上下文无关文法。 文法规则使用相似的表示法。名字用斜体表示（但它是一种不同的字体，所以可与正则表达式相区分）。竖线仍表示作为选择的元符号。并置也用作一种标准运算。但是这里没有重复的元符号（如正则表达式中的星号*），稍后还会再讲到它。表示法中的另一个差别是现在用箭头符号“→”代替了等号来表示名字的定义。这是由于现在的名字不能简单地由其定义取代，而需要更为复杂的定义过程来表示，这是由定义的递归本质决定的。
文法规则是定义在一个字母表或符号集之上。在正则表达式中，这些符号通常就是字符，而在文法规则中，符号通常是表示字符串的记号。我们利用C中的枚举类型定义了在扫描程序中的记号；为了避免涉及到 特定实现语言（例如C 记号。此时的记号就是一个固定的符号，如同在保留字while 中或诸如+或: =这样的特殊符号一样，对于作为表示多于一个串的标识符和数的记号来说，代码字体为斜体，这就同假设这个记号是正则表达式的名字（这是它经常的表示）一样。 上下文无关文法的却利用了与正则表达式中极为类似的命名惯例和运算，二 recursive）。 例子 例子1一个简单的上下文无关文法的例子是：S -> aSb | ε 。这个文法产生了语言{anbn : n ≥ 0} 。不难证明这个语言不是正规的。 例子2 这个例子可以产生变量x,y,z 的算术表达式： S -> T + S | T - S | T T -> T * T | T / T | ( S ) | x | y | z 例如字串"( x + y ) * x - z * y / ( x + x )" 就可以用这个文法来产生。 例子3 字母表{a,b} 上 a 和 b 数目不相等的所有字串可以由下述文法产生： S -> U | V U -> T aU | T aT
基于上下文无关文法的句法分析
常宝宝 北京大学计算语言学研究所 chbb@https://www.doczj.com/doc/bd16882450.html,
句法分析导引
以“词”为单位的分析技术
词语切分(segmentation, tokenization) 形态分析(morphological analysis, lemmatization, stemming) 词类标注(part-of-speech tagging) ……
以“句”为单位的分析技术
句法分析(syntactic parsing) ……
以“篇”为单位的分析技术
指代分析(anaphora resolution) ……
句法分析关心句子的组成规律(词如何组成句子？)
句法学(syntax)
In linguistics, syntax is the study of the rules, or "patterned relations", that govern the way the words in a sentence come together. It concerns how different words are combined into clauses, which, in turn, are combined into sentences. From Wikipedia, the free encyclopedia 语言学中研究句子组成规则的学科是句法学
句子成分分析
句子是词的线性序列，但词和词之间结合的松紧程度 并不一样。
今天 上午 我们 有 两 节 课
句子在构造上具有层次性，较小的成分还可以进一步 组成较大的成分。
今天 上午 我们 有 两 节 课 | | | | | | | | |
不同性质的成分可以有不同的句法功能和分布，可以 区分成不同的类型。
名词短语 (可以充当主谓结构中的主语、述宾结构中的宾语等) 两节课 动词短语 (可以充当主谓结构中的谓语等)
上下文无关文法 百科名片 形式语言理论中一种重要的变换文法，用来描述上下文无关语言,在乔姆斯基分层中称为2型文法。由于程序设计语言的语法基本上都是上下文无关文法，因此应用十分广泛。 目录[隐藏] 简介 例子 范式 同态映射下的性质 文法形式和文法的相似性 文法的二义性 子文法类 [编辑本段] 简介 上下文无关文法（Content-Free Grammar, CFG） 在计算机科学中，若一个形式文法G = (N, Σ, P, S) 的 上下文无关文法 产生式规则都取如下的形式：V -> w，则称之为上下文无关的，其中V∈N ，w∈(N ∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符V 总可以被字串w 自由替换，而无需考虑字符V 出现的上下文。一个形式语言是上下文无关的，如果它是由上下文无关文法生成的﹙条目上下文无关语言﹚。 上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法；实际上，几乎所有程序设计语言都是通
上下文无关文法 过上下文无关文法来定义的。另一方面，上下文无关文法又足够简单，使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。例子可以参见LR 分析器和LL 分析器。 BNF ﹙巴克斯-诺尔范式﹚经常用来表达上下文无关文法。 文法规则使用相似的表示法。名字用斜体表示（但它是一种不同的 上下文无关文法 字体，所以可与正则表达式相区分）。竖线仍表示作为选择的元符号。并置也用作一种标准运算。但是这里没有重复的元符号（如正则表达式中的星号*），稍后还会再讲到它。表示法中的另一个差别是现在用箭头符号“→”代替了等号来表示名字的定义。这是由于现在的名字不能简单地由其定义取代，而需要更为复杂的定义过程来表示，这是由定义的递归本质决定的。 同正则表达式类似，文法规则是定义在一个字母表或
《编译原理》考试试题及答案（附录） 一、判断题： 1.一个上下文无关文法的开始符，可以是终结符或非终结符。 ( X ) 2.一个句型的直接短语是唯一的。 ( X ) 3.已经证明文法的二义性是可判定的。（ X ） 4.每个基本块可用一个DAG表示。（√） 5.每个过程的活动记录的体积在编译时可静态确定。（√） 6.2型文法一定是3型文法。（ x ） 7.一个句型一定句子。 ( X ) 8.算符优先分析法每次都是对句柄进行归约。 (应是最左素短语) ( X ) 9.采用三元式实现三地址代码时，不利于对中间代码进行优化。（√） 10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( x ) 11.一个优先表一定存在相应的优先函数。 ( x ) 12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 13.递归下降分析法是一种自下而上分析法。 ( ) 14.并不是每个文法都能改写成LL(1)文法。 ( ) 15.每个基本块只有一个入口和一个出口。 ( ) 16.一个LL(1)文法一定是无二义的。 ( ) 17.逆波兰法表示的表达试亦称前缀式。 ( ) 18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 19.正规文法产生的语言都可以用上下文无关文法来描述。 ( ) 20.一个优先表一定存在相应的优先函数。 ( ) 21.3型文法一定是2型文法。 ( ) 22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。 ( ) 二、填空题： 1.( 最右推导 )称为规范推导。 2.编译过程可分为（词法分析），（语法分析），（语义分析和中间代码生成），（代码优化）和（目 标代码生成）五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。 4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。 5.语法分析器的输入是（），其输出是（）。 6.扫描器的任务是从（）中识别出一个个（）。 7.符号表中的信息栏中登记了每个名字的有关的性质，如（）等等。 8.一个过程相应的DISPLAY表的内容为（）。 9.一个句型的最左直接短语称为句型的（）。 10.常用的两种动态存贮分配办法是（）动态分配和（）动态分配。 11.一个名字的属性包括( )和( )。 12.常用的参数传递方式有（），（）和（）。 13.根据优化所涉及的程序范围，可将优化分成为（），（）和（）三个级别。 14.语法分析的方法大致可分为两类，一类是（）分析法，另一类是（）分析法。 15.预测分析程序是使用一张（）和一个（）进行联合控制的。 16.常用的参数传递方式有（），（）和（）。 17.一张转换图只包含有限个状态,其中有一个被认为是（）态;而且实际上至少要有一个（）态。
上下文无关文法的基本概念 定义：上下文无关文法G是一个四元组G = (N，T，P，S)，其中 N是非终结符的有限集合； T是终结符或单词的有限集合，它与N不相交； P是形如A →α的产生式的有限集合，其中A∈N,α∈V﹡,V=T∪N S是N中的区分符号，称为开始符号或句子符号。V中的符号称为文法符号，包括终结符和非终结符。 特殊情况：A →ε空产生式 例如，if语句结构的文法产生式表示： stmt →if expr then stmt else stmt Backus - Naur范式（Backus-Naur form）或BNF文法 符号的使用约定： 符号是终结符： 字母表中比较靠前的小写字母，如a，b，c等。 操作符，如+、-等。 标点符号，如括号、逗号等。 数字0，1， (9) 黑体串，如id、if等。 符号的使用约定： 下列符号是非终结符： 字母表中比较靠前的大写字母，如A、B、C等。 字母S，它常常代表开始符号。 小写斜体名字，如expr、stmt等。 字母表中比较靠后的大写字母，如X、Y、Z等，表示文法符号，也就是说，可以是非终结符也可以是终结符。 符号的使用约定： 字母表中比较靠后的小写字母，如u，v，…，z等，表示终结符号的串。 小写希腊字母，如α、β、γ等，表示文法符号的串。因此，一个通用产生式可以写作A →α，箭头左边（产生式左部）是一个非终结符A，箭头右边是文法符号串（产生式右部）。 符号的使用约定： 如果A →α1、A →α2、…、A →αk 是所有以A为左部的产生式（称为A产生式），则可以把它们写成A →α1|α2|…|αk，我们将α1、α2、…、αk称为A的候选式。除非另有说明，否则第一个产生式左部的符号是开始符号。 例1考虑下面的关于简单算术表达式的文法，非终结符为<表达式>和<运算符>，终结符有ID,+,-,*,/,↑,(,)。产生式有 <表达式> → <表达式> <运算符> <表达式> <表达式> → (<表达式>) <表达式> → - <表达式> <表达式> →ID <运算符> → + <运算符> → - <运算符> → * <运算符> → / <运算符> →↑
例题2.1 是非题 1．因名字都是用标识符表示的，故名字与标识符没有区别。（） 2．正规文法产生的语言都可以用上下文无关文法来描述。（） 3．上下文无关文法比正规文法具有更强的描述能力。（） 分析 1．标识符是高级语言中定义的字符串，一般是以英文字母开头（包括大小写字母）的，由数字、字母和一些特殊字符（如下划线等）组成的一定长度（不同的高级语言对标识符的长度的规定不同）的字符串，它只是一个标志，没有其它含义。名字是用标识符表示的，但名字不仅仅是一个字符串，它还具有属性和值，就象一个人的名字不仅仅是一个符号，对于认识这个人的人来说，它还代表着这个人，因此本题错。 2．乔姆斯基把文法分成4种类型，从4种文法的形式化描述来看，它们的差别主要在对规则形式的约束上。0型文法的规则形式是：每个产生式α→β都满 足，α∈（V N ∪V T ）*且至少含有一个非终结符，β∈（V N ∪V T ）*，0型文法也叫短语 文法。1型文法的规则形式是：每个产生式α→β均满足|α|≤|β|，仅仅S→ε例外，且S不得出现在任何产生式的右部，1型文法也称上下文有关文法，从两种文法的规则形式来看，1型文法对规则形式的约束比0型文法强，1型文法能描述的语言0型文法也能描述，而0型文法能描述的语言1型文法不一定能够描述，1 型文法是0型文法的特例。2型文法的规则形式是A→β，其中A∈V N ，β∈（V N ∪ V T ）*，2型文法也称上下文无关文法，分析2型文法的规则形式不难发现，2型文法是1型文法的特例，也是0型文法的特例。3型文法的规则形式是A→αB或 A→α，其中α∈，A、B∈V N ，3型文法也称正规文法，可以看出3型文法是前面3种文法的特例。从上面的分析可以，正规文法是上下文无关文法的特例，可以用正规文法描述的语言，其正规文法描述的形式也是上下文无关文法的描述形式，即可以用上下文无关文法描述，因此本题对。 3．上下文无关文法是2型文法，正则文法是3型文法，从上题的分析可以看出，3型文法是2型文法的特例，3型文法可以描述的语言都可以用2型文法来描述，而2型文法可以描述的语言则不一定能用3型文法来描述。即2型文法比3型文法的描述能力强，因此本题对。 例题2.2 填空题 1．程序语言是由（）和（）两方面定义的。 3．文法G所产生的句子的全体的（），将它记为（）