两级文法查看源代码讨论查看历史
| 两级文法 |
|
中文名: 两级文法 学 科: 计算机 |
两级文法是下列两种形式结构之一：两级形式语言的形式文法，这种语言是按两个级别来指定的形式语言，比如，字和句两个级别。用来生成其他形式文法的形式文法。定义次级文法的规则的上下文无关文法可以生成导出文法的规则的一个有效的无限集合。可以生成另一个上下文无关文法的两级文法比单一层上下文无关文法更加强力，因为有生成力的两级文法已经实际上被证实是图灵完全的。
例子
众所周知的非上下文无关语言是
这个语言的的两级文法是元文法
N::= 1 | N1
X::= a | b
以及文法模式
Start::=
- =
- = X
形式文法
在计算机科学中，形式语言是：某个字母表上，一些有限长字串的集合，而形式文法是描述这个集合的一种方法。形式文法之所以这样命名，是因为它与人类自然语言中的文法相似的缘故[1]。
形式文法描述形式语言的基本想法是，从一个特殊的初始符号出发，不断的应用一些产生式规则，从而生成出一个字串的集合。产生式规则指定了某些符号组合如何被另外一些符号组合替换。举例来说，假设字母表只包含'a'和'b'两个字符，初始符号是'S'，我们应用下述规则：
1. S -> aSb
2. S -> ba
于是我们可以通过把"S"重写为"aSb"（规则1），我们还可以继续应用这条规则把"aSb"重写为"aaSbb"。这个重写的过程不断重复，直到结果中只包含字母表中的字母为止。在例子中，我们可以得到S -> aSb -> aaSbb -> aababb这样的结果。由文法刻画的语言，包含了所有可以这样产生的字串，比如ba, abab, aababb, aaababbb等等。
形式语言
在数学、逻辑和计算机科学中，形式语言（英语：Formal language）是用精确的数学或机器可处理的公式定义的语言。
如语言学中语言一样，形式语言一般有两个方面:语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论，它只研究语言的语法而不致力于它的语义。在形式语言理论中，形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。