Skip to main content
Share Your Experience: Take the 2024 Developer Survey

New answers tagged

1 vote
Accepted

Concatenating strings given a BNF grammar

A production rule for an empty string (or equivalently an empty token) can always succeed by consuming nothing from the input. So, when you peek '(', the parser first tries the production <Letter&...
Bart van Ingen Schenau's user avatar
0 votes

can every program still be written without recursion or cyclic calls?

With a normal programming language, it's theoretically possible to write a static analyzer that determines a program's maximum stack usage, with the caveat that for some programs, the analyzer will ...
Gilles 'SO- stop being evil''s user avatar
0 votes

can every program still be written without recursion or cyclic calls?

Take a read of the Church Turing Thesis, in short all recursion can be replaced with iteration. Now that your limitation is removed, the question is simply can a compiler determine max stack usage. ...
jgn's user avatar
  • 1
-1 votes

can every program still be written without recursion or cyclic calls?

I'm wondering if it was theoretically possible for a compiler to determine maximum stack depth at compile time No, this is not possible. The call depth usually depends on the input data, so in the ...
AnoE's user avatar
  • 5,843
1 vote

can every program still be written without recursion or cyclic calls?

The max call stack depth for a program without recursion would be the number of functions in the program. It is always possible to rewrite recursive functions to be non-recursive with the help of a ...
JacquesB's user avatar
  • 59.7k
-1 votes

can every program still be written without recursion or cyclic calls?

Pigeonhole principle I think this question is being asked so broadly and vaguely that it's ceasing to be useful as an actual code metric. The direct answer here is that if you disallow cyclic calls, ...
Flater's user avatar
  • 51.7k
-1 votes

can every program still be written without recursion or cyclic calls?

Brainfuck can be crammed into a single main procedure with a single dispatch loop, and everything can theoretically be compiled to Brainfuck. Memory usage is unbounded in the Turing-complete limit, ...
Corbin's user avatar
  • 146
1 vote

can every program still be written without recursion or cyclic calls?

Use a compiler to translate your program into assembler. Then write a simulator that can simulate assembler programs. Then replace the assembler code with a huge array of static data.
gnasher729's user avatar
  • 45.7k
9 votes

can every program still be written without recursion or cyclic calls?

I think it is clear we are talking about a programming language environment where all code is organized inside functions with some local scope, all functions exist at compile time and the executing ...
Doc Brown's user avatar
  • 209k
8 votes

can every program still be written without recursion or cyclic calls?

The strict hierarchy of tasks that are computable under one theoretical model of computation vs. another really only exists "in the limit", i.e. when you allow unlimited resources. There are ...
Kilian Foth's user avatar

Top 50 recent answers are included