编译原理(三)语法分析:3.二义性与二义性的消除
文章目录一、二义性1.定义2.原因二、二义性的消除1.改写二义文法为非二义文法(1)步骤(2)例子(3)缺点2.为文法符号规定优先级和结合性一、二义性1.定义定义3.7若文法G对同一句子产生不止一棵分析树,则称G是二义的。例3.7 句子id+id*id和id+id+id可能的分析树E→E+E | E*E |(E)| -E | id“悬空(dangling)else”问题例...
一、二义性
1.定义
定义3.7
若文法G对同一句子产生不止一棵分析树,则称G是二义的。
例3.7 句子id+id*id和id+id+id可能的分析树
E→E+E | E*E |(E)| -E | id
深度越深,越远离开始节点,优先级越高。
非终结符在终结符(如+)的左边是左结合,右边是右结合。
“悬空(dangling)else”问题
例3.8 条件语句if x<3 then if x>0 then x:=5 else x:=-5
S → if C then S (1)
| if C then S else S (2)
| id := E (3)
C → E = E | E < E | E > E (4)…(6)
E → E + E | - E | id | n (7)…(10)
2.原因
原因:在产生句子的过程中某些直接推导有多于一种选择
注意:
明确
最
终
分
析
树
的
形
状
,
仅
与
文
法
有
关
,
而
与
推
导
方
法
无
关
\textcolor{red}{最终分析树的形状,仅与文法有关,而与推导方法无关}
最终分析树的形状,仅与文法有关,而与推导方法无关
一个句子有多于一棵分析树,是因为文法中缺少对文法符号优先级和结合性的规定。
二、二义性的消除
消除文法二义的两种方法:
① 改写二义文法为非二义文法;
② 规定二义文法中符号的优先级和结合性,使仅产生一棵分析树。
左结合性:
对于A→αAβ
,若A
(左右都有的非终结符)在终结符(即终结符在β中)左边出现,则A产生式具有左结合性质。
如:
E → E + T
是左结合(E
即A
,+
是终结符)。F → (E) | -F
是右结合(F
即A
,-
是终结符)
1.改写二义文法为非二义文法
(1)步骤
改写二义文法的关键步骤:
- 划分优先级和结合性
- 引入一个新的非终结符,增加一个子结构并提高一级优先级(优先级的判断);
- 递归非终结符在终结符左边,运算具有左结合性,否则具有右结合性。
(2)例子
例3.10 改写二义文法
E→E+E | E*E |(E)| -E | id
- 优先级从低到高:
[+]
;[*]
;[( ), -, id]
- 结合性:
左结合[+, *]
右结合[-]
无结合[id]
- 非终结符与运算:
E:+
(E产生式,左递归)
T:*
(T产生式,左递归)
F:-,( ),id
(F产生式,右递归)
E → E + T | T
T → T * F | F
F → (E) | -F | id
解决“悬空(dangling)else”问题
例3.8 条件语句if x<3 then if x>0 then x:=5 else x:=-5
S → if C then S (1)
| if C then S else S (2)
| id := E (3)
C → E = E | E < E | E > E (4)…(6)
E → E + E | - E | id | n (7)…(10)
分析原因:if-then-else和if-then:在一个复合if语句中,可能then多于else,使得else不知与哪个then结合。
一般原则是右结合,即else与其左边最靠近的then结合。
改写文法的根据是将S分为 完全匹配(MS) 和 不完全匹配(UMS) 两类,并且在UMS中规定 else右结合 。
S → MS (1)
| UMS (2)
MS → if C then MS else MS (3)
| id := E (4)
UMS→ if C then S (5) (G3.5)
| if C then MS else UMS (6)
C → E = E | E < E | E > E (7)...(9)
E → E + T | T (10)...(11)
T → (E) | -T | id | n (12)...(15)
(3)缺点
- 非终结符的引入,增加了推导步骤(分析树增高)
- 更不容易理解
2.为文法符号规定优先级和结合性
YACC(生成 词法分析器 和 语法分析器 的工具)就是采用这种方法:
%left '+'
%left '*'
%right '-'
E : E '+' E | E '*' E | '-' E | '(' E ')' | id
简单
3.修改语言的语法(表现形式被改变)
① 明确给出结束标志,如Ada中用end if,于是有:
if x<3 then if x>0 then x:=5; end if; else x:=-5; end if;
if x<3 then if x>0 then x:=5; else x:=-5; end if; end if;
② 给表达式加括号,如Pascal中逻辑和算术运算:(a+b)>(c*d)
更多推荐
所有评论(0)