Re: Arithmetic expressions w. recursive descent parser?

bmildh@linuxmail.org writes:


> I'm trying to make a simple java program to parse arithmetic
> expressions. To keep it simple, only integers are used in the
> expression, together with * / + - ( ) as terminals.
> I want the parser to be a predictive recursive descent parser, with 1
> lookahead.
>
> The problem is that I cant get the implementation right with +,- in
> combination w. numbers starting w. + or -, eg. -45, +3, etc.
> I would appreciate any help, pointers, tips, on how to get the + and -
> operator correctly implemented with numbers that could start with + or
> - .
>
> Typical expressions that I want to parse:
> (12--21)
> 5+4-1-2
>
> A made a grammar but it was left-recursive, but I removed it and this
> is the resulting grammar:
>
> E -> TX | T
> X -> +TX | +T | -TX | -T
> T -> FY | F
> Y -> *FY | /FY | /F | *F
> F -> number
> F -> (E)


This doesn't seem like the correct grammar for what you describe.
Initially, we have an ambiguous grammar:


  E -> E+E | E-E | E*E | E/E | +E | -E | number | (E)


Next, we have to decide on the precedence of the operators. The usual
decision is:


  +, -: lowest priority, left associative when infix, highest priority
              when prefix.


  *, /: medium priority, left associative.


Note that + and - have different priorities when prefix or infix.


We now rewrite the grammar to get the precedences right:


  E -> E+T | E-T | T
  T -> T*F | T/F | F
  F -> +F | -F | number | (E)


and eliminate left-recursion:


  E -> TE'
  E' -> +TE' | -TE' | \epsilon
  T -> FT'
  T' -> *FT' | /FT' | \epsilon
  F -> +F | -F | number | (E)


Starting from here, you should have no problem writing a recursive
descent parser.


                Torben

Return to the comp.compilers page.
Search the comp.compilers archives again.