admin 管理员组

文章数量: 887021

文法

文章目录

  • 文法
    • 基本概念
    • 文法的形式定义

文法

基本概念

  • 符号：字母、数字、标点…
  • 字母表∑：一个有穷符号集合*（比如ASCII码就是一个字母表）*
    • 字母表的乘积
      • ∑1∑2 = { ab | a∈∑1，b∈∑2}
    • 字母表的n次幂
      • ∑0 = ∅
      • Σn = Σn-1 * Σ，n > 1
    • 字母表Σ的正闭包
      • Σ+ = Σ ∪ Σ2 ∪ Σ3…
      • 可以看做是len = 1、2、...n，的字符串集合
    • 字母表Σ的克林闭包
      • Σ* = Σ0∪Σ ∪ Σ2 ∪ Σ3…
      • 可以看做是len = 0、1、2、...n，的字符串集合
  • 串（字符串）: ∀x∈Σ*，x称为Σ是Σ上的一个字符串
    • 串是字母表中符号的一个有穷数列
    • 串s的长度记作|s|，指串中字符的个数
    • 用ε表示空串，|ε| = 0
    • 串的运算
      • 连接：若x、y是串，那么x和y的连接为xy或yx，xy中，x称为前缀，y为后缀
      • εs = sε = s

文法的形式定义

  • G = {VT, VN, P, S}

  • VT: 终结符集合
      文法所定义的语言的基本符号  token

  • VN: 非终结符结合
      表示语法成分的符号  语法变量

    • VT ∩ VN = ∅
    • VT ∪ VN = 文法符号集

  • P: 产生式

    • 一般形式：α→β，读作α定义为β
    • α∈（VN∪VT)+，且α中至少包含一个属于VN的元素：称为产生式的头或者左部
    • β∈（VT∪VN):成为产生式的体或者右部
    • 若有α→β1，α→β2…α→βn，即这些产生式中拥有相同的头部，则可以简写成α→β1|β2|…|βn，β1、β2…βn称为α的候选式，| 读作’或’

  • S: 开始符号

    • 表示该文法中最大的语法成分，是特殊的非终结符

本文标签： 文法

版权声明：本文标题：文法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1686718461h28887.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。