How would I implement parsing using operator precedence?

2
votes

I want to implement parsing using operator precedence. I have implemented +, -, *, and /. How would I implement rest with out using any grammar? This is a college project and yacc or bison are not allowed.

3
parsingoperator-precedence
You might find this interesting/useful: blogs.msdn.com/b/ericlippert/archive/2010/10/04/… – Rowland Shaw
@Lazarus: "The homework tag...is now discouraged," but, @sanjoy, please (as always) follow general guidelines: state any special restrictions, show what you've tried so far, and ask about what specifically is confusing you. – Roger Pate
@Roger Pate: of course it is now, after all that would discourage people from posting their homework questions verbatim and actually having to learn. And I thought political correctness in the workplace had passed the point of ridiculousness. – Lazarus
@Lazarus: Verbatim assignments will be posted with or without the [homework] tag; questions that show no effort and are thus too vague to reasonably answer should be downvoted and closed, with instructions on how to better ask questions (I've done all three here). The use of [homework] to somehow indicate other answerers should respond in a particular way is confusing and conflicting, but, more importantly, it doesn't help the OP learn and, I believe, ends up being actively harmful towards that goal: saying it's okay to post a vague question with no effort as long as a specific tag is used. – Roger Pate
How does your grammar look like? It is a full-blown language, or just some math equation? – J-16 SDiZ

3 Answers

2
votes

What you need is a recursive descent parser (because that's the only parser that can easily be written by hand). See Wikipedia for details, it's pretty easy.

So, to get operator precedence right you can do something like this:

term = number
unary = ('-' | '+')* term
multiplication = unary ('*' | '/' unary)*
addition = multiplication ('+' | '-' multiplication)*
expression = addition

Where 'expression' is your starting rule.

1
votes

Since you're not allowed to use a parser generator, I would recommend reading about the Recursive descent parser . A very good introduction is included in the Dragon Book