文法和语言

引子

一个程序设计语言是一个记号系统，它的完整定义应包括语法和语义两个方面。


一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序。目前广泛使用的手段是上下文无关文法。语法只是定义什么样的符号序列是合法的，与这些符号的含义毫无关系。


判定语言是否符合逻辑，是属于语义分析的工作。程序设计语言的语义分为两类：静态语义和动态语义。


静态语义是一系列限定规则，并确定哪些合乎语法的程序是合适的。


动态语义称作运行语义或执行语义，表明程序要做什么，要计算什么


阐明语法的工具是文法，阐明语义要更困难，目前仍没有一种公认的形式系统可以自动构造正确的编译系统，故不再介绍形式语义学。

文法之前-符号和符号串

字母表，是元素的非空有穷集合。字母表中的元素又可称为符号，因此字母表也称为符号集。


举个例子，C语言的字母表由字母、数字、若干专用符号及char、struct、if、do之类的保留字组成。


符号串，由字母表中的符号组成的任何有穷序列称为符号串。


举个例子，001110是字母表Σ={0，1}上的符号串。


如果某符号串x中有m个符号，称其长度为m，表示为|x|=m。


空符号串用ε表示，|ε|=0。


当我们只对符号z=xy的头感兴趣，可以采用省略写法：z=x···；如果只是为了强调x在符号串某处出现，可表示为z=···x···。


符号串的连接

设x=ST，y=abu，他们的连接为xy=STabu。其中|x|=2，|y|=3，|xy|=5。


符号串的方幂

设x是符号串，把x自身连接n次得到符号串z，z=xxx···xxx，称为符号串的方幂。写作$z^n$。


符号串集合

若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。


两个符号串集合A和B的乘积定义如下$AB={xy|x∈A且y∈B}$。


指定字母表Σ之后，可用$Σ^*$表示Σ上所有有穷长的串的集合。并称之为集合Σ的闭包。可以用字母表的方幂形式来表示：$Σ^*=Σ^0∪Σ^1∪Σ^2···Σ^n···$。


举个例子，如Σ={0，1}，则$Σ^*={ε，0，1，00，01，10，11，000，001，010···}$。


而$Σ^+$称为Σ的正闭包。且$Σ^+=Σ^1∪Σ^2···Σ^n···$。显然有$Σ^*=Σ^0∪Σ^+$和$Σ^+=ΣΣ^*=Σ^*Σ$。

文法和语言的形式化定义

规则，也可以称为产生式、生成式，是形如α->β或α::=β的有序对。其中α称为规则的左部，β称为规则的右部。这里的::=读作“定义为”。


文法定义为四元组($V_N,V_T,P,S$)。其中$V_N$是非终结符号集；$V_T$是终结符集；P为规则（α->β）的集合，$α∈(V_N∪V_T)^$且至少包含一个非终结符，$β∈(V_N∪V_T)^$;$V_N,V_T和P$是非空有穷集。S称作识别符或开始符，他是一个非终结符，至少要在一条规则中作为左部出现。


$V_N和V_T$不含公共的元素，即$V_N∩V_T=\varnothing$。通常用V表示$V_N∪V_T$,V称为文法G的字母表或字汇表。


推导,定义了$V^$中的符号之间的关系。包括直接推导$\Rightarrow$、长度为n(n>=1)的推导$\overset{+}{\Rightarrow}$和长度为n(n>=0)的推导$\overset{*}{\Rightarrow}$。接下来仅给出直接推导的形式化定义。


设$\alpha\rightarrow\beta$是文法G=($V_N,V_T,P,S$)的规则，$\gamma和\delta$是$V^$中的任意符号，若有符号串满足$v=\gamma\alpha\delta,w=\gamma\beta\delta$，则说v应用规则$\alpha\rightarrow\beta$直接产生w，或说w是v的直接推导。记作$v\Rightarrow w$。


句型和句子的定义如下：

设G[S]是一个文法，如果符号串x是从识别符号推导出来的，即有$S\overset{}{\Rightarrow}x$，则称x是文法G[S]的句型。若x仅由终结符号组成，即$S\overset{}{\Rightarrow}x,x∈V_T^*$，则称x为G[S]的句子。


最后语言的定义自然推出，是句子的集合。文法G产生的语言形式化定义为集合{x|$S\overset{}{\Rightarrow}x$,其中S为文法识别符号,$x∈V_T^$}。可用L(G)表示该集合。


如果L(G1)=L(G2),则称文法G1和文法G2等价。

文法的类型

Chomsky将文法分为四种类型，即0型、1型、2型和3型。，这些文法的差别在于对产生式施加不同的限制


0型文法：设$G=(V_N,V_T,P,S)$，如果它的每个产生式$\alpha\rightarrow\beta$是这样一个结构：$\alpha∈(V_N∪V_T)^*$且至少含有一个非终结符，而$\beta∈(V_N∪V_T)^*$，则G是一个0型文法。


0型文法亦称短语文法，一个重要的结论：0型文法的能力相当于图灵机。任何0型语言都是递归可枚举的。


1型文法：也称上下文有关文法。设$G=(V_N,V_T,P,S)$，如果它的每个产生式$\alpha\rightarrow\beta$均满足$|\beta|>=|\alpha|$，仅$S\rightarrow\epsilon$除外，则文法G是1型文法。


2型文法：亦称上下文无关文法。设$G=(V_N,V_T,P,S)$，如果它的每个产生式$\alpha\rightarrow\beta$均满足：$\alpha$是一个非终结符，$\beta∈(V_N∪V_T)^*$。此时称文法是2型文法。


3型文法：也称正规文法。设$G=(V_N,V_T,P,S)$，如果它的每个产生式的形式都是$A\rightarrow aB$或$A\rightarrow a$，其中A和B都是非终结符，$a∈V_T^*$，则G是3型文法。

上下文无关文法及其语法树

上下文无关文法有足够能力描述现今程序设计语言的语法结构，如描述算术表达式、描述各种语句等。因此我们开始关心上下文无关文法的句子分析和分析方法的研究。自此开始，若无特殊说明，“文法”一次指上下文无关文法。


语法树，也称推导树，是一种描述上下文无关文法的句型推导的直观工具。通过一个例子可以直观了解：



语法树表示了推导过程中使用了哪个产生式和使用在哪个非终结符上，并没有说明产生式的顺序，上图aabbaa的推导过程可以列举三个：

• $S\Rightarrow aAS\Rightarrow aAa\Rightarrow aSbAa\Rightarrow aSbbaa\Rightarrow aabbaa$
• $S\Rightarrow aAS\Rightarrow aSbAS\Rightarrow aabAS\Rightarrow aabbaS\Rightarrow aabbaa$
• $S\Rightarrow aAS\Rightarrow aSbAS\Rightarrow aSbAa\Rightarrow aabAa\Rightarrow aabbaa$
  

如果在推导的任何一步$\alpha\Rightarrow\beta$，其中$\alpha、\beta$是句型，都是对α中的最左（最右）非终结符进行替换，称这种推导为最左（最右）推导。上述第一个推导是最右推导，第二个推导是最左推导。在形式语言中，最右推导常被称为规范推导。


最后，给出文法二义性的定义，如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义性的。换言之，如果一个文法中存在某个句子，他有两个不同的最左（最右）推导，则这个文法是二义性的。


补充：形式语言理论已经证明，要判定任给的一个上下文无关文法是否为二义的，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的。不存在一个算法，能在有限步骤内确切判定任给的一个文法是否为二义的。