语言的定义
# 语言的定义
# 推导 (Derivations) 和归约 (Reductions)
# 直接推导
定义
- 给定文法
, 如果 ,那么可以将符号串 中的 替换为 - 也就是说,将
重写(rewrite)为 - 记作
- 此时,称文法中的符号串
直接推导(directly derive)出
- 也就是说,将
# n 步推导
定义
- 如果
, 则可以记作 - 称符号串
经过 步推导得出 ,可简记为 , 即为直接推导 表示 “经过正数步推导” 表示 “经过若干(可以是0)步推导”
- 称符号串
# 推导和归约的实例
实例
提示
- 推导是用产生式的右部替换产生式的左部
- 推导是从生成语言的角度应用语法规则
- 归约是用产生式的左部替换产生式的右部
- 归约是从识别语言的角度应用语法规则
- 推导和归纳均相当于代数的代入
- 最左推导的逆过程就是最右归约
# 句型和句子
定义
- 如果
则称 是 的一个句型(sentential form) 为文法的开始符号 - 一个句型中既可以包含终结符,又可以包含非终结符,也可能是空串
- 如果
, 则称 是 的一个句子(sentence) - 句子是不包含非终结符的句型
实例
# 语言的形式化定义
定义
- 由文法
的开始符号 推导出的所有句子构成的集合称为文法 生成的语言,记为 。即
例: 生成标识符语言的文法 G
其中
为字母数字串,其是无穷的, 此处相当于是无穷语言的有穷表示
# 语言上的运算
运算 | 定义和表示 |
---|---|
例: 令
编辑 (opens new window)