Recursive descent parser for algebraic expressions in java

Question

This is the grammar:

Expression= expression+term|expression-term|term

term=term*factor|term/factor|factor

factor=id|expression

I am trying to implement a recursive descent parser.

This is the algorithm I came up with

**

class main
create expression object
take input from user and send it to the expression class

**

Class Expression


Expr
method : check for + or - 
left = left of +/-
right = right of +/-
left=expr(left)//if there are + - or ( ) in left
right=term(right)


term
method : check for * or / 
left = left of * or /
rigth = right of * or /
left=term(left)//if there are * / or ( ) in left
right=factor(right)

factor
method : check for id or exp 
if id return id
else return exp

is this the way to go about it to solve the problem

I am only considering inputs like

alpha+beta*gamma/(zeta-theta)

and I want to generate native code like

PUSH ALPHA
PUSH BETA
PUSH GAMMA
OPERATOR *

etc

I want to know if my thinking is correct.

Answer 1

One problem I see is that your grammar lacks the terminal symbols for grouping: "(" and ")". Also, it specifies that factor is defined recursively in terms of expression, so your factor method should invoke your expression method recursively. You might compare your grammar for expression, term and factor to those seen in this article, Recursive descent parser.

I found StreamTokenizer a useful class for tokenizing input, as it provides a convenient one-token look-ahead.

For code generation, you should also look at this answer discussing the Shunting Yard algorithm.