知识
解析树和派生
考虑以下表达式：
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
为某个句子构造两个不同的最左推导，以证明它是二义性的
京公网安备 11010502036488号