文法定义

字数

643 字

阅读时间

3 分钟

句子的构成规则

自然语言的例子

释义解释：
- 用尖括号括起来的部分称为语法成分，如：<名词> 等
- 没有用尖括号括起来的部分称为语言的基本符号，如：little，boy等

文法的形式化定义

字母表示

$G = (V_{T}, V_{N}, P, S)$

G：文法,
$V_{T}$ ：终结符集合
- V：vector；
- T：terminal symbol（终结符）
  - 终结符：文法所定义的语言的基本符号，有时也称为token
  - 例如： $V_{T} = {a p p l e, b o y, e a t, l i t t l e}$
    - 该集合中，文法G是描述句子的组成规则的，而句子的基本符号是单词，因此这些单词构成了该文法的终结符集
$V_{N}$ ：非终结符集合
- 非终结符(nonterminal)：用来表示语法成分的符号，有时也称为“语法变量”
- 例如： $V_{N} = {< 句子 >, < 名词短语 >, < 动词短语 >, < 名词 >, . . .}$

**注意！！！！！**

终结符 $V_{T}$ 和非终结符 $V_{N}$ 是非相交的（即：没有交集）因此， $V_{T} \cup V_{N} = 文法符号集$

$P$ ：产生式集合
- 产生式：描述了将终结符和非终结符组合成串的方案
- 产生式的一般形式： $α \to β$
  - 读作： $α$ 定义为 $β$
  - $α$ 和 $β$ 都是文法符号串
  - 要求/条件：
    1. $α \in (V_{T} \cup V_{N})^{+}$ ，且 $α$ 中至少包含一个非终结符（ $V_{N}$ 中的一个元素），称为产生式的头部，或称左部
    2. $β \in (V_{T} \cup V_{N})^{*}$ ：称为产生式的体，或称右部
S：开始符号
- $S \in V_{N}$
- $S$ 表示的是该文法中最大的语法成分，例： $S =< 句子 >$

文法例子

$E$ ：表达式（Expression）

约定

在不引起歧义的前提下，可以只写产生式

例子简写后的结果为：

产生式的简写

对一组有相同左部的 $α$ 产生式 $α \to β_{1}, α \to β_{2}, . . . α \to β_{n}$ 可以简记为： $α \to β_{1} | β_{2} | . . . | β_{n}$ 读作： $α$ 定义为 $β_{1}$ ，或者 $β_{2}$ ，...，或者 $β_{n}$ 其中， $β_{1}, β_{2}, . . ., β_{n}$ 称为 $α$ 的候选式(Candidate) 例：

符号约定

除非特别说明，第一个产生式的左部就是开始符号

贡献者

freeway348

文件历史

最后编辑于大约 1 个月前查看完整历史