Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

BNF 文法 (1) - 语法树 | 二义性的解决

Posted on 2007-07-27 11:28 ZelluX 阅读(6112) 评论(2)  编辑  收藏 所属分类: Courses
1. 考虑表达式3 + 4的语法分析树,exp( exp(number (3)), op(+), exp(number (4)) )。
还有一种更为简单的表示方法,例如将(34 - 3) * 42表示为*(-(34, 3), 42)
后者被称为抽象语法树(abstract syntax tree),它的效率更高,但是不能从中重新得到记号序列。


2. 简单的算术表达式的抽象语法树的数据类型
typedef enum {Plus, Minus, Times} OpKind;
typedef 
enum {OpKind, ConstKind} ExpKind;
typedef 
struct streenode
{
    ExpKind kind;
    OpKind op;
    
struct streenode *lchild, *rchild;
    
int val;
} STreeNode;
typedef STreeNode 
*SyntaxTree;


3. 简单算术文法的二义性解决
例如串34 - 3 * 42,可以有两种不同的分析树:
34 - 3 = 31, 31 * 42
3 * 42 = 126, 34 - 126
解决二义性的方法通常有两种,一种是设置消除二义性规则(disambiguating rule),如设置运算符的优先权;另一种是将文法限制为只能分析成单一的分析树,如将上式表示为34 - (3 * 42)。

设置运算符的优先权
定义如下的简单表达式文法:
exp -> exp addop exp | term
addop -> + | -
term -> term mulop term | factor
mulop -> *
factor -> (exp) | number
这样乘法被归在term规则下,而加减法被归在exp规则下,因此在分析树和语法树中加减法将更接近于根,由此也就接受了更低一级的优先权。
这样将算符放在不同的优先权级别中的办法是在语法说明中使用BNF的一个标准方法,成为优先级联(precedence cascade)。
接下来的问题就是如何让同级运算从左往右。
可以将表达式文法改为
exp -> exp addop term | term
addop -> + | -
term -> term mulop factor | factor
mulop -> *
factor -> (exp) | number
这样就使得加法和减法左结合,而如果写成
exp -> term addop exp | term
这样的形式,则会使得它们右结合。

4. else 悬挂的问题
简单 if 语句的文法
statement -> if-stmt | other
if-stmt -> if (exp) statement | if (exp) statement else statement
exp -> 0 | 1
考虑串 if (0) if (1) other else other
这时else other的悬挂就出现了二义性,它既可以理解为是if (0)匹配失败后的选择,也可以理解为if (0)匹配成功,if (1) 匹配失败后的结果。
消除二义性的规则是
statement -> matched-stmt | unmatched-stmt
matched-stmt -> if (exp) matched-stmt else matched-stmt | other
unmatched-stmt -> if (exp) statement | if (exp) matched-stmt else unmatched-stmt
exp -> 0|1
由这个定义,上面的串就可以分析为
if (0)  // unmatched-stmt
    if (1) other else other  // matched-stmt

另外一种解决方法就是在语法中解决这个问题。
可以要求出现else部分,或者使用一个分段关键字(bracketing keyword),例如
if (1) then
    if (0) then other
    else other
    endif
endif


评论

# re: BNF 文法 (1) - 语法树 | 二义性的解决  回复  更多评论   

2011-03-14 22:16 by 过客2011
比如对于 if(a) if(b) b1 else b2 else if(c) c1 else c2。如是请回复。
guoshuai0020000@gmail.com

# 楼主给出的消除二义性的if文法任然是二义性的。。。  回复  更多评论   

2011-03-14 22:18 by 过客2011
比如对于 if(a) if(b) b1 else b2 else if(c) c1 else c2。如是请回复。
guoshuai0020000@gmail.com

只有注册用户登录后才能发表评论。


网站导航: