在计算理论（TOC）中，语法和产生式是什么意思？

让我们了解一下计算理论 (TOC) 中语法的概念。

语法介绍

在字母表∑上的语言是由∑中字符串组成的集合。

语法是用于定义语言的一组规则。简而言之，它是语言中字符串的结构。

为了描述一种语言的语法，需要两个字母表（符号）集合。这些解释如下：

  • 终结符是从中构成语言中所有字符串的符号——生成语言的“给定”字母表的符号。这些通常是小写字母。

  • 非终结符是用于定义语法替换规则（在产生式规则中）的“临时”符号（与终结符不相交）。在产生式成功生成语言的有效字符串之前，必须将所有这些替换为终结符。这些通常是大写字母。

产生式

此外，语言L（在字母表∑上）的语法包含如下形式的一组语法规则（产生式）：

α → β，

其中α，β是从终结符（∑）和非终结符集合中取出的符号字符串。

语法规则α → β可以用以下几种方式阅读：

  • “用β替换α”，

  • “α产生β”，

  • “α重写为β”，

  • “α归约为β”。

语法的形式化定义

考虑以下示例：

如果∑ = {a，b}并且S是一个非终结符，则规则S → aS，S → ∧是语言L的产生式的示例。

现在我们准备给出语法的形式化定义，如下所示：

  • 称为终结符的符号字母表T。这与结果语言的字母表相同。

  • 称为非终结符的语法符号字母表N，用于产生式规则。

  • 一个特定的非终结符，称为起始符号。它通常是S。

  • 形式为α → β的有限产生式集合，其中α和β是字母表N∪T上的字符串。

更新于：2021年6月15日

3K+ 浏览量

启动你的职业生涯

完成课程获得认证

开始学习
广告