离散数学中的语言与文法

形式语言

形式语言可以被描述为通过一组定义良好的语法规则指定的语言。

形式文法

形式文法 G 可以被描述为语言 L 的紧凑、精确的定义。

现在我们将学习一些定义，以便我们能够清楚地理解短语结构文法。

词汇

词汇 V 或字母表可以被描述为有限非空元素集合，也称为符号。

Word

V 上的一个词可以被描述为包含 V 元素有限长度的字符串。词也称为句子。

空字符串（Empty String）

空字符串可以被描述为不包含任何符号的字符串。此字符串也称为空字符串，可以用符号 λ 表示。

词集合和语言集合

借助符号 V*，我们可以表示 V 上的词集合。V 上的语言可以被描述为 V* 的子集。

短语结构文法

短语结构文法 G 可以按以下方式描述

其中

V 用于表示词汇表

T 用于表示 V 的子集 T，其中包含终结符号。

S 用于表示 V 中的起始符号

P 用于表示有限的生成式集合

借助 N，我们可以表示集合 V-T。N 的元素也称为非终结符号。P 中每个生成式的左侧至少包含一个非终结符号。

可推导性

假设有一个短语结构文法 G = (V, T, S, P)。假设 w₀ = lz₀r（l、z₀ 和 r 的连接）和 w₁ = lz₁r 是 V 上的字符串。如果存在 G 的一个生成式：z_o → z₁，在这种情况下，w₁ 将直接从 w₀ 推导出来，换句话说，它可以写成 w₀ ⇒ w₁。如果存在 V 上的字符串序列 w₀, w₁, w₂, w₃, ...., w_n，使得 w₀ ⇒ w₁, w₁ ⇒ w₂, w₂ ⇒ w₃, ...., w_n-1 ⇒ w_n，在这种情况下，w_n 将从 w₀ 推导出来，并且可以写成 w₀ ⇒ w_n。如果存在从 w₀ 获得 w_n 的步骤序列，则它将被视为推导。

G 生成的语言 L

假设有一个短语结构文法 G = (V, T, S, P)。借助符号 L(G)，我们可以表示 G 生成的语言。它用于包含所有终结符字符串的集合，我们可以从起始状态 S 驱动它。G 生成的语言可以通过另一种方式显示，如下所述

L(G) = {w ∈ T* | S ⇒ w}

文法类型

存在各种文法类型和对生成式 w1 → w2 的限制，如下所述

推导树

借助上下文无关文法，我们可以在语言中生成推导。我们可以借助有序有根树以图形方式表示推导树，该树也称为推导树或分析树。这棵树的起始符号可以用根表示。这棵树的非终结符号用于表示内部顶点。终结符号由树的叶子表示。如果存在包含生成式 A → w 的推导，则显示 A 的顶点将包含子顶点，这些子顶点用于显示 w 中的每个符号，其中 w 用于表示一个词。此过程的顺序将从左到右。

巴克斯-瑙尔范式 (BNF)

BNF 可以描述为许多计算机语言（如 Java）的句法规则。如果存在类型 2 文法，则生成式的 LHS 上将只有一个非终结符号。因此，我们不会一个接一个地列出所有生成式，而是将所有这些在 LHS 上具有相同非终结符号的生成式组合成一个语句。为了表示生成式，我们使用符号 →，但在这里我们将使用符号 ::=。所有非终结符号都将用括号 () 括起来，并且所有生成式的 RHS 都将列在同一个语句中，并用竖线分隔。以下示例可用于显示 BNF