رفتن به محتوا

Fixing nested function parsing in custom programming language

این محتوا هنوز به زبان شما در دسترس نیست.

💡 Having trouble with Scratch block assembly? Don’t know how to implement code logic? 🚀 Get Help Now

CD

CodeParser_Dev

Posted on August 5, 2024 • Advanced

🔄 Nested function parsing causing infinite loops

I’m building a custom programming language interpreter in Scratch, but I’m having major issues with nested function calls. When I try to evaluate expressions like:

  • sqrt(abs(-7)+sqrt(4))
  • max(min(5,3), abs(-2))
  • Any function with nested parentheses

The parser gets stuck in infinite loops and never returns a result. I think the issue is with how I’m handling the recursive parsing, but I can’t figure out what’s going wrong. 😵

Has anyone built something similar? How do you properly parse nested function calls without getting stuck?

LP

LanguageParser_Expert

Replied 4 hours later • ⭐ Best Answer

@CodeParser_Dev I’ve built several interpreters in Scratch! The infinite loop issue is very common with recursive parsing. Let me show you a robust solution:

🔍 Step 1: Understanding the Problem

The issue is usually caused by:

  • Not properly extracting inner expressions
  • Missing base cases in recursion
  • Incorrect parentheses matching
  • Stack overflow from too deep recursion

🛠️ Step 2: Proper Expression Tokenizer

First, let’s build a tokenizer that breaks down the expression:

    // Tokenize expression into manageable parts
define tokenize (expression)
delete all of [tokens v]
set [i v] to [1]
set [current token v] to []
repeat (length of (expression))
set [char v] to (letter (i) of (expression))
if <<(char) = [(]> or <(char) = [)]>> then
if <(length of (current token)) > [0]> then
add (current token) to [tokens v]
set [current token v] to []
end
add (char) to [tokens v]
else
if <<(char) = [,]> or <(char) = [ ]>> then
if <(length of (current token)) > [0]> then
add (current token) to [tokens v]
set [current token v] to []
end
else
set [current token v] to (join (current token) (char))
end
end
change [i v] by [1]
end
if <(length of (current token)) > [0]> then
add (current token) to [tokens v]
end

🎯 Step 3: Recursive Descent Parser

Here’s the core parsing logic that handles nested functions properly:

    // Main evaluation function
define evaluate (expression)
set [recursion depth v] to ((recursion depth) + [1])
if <(recursion depth) > [50]> then
say [Error: Maximum recursion depth exceeded] for (2) seconds
set [recursion depth v] to ((recursion depth) - [1])
stop [this script v]
end

// Remove spaces
set [clean expr v] to (replace [ ] with [] in (expression))

// Check if it's just a number
if <(is number? (clean expr)) = [true]> then
set [result v] to (clean expr)
set [recursion depth v] to ((recursion depth) - [1])
else
// Parse function call
set [result v] to (parse function call (clean expr))
set [recursion depth v] to ((recursion depth) - [1])
end

🔧 Step 4: Function Call Parser

This handles the actual function parsing with proper nesting:

    define parse function call (expr)
set [func name v] to []
set [paren count v] to [0]
set [start pos v] to [0]
set [i v] to [1]

// Find function name
repeat until <<(letter (i) of (expr)) = [(]> or <(i) > (length of (expr))>>
set [func name v] to (join (func name) (letter (i) of (expr)))
change [i v] by [1]
end

if <(i) > (length of (expr))> then
// No function, just return the expression
set [parse result v] to (expr)
else
// Extract arguments
set [start pos v] to ((i) + [1]) // Skip opening parenthesis
set [paren count v] to [1]
change [i v] by [1]

repeat until <<(paren count) = [0]> or <(i) > (length of (expr))>>
if <(letter (i) of (expr)) = [(]> then
change [paren count v] by [1]
end
if <(letter (i) of (expr)) = [)]> then
change [paren count v] by [-1]
end
change [i v] by [1]
end

// Extract inner expression (without outer parentheses)
set [inner expr v] to (letters (start pos) to ((i) - [2]) of (expr))

// Parse arguments
parse arguments (inner expr)

// Execute function
execute function (func name)
end

⚙️ Step 5: Argument Parser

This correctly splits arguments while respecting nested parentheses:

    define parse arguments (args string)
delete all of [arguments v]
if <(length of (args string)) = [0]> then
stop [this script v]
end

set [current arg v] to []
set [paren depth v] to [0]
set [i v] to [1]

repeat (length of (args string))
set [char v] to (letter (i) of (args string))

if <(char) = [(]> then
change [paren depth v] by [1]
set [current arg v] to (join (current arg) (char))
else
if <(char) = [)]> then
change [paren depth v] by [-1]
set [current arg v] to (join (current arg) (char))
else
if <<(char) = [,]> and <(paren depth) = [0]>> then
// End of current argument
add (evaluate (current arg)) to [arguments v]
set [current arg v] to []
else
set [current arg v] to (join (current arg) (char))
end
end
end
change [i v] by [1]
end

// Add the last argument
if <(length of (current arg)) > [0]> then
add (evaluate (current arg)) to [arguments v]
end

🎲 Step 6: Function Execution

Finally, execute the actual mathematical functions:

    define execute function (name)
if <(name) = [sqrt]> then
if <(length of [arguments v]) = [1]> then
set [parse result v] to ([sqrt v] of (item [1] of [arguments v]))
else
set [parse result v] to [Error: sqrt requires 1 argument]
end
else
if <(name) = [abs]> then
if <(length of [arguments v]) = [1]> then
set [parse result v] to ([abs v] of (item [1] of [arguments v]))
else
set [parse result v] to [Error: abs requires 1 argument]
end
else
if <(name) = [max]> then
if <(length of [arguments v]) = [2]> then
if <(item [1] of [arguments v]) > (item [2] of [arguments v])> then
set [parse result v] to (item [1] of [arguments v])
else
set [parse result v] to (item [2] of [arguments v])
end
else
set [parse result v] to [Error: max requires 2 arguments]
end
else
if <(name) = [min]> then
if <(length of [arguments v]) = [2]> then
if <(item [1] of [arguments v]) < (item [2] of [arguments v])> then
set [parse result v] to (item [1] of [arguments v])
else
set [parse result v] to (item [2] of [arguments v])
end
else
set [parse result v] to [Error: min requires 2 arguments]
end
else
set [parse result v] to (join [Error: Unknown function ] (name))
end
end
end
end

🐛 Step 7: Debug Helper

Add this debugging system to track what’s happening:

    define debug log (message)
add (join (join [Depth ] (recursion depth)) (join [: ] (message))) to [debug log v]
if <(length of [debug log v]) > [20]> then
delete [1] of [debug log v]
end

when [d v] key pressed
show list [debug log v]

when [c v] key pressed
hide list [debug log v]
delete all of [debug log v]

🧪 Step 8: Test Cases

Test your parser with these examples:

    when [1 v] key pressed
set [test expr v] to [sqrt(4)]
say (join [Result: ] (evaluate (test expr))) for (3) seconds

when [2 v] key pressed
set [test expr v] to [abs(-7)]
say (join [Result: ] (evaluate (test expr))) for (3) seconds

when [3 v] key pressed
set [test expr v] to [sqrt(abs(-7)+sqrt(4))]
say (join [Result: ] (evaluate (test expr))) for (3) seconds

when [4 v] key pressed
set [test expr v] to [max(min(5,3),abs(-2))]
say (join [Result: ] (evaluate (test expr))) for (3) seconds

This approach should eliminate the infinite loops by properly handling recursion depth and correctly parsing nested expressions! 🎉

CD

CodeParser_Dev

Replied 2 hours later

@LanguageParser_Expert This is absolutely incredible! 🤯

The recursion depth check was exactly what I was missing! My parser was getting stuck because it kept calling itself infinitely. Your solution with proper parentheses matching and argument parsing works perfectly.

I tested sqrt(abs(-7)+sqrt(4)) and it correctly returns 3! The debug system is super helpful too for understanding what’s happening at each step.

Thank you so much for this comprehensive solution! 🙏

VB

Vibelf_Community

Pinned Message • Moderator

🚀 Ready to Build Advanced Programming Languages?

Fantastic work on the parser implementation! For those interested in creating even more sophisticated language interpreters, our community can help you implement:

  • 🔄 Advanced recursion patterns
  • 📊 Variable scoping and environments
  • 🎯 Custom operators and precedence
  • 🧠 Memory management systems

📚 Related Discussions

Ready to dive deeper into computer science? Get expert guidance from our programming tutors in the Vibelf app!