I wrote the following code.
(defmacro make-binary-parser (name op next)
`(defun ,name (line)
(let* ((result (,next line))
(token (peek-token line)))
(cond
((eq (op token) ,op)
(next-token line)
(list (op token) result (,name line)))
(t result)))))
(make-binary-parser div-op '/ umn-op)
(make-binary-parser mul-op '* div-op)
(make-binary-parser min-op '- mul-op)
(make-binary-parser pls-op '+ min-op)
it works. But I wished to collapse this into two functions
/* and +-
When I do this I get something like "2/3*2" --> (/ 2 (* 3 2))
How do I avoid this?
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
John Thingstad <··············@chello.no> wrote in message news:<················@news.chello.no>...
> I wrote the following code.
>
> (defmacro make-binary-parser (name op next)
> `(defun ,name (line)
> (let* ((result (,next line))
> (token (peek-token line)))
> (cond
> ((eq (op token) ,op)
> (next-token line)
> (list (op token) result (,name line)))
> (t result)))))
>
> (make-binary-parser div-op '/ umn-op)
> (make-binary-parser mul-op '* div-op)
> (make-binary-parser min-op '- mul-op)
> (make-binary-parser pls-op '+ min-op)
Your problem here is that all you have is a simple chain of handlers.
The next token in the input is examined, and each chain element in
turn compares it to the symbol it wants. If so, it shifts the token
and produces the tree node.
You have effectively placed all of your operators at the same level of
precedence, and given them right associativity, so that:
x1 o1 x2 o2 x3 o3 x4
becomes
(o1 x1 (o2 (x2 (o3 x3 x4))))
regardless of which operators the o's are.
> it works. But I wished to collapse this into two functions
> /* and +-
> When I do this I get something like "2/3*2" --> (/ 2 (* 3 2))
> How do I avoid this?
The short answer is: by implementing a correct algorithm for parsing
operator precedence. There are simplified algorithms that are
specialized for grammars that just have binary and unary operators,
and no other kinds of phrase structures.
It can be done by recursive descent, but you have to left-factor the
grammar. The topmost recursion level handles the lowest precedence.
For example say you have a grammar with brackets, additive operators,
multiplicative operators.
Your highest level function parses a sequence of terms, which is a
single term, or such a sequence followed by an additive operator
followed by another term. At the next lower level, you are handling
the factors of each term, in the same way: term is one factor, or a
term followed by a multiplicative operator followed by another factor.
A factor is a bracketed expression, numeric constant, variable and the
like. A bracketed expression is the recognition of a ( token, with
recursion to the top level, and matching a closing ).