News for hackers. Stuff that matters.

A comment on What type of Machine is the C Preprocessor?.

Re:What type of Machine is the C Preprocessor? by sonnyOrullivan on Monday January 27, 2014 @04:35PM (#7133406)
Wouldn't it simply be a linear bounded automaton (LBA)? I understand you can implement recursion via some tricks but only as many steps as you predefine (see e.g. https://stackoverflow.com/questions/7508475/is-c-preprocesso...) This reeks like an LBA to me.
[ Parent | on HN ]
Re:What type of Machine is the C Preprocessor? by roywiggins on Monday January 27, 2014 @08:01PM (#7134558)
My first instinct is that you're right- at least, I don't think it can be any more powerful than an LBA: if there's a finite number of state transitions it can make, then it can only actually "get to" a certain distance along the tape, and you can just chop the tape at that point.
[ Parent | on HN ]
Re:What type of Machine is the C Preprocessor? by lisper on Tuesday January 28, 2014 @02:20AM (#7135838)
Nope, a cpp-machine is strictly less powerful than an LBA, or even an FSA. An LBA (and an FSA) can enter an infinite loop. A cpp-machine can't.
[ Parent | on HN ]