OpenEuphoria

1. Recursive Decent Parser (example)

• Posted by xecronix 1 month ago
• 372 views

Recursive Decent Parser (example) Just the parser bit is about 100 lines of code. Comments add a little bulk.

Update:

• I just noticed I forgot to include unary -/+. So, I fixed it.
• Noticed tabs and spaces both used for indentation. Fixed it. tab = space * 4
• Fixed "pyramid" code by reducing block level nesting.

 
forward function main() 
forward function opAddSub() 
forward function opMultDiv() 
forward function opPrefix() 
forward function opPower() 
forward function parseTerm() 
forward function advance_ptr() 
 
-- ---    This parser is VERY unforgiving by way of expression format. --- 
-- Most notably the spaces between terms, operations, and parentheses are mandatory as written. 
-- I didn't write a robust tokenizer for this.    It's just an expression parser as simple as  
-- I know how to make it.     
 
-- These were the test cases I used.    Very light weight testing.    Exactly -- Zero (0) -- tests  
-- for malformed expressions.    This parser should not be considered production-ready without 
-- some real tests.    But it's probably close. 
 
--sequence str = "2 + 3 * ( 4 + 5 )" 
--sequence str = "2 + 3 * 4" 
--sequence str = "2 * 3 + 4 * 6" 
--sequence str = "2 + 2 ^ 3" 
--sequence str = "4 ^ 3" 
--sequence str = "( 2 + 2 ) ^ 3" 
--sequence str = "1 + 2 + 4"  
--sequence str = "1 + 2 - 4"  
--sequence str = "4 ^ 2 ^ 2" 
--sequence str = "2 * 3 ^ 2" 
--sequence str = "( 2 + 3 ) * ( 4 + 5 )" 
--sequence str = "( 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 ) * - 1" 
--sequence str = "( 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 )" 
--sequence str = "- 2 ^ 2" 
sequence str = "- 3 + ( 4 * 2 ) ^ ( 1 + 1 ) / 8 - - 1" 
 
-- The simplest tokenizer I know of. 
sequence expression = split(str, " ") 
 
-- simulated pointer. Because for me, it kept things simple. 
integer ptr = 1 
 
-- But even if my fake pointer is "simple," a little safety doesn't hurt. 
function advance_ptr()  
    if ptr < length(expression) then 
        ptr += 1 
    return 1  
    else 
        return 0 
    end if 
end function 
 
-- In this parser, the lowest operation is addition and subtraction.     
-- So, this is the entry point to parsing expressions. 
function opAddSub() 
    atom left = opMultDiv() -- Order of operations states multiply and divide come before add and subtract. 
    sequence op = expression[ptr] 
    sequence ops = "+-" 
    printf(1, "Looking for %s in %s\n", {op[1], ops}) 
    while find(op[1], ops) do  
        if not advance_ptr() then 
            exit -- if we couldn't advance the pointer, bail. 
        end if 
        atom right = opMultDiv()    -- this moves the pointer to the next op. 
        if op = "+" then 
            left = left + right 
        else 
            left = left - right 
        end if 
        op = expression[ptr] -- now we're ready to read the next op 
    end while 
    return left 
end function 
 
-- This is very similar to opAddSub.    The difference is this one is  
-- doing different operations and has a divide by 0 check. 
function opMultDiv() 
    atom left = opPrefix() -- Order of operations states exponents come before multiply and divide. 
    sequence op = expression[ptr] 
    sequence ops = "*/" 
    printf(1, "Looking for %s in %s\n", {op[1], ops}) 
    while find(op[1], ops) do  
        if not advance_ptr() then 
            exit 
        end if 
         
        atom right = opPrefix()    -- this moves the pointer to the next op. 
        if op = "*" then 
            left = left * right 
        elsif right = 0 then 
            puts(1, "Error, cannot divide by 0.\n") 
            abort(1) 
        else 
            left = left / right 
        end if 
        op = expression[ptr] -- now we're ready to read the next op 
    end while 
    return left 
end function 
 
-- This is how unary signs are handled.    Essentially, what's happening here is that there is a sign  
-- where a number should be.    So, we'll handle it. 
function opPrefix() 
    integer sign = 1 
    sequence tok = expression[ptr] 
    while tok = "+" or tok = "-" do 
        if tok = "-" then sign = -sign end if --    in case someone does something like ----4  
        if not advance_ptr() then exit end if 
        tok = expression[ptr] 
    end while 
    return sign * opPower() 
end function 
 
-- This looks the same as the other two, but it isn't.    Exponents are evaluated 
-- Right to Left.    The other operations are evaluated from Left to Right.     
-- This tripped me up a little.    Notice this is the first time  
-- We're actually doing recursion. The right side of the binary expression comes 
-- from calling itself.  I'll point it out with a comment.     
function opPower() 
    atom left = parseTerm() 
    sequence op = expression[ptr] 
    sequence ops = "^" 
    printf(1, "Looking for %s in %s\n", {op[1], ops}) 
    while find(op[1], ops) do  
        if not advance_ptr() then 
            exit 
        end if 
         
        atom right = opPower()    -- this is calling itself and will cause 4 ^ 2 ^ 2 to be evaluated like 4 ^ ( 2 ^ 2 ) 
        left = power(left, right) 
        op = expression[ptr] -- now we're ready to read the next op 
    end while 
    return left 
end function 
 
-- NOTE -- This function moves the pointer.    Be aware of that, please. 
-- The objective of this function is to return a single atom value. 
-- We'll deal with params here.    If I were going to add variables or 
-- function calls to this parser, this is where I would do it. 
function parseTerm() 
    sequence token = expression[ptr]; 
    if atom(to_number(token)) then 
        atom success = advance_ptr() -- <<-- This is why the pointer advances in a seemingly sneaky way.    Sorry. 
        return to_number(token); 
    elsif token = "(" then 
        atom success = advance_ptr() -- consume the (    <<-- pointer moves  
        if not success then 
            printf(1, "No term after open ( ", {token}) 
            abort(0) 
        end if 
        atom retval = opAddSub() 
        if expression[ptr] != ")" then 
            printf(1, "expected ) but got %s", {expression[ptr]})      
            abort(0)         
        end if 
        success = advance_ptr() -- consume the )    <<-- pointer moves  
        return retval 
    else 
        printf(1, "expected number or ( but got %s", {token}) 
        abort(0); 
    end if 
end function 
 
function main() 
    atom num = opAddSub(); 
    return num 
end function 
 
printf (1, "main exited with %f\n", {main()}) 

Ronald Weidner

3. Re: Recursive Decent Parser (example)

• Posted by xecronix 1 month ago
• 322 views

Now, pure Euphoria. Slightly less tested. :)

include std/convert.e 
include std/sequence.e 
 
-- ---    This parser is VERY unforgiving by way of expression format. --- 
-- Most notably, the spaces between terms, operations, and parentheses are mandatory as written. 
-- I didn't write a robust tokenizer for this.    It's just an expression parser as simple as  
-- I know how to make it.     
 
-- These were the test cases I used.    Very light weight testing.    Exactly -- Zero (0) -- tests  
-- for malformed expressions.    This parser should not be considered production-ready without 
-- some real tests.    But it's probably close. 
 
--sequence str = "2 + 3 * ( 4 + 5 )" 
--sequence str = "2 + 3 * 4" 
--sequence str = "2 * 3 + 4 * 6" 
--sequence str = "2 + 2 ^ 3" 
--sequence str = "4 ^ 3" 
--sequence str = "( 2 + 2 ) ^ 3" 
--sequence str = "1 + 2 + 4"  
--sequence str = "1 + 2 - 4"  
--sequence str = "4 ^ 2 ^ 2" 
--sequence str = "2 * 3 ^ 2" 
--sequence str = "( 2 + 3 ) * ( 4 + 5 )" 
--sequence str = "( 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 ) * - 1" 
--sequence str = "( 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 )" 
--sequence str = "- 2 ^ 2" 
sequence str = "- 3 + ( 4 * 2 ) ^ ( 1 + 1 ) / 8 - - 1" 
--sequence str = "( 4 + 5 )" 
 
 
-- The simplest tokenizer I know of. 
sequence expression = split(str, " ") 
 
-- simulated pointer. Because for me, it kept things simple. 
integer ptr = 1 
 
-- But even if my fake pointer is "simple," a little safety doesn't hurt. 
function advance_ptr()  
    if ptr < length(expression) then 
        ptr += 1 
        return 1  
    end if 
    return 0 
end function 
 
-- In this parser, the lowest operation is addition and subtraction.     
-- So, this is the entry point to parsing expressions. 
function opAddSub() 
    atom left = opMultDiv() -- Order of operations states multiply and divide come before add and subtract. 
    sequence op = expression[ptr] 
    sequence ops = "+-" 
    printf(1, "Looking for %s in %s\n", {op[1], ops}) 
    while find(op[1], ops) do  
        if not advance_ptr() then -- Move to the next token, probably a number. 
            exit -- if we couldn't advance the pointer, bail. 
        end if 
        atom right = opMultDiv()    -- fetch an number and move the pointer to the next token.  Probably an op. 
        if equal(op, "+") then 
            left = left + right 
        else 
            left = left - right 
        end if 
        op = expression[ptr] -- now we're ready to read the next op 
    end while 
    return left 
end function 
 
-- This is very similar to opAddSub.    The difference is this one is  
-- doing different operations and has a divide by 0 check. 
function opMultDiv() 
    atom left = opPrefix() -- Order of operations states exponents come before multiply and divide. 
    sequence op = expression[ptr] 
    sequence ops = "*/" 
    printf(1, "Looking for %s in %s\n", {op[1], ops}) 
    while find(op[1], ops) do  
        if not advance_ptr() then 
            exit 
        end if 
         
        atom right = opPrefix()    -- this moves the pointer to the next op. 
        if equal(op, "*") then 
            left = left * right 
        elsif right = 0 then 
            puts(1, "Error, cannot divide by 0.\n") 
            abort(1) 
        else 
            left = left / right 
        end if 
        op = expression[ptr] -- now we're ready to read the next op 
    end while 
    return left 
end function 
 
-- This is how unary signs are handled.    Essentially, what's happening here is that there is a sign  
-- where a number should be.    So, we'll handle it. 
function opPrefix() 
    integer sign = 1 
    sequence tok = expression[ptr] 
    while equal(tok, "+") or equal(tok, "-") do 
        if equal(tok, "-") then sign = -sign end if --    in case someone does something like ----4  
        if not advance_ptr() then exit end if 
        tok = expression[ptr] 
    end while 
    return sign * opPower() 
end function 
 
-- This looks the same as the other two, but it isn't.    Exponents are evaluated 
-- Right to Left.    The other operations are evaluated from Left to Right.     
-- This tripped me up a little.    Notice this is the first time  
-- We're actually doing recursion. The right side of the binary expression comes 
-- from calling itself.  I'll point it out with a comment.     
function opPower() 
    atom left = parseTerm() 
    sequence op = expression[ptr] 
    sequence ops = "^" 
    printf(1, "Looking for %s in %s\n", {op[1], ops}) 
    while find(op[1], ops) do  
        if not advance_ptr() then 
            exit 
        end if 
         
        atom right = opPower()    -- this is calling itself and will cause 4 ^ 2 ^ 2 to be evaluated like 4 ^ ( 2 ^ 2 ) 
        left = power(left, right) 
        op = expression[ptr] -- now we're ready to read the next op 
    end while 
    return left 
end function 
 
-- NOTE -- This function moves the pointer.    Be aware of that, please. 
-- The objective of this function is to return a single atom value. 
-- We'll deal with parentheses here.    If I were going to add variables or 
-- function calls to this parser, this is where I would do it. 
function parseTerm() 
    sequence token = expression[ptr] 
    if is_number(token) then 
        atom success = advance_ptr() -- <<-- This is why the pointer advances in a seemingly sneaky way.    Sorry. 
        return to_number(token) 
    elsif equal(token, "(") then 
        atom success = advance_ptr() -- consume the (    <<-- pointer moves  
        if not success then 
            printf(1, "No term after open ( ", {token}) 
            abort(0) 
        end if 
        atom retval = opAddSub() -- <<-- This is recursion 
        if not equal(expression[ptr], ")") then 
            printf(1, "expected ) but got %s", {expression[ptr]})      
            abort(0)         
        end if 
        success = advance_ptr() -- consume the )    <<-- pointer moves  
        return retval 
    else 
        printf(1, "expected number or ( but got %s", {token}) 
        abort(0) 
    end if 
end function 
 
function is_number(sequence maybe) 
    integer found_dot = 0 
    integer i = 1 
    integer c = 0 
    integer retval = 1 
    while i < (length(maybe) + 1) do 
        c = maybe[i] 
        if equal(c, '.') and found_dot then 
            return 0 
        end if 
 
        if equal(c, '.') then  
            found_dot = 1 
        elsif not find(c, "0123456789") then 
            return 0 
        end if 
        i+=1 
    end while 
    return retval 
end function 
 
function main() 
    atom num = opAddSub() 
    return num 
end function 
 
printf (1, "main exited with %f\n", {main()}) 

5. Re: Recursive Decent Parser (example)

• Posted by RobertS 3 weeks ago
• 186 views

I think I've saved myself a lot of trouble by using RPN for my Hypatia calculator ...

7. Re: Recursive Decent Parser (example)

• Posted by RobertS 3 weeks ago
• 168 views

Originally it was in Euphoria, but there were a few problems which I couldn't resolve - I don't fully remember what they were, but they went away when I tried Phix, so it's been Phix ever since.

Yes, you can freely download it from hypatia-rpn.net, also the source code, though this is regrettably poorly documented.

If you have a look at it, I'd be happy to hear what you think!

9. Re: Recursive Decent Parser (example)

• Posted by RobertS 3 weeks ago
• 116 views

Thank you for your praise! As I've said and you have now seen for yourself, the code is poorly documented, it has grown slowly and not always systematically (to put it mildly) over a period of almost 20 years, and I tend to use variable names that are short and convey little information ... If you have any questions please feel free to ask, you can reach me by mail, robert@drs.at

Oh, there was no deep meaning to those words - looking at your code just showed me again that it isn't trivial to parse infix notation, and made me glad that I never tried it. :) Even though laziness wasn't my only motive to avoid it, I really like RPN.