语言的形式化定义


文法和语言之间的联系
给定一个文法，就能从结构上唯一地确定其语言，即 G → L(G)
给定一种语言，能确定其文法，但这种文法不是唯一的，即 $L → G_1$ 或 $G_2$ 或…或 $G_n$

句子和句型


举例：



推导和规约
推导：用产生式的右部替换产生式的左部 （生成语言）

规约：用产生式的左部替换产生式的右式 （识别语言）
举例：根据下列文法，对  little boy eats apple 进行推导和规约


有了文法（语言规范），如何判定某一词串是否是满足文法的句子？


从生成语言的角度，如果从文法的开始符号可以推导出词串，则该词串是语言的句子


从识别语言的角度，如果词串可以规约出文法的开始符号，则该词串是语言的句子



参考地址：

https://www.icourse163.org/learn/HIT-1002123007?tid=1003246005#/learn/announce

语言的定义——编译原理

给定文法G=(VT,VN,P,S),如果α→β∈P,那么可以将符号串中的γαδ中的α替换为β,记作 γαδ⇒γβδ,此时称γαδ直接推导出γβδ.

推导(derivation)和规约(reduction)

有上述例子可知,推导是一个自顶向下的过程,而规约是自定向上的过程,换句话说:推导是由抽象到具体,而规约是由具体到抽象
句型和句子


语言的形式化定义

由文法G的开始符号S所推导出来的所有句子的集合称为文法G的生成的语言,记做

称为文法G的生成的语言,记做

文章目录
推导和规约
句子和句型
短语，直接短语和句柄
素短语

推导和规约


下面是关于推导的定义：

当n=1时，即符号串a0经过1步推导出an，记为直接推导。



如下，推导的过程就是用产生式的右部替换左部

相反，规约的过程就是用产生式的左部替换右部

由此得出：推导和规约两者互为逆过程



问题: 有了文法，如何判断某一词串是否是该语言的句子？
解决办法1：

由开始符S进行推导，若能推导出该词串，则该词串是该语言的句子。

解决办法2：

由该词串进行规约，若能规约到开始符S，则该词串是该语言的句子。

句子和句型
S经过正数步推导得出的α是G的一个句型



在刚才的例子中，所有步骤都可以称之为句型，但只有最后一步推导式可以称为句子（因为没有非终结符）。





下图中对左边的文法进行分析，由简单的开始：

D是表示数字串，L表示字母串

T既可以是数字串，也可以是字母串，同时按照右式可以推导出T可以表示字母数字串

S推导出的就是字母串或字母数字串，即标识符。





短语，直接短语和句柄




素短语
定义： 是指一个短语至少包含一个终结符，并且除它自身之外不再包含其他素短语

特殊的：

最左素短语

定义： 最左素短语就是句型最左边的素短语，是算符优先分析法的规约对象。

语法树： 通过语法树分析时，要注意先判断是否为素短语，再找相对最左端的素短语。

文章目录
一、语言
1、形式语言
2、符号和符号串
二、文法
1、推导
2、语言的定义
3、文法等价
4、语法树
5、句型分析
6、文法二义性
7、文法分类

一、语言
语言是其句子的集合。

汉语–所有符合汉语语法的句子的全体
英语–所有符合英语语法的句子的全体
程序设计语言–所有该语言的程序的全体

$研究语言=\left\{
\begin{aligned}
每个句子构成的规律 \\
每个句子的含义\\
每个句子和使用者的关系 \\
\end{aligned}
\right.$
三个方面：

语法	Syntax

表示构成语言句子的各个记号之间的组合规律
语义	Semantics

表示各个记号及其组合的特定含义（各个记号和记号所表示对象之间的关系）
语用	Pragmatics

表示在各个记号所出现的行为中，它们的来源、使用和影响

1、形式语言
可用于形式化地描述程序设计语言，包括它由哪些符号串构成，这些符号串的表示、结构和特性
2、符号和符号串
任何一种语言都是由该语言的基本符号组成的符号串集合
一些基本概念：

符号:

一个抽象实体,我们不再形式地定义它(就象几何中的”点”一样).例如字母是符号,数字也是符号。
字母表:

字母表是元素的非空有穷集合，我们把字母表中的元素称为符号，因此字母表也称为符号集。不同的语言可以有不同的字母表，例如：汉语的字母表中包括汉字、数字及标点符号等，PASCAL语言的字母表是由字母、数字、若干专用符号及BEGIN、IF之类的保留字组成。
符号串:

由字母表中的符号组成的任何有穷序列称为符号串，例如00 11 10 是字母表 ∑ =｛0，1｝上的符号串。
字母表A=｛a,b,c｝上的一些符号串有：a,b,c,ab,aaca。在符号串中，符号的顺序是很重要的，符号串ab就 不同于ba,abca和aabc也不同。
可以使用字母表示符号串，如x=STR表示 x 是由符号S、T和R，并按此顺序组成的符号串。


符号串的长度:

如果某符号串x中有m个符号，则称其长度为m，表示为｜x｜=m，如001110的长度是6。
空符号串：

即不包含任何符号的符号串，用ε表示，其长度为0，即｜ε｜=0。
符号串的头、尾，固有头和固有尾：

如果z=xy是一符号串，那么x是z的头，y是z的尾；
如果x是非空的，那么y是固有尾；
如果y非空，那么x是固有头。




例如：设z=abc，那么z的头是ε,a,ab,abc，除abc外， 其它都是固有头；z的尾是ε,c,bc,abc,z的固有尾是

ε,c,bc。
当对符号串z=xy的头感兴趣而对其余部分不感兴趣时，采用省略写法：z=x…；

如果只是为了强调x在符号串z中的某处出现，则可表示为：z=…x…；符号t是符号串z的第一个符号，则表示为z=t…。



符号串的连接：

设x和y是符号串，它们的连接xy 是把y的符号写在x的符号之后得到的符号串. 由于ε的含义，显然有ε x=x，x ε =x

例如：x=ST，y=abu，则它们的连接xy=STabu，看出

｜x｜=2，｜y｜=3，｜xy｜=5


符号串的方幂：

符号串自身连接n次得到的符号串，an 定义为 aa…aa n个a，a1=a, a2=aa且a0=ε

例：若x=AB，则:

x0 = ε

x1 =AB

x2 = ABAB

x3 = ABABAB

xn = xxn-1 = xn-1 x	(n>0)



符号串集合：

若集合A中所有元素都是某字母表 ∑ 上的符号串，则称A为字母表上的符号串集合。


两个符号串集合A和B的乘积：

定义为 AB = {xy|x∈A且y∈B}

若集合A={ab,cde}	集合B = {0,1}，则

AB ={ab1,ab0,cde0,cde1}


使用 ∑* 表示 ∑ 上的一切符号串（包括 ε ）组成的集合。Σ* 称为 Σ 的闭包。
∑ 上的除ε外的所有符号串组成的集合记为∑+。 ∑+称为Σ的正闭包。
编译原理的闭包：

V是一个符号集合，假设V指的是三个符号a, b, c的集合，记为 V = {a, b, c } V*

读作“V的闭包”，它的数学定义是V自身的任意多次自身连接（乘法）运算的积，也是一个集合。

也就是说，用V中的任意符号进行任意多次（包括0次）连接，得到的符号串，都是V*这个集合中的元素。 0次连接的结果是不含任何符号的空串，记为

ε 1次连接就是只有一个符号的符号串，比如，a，b， c 2次连接是两个符号构成的符号串，比如，aa, ab, ac, ba, bb,

bc,等等

二、文法

符号$->$符号串$->$句子$->$语言


并非所有符号串都能形成句子

文法G定义为一个四元组$(V_N，V_T，P，S )$，其中：


$V_N$为非终结符号(或语法实体，或变量)集；
非终结符(nonterminal) 是用来表示语法成分的符号，有时也称为语法变量
例: $V_N = \{ <句子>, <名词短语>, <动词短语>,<名词>, … \}$


$V_T$为终结符号集；
终结符（terminal symbol）是文法所定义的语言的基本符号，有时也称为$token$
例: $V_T=\{ apple, boy, eat, little\}$


$P$为产生式(也称规则)的集合； $V_N$，$V_T$和$P$是非空有穷集；
产生式（production）描述了将终结符和非终结符组合成串的方法产生式的一般形式：
α→β  读作：α定义为β


$α∈(V_T∪V_N)^+$，且α中至少包含$V_N$中的一个元素：称为产生式的头(head)或左部(left side)


$β∈(V_T∪V_N)^*$：称为产生式的体(body)或右部(right side)
例：
$P=\left\{ \begin{aligned}  <句子>\rightarrow<名词短语>\rightarrow<动词短>， \\ <名词短语>\rightarrow<形容词>\rightarrow<名词短语>， \\ …\end{aligned} \right.$




$S$为识别符号或开始符号，它是一个非终结符。
$S∈V_N$。开始符号(start symbol ) 表示的是该文法中最大的语法成分
➢例：$S = <句子>$



$V_N$和$V_T$不含公共的元素，即$V_N$ ∩ $V_T$ = $φ$


用$V$表示$V_N$ ∪ $V_T$ ，称为文法$G$的字母表或字汇表规则，也称重写规则、产生式或生成式，

是形如α→β或α∷=β的$(α，β)$有序对，其中 α 是字母表$V$的正闭包$V^+$中的一个符号，β 是$V^*$中的一个符号。

α 称为规则的左部，β称作规则的右部。



1、推导
直接推导：“$=>$”
α→β 是文法G的产生式，若有 δ1, δ2 满足：δ1 =γ1αγ2, δ2 = γ1βγ2,  其中γ1,γ2∈V
​      - 则称δ1直接推导到δ2,记作δ1$=>$δ2
​      - 也称δ2直接归约到δ1
例：
G：S→0S1， S→01


0S1 => 00S11


00S11 => 000S111


000S111 => 00001111


S => 0S1



规范推导：最右推导







     中间为规范推导



句型、句子的定义


句型：

有文法G，若S =>* x，则称x是文法G的句型。


句子：

有文法G，若S =>*x，且x∈${V_T}$*，则称x是文法G的句子。


例：
G： S→0S1， S→01

S $=>$ 0S1 $=>$ 00S11$=>$ 000S111 $=>$ 00001111
G的句型S, 0S1, 00S11,000S111, 00001111
G的句子00001111, 01

2、语言的定义
由文法G生成的语言记为L(G),它是文法G的一切句子的集合：
$L(G)=\{x|S =>^*x，其中S为文法的开始符号，且x ∈V*\}$
例：G： S→0S1， S→01
$L(G)=\{0^n1^n|n≥1\}$


3、文法等价
若$L(G1)=L(G2)$, 则称文法$G1$和$G2$是等价的。
如文法 $G1[A]：A→0R$ 与 $G2[S]：S→0S1$ 等价

A→01	S→01  R→A1
4、语法树
文法G[Z]的语法树：


每个结点都是G的符号


树根是文法的开始符号


若某个结点至少有一个从它出来的分支，则该结点一定是非终结符


若某个结点A有n个分支，假设其分支结点为B1,B2,…Bn，则A::=B1B2B3…Bn一定是文法的一条规则


语法树可以从推导过程产生。
凡使用一条规则推导，则可以从规则左部符号结点长出若干分支。

5、句型分析

句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。


在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序，分析算法又称识别算法。


从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。

句型分析分析算法可分为：

自上而下分析法：

从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。
自下而上分析法：

从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。

两种方法反映了两种语法树的构造过程:


自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串


自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树


 
句型分析的有关问题

1）在自上而下的分析方法中如何选择使用哪个产生式进行推导？

假定要被代换的最左非终结符号是A，且有n条规则：A→B1|B2|…|Bn，那么如何确定用哪个右部去替代A？
2）在自下而上的分析方法中如何识别可归约的串？

在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”

刻画“可归约串”




短语是句型中某非终结符号通过若干步推导出的子串


归约：如果每次都从当前句型的句柄进行归约，则可以归约到文法的开始符号



6、文法二义性


文法二义性：两棵语法树对应同一句子


根据语法树，可以发现文法的二义性二义文法



若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。


判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，

这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件。

文法的二义性和语言的二义性是两个不同的概念：

可能有两个不同的文法G和G′，其中G是二义的，但是却有：L(G)=L(G′)，

即，这两个文法所产生的语言是相同的。

7、文法分类
通过对产生式施加不同的限制，Chomsky将文法分为四种类型：

0型文法：对任一产生式 $α→β$，都有$α∈(V_N∪V_T)^+$， $β∈(V_N∪V_T)^*$
1型文法：对任一产生式$α→β$，都有$|β|≥|α|$ ，仅 $S→ε$ 除外, S为文法初始符号且不出现在任何产生式右边
2型文法：对任一产生式$α→β$，都有$α∈V_N$， $β∈(V_N∪V_T)^*$
3型文法：任一产生式$α→β$的形式都为$A→aB$或$A→a$， 其中$A∈V_N$，$B∈V_N$，$a∈V_T$





类型
例子




1型文法



2型文法



3型文法



文法的实用限制:

ε 规则:

关于区分上下文是否相关，引入知乎大佬的解释：