MENU

【编译原理】上下文无关文法(CFG)及其他基本概念

June 2, 2020 • Read: 813 • 编程之路,编译原理

上下文无关法

一个生动的例子

自然语言中的句子的典型结构 :

  • 主语 谓语 宾语
  • 名词 动词 名词

例子:

  • 名词:{羊、老虎、草、水}
  • 动词:{吃、喝}
  • 句子:羊吃草、老虎喝水、老虎吃草、老虎吃水、羊喝草等等(因为是语法分析,所以暂时不考虑语义的正确性)

用字母代替上述词语:名词N、动词V、羊s、老虎t、草g、水w、吃e、喝d。

形式化如下:

S -> N V N
N -> s
N -> t
N -> g
N -> w
V -> e
V -> d
//非终结符: {S, N, V}
//终结符: {s, t, g, w, e, d}
//开始符号: S
  • 由N可以推出{s, t, g, w},V可以推出{e, d},S可以推出N V N。
  • N、V、S这些可以推出其他符号的叫非终结符
  • s, t, g, w, e, d这些不能够再推出其他符号的叫终结符
  • S是整个结构的开始,称为开始符号
  • 像$S \rightarrow N V N$、$N \rightarrow s$这样的式子叫做产生式
  • 这种写法又叫做文法

这里我们约定俗成大写字母表示非终结符号,小写字母表示终结符号。其他地方也有可能不一样。

得出公式

上下文无关文法G是一个四元组: $G=(T,N,P,S)$

  • T是终结符集合
  • N是非终极符集合
  • P是一组产生式规则

    • 规则形式:$X \rightarrow β_1 β_2 ...$
    • 其中$X ∈ N$,$β ∈ (T U N)$
  • S是唯一的开始符号,切$S ∈ N $

另一个例子

E -> num
   | id
   | E + E
   | E * E
 
// G = (N, T, P, S)
// N = {E}
// T = {num, id, +, *}
// S = E
// P = 略

以后为了方便书写与直观感受,相同部分直接用或符号 “|”代替

分析树和二义性

分析树

推导可以表达成树状结构(和推导所用的顺序无关)
特点:

  • 非叶子结点代表非终结符
  • 叶子节点代表终结符
  • 每一步推导代表如何从双亲节点生成它的直接孩子节点

示例

E -> num
   | id
   | E + E
   | E * E
 
// 推导句子:3+4*5
E -> E + E
  -> 3 + E
  -> 3 + E * E
  -> 3 + 4 * E
  -> 3 + 4 * 5
// 推导方式2
E -> E * E
  -> E + E * E
  -> 3 + E * E
  -> 3 + 4 * E
  -> 3 + 4 * 5

分析树分别如下(左右):

分析树的含义取决于树的后序遍历。

二义性

  • 给定文法G,如果存在句子s,它有两棵不同的分析树,那么称G是二义性文法。
  • 从编译器角度,二义性文法使同一个程序会有不同的含义,因此程序运行的结果不唯一
  • 解决方案: 文法的重写
E -> E + T
   | T
T -> T * F
   | F
F -> num
   | id
 
// 推导句子:3+4*5
E -> E + T
-> T + T
-> F + T
-> 3 + T
-> 3 + T * F
-> 3 + F * F
-> 3 + 4 * F
-> 3 + 4 * 5

其他基本概念

  • 最左推导:每次总是选择最左侧的符号进行替换。
  • 最右推导:每次总是选择最右侧的符号进行替换。
  • 句柄:给定句型中的最左简单短语就是句柄。
  • 句型:开始符号 S → x,其中x是非终结符or终结符。
  • 句子:开始符号 S → x,其中x是终结符。(给定文法G,从G的开始符号S开始,用产生式的右部替换左侧的非终结符,此过程不断重复,直到不出现非终结符为止,最终的串称为句子)

给定文法G和句子s,语法分析要回答的问题:是否存在对句子s的推导。

  • 活前缀:在得到一个规范句型的完整句柄之前所识别的符号串

从语法分析树看3个概念:

  • 短语:一个句型的语法树中任一子树叶结点所组成的符号串
  • 直接短语:子树中不再包含其他的子树,不能再推出其他的式子,即叶子结点。
  • 句柄:给定句型中的最左简单短语就是句柄

短语/直接短语/句柄 案例

问:

解:

$E+T*F$为此文法的一个句型:

  • 短语: $T*F$, $E+T*F$
  • 直接短语/简单短语:$T*F$
  • 句柄:$T*F$

简析:对于子树T来说,其所有叶子节点为:$T*F$,对于E来说,其所有叶子节点为:$E+T*F$,故短语为 $T*F$ 和 $E+T*F$, 直接短语为 $T*F$, 句柄为最左边的直接短语$T*F$

- - - 结束 - - -
  • 文章标题:【编译原理】上下文无关文法(CFG)及其他基本概念
  • 文章链接:https://blog.canye365.cn/archives/325.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )
  • Last Modified: April 10, 2021