形式文法

✍ dations ◷ 2025-09-15 16:41:10 #形式文法
在形式语言理论中,文法(为了避免歧义,常称作“形式文法”)是形式语言中字符串的一套产生式规则(英语: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 为最左边符号的字符串,那么上下文无关语言的文法就是左递归的。尽管有大量关于语法分析算法的文献,但这些算法大多假设要被分析的语言最初是通过生成式文法来描述的,并且目标是将生成式文法转换成一个有效的语法分析器。严格地说,生成文法不以任何方式对应用于解析语言的算法,而且各种算法对被认为是格式良好的产生式规则的形式有不同的限制。严格地说,生成文法不能在任何方面都与解析语言的算法对应上,而且各种算法对产生式规则的形式有不同的限制,这些产生式规则被认为是形式良好的。另一种方法是首先根据分析型文法将语言形式化,分析型文法能更直接地对应于语言分析器的结构和语义。分析型文法体系的例子包括:

相关

  • 肌萎缩性脊髓侧索硬化症肌萎缩性脊髓侧索硬化症(英语:Amyotrophic lateral sclerosis,缩写为 ALS),也称为肌萎缩侧索硬化症,有时也称为卢·贾里格症(英语:Lou Gehrig's disease)、渐冻人症、运动神经元病,是
  • 流汗汗液,或汗,是由人等高等动物透过汗腺所分泌出的液体。汗的分泌受到植物性神经系统调节。汗液的主要成分是水,约占总成分的98%到99%,其余物质为氯化钠,极少量的尿素、氨和其他盐类
  • 心内膜炎心内膜炎(英语:Endocarditis)是心脏的心内膜(心腔中的最深层的组织)引发的炎症,通常和心脏瓣膜有关。此外,心内膜炎也可能与室间隔(英语:interventricular septum)、腱索(英语:chordae t
  • 轴突轴突(Axon)由神经元组成,即神经细胞之细胞体长出突起,功能为传递细胞本体之动作电位至突触。于神经系统中,轴突为主要神经信号传递渠道。大量轴突牵连一起,以其外型类似而称为神经
  • 原住民语美洲原住民语言(有时也称为印第安语)并不是一种语言,甚至也不是属于一种语系,而是美洲所有原住民的各种语言的总称。其中玛雅语曾经有自己的文字系统。随着15世纪末开始西方殖民
  • 塑胶添加剂为了使生产的塑料符合要求的一些特性、符合经济的需求,一定都会加入或多或少‘添加剂’。塑料添加剂有很多种,有润滑剂、氧化防止剂、热稳定剂、强化剂等等。部分原料必须加入
  • 电负性电负性(英语:electronegativity,简写EN),也译作离子性、负电性及阴电性,是综合考虑了电离能和电子亲合能,首先由莱纳斯·鲍林于1932年提出。它以一组数值的相对大小表示元素原子在
  • 阿杰隆阿杰隆(阿拉伯语:عجلون‎是约旦的城镇,位于该国西北部,是阿杰隆省的首府,距离首都安曼76公里,海拔高度793米,该城镇有一处十二世纪城堡的遗址,2009年人口8,356。坐标:32°21′N
  • 维谷斯基利维·维果斯基(俄语:Лев Семёнович Выготский,1896年11月17日-1934年6月11日,其姓氏台湾译为维高斯基,其他的翻译还包括维果茨基、维谷斯基、维戈茨基等),苏
  • 诗经《诗经》是中国最早的诗歌总集,收录自西周初年至春秋中叶(约前11世纪-前6世纪)的诗歌305篇(除此之外还有6篇有题目无内容,即有目无辞,称为笙诗六篇,题目分别是南陔、白华、华黍、由