Compilers Second Lecture: Languages and Syntax

2.1 基本概念

• 字母表(Alphabet)：\Sigma（Sigma），有穷字符集合

• 字母表上的运算

  • 乘积(Product)：\Sigma_1\Sigma_2 = \{ab | a ∈ Σ₁, b ∈ Σ₂\}
  • 幂(Power)：\Sigma^0 = {\epsilon}, Σ^n = Σ^{n-1}Σ, n ≥ 1
  • 正闭包(Positive Closure)：\Sigma^+ = Σ ∪ Σ¹ ∪ Σ² ∪ …
  • 克林闭包(Kleene Closure)：\Sigma^* = Σ⁰ ∪ Σ⁺

• string(String)：对于所有x \in \sum^*，

• \sum上的每个符号都是有限个数的排列，

• 串s的长度记作d(s)，

• d(\epsilon) = 0

在字符串上的操作
连接操作
空字符串在连接运算中起着单位元的作用
对于任意字符串x = yz(其中 y,z \in S^*)，称 y 为 x 的前缀部分而 z 为 x 的后缀部分

* 幂运算：连接$n$次，$s^0 = \epsilon$

2.2 文法的定义

自然语言 - 句子构成

* 语法成分