刚刚看到《动态计算字串表达式值的类》,好像有许多人表示更喜欢解析器形式的求值类。其实我个人倒觉得用反射实现没什么不好,恰恰相反,我觉得这种实现方法很聪明!另外,装配中的脑袋的代码可以稍微修改一下来提高效率,那样再用的话就不会因为反复编译而影响效率了。
言规正传,不知道大家有没有注意我最近在Blog中添加了一个叫ANTLR的连接,它就是一个著名的“编译器的编译器”,不过它实际上是ANother Tool for Language Recognition(ANTLR),它的描述语言可以生成词法分析器、语法分析器与语义分析器,也就是说,我们可以用它来识别加工不同的语言(编译器的编译器)。它同时支持3大类语言的输出:C++, Java, C#(按照生日排序),也就是说,我们可以利用它来用C#生成编译器。ANTLR是免费开源的,而且历史也很久远了,目前的版本是2.7.5,有兴趣的朋友可以在我的Blog的连接中找到网址。
那么,除了用反射轻松的实现计算值之外我们也可以用ANTLR来描述这些数学表达式,下面我附上一个我在看到《动态计算字串表达式值的类》后写的一个语法文件,感兴趣的朋友可以去下载ANTLR来试一试下面的语法哦!
![](http://image.360doc.cn/DownloadImg/8309/303767_1.gif)
文件Calc.g
header
{
using CharBuffer = antlr.CharBuffer;
}
options
{
language = "CSharp";
namespace = "Cavingdeep.Test.Calc";
}
/******************************\
Calc Parser
\******************************/
class CalcParser extends Parser;
options
{
exportVocab = Calc;
buildAST = true;
}
expr
: sumExpr EOF
;
sumExpr
: mulExpr ( ( SUM^ | NEG^ ) mulExpr )*
;
mulExpr
: powExpr ( ( MUL^ | DIV^ ) powExpr )*
;
powExpr
: negExpr ( POW^ negExpr )*
;
negExpr
: ( NEG^ )* a:atom!
{
if (#negExpr != null) {
AST lastNegNode = #negExpr;
while (lastNegNode.getNumberOfChildren() > 0) {
lastNegNode = lastNegNode.getFirstChild();
}
lastNegNode.setFirstChild(#a);
} else {
## = #a;
}
}
;
atom
: NUMBER
| LCURLY! sumExpr RCURLY!
;
/***************************\
Calc Lexer
\***************************/
class CalcLexer extends Lexer;
options
{
caseSensitive = false;
exportVocab = Calc;
}
WS
: ( ‘ ‘
| ‘\t‘
| ‘\n‘
| ‘\r‘ )+ { $setType(Token.SKIP); }
;
NUMBER
: ( ( ‘0‘..‘9‘ )+ ‘.‘ ( ‘0‘..‘9‘ )+ ) => ( ‘0‘..‘9‘ )+ ‘.‘ ( ‘0‘..‘9‘ )+
| ‘0‘..‘9‘
;
SUM : ‘+‘ ;
NEG : ‘-‘ ;
MUL : ‘*‘ ;
DIV : ‘/‘ ;
POW : ‘^‘ ;
LCURLY : ‘(‘ ;
RCURLY : ‘)‘ ;
/***************************\
Calc Tree Parser
\***************************/
class CalcTreeParser extends TreeParser;
options
{
exportVocab = Calc;
}
{
public static void Main(string[] args) {
CalcLexer lexer = new CalcLexer(new CharBuffer(Console.In));
CalcParser parser = new CalcParser(lexer);
parser.expr();
AST ast = parser.getAST();
CalcTreeParser treeParser = new CalcTreeParser();
double r = treeParser.eval(ast);
Console.WriteLine("结果是:" + r);
}
}
eval returns [double v = 0]
: v=expr
;
protected
expr returns [double v = 0]
{
double izq = 0;
double der = 0;
}
: i:NUMBER { v = Convert.ToDouble(i.getText()); }
| #( SUM izq=expr der=expr ) { v = izq + der; }
| #( DIV izq=expr der=expr ) { v = izq / der; }
| ( #( NEG expr expr ) ) => #( NEG izq=expr der=expr ) { v = izq - der; }
| #( MUL izq=expr der=expr ) { v = izq * der; }
| #( POW izq=expr der=expr ) { v = Math.Pow(izq, der); }
| #( NEG izq=expr ) { v = -(izq);}
;
2005年4月5日 15:24 - (阅读:6828;评论:18)
反馈
(a+b)(a+c)+b(c+d) = a*a +a*c+a*b+b*c +b*c + b*d
= a + ac+ab+bc+bd
= a(1+b+c)+bc+bd
= a+bc+bd
a,b,c,d都是布尔值,
你是否可具体解释一下它的断言(Predicates)、动作(Actions)与动作的参数 ?
我在上面给出的例子中就用到了断言、动作、参数等,概念上说简单也简单,说复杂也复杂,我就简单点说吧:)
断言:分为三种类型,语法断言、语义断言(区分断言、验证断言)。看下面例子:
INT : ( DIGIT )+ ;
DIGIT : ‘0‘..‘9‘ ;
REAL : INT ‘.‘ INT ;
当k=1的时候,我们就不能确定到底是INT,还是REAL,那么再往下走应该算哪个Token的呢?这时候通常的解决方法就是将k设为2,这样就能识别了,一般会出现情况要将k设的很大,但是k很大的话就会很影响效率,这时就可以用语法断言(Syntactic Predicate)来临时增大一下k,直到k满足为止,如下:
REAL
: ( INT ‘.‘ ) => INT ‘.‘ INT
| INT
;
在有的情况下也只能通过语法断言来检查语法情况,如:
A
: ( ( CHAR )* ‘;‘ ) => ( CHAR )* ‘;‘
| ( CHAR )*
;
区分断言,利用输出语言做区分,如用C#语法区分,下面用自定义的isType方法接受第一个Token并检测是否是一个定义的语言中的类型:
a
: { isType(LT(1)) }? ID ID ";" // 声明
| ID "=" expr ";" // 赋值
;
验证断言类似,不过写在规则(Rule)之后,如果验证断言失败那么抛出SemanticException。
动作:就是你在上面看到的{}中的内容,这部分是直接签入在输出源代码中的代码,直接用输出语言写的,比如上面的isType方法就可以在动作中写出。
参数,我上面说错了,不是动作的参数,是规则(Rule)的参数,你看我Blog上的TreeParser那部分计算结果时就用到了动作与返回参数,通过参数,我可以让规则可以有返回值或可以接受参数(规则在输出源代码中是一个方法)。
关于继承的问题,我想你可以用另一个类来将生成好的Parser等封装起来,比如可以考虑使用代理模式,这样应该就可以解决你需要继承的问题了。^_^
coco/r 提供的方法是可以自行取下面N个token来进行判断,因为是递归下降的分析方法 所以它的生成代码可读性和可调试性都非常好(不过词法分析没办法,而且我还给他们指出了一个错误,现在已经修正了)
而接受参数和返回值,我觉得coco/r做得也很好:
ConstantList<out Constant node> = Constant<out node>
["," ConstantList<out node.nextconstant>]
这里node就是返回的参数了,当然参数也可以多个,byval byref out都可以 因为它因为是LL分析的,所以很多时候只能把上面的写成这种方式,或者:
ConstantList = Constant {"," Constant }
其实最好的答案是:
ConstantList = ConstaintList {"," Constant}
也就是它只支持EBNF 不支持BNF的写法,而我觉得golden parser对于LL冲突解决的最好 而且可以可以验证BNF语法,可以做为初期语法设计使用,不足的就是它只能生成Yacc的语法文件。
首先值得注意的一点是语法断言可以支持non-LL(k)表达式,也就是
A
: ( (CHAR)* B ) => (CHAR)* B
| (CHAR)* C
;
关于这一点我不知道Coco/R是怎么处理的?
另外一点比较关键的是其实ANTLR在LL(k)的基础上将算法做了优化,将原本的m^k变成了m*k,大大的提高了分析效率。不过这样做会导致ANTLR不是纯正的LL(k),而是pred-Strong-LL(k)或pred-SLL(k)。
其实我觉得ANTLR最大的好处还是在于它用统一的语法结合了三大类分析器:词法分析器、语法分析器与语义分析器(AST),这样使得它在使用上非常的方便,另外由于它是一个pred-LL(k) parser(有断言的LL(k) parser),它的能力是所有其他LL(k) parser所不及的。我想也正是以上这两种原因使我选择了ANTLR吧,不过另外一件激励我选择ANTLR的原因是:当JetBrains公司决定做IntelliJ IDEA与ReSharper的时候,他们,也选择了ANTLR。^_^
gold parser就能够很好地处理LL(K)的问题,但正因为此,会导致语法设计的不严谨,可能是自己设计的一些小错误,结果会被它自动处理掉,但这种错误会导致语法歧义 当然一些语法本身是允许歧义的,这就又另当别论了
(怎么博客堂老说我校验码不正确?是时间太长session失效还是我没认清1I 0o,这种字体实在不好辨认)
看来cavingdeep的编译原理的基本功很扎实嘛!!赞一下:)
好的入门资料有倒是有,有一个西班牙语的比较好的PDF,我就是看它慢慢学的!;)英文的就不知道哪个好了,我看了几个入门都不怎么好:(
西班牙语我就别指望了:)呵呵,还是以后要用的时候再问你吧:)