2-1文法和语法

文法和语法

语言LV1.

• 语言 = 语法(语言的描述规则)+语义(语言的含义)
• 语法是一种媒介，语义以语法为媒介来予以说明

BNF 范式表示法

元语言符号	含义
<>	表示语法成份
->	(也可用::=) 表示”定义为”或”由…组合成”的含义
|	“或”的含义表示具有相同左部的产生规则可用”|”分开

• 元语言：描述另一个语言的语言

语句分析的语法树

• 

句子推导

• 

句子的规约

• 

字符&字符串

• 任何一种语言，都是有该语言的基本字符所组成的字符串的集合

字符表

• 字母表是元素的非空有穷集合。字母表中的元素称为符号,因此字母表也称为符号集。
• 用希腊字母∑或大写英文字母等表示字母表,用集合元素表示形式枚举字母表中的符号

  z.B.
  字母表A={a,b,c,d}与字母表 ∑={0,1}等

符号串

• 由字母表中的符号组成的任何有穷序列称为符号串
• 通常使用小写字母表示符号串

  z.B.
  x=STR表示x是由符号S、T和R,并按此顺序组成的符号串
  字母表A= {a,b,c}上的一些符号串有:a, b, c, ab, ba, aaca等。

• 符号串长度
  • 如果某符号串x中有m个符号,则称其长度为m,记为 | x | = m
  • 允许不包含任何符号的符号串,称其为空串。空串用ε表示,其长度为0,记为 |ε| = 0

符号串的前缀，后缀和子字符串

• 符号串x的前缀(后缀):从x的尾部(首部)删去0个或若干个符号之后剩余的部分
• 若x的前缀(后缀)不是x自身,则将其称为x的真前缀(真后缀)
• 子符号串
  • 从一个符号串中删去它的一个前缀或 (和) 一个后缀之后剩余的部分称为该符号串的子符号串或子串

文法形式定义

• 一部文法G是一个四元组G =( V_N, V_T, S, P)
  • V_N:非空有限的非终结符号集(一般用大写字母表示)
  • V_T:非空有限的终结符号集(一般用小写字母表示)，设V是文法G的符号集,则有V=V_T∪V_N ,V_T∩V_N=∅
  • S:文法的开始符号或识别符号,亦称公理,S ∈V_N。S代表语言最终要得到的语法范畴
  • 
  • P:有限产生式集

    产生式

    • 就是按一定格式书写的定义语法范畴的文法规则,它是一部文法的实体
    • 形式
      • P->α或P::=α
      • P称为产生式的左部,α为产生式的右部或称为P的侯选式,有P∈V⁺,α∈V^*
    • 公理S至少且必须在文法某个产生式的左部出现一次

  • z.B
    • 数字文法定义为< NUMBER > -> 0 | 1 | 2 | 3 | …| 9
    • V_N = { NUMBER } , V_P = {0,1,2, …,9} , S= V_N,P为定义式本身。

符号串运算

符号串的连接

• 设x和y是两个符号串,如果将符号串y直接拼接在符号串x之后,则称此操作为符号串x和y的连接,记作xy

  设有字符串 j=abc,k=xyz 则jk=abcxyz,kj=xyzabc

符号串的方幂

• 设x是某字母表上符号串,把x自身连接 n 次得到符号串z,即 z = xx…x (n个x) ,称z是符号串x的n次幂,记作z=xⁿ

  设x=abc

  • x⁰=ε
  • x¹=abc
  • x²=abcabc

符号串集合的乘积

• 设A、B 是两个符号串集合,AB表示A与B的乘积,则有定义AB={xy | (x∈A)∧(y∈B) }

  设A={ab,c}, B={d,ef},则AB={abd, abef, cd, cef}

• 注:{ε}A=A{ε}=A, ∅A=A∅=∅ ,其中∅为空集
• 注:∅={ }≠{ε}

符号串集合的方幂

• 设A是符号串集合,A自身的乘积可以用方幂表示 则有定义-设P为字符串集:
  • A⁰= {ε}
  • A¹=A
  • A²=AA
  • A³=A²A=AAA
  • ……
  • Aⁿ=A^n-1A=AA…A
• 显然有 A^i+j=AⁱA^j

  设P= { ab, x, aby }
  有 P2=PP={abab, abx,ababy, xab, xx, xaby,abyab, abyx, abyaby}

符号串集合的并

• 设P、Q为字符串集,集合P∪Q为P和Q的并,它的元素是P或Q中的元素。

  P={0, 1, 01} Q={0, 10, 11, 00}

  • P ∪ Q = {0, 1, 01, 10, 11, 00}

符号串集合的闭包

• 设A为符号串集
  • A的正闭包记作A⁺,则有A⁺= A¹∪A²∪…∪ Aⁿ∪…
  • A的自反闭包记作A^*,则有A^*=A⁰∪A⁺={ε}∪A⁺= A⁺∪{ε}
• 由定义可知
  • A⁺=AA^*=A^*A
  • A^*=A⁰UA⁺

    设有A={01,10}

    • A^* ={ ε,01,10,0110,1001,010101,100110,…}
    • A⁺ ={01,10,0110,1001,010101,100110,…}

语言LV2

非形式化定义

• 给定一部文法G, 从G的开始符号S出发,反复使用产生式对非终结符进行替换,最后所得到的终结符号串的全体,即为文法G所描述的语言L(G)

  设有文法G

  • S → P | aPb
  • P → ba | bQa
  • Q → ab

  则:L(G)={ba, abab, baba, ababab}

直接推导 “ => ”

• 有V=αAβ=>αγβ=W(α,β,γ∈(V_N∪V_T)*),当且仅当P中存在一条规则A->γ,称V直接推导出W (或W直接归约到V),记作:V => W

直接推导序列

• 如果存在V = α₀ => α₁ , α₁ => α₂ , … , α _n-1 => α_n = W 或α₁ => α₂ => α₃ => … => α_n-1 => α_n
  • 则 V 经过n步(n>0)可以推导出 W,记作:

    

  • 当
    V =>(+) W或V = W,记作

    

最左/右推导

• 在推导过程中,总是对句型中的最左(右)边的非终结符进行替换,称为最左(右)推导

  • 句型

    • 设有文法G[S],若 (α∈(V_T∪V_N)^*),则称α为G[S]的句型

  • 句子

    • 设有文法G[S],若 (α∈V_T^*),则称α为G[S]的句子

  • 规范推导/规范句型/ 规范归约

    • 最右推导也称为规范推导。仅用规范推导得到的句型称为规范句型 。规范推导的逆序为规范归约。

      设有文法G[E]:E -> E*E | E+E | (E) | i
      设有句子$1: i*i+i

      • 最左推导:E => E*E => i*E => i*E+E => i*i+E => i*i+i
      • 最右推导:E => E*E => E*E+E => E*E+i => E*i+i => i*i+i

  • 文法的递归
    • 设有文法G,A->γ是G的产生式,若γ具有αAβ的形式,或 ,则称G是递归文法
    • 若α = ε,则G为左递归文法。若β = ε,则G为右递归文法
    • 递归文法分类
      • 直接递归 : 直接引用自身 如 E-> Ea
      • 间接递归 : 间接引用自身 如 E-> Ab A->Ea => E-> Eab
      • 左(右)递归 : 与直接间接无关

        设有文法G：T -> Qc | c ; Q → Rb | b ; R → Ta | a
        有T=>Qc=>Rbc=>Tabc 即 则文法G是间接左递归文法

形式定义

• 文法G所产生的语言L(G)
• 

• z.B.

  • 设有语言 L(G1)={abⁿa | n>=0} 求G1?

    G1:S-> aa|aRa R->b|Rb

  • 设有文法G: S->0S1|01 求L(G)?

    L(G)={0ⁿ1ⁿ|n>=1}

• 文法等价

  • 若 L(G1)= L(G2),则称文法G1和G2是等价的

    z.B.

    • G1: S-> aa|aRa R->b|Rb
    • G2: S->aRa R->Rb|b|ε
    • L(G1)=L(G2)

BNF表示法

• 元语言符号集:{->,<,>,|}
• 详细见文首

扩充BNF表示法

1. 引入花括号
   • 表示字符串t的多次或任意次出现
   • n表示t重复的最小次数
   • m表示t重复的最大次数

     z.B.
     FORTRAN语言中标识符的定义。假设标识符是长度≤8的字母开头后跟字母或数字的字符串,则有
     

2. 引入圆括号 ( )
   • 提取产生式中的公共因子,简化产生式的表示

     有文法规则 U -> xa | xb | … | xz
     引入圆括号提取公共字符串x后有:
     U -> x(a | b | … | z)

3. 引入方括号 [ t ]
   • 表示字符串 t 可有可无。

     设有条件语句的文法
     <条件语句> -> <如果子句>|<如果子句>else<语句>
     可简化为
     <条件语句> -> <如果子句> [else<语句>]

语法图

PASCAL语言中标识符的定义如下图:

语法树与二义性

树的组成	对应文法G的结构
根节点	S
中间节点	VN
叶节点	VT
结点间的关系	G的产生式规则

• 语法树是句子结构的图形表示,它代表了句子的推导结果,有利于理解句子语法结构的层次

  z.B.
  设有无符号整数的文法

  • <无符号整数> -> <数字串>
  • <数字串> -> <数字串><数字>|<数字>

  • <数字> -> 0 | 1 | 2 | … | 9

    
    一棵语法树包括了一个句型的所有可能的推导过程

二义文法

• 对一部文法G,如果至少存在一个句子,有两棵(或两棵以上)不同的语法树,则称该句子是二义性的。包含有二义性句子的文法称为二义文法
• 定义提供了对给定文法在某一范围内判定是否是二义性文法的充分条件

  设有文法G1 : E → E+E | E*E | (E) | i
  
  
  

文法二义性的消除

• 原因分析
  • 运算符+和*未体现优先级
  • +和*自身结合规则不明确
• N.Chomsky 分类
  1. 0型文法(语文法)
     • 如果对文法G中的规则α->β不加任何限制,则称G为0型文法或短语文法,其中,α,β∈(V_T∪V_N)^*且α≠ε
     • 0型文法相应的语言为0型语言L0,0型语言可由图灵机(Turing)来识别。

       例如文法G:

       • S → aQb
       • aQb → caRbc
       • aRb → caba

  2. 1型文法(上下文有关文法)
     • 设文法G=(VN,VT,S,P),对P中的每个产生式限制为形如:
       αAβ->αγβ
       其中,A∈V_N,α,β∈(V_T∪V_N)^*,γ∈(V_T∪V_N)⁺,则称文法G为1型文法或上下文有关文法
     • 1型文法相应的语言为1型语言L1,1型语言可由线性有界自动机来识别

       例如文法G:

       • S → aSBC | abC
       • CB → CD
       • CD → BD
       • BD → BC
       • bB → bb
       • bC → bc
       • cC → cc

       L(G1) ={aⁿbⁿcⁿ | n≥1}

  3. 2型文法(上下文无关文法)
     • 设文法G =(V_N ,V_T , S , P),对P中的每个产生式限制形如:
       A->α
       其中,A∈V_N,α∈(V_T∪V_N)^* 则称文法G为2型文法或上下文无关文法
     • 2型文法相应的语言为2型语言L ,2型语言可由非确定的下推2自动机来识别

       例如文法G:

       • S → Ac | Sc
       • A → ab | aAb

       L(G₂) ={aⁿbⁿc^m | n,m≥1}

  4. 3型文法(正则文法、线性文法)
     • 设文法G=(V_N,V_T, S, P),对P中的每个产生式形如
       A->aB或A->a或(A->Ba 或 A->a)
       其中 A,B∈ V_N ,a∈V_T ,则称文法G为3型文法(正则文法或线性文法)
     • 3型文法相应的语言为3型语言L3,3型语言可由确定的有限状态自动机来识别。

       例如文法G:

       • S → Bc | Sc
       • B → Ab | Bb
       • A → Aa | a

       L(G3) ={a_nb_mc_k | n,m,k≥1}

四类文法总结

文法	识别
0型文法L0	图灵机
1型文法L1	线性有界自动机
2型文法L2	非确定下推自动机
3型文法L3	确定有限自动机

•