第四章-2-CFG探讨

知识

解析树和派生

考虑以下表达式：

E→E+E | E*E |（E）|-E | id

id+id*id的最左导数

替代解析树与派生

这里有什么问题？

两个截然不同的最左边的派生词！

模棱两可(二义性）

• 一个语法为一个句子生成多个解析树，称为歧义语法。

对于大多数解析器来说，语法必须是明确的。

• 明确的语法➔ 句子解析树的唯一选择

• 我们应该在编译器的设计阶段消除语法中的歧义。

• 应编写歧义语法以消除歧义。

• 我们必须选择一个句子的解析树（由歧义语法生成）来消除该语法的歧义，通过“扔掉”不需要的解析树来限制这种选择

id+id*id的两个解析树

歧义–运算符优先级

• 可以根据优先级和关联性规则消除歧义语法（因为存在歧义运算符）。

消除歧义（第174页）

考虑下面的语法部分：

stmt → if expr then stmt
| if expr then stmt else stmt
| other (any other statement)

有什么问题吗？

让我们考虑一个简单的解析树：

否则必须与上一个匹配。

结构指示表达式的解析子树。

示例：这个字符串会发生什么？

一个歧义句子的两个解析树

• 我们更喜欢第二个解析树（else与最近的if匹配）。

• 因此，我们必须消除语法歧义，以反映这一选择。

• 明确的语法将是：

stmt → matchedstmt 
| unmatchedstmt
matchedstmt → if expr then matchedstmt else matchedstmt 
| otherstmts
unmatchedstmt → if expr then stmt 
| if expr then matchedstmt else unmatchedstmt

一般的规则是“用最接近的前一个未匹配的进行匹配”

左递归（第176页）

• 语法是递归的(左递归） 如果它有一个非终端a，这样就有一个派生a→ Aα表示某个字符串α。

• 左递归可能出现在推导的单个步骤中（立即左递归直接左递归), 或者可能出现在推导的多个步骤中。

• 自上而下的解析技术无法处理左递归语法。

• 因此，我们必须将我们的左递归语法转换为一个等价的非左递归语法。

为什么左递归是个问题？

这是如何构建字符串的？

每个字符串都必须以什么开头？

立即左递归

消除课堂上的直接左递归练习1

左递归——问题

• 语法不能立即保持递归，但仍然可以保持递归。

• 仅仅通过消除直接左递归，我们可能不会得到一个非左递归的语法。

作业

1. 消除下列文法的左递归性。

(1) S→SA|A

A→SB|B|(S)|( )

B→［S］|［ ］

(2) S→(L)|a

L → L, S | S

(3) S→AS|b

A→SA|a

2. 给定文法

S->aSbS|bSaS|e (注： e是空）

a) 该文法是否有二义性，证明之。

b) 构造abab的最右推导

c) 构造abab语法树

3. 考虑文法

S→aSbS | bSaS | e

为某个句子构造两个不同的最左推导，以证明它是二义性的