Arithmetic expression grammar
I'm trying to create an appropriate grammer for some arithmetic expressions. The valid tokens for my expressions are the following:
'+', '-', '/', '*'
, and '**'
for powers. The expressions could also contain symbols and functions. The functions can take multiple arguments, some of which might be optional. From what little I remember from expression parsing, I must come up with a grammar that is not left-recursive and also preserves operator associativity.
So here is what I came up with, after a little bit of searching (though not sure about associativity):
E = T Eopt
Eopt = '+' T Eopt | '-' T Eopt | ε
T = F Topt
Topt = '*' F Topt | '/' F Topt | ε
F = Number | '(' E ')'
which can be found in many te开发者_JAVA技巧xtbooks. What changes does the above grammar need, so that it can acommodate the power token ('**') and both symbols and functions ?
Please do not point me to flex/yacc etc. Thank you.
You're almost there. Changes begin at F:
E = T Eopt
Eopt = '+' T Eopt | '-' T Eopt | ε
T = F Topt
Topt = '*' F Topt | '/' F Topt | ε
F = P Fopt
Fopt = '**' P Fopt | ε
P = Number | '(' E ')'
This assumes your tokenizer is distinguishing between *
and **
.
精彩评论