首页 >
形式文法
✍ dations ◷ 2025-04-25 00:19:43 #形式文法
在形式语言理论中,文法(为了避免歧义,常称作“形式文法”)是形式语言中字符串的一套产生式规则(英语:Production (computer science))。这些规则描述了如何用语言的字母表生成符合语法(英语:syntax (programming languages))的有效的字符串。文法不描述字符串的含义,也不描述在任何上下文中可以用它们做什么——只描述它们的形式。形式语言理论是应用数学的一个分支,是研究形式文法和语言的学科。它在理论计算机科学、理论语言学、形式语义学、数理逻辑等领域有着广泛的应用。形式文法是从一个“开始符号”出发的一套重写字符串的规则。因此,文法通常被认为是语言生成器。然而,它有时也可以用作“识别器”(计算机学中的一种函数,用于确定给定字符串是否属于该语言,是否为语法错误)的基础。形式语言理论使用另一个理论来描述识别器,也就是自动机理论。自动机理论有一个有趣的结果,某些形式语言是无法设计出识别器的。
语法分析是通过将一段话语(自然语言中的一个字符串)分解成一组符号,并根据语言的语法分析每一个符号的过程。大多数语言的话语含义都是根据其句法结构来确定的——这种做法被称为组合语义学。因此,在语言中描述话语含义的第一步就是把它分解成若干部分,然后观察它经过分析后的形式(在计算机科学中被称为分析树,在生成文法中被称为深层结构)。文法主要由一组变换字符串的规则组成。(如果它只包含这些规则,那么它就是一个半图厄系统(英语:semi-Thue system)。)要在该语言中生成字符串,首先需要一个只包含一个开始符号的字符串。然后按任意顺序应用产生式规则,直到生成既不包含起始符号也不包含指定非终结符号的字符串。产生式规则是通过把字符串中第一次出现产生式规则左边的地方,替换成产生式规则的右边,来作用于这个字符串的(参见理论图灵机的运算)。由文法产生的语言包含能用这种方式产生的所有不同的字符串。开始符号上的任何特定产生式规则序列都会在语言中产生一个不同的字符串。如果产生同一个字符串有多种不同的方式,那这个文法就是具有二义性的文法了。例如,假设字母表由 a 和 b 组成,开始符号是 S,我们有以下产生式规则:那么我们从 S 开始,选择一个规则。如果我们选择规则1,我们将获得字符串 aSb。如果我们再次选择规则1,我们用 aSb 替换 S,得到字符串 aaSbb。如果我们现在选择规则2,我们将 S 替换为 ba 并获得字符串 aababb,然后就完成了。我们可以用符号将这一系列选择写得更简短:
S
⇒
a
S
b
⇒
a
a
S
b
b
⇒
a
a
b
a
b
b
{displaystyle SRightarrow aSbRightarrow aaSbbRightarrow aababb}
。这种文法的语言就是无限集
{
a
n
b
a
b
n
∣
n
≥
0
}
=
{
b
a
,
a
b
a
b
,
a
a
b
a
b
b
,
a
a
a
b
a
b
b
b
,
…
}
{displaystyle {a^{n}bab^{n}mid ngeq 0}={ba,abab,aababb,aaababbb,dotsc }}
,其中
a
k
{displaystyle a^{k}}
是
a
{displaystyle a}
重复
k
{displaystyle k}
次(
n
{displaystyle n}
表示使用规则1的次数)。20世纪50年代,诺姆·乔姆斯基首次提出了生成语法的经典形式化理论, 其中文法 G 由以下部分组成:文法的形式定义为四元组
(
N
,
Σ
,
P
,
S
)
{displaystyle (N,Sigma ,P,S)}
。这种形式语法在文献中常被称为重写系统或短语结构文法(英语:phrase structure grammar)。文法的运算可以用字符串的关系来定义:注意文法
G
=
(
N
,
Σ
,
P
,
S
)
{displaystyle G=(N,Sigma ,P,S)}
实际上是半图厄系统(英语:semi-Thue system)
(
N
∪
Σ
,
P
)
{displaystyle (Ncup Sigma ,P)}
,以完全相同的方式重写字符串;唯一的区别在于我们区分了特定的非终结符号,这些符号必须在重写规则中重写,并且只对从指定的开始符号
S
{displaystyle S}
到没有非终结符号的字符串的重写感兴趣。在这些例子中,形式语言使用集合建构式符号描述。考虑文法
G
{displaystyle G}
,其中
N
=
{
S
,
B
}
{displaystyle N=left{S,Bright}}
,
Σ
=
{
a
,
b
,
c
}
{displaystyle Sigma =left{a,b,cright}}
,
S
{displaystyle S}
是开始符号,
P
{displaystyle P}
由以下产生式规则组成:这个文法定义了语言
L
(
G
)
=
{
a
n
b
n
c
n
∣
n
≥
1
}
{displaystyle L(G)=left{a^{n}b^{n}c^{n}mid ngeq 1right}}
,这里
a
n
{displaystyle a^{n}}
表示 n 个
a
{displaystyle a}
串连所得的字符串。因此,该语言是由1个或更多的
a
{displaystyle a}
,后面跟着相同数量的
b
{displaystyle b}
,接着是相同数量的
c
{displaystyle c}
组成的字符串集合。L
(
G
)
{displaystyle L(G)}
内字符串的推导例子如下:1956年诺姆·乔姆斯基首次将生成文法形式化时, 他将它们分为现在称为乔姆斯基谱系的四种类型。其中两种重要的文法类型分别是上下文无关文法(2型)和正则文法(3型)。可以用这两种文法描述的语言分别称为上下文无关语言和正则语言。尽管比无限制文法(0型,实际上无限制文法可以表示任何图灵机可以接受的语言)要弱得多,但这两种受限制的语法最常用,因为它们的解析器可以高效地实现。 例如,所有正则语言都可以被有限状态机识别,对于上下文无关文法的有用子集,有一些著名的算法可以生成高效的LL分析器LR分析器,以识别文法生成的相应语言。上下文无关文法要求产生式左侧只能包含一个符号,并且该符号为非终结符号。这个限制是非常重要的;不是所有的语言都可以由上下文无关的语法生成。那些可以被称为上下文无关语言。上例定义的语言
L
(
G
)
=
{
a
n
b
n
c
n
∣
n
≥
1
}
{displaystyle L(G)=left{a^{n}b^{n}c^{n}mid ngeq 1right}}
并不是一个上下文无关语言,并且这个可以用上下文无关语言的泵引理严格证明,但
{
a
n
b
n
∣
n
≥
1
}
{displaystyle left{a^{n}b^{n}mid ngeq 1right}}
(1个及以上
a
{displaystyle a}
后面跟同样数量的
b
{displaystyle b}
)是一个上下文无关语言。因为它可以由文法
G
2
{displaystyle G_{2}}
(
N
=
{
S
}
{displaystyle N=left{Sright}}
,
Σ
=
{
a
,
b
}
{displaystyle Sigma =left{a,bright}}
,
S
{displaystyle S}
为开始符号)定义,用下列产生式规则:通过Earley算法(英语:Earley's algorithm)可以在
O
(
n
3
)
{displaystyle O(n^{3})}
时间(参见大O符号)内识别上下文无关语言。也就是说,对于每一种上下文无关的语言,都可以构建一台以字符串为输入并及时确定字符串是否为该语言成员的机器,其中
n
{displaystyle n}
是字符串的长度。 确定性上下文无关语言(英语:Deterministic context-free language)是可在线性时间内识别的上下文无关语言的子集。 由多种算法针对这类语言或它的子集。在正则文法中,左侧仍然只是一个非终结符号,但右侧也受到限制。右侧可以是空字符串,也可以是单个终结符号,或者是后跟非终结符号的单个终结符号,但不能是其他符号。(有时会使用更宽泛的定义:可以允许更长的终结字符串或单个非终结字符串,而不能有其他任何东西,从而使语言更易于表示,同时仍然定义同一类语言。)上面定义的语言
{
a
n
b
n
∣
n
≥
1
}
{displaystyle left{a^{n}b^{n}mid ngeq 1right}}
不是一个正则语言,但下面这个语言是:
{
a
n
b
m
∣
m
,
n
≥
1
}
{displaystyle left{a^{n}b^{m}mid m,ngeq 1right}}
(一个或多个
a
{displaystyle a}
后面跟着一个或多个
b
{displaystyle b}
,这两个的数量可以不一样)。它之所以是正则语言,是因为可以通过文法
G
3
{displaystyle G_{3}}
定义,其中
N
=
{
S
,
A
,
B
}
{displaystyle N=left{S,A,Bright}}
,
Σ
=
{
a
,
b
}
{displaystyle Sigma =left{a,bright}}
,
S
{displaystyle S}
为开始符号,还有如下产生式规则:由正则文法生成的所有语言都可以被有限状态机在
O
(
n
)
{displaystyle O(n)}
时间内识别出来。虽然在实际应用中,正则文法通常使用正则表达式来表示,但是实际应用中使用的一些正则表达式并没有严格地生成正则语言,也因此没有表现出线性识别性能。语言学家和计算机科学家对乔姆斯基的形式语法的原始层次结构进行了许多扩展和变化,通常是为了增强表达能力,或者是为了使分析或解析更加容易。一些形式的文法包括:递归文法是包含递归产生式规则的语法。例如,如果存在一个非终结符 A,可以通过产生式规则生成一个以 A 为最左边符号的字符串,那么上下文无关语言的文法就是左递归的。尽管有大量关于语法分析算法的文献,但这些算法大多假设要被分析的语言最初是通过生成式文法来描述的,并且目标是将生成式文法转换成一个有效的语法分析器。严格地说,生成文法不以任何方式对应用于解析语言的算法,而且各种算法对被认为是格式良好的产生式规则的形式有不同的限制。严格地说,生成文法不能在任何方面都与解析语言的算法对应上,而且各种算法对产生式规则的形式有不同的限制,这些产生式规则被认为是形式良好的。另一种方法是首先根据分析型文法将语言形式化,分析型文法能更直接地对应于语言分析器的结构和语义。分析型文法体系的例子包括:
相关
- 白血球白血球,又称为白细胞,是血液中重要的血细胞之一。除白细胞外,人体血液中还含有红细胞、血小板和血浆。白细胞是免疫系统的一部分,帮助身体抵抗传染病以及外来的东西。白细胞可以
- 铁3d6 4s22, 8, 14, 2蒸气压第一:762.5 kJ·mol−1 第二:1561.9 kJ·mol−1 第三:2957 kJ·mol−1 (主条目:铁的同位素铁(Iron)是一个化学元素,化学符号是Fe (源自拉丁语 ferrum),原
- Mayo Clinic坐标:44°1′20″N 92°28′0″W / 44.02222°N 92.46667°W / 44.02222; -92.46667梅奥诊所医学中心(英语:Mayo Clinic),又译为梅奥诊所、梅约诊所、马约诊所,是世界最著名的医疗
- 扁盘动物门黏丝盘虫(Trichoplax adhaerens)是1883年由德国生物学家Franz Eilhard Schulze (1840-1921)在奥地利Graz大学的水族馆发现的。目前在扁盘动物门中仅确认此一种,一般称丝盘虫即
- 飞机综合数据系统飞机综合数据系统(英语:Aircraft Integrated Data System,简称AIDS)是一种飞机系统,允许航空公司记录和/或监控飞机总线上的所有可用参数。例如空客A320等某些飞机有一个AIDS打印
- UNAIDS行政总监联合国艾滋病规划署(英语:Joint United Nations Programme on HIV and AIDS,缩写UNAIDS)是全球范围内组织、推广及协调世界艾滋病运动的机构。规划署旨在唤起全球对艾滋
- 污染源监测污染源监测是一种环境监测内容,主要用环境监测手段确定污染物的排放来源、排放浓度、污染物种类等,为控制污染源排放和环境影响评价提供依据,同时也是解决污染纠纷的主要依据。
- 基克拉泽斯文明基克拉泽斯文明(或称为基克拉泽斯文化、基克拉泽斯时期)是爱琴海基克拉泽斯群岛上的一种早期青铜时代(Early Bronze Age)文化,他大致从公元前3300年延续到前2000年,考古发现上最早
- 撒拉撒拉,或称撒辣(天主教通译)(希伯来语:שָׂרָה,Sara,Śārāh;阿拉伯语:سارة,Sāra)是亚伯拉罕(古兰经中称为易卜拉辛)的妻子,以撒的母亲,记载在圣经·创世纪和古兰经中。撒拉本名
- 爱斯基摩-阿留申语系爱斯基摩-阿留申语系是一个位于阿拉斯加、加拿大北部、努纳维克、努纳武特、格陵兰岛、西伯利亚东部楚科奇半岛的语系。该语系分为两个部分,分别为爱斯基摩语族、阿留申语族。