IT小白

这个屌丝很懒，什么也没留下！

热门标签

编译原理-4-上下文无关文法

作者：IT小白 | 2024-03-28 20:44:14

踩

上下文无关文法

上下文无关文法(CFG, Context-Free Grammer, 上下文无关文法)

LL(1)可以完成手写分析器
LR(1)可以更不容易出现细节问题
Bison工具是本实验使用的工具。

1. 上下文无关文法(CFG)定义

上下文无关文法 $G$ 是一个四元组 $G = (T, N, P, S)$ :
1. T是终结符号 Terminal集合, 对应于词法分析器产生的词法单元
2. N是非终结符号 Non-terminal集合
3. P是产生式 Production集合

$\in N \rightarrow \alpha \in (T \cup N)*$

头部/左部(Head) $A$ :
1. 单个非终结符，必须只有一个，是命名为上下文无关文法的原因。
2. 如果有多个则不符合上下文无关文法，会被成为上下文有关文法，但是几乎无法处理。
体部/右部(Body) $\alpha$ :
1. 终结符与非终结符构成的串
2. 也可以是空串 $\epsilon$
$S$ 为开始(Start)符号
要求 $\in N$ 且唯一。

1.1. 上下文无关文法示例

一个符号要么是终结符号，要么是非终结符号
终结符号表示到此为止，无法再进行替换

\begin{array}{l} G = ({S}, {(,)}, P, S) \\ S \to S S \\ S \to (S) \\ S \to () \end{array}

$\begin{array}{l} G = (\{S\}, \{(, )\}, P, S) \\ S \rightarrow SS \\ S \rightarrow (S) \\ S \rightarrow () \\ \end{array}$

G = ({S}, {(,)}, P, S) S \to S S S \to (S) S \to ()

上面的文法表示任意嵌套的所有匹配好的括号串

\begin{array}{l} G = ({S}, {a, b}, P, S) \\ S \to a S b \\ S \to ϵ \end{array}

$\begin{array}{l} G = (\{S\}, \{a, b\}, P, S) \\ S \rightarrow aSb \\ S \rightarrow \epsilon \\ \end{array}$

G = ({S}, {a, b}, P, S) S \to a S b S \to ϵ

可以有很多的情况

1.2. 条件语句文法

条件语句文法中包含悬空(Dangling)-else文法的问
这样的文法是有问题，我们进一步分析才可以，OTHER作为终结符。

1.3. 约定

约定: 如果没有明确指定, 第一个产生式的头部就是开始符号，用来避免写如上例子中的一些描述

1.4. 关于终结符号的约定

下述符号是终结符号:(通常的约定)

在字母表里排在前面的小写字母，比如a、b、c。
运算符号，比如+、*等。
标点符号，比如括号、逗号等。
数字，0、1、… 9。
黑体字符串，比如id或if。每个这样的字符串表示一个终结符号。

1.5. 关于非终结符号的约定

下述符号是非终结符号:

在字母表中排在前面的大写字母，比如A、B、C。
字母S。它出现时通常表示开始符号。
小写、斜体的名字，比如expr或stmt.

2. 语义

上下文无关文法 $G$ 定义了一个语言 $L (G)$
语言是串的集合

3. 推导(Derivation)的定义

3.1. 表达式文法

$\rightarrow -E|E + E | E ∗ E | (E) | id$

推导即是将某个产生式的左边替换成它的右边
每一步推导需要选择替换哪个非终结符号，以及使用哪个产生式

$\Rightarrow -E \Rightarrow −(E) \Rightarrow −(E+E) \Rightarrow −(id+E) \Rightarrow −(id+id)$

\begin{array}{l} E \Rightarrow - E : 经 过 一 步 推 导 得 出 \\ E \xRightarrow + - (i d + E) : 经 过 一 步 或 多 步 推 导 得 出 \\ E \xRightarrow * - (i d + E) : 经 过 零 步 或 多 步 推 导 得 出 \end{array}

$\begin{array}{l} E \Rightarrow −E : 经过一步推导得出 \\ E \xRightarrow{+} −(id + E):经过一步或多步推导得出 \\ E \xRightarrow{*} −(id +E):经过零步或多步推导得出 \\ \end{array}$

E \Rightarrow - E : 经 过 一 步 推 导 得 出 E + - (i d + E) : 经 过 一 步 或 多 步 推 导 得 出 E * - (i d + E) : 经 过 零 步 或 多 步 推 导 得 出

$\Rightarrow -E \Rightarrow −(E) \Rightarrow −(E+E) \Rightarrow −(E+id) \Rightarrow −(id+id)$

3.2. Definition (Sentential Form，句型)

如果 $\xRightarrow{*} \alpha$ ，且 $\alpha \in ( T \cup N)^*$ ，则称 $\alpha$ 是文法G的一个句型(包含非终结符)

\begin{array}{l} E \to - E | E + E | E * E | (E) | i d \\ E \Rightarrow - E \Rightarrow - (E) \Rightarrow - (E + E) \Rightarrow - (i d + E) \Rightarrow - (i d + i d) \end{array}

$\begin{array}{l} E \rightarrow -E | E + E | E ∗ E | (E) | id \\ E \Rightarrow -E \Rightarrow −(E) \Rightarrow −(E+E) \Rightarrow −(id+E) \Rightarrow −(id+id) \end{array}$

E \to - E ∣ E + E ∣ E * E ∣ (E) ∣ i d E \Rightarrow - E \Rightarrow - (E) \Rightarrow - (E + E) \Rightarrow - (i d + E) \Rightarrow - (i d + i d)

3.3. Definition (Sentence，句子)

如果 $\xRightarrow{*} w$ ，且 $\in T^*$ ，则称w是文法G的一个句子(没有非终结符了)
句子就是这个语言中的串

4. Definition (文法G生成的语言L(G))

文法F的语言L(G)是它能推导出的所有句子构成的集合。

$\in L(G) \Leftrightarrow S \xRightarrow{*} w$

4.1. 关于文法G的两个基本问题

Membership问题:给定字符串 $\in T^*, x \in L(G)$ ？字符串可不可以由文法推理得到
L(G)究竟是什么？

4.1.1. 问题一:Membership问题

给定字符串 $\in T^*, x \in L(G)$ ，(即检查x是否符合文法G)
这就是语法分析器的任务:为输入的词法单元流寻找推导、构建语法分析树, 或者报错

根节点是文法G的起始符号
叶子节点是输入的词法单元流
常用的语法分析器以自顶向下或自底向上的方式构建中间部分

4.1.2. 问题二:L(G) 是什么?

这是程序设计语言设计者需要考虑的问题

4.1.2.1. 根据文法G推导语言L(G)

例子一

$\begin{array}{l} S \to S S \\ S \to (S) \\ S \to () \\ S \to ϵ \\ L (G) = {良匹配括号串} \end{array}$ $\begin{array}{l} S \rightarrow SS \\ S \rightarrow (S) \\ S \rightarrow () \\ S \rightarrow \epsilon \\ L(G) = \{良匹配括号串\} \\ \end{array}$ $S \to S S S \to (S) S \to () S \to ϵ L (G) = {良匹配括号串}$

例子二

$\begin{array}{l} S \to a S b \\ S \to ϵ \\ L (G) = a^{n} b^{n} | n \geq 0 \end{array}$ $\begin{array}{l} S \rightarrow aSb \\ S \rightarrow \epsilon \\ L(G) = {a^nb^n|n \geq 0 } \\ \end{array}$ $S \to a S b S \to ϵ L (G) = a^{n} b^{n} ∣ n \geq 0$

4.1.2.2. 根据语言L(G)来推导文法G

目标生成：字母表 $\sum = {a, b}$ 上的所有回文串(Palindrome)构成的语言

\begin{array}{l} S \to a S a \\ S \to b S b \\ S \to a \\ S \to b \\ S \to ϵ \\ S \to a S a | b S b | a | b | ϵ \end{array}

$\begin{array}{l} S \rightarrow aSa \\ S \rightarrow bSb \\ S \rightarrow a \\ S \rightarrow b \\ S \rightarrow ϵ \\ S \rightarrow aSa|bSb|a|b|\epsilon \\ \end{array}$

S \to a S a S \to b S b S \to a S \to b S \to ϵ S \to a S a ∣ b S b ∣ a ∣ b ∣ ϵ

目标生成： ${b^na^mb^{2n}|n \geq 0, m \geq 0}$

$\begin{array}{l} S \to b S b b | A \\ A \to a A | ϵ \end{array}$ $\begin{array}{l} S \rightarrow bSbb|A \\ A \rightarrow aA|\epsilon \\ \end{array}$ $S \to b S b b ∣ A A \to a A ∣ ϵ$
目标生成： $\{x\in \{a, b\}^* | x 中a,b个数相同 \}$
1. 证明：a可以是空串
2. 证明：a以a开头，那么后面肯定能找到一个b保证被分为了aVbV并且V中的ab数量均相同，以b开头类似。

\begin{array}{l} V \to a V b V | b V a V | ϵ \end{array}

$\begin{array}{l} V \rightarrow aVbV | bVaV | \epsilon \\ \end{array}$

V \to a V b V ∣ b V a V ∣ ϵ

目标生成： $\{x\in \{a, b\}^* | x 中a,b个数不同 \}$
1. T表示a多一个或者更多
2. U表示b多一个或者更多
3. UT不能同时出现，和V去组合即可
4. 证明

\begin{array}{l} S \to T | U \\ T \to V a T | V a V \\ U \to V b U | V b V \\ V \to a V b V | b V a V | ϵ \end{array}

$\begin{array}{l} S \rightarrow T | U \\ T \rightarrow VaT |VaV \\ U \rightarrow VbU | VbV \\ V \rightarrow aVbV | bVaV | \epsilon \\ \end{array}$

S \to T ∣ U T \to V a T ∣ V a V U \to V b U ∣ V b V V \to a V b V ∣ b V a V ∣ ϵ

4.2. 顺序语句、条件语句、打印语句

上图中的L是顺序语句

5. L-System(不考)

L-System:这不是上下文无关文法, 但精神高度一致

\begin{array}{l} v a r i a b l e s : A B \\ c o n s t a n t s : + - \\ s t a r t : A \\ r u l e s : (A \to B - A - B), (B \to A + B + A) \\ a n g l e s : 60^{'} \end{array}

$\begin{array}{l} variables: A B \\ constants: + - \\ start: A \\ rules:(A \rightarrow B-A-B),(B \rightarrow A+B+A) \\ angles:60' \\ \end{array}$

v a r i a b l e s : A B c o n s t a n t s : + - s t a r t : A r u l e s : (A \to B - A - B), (B \to A + B + A) a n g l e s : 6 0^{'}

$A, B$ :向前移动并画线
+:左转
-:右转
每一步都并行地应用所有规则

\begin{array}{l} v a r i a b l e s : X Y c o n s t a n t s : F + - s t a r t : F X r u l e s : (X \to X + Y F +), (Y \to - F X - Y) a n g l e s : 90^{'} \end{array}

$\begin{array}{l} variables: X Y constants: F + - start: FX rules:(X \rightarrow X+YF+),(Y \rightarrow -FX-Y) angles:90' \end{array}$

v a r i a b l e s : X Y c o n s t a n t s : F + - s t a r t : F X r u l e s : (X \to X + Y F +), (Y \to - F X - Y) a n g l e s : 9 0^{'}

$F$ :向前移动并画线
+:右转
-:左转
X:仅用于展开，在作画时被忽略
每一步都并行地应用所有规则

6. 最左(leftmost) 推导与最右(rightmost) 推导

\begin{array}{l} E \to E + E | E * E | (E) | i d \\ E \xRightarrow [l m] - E \xRightarrow [l m] - (E) \xRightarrow [l m] - (E + E) \xRightarrow [l m] - (i d + E) \xRightarrow [l m] - (i d + i d) \end{array}

$\begin{array}{l} E \rightarrow E + E | E * E | (E) | id \\ E \xRightarrow[lm]{} -E \xRightarrow[lm]{} -(E) \xRightarrow[lm]{} -(E+E) \xRightarrow[lm]{} -(id + E) \xRightarrow[lm]{} -(id+id) \end{array}$

E \to E + E ∣ E * E ∣ (E) ∣ i d E l m - E l m - (E) l m - (E + E) l m - (i d + E) l m - (i d + i d)

$\xRightarrow[lm]{} -E$ :经过一步最左推导得出
$\xRightarrow[lm]{+} -(id + E)$ :经过一步或多步最左推导得出
$\xRightarrow[lm]{*} -(id + E)$ :经过零步或多步最左推导得出
最左推导是有非终结符优先选择最左侧的进行推导
最右推导是有非终结符有限选择最右侧的进行推导

$\xRightarrow[rm]{} -E \xRightarrow[rm]{} -(E) \xRightarrow[rm]{} -(E+E) \xRightarrow[rm]{} -(E + id) \xRightarrow[rm]{} -(id+id)$

6.1. Definition (Left-sentential Form，最左句型)

如果 $\xRightarrow[lm]{*} \alpha$ , 并且 $\alpha \in (T \cup N)^*$ ，则称 $\alpha$ 是文法G的一个最左句型。

$\xRightarrow[lm]{} -E \xRightarrow[lm]{} -(E) \xRightarrow[lm]{} -(E+E) \xRightarrow[lm]{} -(id + E) \xRightarrow[lm]{} -(id+id)$

6.2. Definition (Right-sentential Form，最右句型)

如果 $\xRightarrow[rm]{*} \alpha$ , 并且 $\alpha \in (T \cup N)^*$ ，则称 $\alpha$ 是文法G的一个最右句型。

$\xRightarrow[rm]{} -E \xRightarrow[rm]{} -(E) \xRightarrow[rm]{} -(E+E) \xRightarrow[rm]{} -(id + E) \xRightarrow[rm]{} -(id+id)$

7. 语法分析树

语法分析树是静态的, 它不关心动态的推导顺序

一棵语法分析树对应多个推导
但是, 一棵语法分析树与最左(最右) 推导一一对应

7.1. 二义性引入

1 - 2 - 3的语法树的两种不同表达形式
以下的两棵语法树是不同的，生成出来的目标代码也是不同的
这个文法是有问题的，这个文法具有二义性，我们需要通过修改文法避开二义性问题。
语法没有二义性的描述，L(G)本身只是一个串的集合。

7.2. Definition (二义性(Ambiguous) 文法)

如果L(G) 中的某个句子有一个以上语法树/最左推导/最右推导,则文法G是二义性的。
1 + 2 * 3的语法树

7.3. 悬空-else

8. 二义性文法

不同的语法分析树产生不同的语义
所有语法分析器都要求文法是无二义性的

Q:如何识别二义性文法?这是不可判定的问题，是指没有通用的算法，可以判断任意的文法G
Q:如何消除文法的二义性?

8.1. 消除文法二义性

四则运算均是左结合的
优先级: 括号最先, 先乘除后加减
二义性表达式文法以相同的方式处理所有的算术运算符
要消除二义性, 需要区别对待不同的运算符
将运算的"先后" 顺序信息编码到语法树的"层次"结构中

\begin{array}{l} E \to E + E | i d \end{array}

$\begin{array}{l} E \rightarrow E + E | id \\ \end{array}$

E \to E + E ∣ i d

8.2. 左结合文法

\begin{array}{l} E \to E + T \\ T \to i d \end{array}

$\begin{array}{l} E \rightarrow E + T \\ T \rightarrow id \\ \end{array}$

E \to E + T T \to i d

8.3. 右结合文法

\begin{array}{l} E \to T + E \\ T \to i d \end{array}

$\begin{array}{l} E \rightarrow T + E \\ T \rightarrow id \\ \end{array}$

E \to T + E T \to i d

8.4. 使用左(右)递归实现左(右)结合

8.5. 括号最先, 先乘后加文法

乘号更靠近叶子节点

\begin{array}{l} E \to E + E | E * E | (E) | i d \\ E \to E + T | T \\ T \to T * F | F \\ F \to (E) | i d \end{array}

$\begin{array}{l} E \rightarrow E + E|E*E|(E)|id \\ E \rightarrow E + T|T \\ T \rightarrow T * F | F\\ F \rightarrow (E)|id \end{array}$

E \to E + E ∣ E * E ∣ (E) ∣ i d E \to E + T ∣ T T \to T * F ∣ F F \to (E) ∣ i d

8.6. Summary

\begin{array}{l} E \to E + E | E - E | E * E | E / E | (E) | i d | n u m b e r \\ E \to E + T | E - T | T \\ T \to T * F | T / F | F \\ F \to (E) | i d | n u m b e r \end{array}

$\begin{array}{l} E \rightarrow E + E|E - E|E*E|E/E|(E)|id|number \\ E \rightarrow E + T | E - T|T \\ T \rightarrow T * F | T/F | F \\ F \rightarrow (E) | id | number \\ \end{array}$

E \to E + E ∣ E - E ∣ E * E ∣ E / E ∣ (E) ∣ i d ∣ n u m b e r E \to E + T ∣ E - T ∣ T T \to T * F ∣ T / F ∣ F F \to (E) ∣ i d ∣ n u m b e r

无二义性的表达式文法
1. E:表达式(expression)
2. T:项(term)
3. F:因子(factor)
将运算的"先后"顺序信息编码到语法树的"层次"结构中

8.7. IF-Then-Else问题

每个else与最近的尚未匹配的then匹配

基本思想: then与else之间的语句必须是"已匹配的"
证明两件事情：证明部分不作为重点
1. $L (G) = L (G^{'})$
2. $G^{'}$ 是无二义性的

8.7.1. $L (G) = L (G^{'})$ 证明过程

\begin{array}{l} L (G^{'}) \subseteq L (G) 简 单 容 易 证 明 \end{array}

$\begin{array}{l} L(G') \subseteq L(G) 简单容易证明\\ \end{array}$

L (G^{'}) \subseteq L (G) 简 单 容 易 证 明

文法是递归的，我们可以使用数学归纳法，对推导步骤进行归纳

$\begin{array}{l} L (G) \subseteq L (G^{'}) \\ x \in L (G) \to x \in L (G^{'}) \\ s t m t \to . . . \to x \end{array}$ $\begin{array}{l} L(G) \subseteq L(G') \\ x \in L(G) \rightarrow x \in L(G') \\ stmt \rightarrow ... \rightarrow x \\ \end{array}$ $L (G) \subseteq L (G^{'}) x \in L (G) \to x \in L (G^{'}) s t m t \to . . . \to x$

只要G中展开一步，G’中都有相应的对应即证明了 $\subseteq L(G')$

8.7.2. $G^{'}$ 是无二义性的

每个句子对应的语法分析树是唯一的
只需证明: 每个非终结符的展开方式是唯一的

\begin{array}{l} L (m a t c h e d_s t m t) \cap L (o p e n_s t m t) = \emptyset \\ L (m a t c h e d_s t m t_{1}) \cap L (m a t c h e d_s t m t_{2}) = \emptyset \\ L (o p e n_s t m t_{1}) \cap L (o p e n_s t m t_{2}) = \emptyset \end{array}

$\begin{array}{l} L(matched\_stmt) \cap L(open\_stmt) = \emptyset \\ L(matched\_stmt_1) \cap L(matched\_stmt_2) = \emptyset \\ L(open\_stmt_1) \cap L(open\_stmt_2) = \emptyset \\ \end{array}$

L (m a t c h e d_s t m t) \cap L (o p e n_s t m t) = \emptyset L (m a t c h e d_s t m t_{1}) \cap L (m a t c h e d_s t m t_{2}) = \emptyset L (o p e n_s t m t_{1}) \cap L (o p e n_s t m t_{2}) = \emptyset

上面的下标代表子句

Q：为什么不使用优雅、强大的正则表达式描述程序设计语言的语法?
A：正则表达式的表达能力严格弱于上下文无关文法

每个正则表达式r对应的语言L® 都可以使用上下文无关文法来描述

$r=(a|b)^∗abb$

此外, 若 $\delta(A_i,\epsilon) = A_j$ ，则添加 $A_i \rightarrow A_j$

\begin{array}{l} S \to a S b \\ S \to ϵ \\ L = a^{n} b^{n} | n \geq 0 \end{array}

$\begin{array}{l} S \rightarrow aSb \\ S \rightarrow \epsilon \\ L = {a^nb^n|n \geq 0} \\ \end{array}$

S \to a S b S \to ϵ L = a^{n} b^{n} ∣ n \geq 0

该语言无法使用正则表达式来描述
定理: $L = \{a^nb^n | n ≥ 0\}$ 无法使用正则表达式描述
反证法
1. 假设存在正则表达式r: $L (r) = L$
2. 则存在有限状态自动机D®: $L (D (r)) = L$ ; 设其状态数为k
3. 考虑输入 $a^m(m>k)$

$D (r)$ 也能接受a^{i+j}bi，矛盾！
Pumping Lemma for Regular Languages： ${a^nb^n | n \geq 0}$
Pumping Lemma for Context-free Languages: ${a^nb^nc^n | n \geq 0}$
只考虑无二义性的文法这意味着,每个句子对应唯一的一棵语法分析树

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/331263