文法和语言
形式语言基础
字母表和符号串
字母表：符号的非空有限集合 例：∑={a，b，c}
符号：字母表中的元素 例： a，b，c
符号串：符号的有穷序列 例：a, aa, ac, abc，.. 特别地，空符号串：无任何符号的符号串(ε)
符号串集合：由符号串构成的集合。
符号串和符号串集合的运算
符号串相等：若x、y是集合上的两个符号串，则x＝y当且仅当组成x的每一个符号和组成y的每一个符号依次相等。
符号串的长度：x为符号串，其长度|x|等于组成该符号串的符号个数。例： x＝STV ， |x|=3 特别地，|ε| =0
符号串的联接：若x、y是定义在Σ是上的符号串，且x＝XY，y＝YX，则x和y的联接 xy＝XYYX也是Σ上的符号串。 注意：一般xy≠yx，而εx＝xε＝x
符号串集合的乘积运算：令A、B为符号串集合，定义AB＝{ xy |x∈A，y∈B} 因为εx＝xε＝x，所以{ε}A= A{ε} =A
方幂运算
符号串集合的方幂 有任一符号串集合A，定义：$A^0=\lbrace\epsilon\rbrace，A^1=A，A^2=AA，A^3=AAA，...$
符号串的方幂 有任一符号串X，定义：$X^0=\epsilon，X^1=X，X^2=XX，X^3=XXX，...$
符号串集合的闭包运算：设A是符号串集合，定义
$A^+=A^1\cup A^2\cup A^3\cup ...\cup A^n$称为集合A的正则闭包
$A^*=A^0\cup A^1\cup A^2\cup...\cup A^n=A^0\cup A^+$称为集合A的星闭包
文法的直观理解
<句子>::=<主语><谓语> <主语>::=<代词>|<名词> <代词> ::=你|我|他 <名词>::= 王民|大学生|工人|英语 <谓语>::=<动词><直接宾语> <动词>::=是|学习 <直接宾语>::=<代词>|<名词>
什么是文法： 文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称为“语法”）。
语法规则： 我们通过建立一组规则（产生式），来描述句子的语法结构。规定用“::=”表示“由……组成”。
由产生式推导句子： 推导方法：从一个要开始的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。 例：<句子> => <主语><谓语> <主语><谓语> => <代词><谓语> ...... 这种推导一直进行下去，直到所有带< >的符号都由终结符号替代为止。
文法和语言的定义
文法的定义
定义: 文法G=（VN，VT，P，Z）
VN ：非终结符号集
VT ：终结符号集
P：产生式或规则的集合
Z：开始符号（识别符号） Z∈VN
其中: ①产生式：产生式是一个有序对(U, x), 通常写为： U ::=x 或U → x； |U|≧ 1 , |x| ≧ 0 ②非终结符号：出现在产生式的左部,且能推出符号或符号串的那些符号。其全体构成非终结符号集，记为VN 。 ③终结符号：不出现在产生式的左部,且不能推出符号或符号串的那些符号。其全体构成终结符号集，记为VT 。
推导和归约
直接推导： 文法G：v＝x Uy，w＝xuy, 其中x、y ∈V* ，U∈VN, u ∈V*, 若U ::=u∈P，则$v\Rightarrow w$，即x Uy$\Rightarrow$xuy 。 若x＝y＝ε，有U ::=u，则U$\Rightarrow$u 换句话说，x和y是符号串，若使用一次产生式可以从x变换出y，则称x直接推导出y(或者说y是x的直接推导），记为x$\Rightarrow$y。
+推导： x和y是符号串，若使用若干次产生式可以从x变换出y，则称x推导出y(或者说y是x的推导），记为x$\overset{+}{\Rightarrow}$y。 或者说：若有直接推导序列：x=U0$\Rightarrow$U1$\Rightarrow$U2$\Rightarrow$……$\Rightarrow$Un=y,则 x$\overset{+}{\Rightarrow}$y 。
*推导： x和y是符号串，若使用0次或若干次产生式可以从x变换出y，则称x*推导出y(或者说y是x的*推导），记为x$\overset{*}{\Rightarrow}$y。
最右推导： 若符号串α中有两个以上的非终结符时，对推导的每一步坚持把α中的最右非终结符进行替换，称为最右推导。
最左推导： 若符号串α中有两个以上的非终结符时，对推导的每一步坚持把α中的最左非终结符进行替换，称为最左推导。
归约： 推导的逆过程称之为归约。
语言的形式定义
文法G[Z] （1）句型：x是句型$\Leftrightarrow$ Z $\overset{*}{\Rightarrow}$ x,且x∈V*； 即：句型是由文法开始符号推导出来的由终结符和非终结符组成的符号串。 （2）句子：x是句子$\Leftrightarrow$Z$\overset{*}{\Rightarrow}$x, 且x∈VT*； 即：句子是由文法开始符号推导出来的由终结符组成的符号串。 （3）语言：L（G[Z]）={x| Z$\overset{*}{\Rightarrow}$x，x∈VT* }；
等价文法： G和G'是两个不同的文法，若 L(G) = L(G')，则G和G’为等价文法。
递归文法
递归产生式： 产生式右部有与左部相同的符号 对于 U::= xUy 若x=ε,即U::= Uy，左递归； 若y=ε,即U::= xU，右递归；
递归文法： 文法G，存在U ∈VN if U$\Rightarrow$…U…, 则G为递归文法； if U$\Rightarrow$U…, 则G为左递归文法； if U$\Rightarrow$…U, 则G为右递归文法；
文法的类型
形式语言：用文法和自动机所描述的没有语义的语言。
语言定义： L（G[Z]）={x| Z$\overset{*}{\Rightarrow}$x , x∈VT*}
文法定义：乔姆斯基将所有文法都定义为一个四元组：G=（VN，VT，P，Z） VN：非终结符号集 VT：终结符号集 P：产生式或规则的集合 Z：开始符号（开始符号） Z∈VN
文法和语言分类：0型、1型、2型、3型 这几类文法的差别在于对产生式施加不同的限制。
0型文法： P： u::=v，其中u∈V* ，v∈V* 0型文法称为短语结构文法。产生式的左部和右部都可以是符号串，一个短语可以产生另一个短语。 0型语言：L0 这种语言可以用图灵机(Turing)接受。
1型文法： P： xUy::= xuy，其中 U∈VN， x、y、u∈V* 称为上下文敏感或上下文有关。也即只有在x、y这样的 上下文中才能把U改写为u
1型文法： P： u::= v |u|≥ |v|，u, v ∈V* 1型语言：L1 这种语言可以由一种线性界限自动机接受。
2型文法： P： U::= u ，其中 U∈VN， u∈V* 称为上下文无关文法。也即把U改写为u时，不必考虑上下文。 注意：2型文法与BNF表示相等价。 2型语言：L2 这种语言可以由下推自动机接受。
3型文法： （左线性） P： U::=t或 U::=Wt，其中 U、W∈VN，t∈VT （右线性） P： U::=t或 U::=tW，其中 U、W∈VN，t∈VT
3型文法又被称为正则文法。它是对2型文法进行进一步限制。
3型语言：L3 又称正则语言、正则集合，这种语言可以由有穷自动机接受。
语言之间的关系： L0$\supset$L1$\supset$L2$\supset$L3 0型文法可以产生L0、L1、L2、L3 ；但2型文法只能产生L2、 L3，不能产生L1。
语法树与二义性
推导与语法树
语法树：句子结构的图示表示法，它是一种有向图，由结点和有向边组成。
结点：符号
根结点：开始符号
中间结点：非终结符
叶结点：终结符或非终结符
有向边：表示结点间的派生关系
句型的推导及语法树的生成（自顶向下） 给定G[Z]，句型w： 可建立推导序列，Z$\overset{*}{\Rightarrow}$w 可建立语法树，以Z为树根结点，每步推导生成语法树的一层分支，最终可生成句型的语法树。
子树与简单子树 子树：语法树中的某个结点（子树的根）连同它向下派生的部分所组成。 简单子树：只有单层分枝的子树称为简单子树。
树与推导 句型推导过程$\Leftrightarrow$句型语法树的生长过程
由推导构造语法树
从开始符号开始，自左向右建立推导序列
由根结点开始，自上而下建立语法树
由语法树构造归约
自下而上地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次归约
从句型开始，自右向左地逐步进行归约，建立归约序列
规范句型： 通过规范推导或规范归约所得到的句型称为规范句型。
文法的二义性
定义1： 若对于一个文法的某一句子存在两棵不同的语法树，则该文法是二义性文法，否则是无二义性文法。 换而言之，无二义性文法的句子只有一棵语法树，尽管推导过程可以不同。
定义2： 若一个文法的某句子存在两个不同的规范推导，则该文法是二义性的，否则是无二义性的。
定义3 若一个文法的某规范句型的句柄不唯一，则该文法是二义性的，否则是无二义性的。
句型的分析
句型的短语、简单短语和句柄
短语： 给定文法G[Z], w=xuy∈V+，为该文法的句型，若Z$\overset{*}{\Rightarrow}$xUy, 且U$\overset{+}{\Rightarrow}$u, 则u是句型w相对于U的短语；其中U ∈VN，u ∈V+，x,y ∈V*
或短语定义: 设G[Z]是给定文法, w=xuy∈V+，为该文法的句型,如果满足下面两个条件: ① Z$\overset{*}{\Rightarrow}$xUy； ② U$\overset{+}{\Rightarrow}$u； 则称句型xuy 中的子串u是句型xuy的短语。 直观理解：短语是前面句型中的某个非终结符所能推出的符号串。
简单短语： 给定文法G[Z], w=xuy∈V+，为该文法的句型，若 Z$\overset{*}{\Rightarrow}$xUy, 且U$\Rightarrow$u, 则u是句型w相对于U的简单短语。其中U ∈VN，u ∈V+，x,y ∈V*
句柄： 任一句型的最左简单短语称为该句型的句柄。
给定句型找句柄的步骤：短语$\Longrightarrow$简单短语$\Longrightarrow$句柄
《编译原理（第2版）》张素琴 吕映芝 蒋维杜 戴桂兰 著
Last updated
