构造文法时表达式中算符优先级的问题
文法用于描述一种语言,语言中包含多个句子,句子又是由表达式组成的。多个原子表达式(不可再分的表达式,比如:a+b,c*d,-a等)和操作符或者括号一起又可以组成复合表达式(比如:a+b*c,a*(b+c)等)。在书写表达式文法时需要注意算符优先级问题,比如:四则运算中要优先计算乘除,然后才是加减,而被括号括起的表达式具有更高的优先级。解决优先级问题可以采取从优先级低的算符到优先级高的算符的顺序构造文法规则,由于括号相对于操作符具有更高的优先级,所以由括号括起的复合表达式可以作为原子表达式处理。下面拿四则运算举例说明:[plain]
expr : expr '+' term
| expr '-' term
| term
term : term '*' factor
| term '/' factor
| factor
factor : NUMBER
| '(' expr ')'
expr和term都是复合表达式。expr就是表达式的起始规则,处理+和-操作符以及不含+和-的情况。term用于表示*和/操作符以及不含*和/的情况。factor就是原子表达式,直接返回词法单元或者是由括号括起来的复合表达式。
下面为比较运算构造文法,只涉及'>','<','==','!='和逻辑运算符'&&'和'||'。我们知道所有比较运算符都具有相同的优先级,逻辑运算符中'&&'优先级要比'||'高。所以,与四则运算的文法类似,先构建低优先级的复合表达式,最后是最高优先级的原子表达式。所以首先是描述||的规则,然后是&&,最后是原子表达式,根据上面阐述,比较运算的文法可以构造为:
[plain]
compexpr : compexpr '||' andexpr
| andexpr
andexpr : andexpr '&&' factor
| factor
factor : ID '>' NUMBER
| ID '<' NUMBER
| ID '==' NUMBER
| ID '!=' NUMBER
| '(' compexpr ')'
根据四则运算和比较运算的文法,我们可以总结具有优先级的表达式文法的构造原则是:
1. 从低优先级到高优先级的顺序构造规则。
2. 每个复合表达式都有一个只包含下一个优先级的表达式作为解析选项。
3. 括号具有高优先级,被括号括起的符合表达式作为原子表达式。
补充:综合编程 , 其他综合 ,