# Determining the maximum stack depth

Filed under:
|
|
|
|
##### algorithm

Imagine I have a stack-based toy language that comes with the operations Push, Pop, Jump and If.

I have a program and its input is the toy language. For instance I get the sequence

``````Push 1
Push 1
Pop
Pop
``````

In that case the maximum stack would be 2. A more complicated example would use branches.

``````Push 1
Push true
If   .success
Pop
Jump .continue
.success:
Push 1
Push 1
Pop
Pop
Pop
.continue:
``````

In this case the maximum stack would be 3. However it is not possible to get the maximum stack by walking top to bottom as shown in this case since it would result in a stack-underflow error actually.

CFGs to the rescue you can build a graph and walk every possible path of the basic blocks you have. However since the number of paths can grow quickly for n vertices you get (n-1)! possible paths.

My current approach is to simplify the graph as much as possible and to have less possible paths. This works but I would consider it ugly. Is there a better (read: faster) way to attack this problem? I am fine if the algorithm produces a stack depth that is not optimal. If the correct stack size is m then my only constraint is that the result n is n >= m. Is there maybe a greedy algorithm available that would produce a good result here?

© Stack Overflow or respective owner

• #### Removing Left Recursion in ANTLR

as seen on Stack Overflow - Search for 'Stack Overflow'
As is explained in http://stackoverflow.com/questions/2652060/removing-left-recursion , there are two ways to remove the left recursion. Modify the original grammar to remove the left recursion using some procedure Write the grammar originally not to have the left recursion What people normally… >>> More

• #### Translate a<b to IR Trees

as seen on Stack Overflow - Search for 'Stack Overflow'
I have to translate the mini-java (java like language) statements into intermediate-representation trees. But for this question I have no idea what it is asking... a>b moves a 1 or 0 into some newly defined temporary, and whose right-hand side is a temporary Does the wording make sense to anyone… >>> More

• #### Determining the maximum stack depth

as seen on Stack Overflow - Search for 'Stack Overflow'
Imagine I have a stack-based toy language that comes with the operations Push, Pop, Jump and If. I have a program and its input is the toy language. For instance I get the sequence Push 1 Push 1 Pop Pop In that case the maximum stack would be 2. A more complicated example would use branches. Push… >>> More

• #### What are modern and old compilers written in?

as seen on Stack Overflow - Search for 'Stack Overflow'
As a compiler, other than an interpreter, only needs to translate the input and not run it the performance of itself should be not that problematic as with an interpreter. Therefore, you wouldn't write an interpreter in, let's say Ruby or PHP because it would be far too slow. However, what about… >>> More

• #### Advantages of compilers for functional languages over compilers for imperative languages

as seen on Stack Overflow - Search for 'Stack Overflow'
As a follow up to this question What are the advantages of built-in immutability of F# over C#?--am I correct in assuming that the F# compiler can make certain optimizations knowing that it's dealing with largely immutable code? I mean even if a developer writes "Functional C#" the compiler wouldn't… >>> More

• #### Java: immutability, overuse of stack -- better data structure?

as seen on Stack Overflow - Search for 'Stack Overflow'
I overused hashSets but it was slow, then changed to Stacks, speed boost-up. Poly's reply uses Collections.emptyList() as immutable list, cutting out excess null-checkers. No Collections.emptyStack(). Combining the words stack and immutability, from the last experiences, gets "immutable stack" (probably… >>> More

• #### iTunes 9.0.2 hangs on launch on Mac OS X 10.6.2

as seen on Super User - Search for 'Super User'
My iTunes 9.0.2 hangs on launch in OS X 10.6.2. This doesn't happen all the time, only if I've been running for a while. Then it will recur until I restart. Similarly Safari 4.0.4 will hang in the flash player plugin when about to play a video. If I restart both these problems go away until later… >>> More

• #### How to write Haskell function to verify parentheses matching?

as seen on Stack Overflow - Search for 'Stack Overflow'
I need to write a function par :: String -> Bool to verify if a given string with parentheses is matching using stack module. Ex: par "(((()[()])))" = True par "((]())" = False Here's my stack module implementation: module Stack (Stack, push, pop, top, empty, isEmpty) … >>> More

• #### PSTN Trunk TDM400P Install on Asterisk / Trixbox

as seen on Server Fault - Search for 'Server Fault'
Hey All, I'm trying to get a TDM400P card with FXO module to connect to our PSTN line. The card is correctly detected by Linux: [trixbox1.localdomain asterisk]# lspci 00:09.0 Communication controller: Tiger Jet Network Inc. Tiger3XX Modem/ISDN interface I've run setup-pstn which… >>> More

• #### how to clear stack after stack overflow signal occur

as seen on Stack Overflow - Search for 'Stack Overflow'
In pthread, After reaching yellow zone in stack, signal handler stop the recursive function by making it return however, we can only continue to use extra area in yellow zone, how to clear the rubbish before the yellow zone in the thread stack ? (Copied from "answers"): #include <pthread… >>> More