子串
一个字符串 s 被称作另一个字符串 S 的子串，表示 s 在 S 中出现了。比如，“中出”是“我们中出了一个叛徒”的子串。注意子串和子序列是不同的：“果机”是“蘋果手机”的子序列，而不是子串。 前缀和后缀是两种特殊的子串：一个前缀在原串的开始位置出现，而一个后缀在原串的末端出现。 例如，“苹果手机”的所有子串是：“”（空串），“苹”，“果”，“手”，“机”，“苹果”，“果手”，“手机”，“苹果手”，“果手机”，“苹果手机”。 定义 一个…
标签：#形式语言
共 64 篇文章
空字串
在計算機科學或形式語言中，空字串是指在字母表Σ上，其長度為 0 的那唯一字串，以ε或λ來標記。 在物件導向程式語言中，空字串共非空參照。一個字串型別的空參照並未指向一個字串物件，而對其操作則會導致錯誤。空字串則可以使用字串運算。 特性 在形式語言中，空字串有以下特性： | \lambda \, | = 0。字串長度為 0 。 \lambda \, + s = s + \lambda \, = s。在串接運算之下，空字串是一個在Σ上之自由…
串接
在形式語言理論（特別是編程語言），字串串接（Concatenation），又稱字串相加、連接、序連、串連、相連，指將兩個字串的首尾相接的操作。例如「foo」和「bar」串接後便成了「foobar」。部分語言，串接的操作是透過將串接運算子放在兩個字串（運算元）之間。 不同語言的運算子 大部分語言都使用「+」號作字串串接運算子，以下是一些例外： Perl（版本6之前）和PHP：. Perl 6：_ Visual Basic：&；在運算元不是…
作用代数
在代数逻辑中，作用代数是既是剩余半格又是克莱尼代数的代数结构。它向剩余半格增加了克莱尼代数的星号或自反传递闭包运算，或者说向克莱尼代数增加了剩余半格的左和右剩余或蕴涵运算。不像程序的动态逻辑和其他模态逻辑，对于它们程序和命题形成了两个不同的类别，作用代数合并了二者为一个单一类别。它可被认为是变异的直觉逻辑，带有星号并带有非交换性的合取，它的单位元不需要是顶元素。不像克莱尼代数，作用代数形成了一个簇，它进一步的是可有限公理化的，至关重要的…
扩充巴科斯范式
在计算机科学中，扩充巴科斯-瑙尔范式（ABNF）是一种基于巴科斯-瑙尔范式（BNF）的拓展分支。该语言有自己的语法和派生规则。ABNF提供一种用于描述双向通信协议的语言的形式系统并由[http://www.rfc-editor.org/std/std68.txt 第68号互联网标准] （"STD 68"，大小写样式按照原文）定义——RFC 5234。该语言经常用于互联网工程任务组（IETF）通信协议的定义语言。 RFC 5234取代RF…
解析表达文法
在计算机科学領域，解析表达文法，简称PEG（），是一种分析型形式文法。PEG在2004年由布莱恩·福特（Bryan Ford）推出，它与20世纪70年代初引入的家族密切相关。 在语法上，PEG很接近上下文无关文法（CFG），但是他們採用了不同的解釋：例如PEG中的选择操作符總是会选中第一个匹配项，而在CFG中则是不明确的。这更接近于字符串识别在实际中的应用，例如使用递归下降解析器的情況。另外不像CFG，PEG不能有：在解析一个字符串的时…
双字母组
双字母组或称二元语法（，或称），作为统计分析文本使用非常广泛；它是由两个字母，或者两个音节，或者两个词构成的双字母组。 簡介 在给定一个前导词情况下，双字母组可帮助计算出现某个词的概率，这是条件概率应用场景： P(W_n|W_{n-1}) = { P(W_{n-1},W_n) \over P(W_{n-1}) } 即，在给定前面一个词W_{n-1}的前提下，出现某个词W_n的概率P(W_n)与他们构成的双字母组的概率一致，换言之，两个词…
形式系統
在邏輯與數學中，一個形式系統（）是由兩個部分組成的，一個形式语言加上一個推理規則或轉換規則的集合。大衛·希爾伯特在1921年推动以形式系統来描述数学知识 。 一個形式系統也許是純粹抽象地制定出來，只是為了研究其自身。另一方面，也可能是為了描述真實現象或客觀現實的領域而設計的。命題邏輯是最简单的形式系統。 理論 在數學領域裡，形式證明是形式系統的產物，由一些公理與演繹規則組成。定理便是形式證明可能的最後一行結論。這幾個步驟總和起來便是數學…
巴科斯范式
巴科斯范式（，縮寫為 ），又称为巴科斯-诺尔范式（，縮寫同樣為 ，也譯为巴科斯-瑙尔范式、巴克斯-诺尔范式），是一种用于表示上下文无关文法的语言，上下文无关文法描述了一类形式语言。它是由约翰·巴科斯（John Backus）和彼得·诺尔（Peter Naur）首先引入的用来描述计算机语言语法的符号集。 尽管巴科斯范式也能表示一部分自然语言的语法，它还是更广泛地使用于程序设计语言、指令集、通信协议的语法表示中。大多数程序设计语言或者形式语…
字符串
字符串（），是由零个或多个字符组成的有限序列。一般记为s=a_1 a_2\dots a_n（0\leq n \lneq\infty）。它是编程语言中表示文本的資料型別;}-。 通常以串的整体作为操作对象，如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。两个字符串相等的充要条件是：长度相等，并且各个对应位置上的字符都相等。设p、q是两个串，求q在p中首次出现的位置的运算叫做模式匹配。串的两种最基本的存…
上下文有关文法
上下文有关文法（CSG，）是一種形式文法，其中任何产生式规则的左手端和右手端都可以被终结符和非终结符構成的上下文所围绕。上下文有关文法比上下文无关文法更一般性，但仍足够有秩序得可以被线性有界自动机所解析。 上下文有关文法的概念是诺姆·乔姆斯基在1950年代介入的，被作为描述自然语言的语法的一种方式，在自然语言中一个单词是否可以出现在特定位置上，要依赖于上下文。可以被上下文有关文法描述的形式语言叫做上下文有关语言。 形式定义 形式文法 G…
抽象語法樹
編程碼的抽象語法樹: ]] 在计算机科学中，抽象语法树（Abstract Syntax Tree，AST），或简称语法树（Syntax tree），是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构。之所以说语法是“抽象”的，是因为这里的语法并不会表示出真实语法中出现的每个细节。比如，嵌套括号被隐含在树的结构中，并没有以节点的形式呈现；而类似于 if-condition-then…
上下文有关语言
在理论计算机科学中，上下文有关语言是可被上下文有关文法定义的形式语言。它是乔姆斯基谱系中的四类文法之一。它在理论和实践中都是最少使用的。 计算性质 上下文有关语言的可计算性等价于线性有界非确定图灵机。它是磁带只有 kn 个单元的非确定图灵机，这里的 n 是输入的大小而 k 是与这个机器关联的常数。这意味着可以被这种机器判定的所有形式语言都是上下文有关语言，而所有上下文有关语言都可以被这种机器判定。 这种语言的集合也叫做 NLIN-SPA…
元字符
元字符（Metacharacter），指SHELL直譯器或正则表达式（regex）引擎等计算机程序中具有特殊意义的字符。 在POSIX擴展正则表达式裡，定义了14个元字符，它们被作为一般的字符使用时，必须要通过「转义」（前面加一个反斜杠「\」）来去除他们本身的特殊意义，这些元字符包括： 开和闭方括号：[和] 反斜线：\ 脱字符：^ 美元符号：$ 句号/点：. 竖线/管道符：| 问号：? 星号： 加号：+ 开和闭 花括号：{和} 开和闭 …
适度上下文有关语言
在形式文法理论中，适度上下文有关语言是可以有效解析但仍拥有足够的上下文敏感性来允许自然语言的解析的一类形式语言。这个概念是 Aravind Joshi 在1985年首次介入的。 此语言类的形式条件有: 1: 语言必须是在多项式时间内可解析的。 2: 语言必须有恒定增长；这意味着字符串长度的分布应当是线性的而非上线性(supralinear)的。这通常由证明某类适度上下文有关语言的泵引理来保证。 3: 语言应当容许有限的跨序列依赖(cro…
重写逻辑
在数学、计算机科学和逻辑学中，重写逻辑是把目标逻辑的抽象语法替换为代数结构，通过用其他术语表示公式子项的各种实现方法。利用重写规则，目标逻辑的推理规则可以被描述出来。 重写逻辑中的结构化公理和语法都由用户自己定义，这使其变得极为简单且通用。在最基本的形式中，一种重写的规则可适用多个规则。因此，当与适当的算法结合时，重写系统被视为绝大多数编程语言和系统应用程序进行规范描述的计算机逻辑，许多定理证明和宣告式编程语言是基于重写的。 1992年…
表现度
表现度在遗传学上指遗传缺陷的表现程度；表现度不同时，性状外显可有轻重的不同，但只要是有这种相应基因型的人，不会完全没有表现。 表现度在计算机科学领域中的形式语言以及有限状态自动机中，代表一个(形式)语言用于描述一类问题或一些解决方案的能力。 请参看 外显度 外部链接 [https://web.archive.org/web/20051210180117/http://www.ndsu.nodak.edu/instruct/mcclean…
无限制文法
在形式语言理论中，无限制文法是对文法的产生式左右两侧都没有限制的形式文法。这是乔姆斯基层级中最一般性的文法类，它们可以识别任意的递归可枚举语言。 形式定义 无限制文法是形式文法 G = (N, \Sigma, P, S)，这里的 N 是非终结符的集合，\Sigma 是终结符的集合，这里的 N 和 \Sigma 是无交集的(实际上这个限制不是必需的，因为无限制文法在非终结符和终结符之间不做真实区分，存在这个指定纯粹是为了使得你在尝试生成文…
帕里克定理
在理論計算機科學中，帕里克定理指出，对于上下文无关语言，如果只关心其中每个终止符号出现的次数，而不考虑它们的顺序，那么存在正则语言与其对应。这个定理可用于确定具有给定数量终止符号的字符串是否能为上下文无关语法接受。1961年罗希特·帕里克第一次证明了它，论文于1966年再次发表。 定义及形式化表述 令\Sigma=\{a_1,a_2,\ldots,a_k\}为一个字母。定义单词的帕里克矢量p:\Sigma^\to\mathbb{N}^k…
语法分析组合子
在计算机编程中 语法分析组合子 是一个 高阶函数 ，它接受几个的语法分析器作为输入，并返回一个新的语法分析函器作为其输出。 在这个上下文中， 语法分析器 是一个函数，它接受字符串作为输入，返回的一些结构作为输出，通常为 分析树 或一组索引表示在字符串中成功停止分析的位置。 分析器组合子使用 递归下降分析 战略，提倡模块式建造和测试。 这种分析技术是所谓的 组合分析。 使用组合子构建的分析器易于构造、可读、模块化、结构良好且易于维护它们被…