Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

In other words, a language where every possible string is valid syntax?

EDIT: This is a theoretical question.
I have no interest in using such a language; I'm just asking whether it's possible.

share|improve this question

closed as not constructive by Josh K, Walter Jan 19 '11 at 16:11

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

2  
If we could do that, we'd have created AI. –  Michael K Jan 19 '11 at 14:07
3  
@Michael: No; I don't think so. –  SLaks Jan 19 '11 at 14:10
5  
!!! Perl !!! –  user1249 Jan 19 '11 at 15:07
3  
I strongly object to the question being closed! It's neither subjective nor not constructive!!! –  Felix Dombek Jan 19 '11 at 20:47
1  
why not take a assembly language with: exacly 256 instructions, 128 registers, and a general syntax of instruction operand*, where an operand may be a register or a number between 0-127 (and everything above that is treated as a register) and if an operand is missing for a multi-arity instruction, '0' is assumed. –  Felix Dombek Jan 19 '11 at 20:50

8 Answers 8

up vote 6 down vote accepted

Yes, if you look at this in a very analitic way creating a Deterministic Turing Machine that always stops in a good final state for every single string of a certain language, then you'll have demostrated that is possible. The demostration is pretty straight forward, you must a regular TM with a transition function with only one transition, that looks like this:

TF(w,q) -> (w,Qa) 

Considerations:
    L = { w | w is any possible string }
    w e L
    q e Q
    F is a set with all good final states {Qa,Qr}
    Qa e F

Its been demostrated that a TM has the same computing power that any single real life computer, so this is absolutely possible

share|improve this answer
    
What on earth does this mean, to us common layfolk? What is 'w', 'e', 'L', 'q', 'Q', 'Qa', 'Qr', 'F', 'TF'. Without any of these defined I have no frame of reference. –  Berin Loritsch Jan 20 '11 at 16:26
    
Sorry but there is no easy way to explain the Turing Machine approach to this answer. Check this link to clarify a little: en.wikipedia.org/wiki/Turing_machine –  guiman Jan 20 '11 at 17:25

Yes, of course it's possible, it's even trivially easy.

<programm> ::= char | char <program> |

I don't understand how anybody can say "no". That said, it might be rather hard to define a meaningful semantic for such a language, but that's possible too. Just look at whitespace.

share|improve this answer
    
So if the language ignores it, it's valid systax? and isn't "tabtabspace" a valid string? –  Michael K Jan 19 '11 at 14:27
1  
The semantics of the language were my issue with it, but can't really discuss it without it getting off-topic to philosophy/linguistics proper. –  StuperUser Jan 19 '11 at 14:30
1  
Michael: Exactly. Everything is syntactically valid, but it can possibly be a NOP (have no special meaning). Nothing wrong with a language ignoring lots of stuff. Just look at all the things C ignores in this sample program: int main() { 3;;; /* comment */ } –  user281377 Jan 19 '11 at 14:36
    
Many people say "no" because they have no conceptional distinction between syntax and semantics. "It doesn't compile? Must be a syntax error, then!" –  FredOverflow Jan 19 '11 at 17:40
    
Many people say "no" because there is no real meaning in this. As soon as you add structure (i.e. more than a self recursive parsing rule) you have the concept of syntax. Violation of the structure is a syntax induced error. Syntax induced error is a Syntax Error, whether the parser flags it as such or not. –  Berin Loritsch Jan 20 '11 at 16:29

I guess it depends on what you mean by valid syntax.

You could design a language that accepted any string but ignored anything that had not been prescribed specific meaning. This is basically the equivalent of saying "I'll get rid of syntax errors but saying they're not errors" - pretty pointless and hugely undesirable for many reasons.

Beyond that the only way you could have a language which had no syntax errors would be to have every possible string have a valid instruction / use associated with it. The only way I can see to do that would be to have all operations as single characters and to ensure that every single character had an operation assigned to it.

There are a million things wrong with this - obviously there are no reserved words, it's all about where it's used in context and as a result it would be basically illegible and, while immune from syntax errors would be far more likely to experience every other sort of error.

So theoretically possible (AmmoQ puts it far more neatly than I) but entirely undesirable.

share|improve this answer
    
I've read that TECO was like that, each character being assigned a meaning. –  David Thornley Jan 19 '11 at 14:41
3  
Machine code works pretty much that way. Every possible combination of bytes can be viewed as a program that does something, even if all it does is causing an interrupt. –  user281377 Jan 19 '11 at 15:19
    
David, thats what I was thinking, very TECO like. Although IIRC TECO input could contain syntax errors. But it demonstrates the difficulty of such a dense language -very hard to read and prone to difficult to understand errors. –  Omega Centauri Jan 19 '11 at 15:22
    
@user281377: On the 6502, there are quite a few instructions with no defined meanings. Some have behaviors which are consistent, useful, and not available with any documented instruction (my favorite is nicknamed "DCP"--decrement a memory address and compare the result with the accumulator, setting flags appropriately), but some have behavior that depend upon bus timings in weird and bizarre ways, and some will lock up the processor hard enough to require a reset (even a "non-maskable" interrupt won't help). I think the latter instructions could be considered "syntax errors". –  supercat May 10 at 15:02

Code in a non-text based programming language may not have syntax errors.

I am thinking of a visual language like BYOB. You can not accidentally type "if x ten else foo" because the "syntax" is defined by graphical blocks.

share|improve this answer

The very purpose of syntax is to differentiate between valid and non-valid in a manner that's faster and more effective than executing the code. Syntax is just an optimisation, what goes in it and what goes into semantics is arbitrary.

Usually you want quite the opposite: to make the syntax stretch as far as possible to save more time, but of course you can alsp omit syntax altogether and declare every error a semantic one: you'll end up with a non-tokenizing interpreter.

share|improve this answer

Ahbefiasdlk aslerhsofa;f jwi [asdfasdf]aew /&Q!@#$ }{ ;-P

So what does that mean?

As long as the language has structure and grammar, there will always be the concept of a syntax error. The question is whether you enforce it or not. People will make mistakes, and syntax errors are what most language designers reach for to help programmers avoid stupid mistakes.

A syntax error is an error introduced by programmers writing code that has no meaning to the language.

It is impossible to get rid of syntax errors based on the above definition. We've all mispelled identifiers, we've all mispelled method names. Having the language silently accept the mispelling and happily do nothing is not my idea of an enjoyable experience.

It is possible to design a language that can use any valid unicode character (or character sequence) as identifiers. There are challenges, such as normalizing equivalent characters/character sequences so that they are recognized as the same thing--but it's possible. NOTE: there are four standard types of unicode normalization.

share|improve this answer
1  
The need for structure does not require a grammar. Consider Piet where the structure is in the position of the character (or color) in a grid, not its relation to other characters in a morpheme. –  Mike Samuel Jan 19 '11 at 19:03
1  
Violate the structure and what happens? –  Berin Loritsch Jan 19 '11 at 19:29

Not for a text based language that can do anything. However if your langage has a custom editor, you could stop invalid syntax from being created in the first place.

share|improve this answer

It's possible if the language is trivial - I.e., all functionality is deterministic and takes no input. For example, create a language where every character represents a NOOP - Anything goes :)

On the other hand, if you need to be able to parse input of arbitrary size, you end up facing the halting problem - Your language may support any string, but there's no way to prove it does.

share|improve this answer
3  
The halting problem is irrelevant here; if nothing else, parsing can be done with constructs less powerful than full Turing machines. –  David Thornley Jan 19 '11 at 14:38
1  
Totally false. I can prove pretty easily that the Whitespace language accepts any string. –  uman Jan 19 '11 at 15:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.