文法，语言

文法和语言的形式定义

  • 规则：规定用”::=”表示产生式（由…组成）对(U, x), 通常写为: U ::= x 或U → x
  • 用规则推导句子：不断地用规则右部替代左部（最左推导从左向右替代、最右推导），直到句子只包含终结符
  • 文法（描述规定语言结构）：G=(Vn, Vt, P, Z)
    • Vn：非终结符
    • Vt：终结符
    • P：规则的集合
    • Z：开始符号，Z∈Vn
  • 语言：L(G)={w|w∈Vt*, Z=>w} 已知文法可以通过推导得到语言（句子的集合）
  • 句型：通过画出句型的语法树，可以方便地找到句型的短语（句型的某个非终结符所能推出的符号串），简单短语，句柄（最左简单短语）