文法和语言的基本知识⚓︎

字母表和符号串⚓︎

字母表是元素的非空有穷集合，例如\(\{a,b,c\}\)就是一个字母表；其中各个元素称为符号；由符号形成的有穷序列称为符号串。

符号串的运算⚓︎

符号串的连接⚓︎

若\(x=12a\)，\(y=cd4\)，那么有

这就叫符号串的连接。

集合的乘积⚓︎

对于给定的集合\(A\)和\(B\)，它们的乘积定义为

符号和集合的幂运算⚓︎

根据上述乘积运算的定义，可以容易定义：

额外定义：

也就是说，集合\(A\)的\(n\)次幂是长度为\(n\)的字符串的集合。

集合的闭包⚓︎

定义集合\(A\)的正闭包\(A^+\)和闭包\(A\)如下：

集合的正闭包就表示集合包含的字符所能组成所有字符串的集合，闭包比正闭包多考虑了空字符串。

文法的形式定义⚓︎

形式语言⚓︎

形式语言是字母表上按照某种规则构成的字符串的集合；每一种不同的集合也相反构成一种形式语言。例如：\(A=\{a,b,c\}\)时，

都是形式语言。

文法的形式定义⚓︎

文法是规则的非空有穷集合，通常用\(G=\{V_N.V_T,P,S\}\)来表达。

规则\(P\)是符号与符号串的一组有序对，通常记作

表示左边的符号\(P\)用右边的字符串\(\beta\)来定义，也即\(P\)生成\(\beta\)。

规则左部称为非终结符号\(V_N\)，右部称为终结符号\(V_T\)，一般来说，有

\(S\)是一个非终结符号，叫做文法的开始符号或者识别符号。从这个符号开始，我们逐渐识别我们用文法所定义的语言。

语言的形式定义⚓︎

推导⚓︎

假设有一文法\(G\)，如果我们从\(xAy\)直接能够推出\(a\alpha y\)，当且仅当\(A\Rightarrow \alpha\)且\(x,y \in (V_N\cup V_T)^*\)。也就是说，这步推导我们只使用了\(P\)中一个规则。

句型和句子⚓︎

对于文法\(G[S]\)，如果我们从开始符号\(S\)开始经过零或若干次推导能够得到字符串\(x\)，并且\(x\in (V_N\cup V_T) ^*\)，我们就称\(x\)是文法的一个句型。特殊地，如果\(x\in V_T ^*\)，我们就称其为一个句子。

换句话说，由开始符号经过若干次推导得到的字符串称为一个句型；不含非终结符的句型称为一个句子。

所有句子的集合称为该文法定义出的语言。

规范推导和规范归约⚓︎

对于一个句型，我们通过不断使用规则将其展开，消除其中的非终结符，这个过程叫做推导。

优先展开最左边的非终结符的推导称为最左推导；优先展开最右边的非终结符的推导称为最右推导。最右推导又称为规范推导。

反过来，我们通过逆向使用规则将句型收缩成非终结符的过程称为归约。

最左推导的逆过程叫做最右归约；最右推导的逆过程叫做最左归约。最左规约又称为规范归约。

由开始符号开始推导某一句子的过程，如果用树的形式表示，那么这棵树称为语法树。

短语、直接短语和句柄⚓︎

对于文法\(G[S]\)，如果\(\alpha \beta \delta\)是一个句型，\(S\)经过若干次推导可以得到\(\alpha A\delta\)且\(A\)经过若干次推导可以得到\(\beta\)，则称：\(\beta\)是\(\alpha A\delta\)关于非终结符\(A\)的一个短语。

若\(\beta\)可由\(A\)经过一次推导得到，那么加强为直接短语。

给定句型的最左直接短语称为该句型的句柄。

语法树⚓︎

定义⚓︎

语法树是对推导过程的一种表示形式。

对于一颗语法树，其每个节点都是一个标记，并且其为\(V_N\cup V_T\cup \left |\varepsilon\right |\)中的一个符号。该树的树根是文法的开始符号\(S\)，非叶子节点一定是一个非终结符。

语法树反应的文法概念⚓︎

对于任意一个句型的语法树，可以根据语法树判断出短语、直接短语以及句柄的概念。

某棵子树的所有叶子结点组成的字符串是树根所对应的非终结符的短语；如果上述是简单子树，则是树根对应的直接短语；最左简单子树的叶子结点组成的字符串是句柄。

文法和语言的分类⚓︎

0型文法⚓︎

若文法\(G\)中的每一条规则\(\alpha\to\beta\)是结构：\(\alpha \in (V_T\cup V_N)^*\)并且包含至少一个非终结符，\(\beta \in (V_T\cup V_N)^*\).这样的规则对于语言本身没有任何约束，称这样的\(G\)为0型文法，相对应的语言称为无限制性语言。

1型文法⚓︎

文法中每一条规则的形式都是\(\alpha A\beta \to \alpha u \beta\)，其中\(\beta ,u\in (V_N\cup V_T)^*\)。这样的文法所定义出的语言是上下文相关的，所以这样的文法又称为上下文相关文法，对应的语言称为上下文相关语言。

2型文法⚓︎

若文法中的每一条规则都是\(A\to \beta\)的形式，其中\(A\in V_N,\beta in (V_N\cup V_T)^*\)。这样的文法称为上下文无关文法，对应的语言称为上下文无关语言。

3型文法⚓︎

若文法中的每一条规则满足\(A\to \alpha B\mid \alpha\)或\(A\to B\alpha \mid \alpha\)，则前者称为右线性文法，后者称为左线性文法。两者都是3型文法，又称正规文法。

四种文法的关系⚓︎

根据限制条件，可以知道对于文法的限制条件是加大的。即，正规文法一定是上下文无关的；上下文无关的一定是上下文有关的；上下文有关的一定是无限制的。也即：

评论