0
$\begingroup$

I do sure that "grammar" and "syntax" is two different thing in CS, e.g

Syntax of Java language is defined by a context-free grammar.

My question are

What is different in definitions of "grammar" and "syntax" in CS?

What is relation between them, can we describe it by using set theory?

|cite|improve this question
$\endgroup$
7
$\begingroup$

Your quote has the following operational meaning for syntax in the context of programming languages:

The syntax of a programming language is the set of all syntactically valid programs.

The syntax only describes what the valid programs look like; semantics gives them meaning – tells you how to execute them.

The set of all valid programs is an example of a formal language; a formal language is just a collection of strings. There are many ways of describing formal languages. One of them is through formal grammars, which you can think of as a type of formula that describes a formal language. Context-free grammars are a restricted type of formal grammars. As such, they cannot describe all formal languages, but only context-free languages. (General grammars also describe only some of the formal languages; this is due to the fact that there are countably many grammars but uncountably many formal languages.) Summarizing:

A grammar is one way to specify a formal language.

Finally, let me mention that the set of syntactically valid Java programs actually cannot be described by a context-free grammar; only some features can be described. Context-free grammars cannot enforce, for example, that a variable not be defined twice in the same context. However, once we abstract away such details (for example, by replacing variable names with generic placeholders), the resulting set of syntactically valid Java programs does lend itself (perhaps) to being captured by a context-free grammar.

Parsing (in our context) is the process of reading the source code of a Java program and constructing its parse tree, which is its structure as seen from the perspective of the context-free grammar. The parse tree captures the semantics of the program in a form amenable to further manipulation in the compilation process. Abstracting away details such as variable names and values of constants relegates this information into the form of parameters, but doesn't obstruct the control structure of the program.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ So how do you define syntactically valid? It's what a program is when ... well, what? A Java compiler doesn't throw any syntax errors on them? $\endgroup$ – reinierpost Aug 23 '16 at 15:39
  • $\begingroup$ @reinierpost That's right. A syntactically valid program is one which has no syntax errors. $\endgroup$ – Yuval Filmus Aug 23 '16 at 15:40
  • $\begingroup$ So what is a syntax error? I just want to make sure we can eventually end up with a definition that doesn't already have the word syntax or syntactical in it. E.g. I'm fine with letting a particular piece of software be the judge, but that has its problems. (A bugfix that causes a syntax error to be reported that previously wasn't will then change the syntax of Java.) $\endgroup$ – reinierpost Aug 23 '16 at 15:46
  • $\begingroup$ @reinierpost Formal definitions are a nice pastime, but in reality this is an intuitive concept, some details of which might be contentious. For example, is importing a missing package a syntax error? I don't think so, but you can disagree. In practice, committees publish standards which include the syntax of programming languages, including Java, thus answering your question in an official manner. $\endgroup$ – Yuval Filmus Aug 23 '16 at 15:50
  • $\begingroup$ I don't think this is about formality, but about ontology: what sort of thing is a programming language and what sort of thing is its syntax? I wanted to see it clarified that for you (as for me) it is basically something like a natural language: the language and its syntax are "out there" and formal definitions, such as grammars, mearly try to describe it. Different views exist (e.g. "the grammar is the syntax"). $\endgroup$ – reinierpost Aug 23 '16 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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