In computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, the syntax of a
computer language
A computer language is a formal language used to communicate with a computer. Types of computer languages include:
* Construction language – all forms of communication by which a human can specify an executable problem solution to a compu ...
is the rules that defines the combinations of symbols that are considered to be correctly structured
statements or
expression
Expression may refer to:
Linguistics
* Expression (linguistics), a word, phrase, or sentence
* Fixed expression, a form of words with a specific meaning
* Idiom, a type of fixed expression
* Metaphorical expression, a particular word, phrase, o ...
s in that language. This applies both to
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
s, where the document represents
source code
In computing, source code, or simply code, is any collection of code, with or without comments, written using a human-readable programming language, usually as plain text. The source code of a program is specially designed to facilitate the wo ...
, and to
markup language
Markup language refers to a text-encoding system consisting of a set of symbols inserted in a text document to control its structure, formatting, or the relationship between its parts. Markup is often used to control the display of the document ...
s, where the document represents data.
The syntax of a language defines its surface form.
Text-based
In computing, text-based user interfaces (TUI) (alternately terminal user interfaces, to reflect a dependence upon the properties of computer terminals and not just text), is a retronym describing a type of user interface (UI) common as an ear ...
computer languages are based on sequences of
character
Character or Characters may refer to:
Arts, entertainment, and media Literature
* ''Character'' (novel), a 1936 Dutch novel by Ferdinand Bordewijk
* ''Characters'' (Theophrastus), a classical Greek set of character sketches attributed to The ...
s, while
visual programming languages
In computing, a visual programming language (visual programming system, VPL, or, VPS) is any programming language that lets users create programs by manipulating program elements ''graphically'' rather than by specifying them ''textually''. A VPL ...
are based on the spatial layout and connections between symbols (which may be textual or graphical). Documents that are syntactically invalid are said to have a
syntax error. When designing the syntax of a language, a designer might start by writing down examples of both legal and illegal
strings, before trying to figure out the general rules from these examples.
Syntax therefore refers to the ''form'' of the code, and is contrasted with
semantics
Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference, meaning, or truth. The term can be used to refer to subfields of several distinct disciplines, including philosophy
Philosophy (f ...
– the ''meaning''. In processing computer languages, semantic processing generally comes after syntactic processing; however, in some cases, semantic processing is necessary for complete syntactic analysis, and these are done together or
concurrently. In a
compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
, the syntactic analysis comprises the
frontend, while the
semantic analysis comprises the
backend (and middle end, if this phase is distinguished).
Levels of syntax
Computer language syntax is generally distinguished into three levels:
* Words – the lexical level, determining how characters form
tokens;
* Phrases – the grammar level, narrowly speaking, determining how tokens form phrases;
* Context – determining what objects or variables names refer to, if types are valid, etc.
Distinguishing in this way yields modularity, allowing each level to be described and processed separately and often independently. First, a lexer turns the linear sequence of characters into a linear sequence of tokens; this is known as "
lexical analysis
In computer science, lexical analysis, lexing or tokenization is the process of converting a sequence of characters (such as in a computer program or web page) into a sequence of ''lexical tokens'' ( strings with an assigned and thus identified ...
" or "lexing". Second, the parser turns the linear sequence of tokens into a hierarchical syntax tree; this is known as "
parsing
Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. The term ''parsing'' comes from Lati ...
" narrowly speaking. Thirdly, the contextual analysis resolves names and checks types. This modularity is sometimes possible, but in many real-world languages an earlier step depends on a later step – for example,
the lexer hack In computer programming, the lexer hack is a common solution to the problems in parsing ANSI C, due to the reference grammar being context-sensitive. In C, classifying a sequence of characters as a variable name or a type name requires contextual i ...
in C is because tokenization depends on context. Even in these cases, syntactical analysis is often seen as approximating this ideal model.
The parsing stage itself can be divided into two parts: the
parse tree
A parse tree or parsing tree or derivation tree or concrete syntax tree is an ordered, rooted tree that represents the syntactic structure of a string according to some context-free grammar. The term ''parse tree'' itself is used primarily in co ...
, or "concrete syntax tree", which is determined by the grammar, but is generally far too detailed for practical use, and the
abstract syntax tree
In computer science, an abstract syntax tree (AST), or just syntax tree, is a tree representation of the abstract syntactic structure of text (often source code) written in a formal language. Each node of the tree denotes a construct occurring ...
(AST), which simplifies this into a usable form. The AST and contextual analysis steps can be considered a form of semantic analysis, as they are adding meaning and interpretation to the syntax, or alternatively as informal, manual implementations of syntactical rules that would be difficult or awkward to describe or implement formally.
The levels generally correspond to levels in the
Chomsky hierarchy
In formal language theory, computer science and linguistics, the Chomsky hierarchy (also referred to as the Chomsky–Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars.
This hierarchy of grammars was described by ...
. Words are in a
regular language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
, specified in the
lexical grammar In computer science, a lexical grammar is a formal grammar defining the syntax of tokens. The program is written using characters that are defined by the lexical structure of the language used. The character set is equivalent to the alphabet used b ...
, which is a Type-3 grammar, generally given as
regular expression
A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...
s. Phrases are in a
context-free language
In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG).
Context-free languages have many applications in programming languages, in particular, most arithmetic expressions are generated by ...
(CFL), generally a
deterministic context-free language In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic pushdown automaton. DCFLs are always unambiguous, mea ...
(DCFL), specified in a
phrase structure grammar
The term phrase structure grammar was originally introduced by Noam Chomsky as the term for grammar studied previously by Emil Post and Axel Thue (Post canonical systems). Some authors, however, reserve the term for more restricted grammars in the ...
, which is a Type-2 grammar, generally given as
production rules in
Backus–Naur form (BNF). Phrase grammars are often specified in much more constrained grammars than full
context-free grammars, in order to make them easier to parse; while the
LR parser
In computer science, LR parsers are a type of bottom-up parser that analyse deterministic context-free languages in linear time. There are several variants of LR parsers: SLR parsers, LALR parsers, Canonical LR(1) parsers, Minimal LR(1) parse ...
can parse any DCFL in linear time, the simple
LALR parser
In computer science, an LALR parser or Look-Ahead LR parser is a simplified version of a canonical LR parser, to parse a text according to a set of production rules specified by a formal grammar for a computer language. ("LR" means left-to-rig ...
and even simpler
LL parser
In computer science, an LL parser (Left-to-right, leftmost derivation) is a top-down parser for a restricted context-free language. It parses the input from Left to right, performing Leftmost derivation of the sentence.
An LL parser is called a ...
are more efficient, but can only parse grammars whose production rules are constrained. In principle, contextual structure can be described by a
context-sensitive grammar, and automatically analyzed by means such as
attribute grammar An attribute grammar is a formal way to supplement a formal grammar with semantic information processing. Semantic information is stored in attributes associated with terminal and nonterminal symbols of the grammar. The values of attributes are resu ...
s, though, in general, this step is done manually, via
name resolution rules and
type checking
In computer programming, a type system is a logical system comprising a set of rules that assigns a property called a type to every "term" (a word, phrase, or other set of symbols). Usually the terms are various constructs of a computer progra ...
, and implemented via a
symbol table
In computer science, a symbol table is a data structure used by a language translator such as a compiler or interpreter, where each identifier (or symbols), constants, procedures and functions in a program's source code is associated with info ...
which stores names and types for each scope.
Tools have been written that automatically generate a lexer from a lexical specification written in regular expressions and a parser from the phrase grammar written in BNF: this allows one to use
declarative programming
In computer science, declarative programming is a programming paradigm—a style of building the structure and elements of computer programs—that expresses the logic of a computation without describing its control flow.
Many languages that ap ...
, rather than need to have procedural or functional programming. A notable example is the
lex
Lex or LEX may refer to:
Arts and entertainment
* ''Lex'', a daily featured column in the ''Financial Times''
Games
* Lex, the mascot of the word-forming puzzle video game ''Bookworm''
* Lex, the protagonist of the word-forming puzzle video ga ...
-
yacc
Yacc (Yet Another Compiler-Compiler) is a computer program for the Unix operating system developed by Stephen C. Johnson. It is a Look Ahead Left-to-Right Rightmost Derivation (LALR) parser generator, generating a LALR parser (the part of a com ...
pair. These automatically produce a ''concrete'' syntax tree; the parser writer must then manually write code describing how this is converted to an ''abstract'' syntax tree. Contextual analysis is also generally implemented manually. Despite the existence of these automatic tools, parsing is often implemented manually, for various reasons – perhaps the phrase structure is not context-free, or an alternative implementation improves performance or error-reporting, or allows the grammar to be changed more easily. Parsers are often written in functional languages, such as
Haskell
Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lan ...
, or in scripting languages, such as
Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
or
Perl
Perl is a family of two high-level, general-purpose, interpreted, dynamic programming languages. "Perl" refers to Perl 5, but from 2000 to 2019 it also referred to its redesigned "sister language", Perl 6, before the latter's name was offici ...
, or in
C or
C++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
.
Examples of errors
As an example,
(add 1 1)
is a syntactically valid Lisp program (assuming the 'add' function exists, else name resolution fails), adding 1 and 1. However, the following are invalid:
(_ 1 1) lexical error: '_' is not valid
(add 1 1 parsing error: missing closing ')'
Note that the lexer is unable to identify the first error – all it knows is that, after producing the token LEFT_PAREN, '(' the remainder of the program is invalid, since no word rule begins with '_'. The second error is detected at the parsing stage: The parser has identified the "list" production rule due to the '(' token (as the only match), and thus can give an error message; in general it may be
ambiguous.
Type errors and undeclared variable errors are sometimes considered to be syntax errors when they are detected at compile-time (which is usually the case when compiling strongly-typed languages), though it is common to classify these kinds of error as
semantic
Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference, meaning, or truth. The term can be used to refer to subfields of several distinct disciplines, including philosophy, linguistics and comput ...
errors instead.
[Semantic Errors in Java](_blank)
/ref>
As an example, the Python code
'a' + 1
contains a type error because it adds a string literal to an integer literal. Type errors of this kind can be detected at compile-time: They can be detected during parsing (phrase analysis) if the compiler uses separate rules that allow "integerLiteral + integerLiteral" but not "stringLiteral + integerLiteral", though it is more likely that the compiler will use a parsing rule that allows all expressions of the form "LiteralOrIdentifier + LiteralOrIdentifier" and then the error will be detected during contextual analysis (when type checking occurs). In some cases this validation is not done by the compiler, and these errors are only detected at runtime.
In a dynamically typed language, where type can only be determined at runtime, many type errors can only be detected at runtime. For example, the Python code
a + b
is syntactically valid at the phrase level, but the correctness of the types of a and b can only be determined at runtime, as variables do not have types in Python, only values do. Whereas there is disagreement about whether a type error detected by the compiler should be called a syntax error (rather than a static semantic error), type errors which can only be detected at program execution time are always regarded as semantic rather than syntax errors.
Syntax definition
The syntax of textual programming languages is usually defined using a combination of regular expression
A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...
s (for lexical
Lexical may refer to:
Linguistics
* Lexical corpus or lexis, a complete set of all words in a language
* Lexical item, a basic unit of lexicographical classification
* Lexicon, the vocabulary of a person, language, or branch of knowledge
* Lex ...
structure) and Backus–Naur form (for grammatical
In linguistics, grammaticality is determined by the conformity to language usage as derived by the grammar of a particular variety (linguistics), speech variety. The notion of grammaticality rose alongside the theory of generative grammar, the go ...
structure) to inductively specify syntactic categories A syntactic category is a syntactic unit that theories of syntax assume. Word classes, largely corresponding to traditional parts of speech (e.g. noun, verb, preposition, etc.), are syntactic categories. In phrase structure grammars, the ''phrasal c ...
(nonterminals) and ''terminal'' symbols. Syntactic categories are defined by rules called ''productions'', which specify the values that belong to a particular syntactic category. Terminal symbols are the concrete characters or strings of characters (for example keyword
Keyword may refer to:
Computing
* Keyword (Internet search), a word or phrase typically used by bloggers or online content creator to rank a web page on a particular topic
* Index term, a term used as a keyword to documents in an information syst ...
s such as ''define'', ''if'', ''let'', or ''void'') from which syntactically valid programs are constructed.
A language can have different equivalent grammars, such as equivalent regular expressions (at the lexical levels), or different phrase rules which generate the same language. Using a broader category of grammars, such as LR grammars, can allow shorter or simpler grammars compared with more restricted categories, such as LL grammar, which may require longer grammars with more rules. Different but equivalent phrase grammars yield different parse trees, though the underlying language (set of valid documents) is the same.
Example: Lisp S-expressions
Below is a simple grammar, defined using the notation of regular expressions and Extended Backus–Naur form
In computer science, extended Backus–Naur form (EBNF) is a family of metasyntax notations, any of which can be used to express a context-free grammar. EBNF is used to make a formal description of a formal language such as a computer programm ...
. It describes the syntax of S-expression
In computer programming, an S-expression (or symbolic expression, abbreviated as sexpr or sexp) is an expression in a like-named notation for nested list (tree-structured) data. S-expressions were invented for and popularized by the programming la ...
s, a data syntax of the programming language Lisp
A lisp is a speech impairment in which a person misarticulates sibilants (, , , , , , , ). These misarticulations often result in unclear speech.
Types
* A frontal lisp occurs when the tongue is placed anterior to the target. Interdental lisping ...
, which defines productions for the syntactic categories ''expression'', ''atom'', ''number'', ''symbol'', and ''list'':
expression = atom , list
atom = number , symbol
number = - 0'-'9'
symbol = A'-'Z''A'-'Z''0'-'9'].*
list = '(', expression*, ')'
This grammar specifies the following:
* an ''expression'' is either an ''atom'' or a ''list'';
* an ''atom'' is either a ''number'' or a ''symbol'';
* a ''number'' is an unbroken sequence of one or more decimal digits, optionally preceded by a plus or minus sign;
* a ''symbol'' is a letter followed by zero or more of any characters (excluding whitespace); and
* a ''list'' is a matched pair of parentheses, with zero or more ''expressions'' inside it.
Here the decimal digits, upper- and lower-case characters, and parentheses are terminal symbols.
The following are examples of well-formed token sequences in this grammar: '12345
', '()
', '(A B C232 (1))
'
Complex grammars
The grammar needed to specify a programming language can be classified by its position in the Chomsky hierarchy
In formal language theory, computer science and linguistics, the Chomsky hierarchy (also referred to as the Chomsky–Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars.
This hierarchy of grammars was described by ...
. The phrase grammar of most programming languages can be specified using a Type-2 grammar, i.e., they are context-free grammars, though the overall syntax is context-sensitive (due to variable declarations and nested scopes), hence Type-1. However, there are exceptions, and for some languages the phrase grammar is Type-0 (Turing-complete).
In some languages like Perl and Lisp the specification (or implementation) of the language allows constructs that execute during the parsing phase. Furthermore, these languages have constructs that allow the programmer to alter the behavior of the parser. This combination effectively blurs the distinction between parsing and execution, and makes syntax analysis an undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an ...
in these languages, meaning that the parsing phase may not finish. For example, in Perl it is possible to execute code during parsing using a BEGIN
statement, and Perl function prototypes may alter the syntactic interpretation, and possibly even the syntactic validity of the remaining code. Colloquially this is referred to as "only Perl can parse Perl" (because code must be executed during parsing, and can modify the grammar), or more strongly "even Perl cannot parse Perl" (because it is undecidable). Similarly, Lisp macros introduced by the defmacro
syntax also execute during parsing, meaning that a Lisp compiler must have an entire Lisp run-time system present. In contrast, C macros are merely string replacements, and do not require code execution.
Syntax versus semantics
The syntax of a language describes the form of a valid program, but does not provide any information about the meaning of the program or the results of executing that program. The meaning given to a combination of symbols is handled by semantics (either formal or hard-coded in a reference implementation
In the software development process, a reference implementation (or, less frequently, sample implementation or model implementation) is a program that implements all requirements from a corresponding specification. The reference implementation o ...
). Not all syntactically correct programs are semantically correct. Many syntactically correct programs are nonetheless ill-formed, per the language's rules; and may (depending on the language specification and the soundness of the implementation) result in an error on translation or execution. In some cases, such programs may exhibit undefined behavior
In computer programming, undefined behavior (UB) is the result of executing a program whose behavior is prescribed to be unpredictable, in the language specification to which the computer code adheres. This is different from unspecified behavior ...
. Even when a program is well-defined within a language, it may still have a meaning that is not intended by the person who wrote it.
Using natural language
In neuropsychology, linguistics, and philosophy of language, a natural language or ordinary language is any language that has evolved naturally in humans through use and repetition without conscious planning or premeditation. Natural languages ...
as an example, it may not be possible to assign a meaning to a grammatically correct sentence or the sentence may be false:
* " Colorless green ideas sleep furiously." is grammatically well formed but has no generally accepted meaning.
* "John is a married bachelor." is grammatically well formed but expresses a meaning that cannot be true.
The following C language fragment is syntactically correct, but performs an operation that is not semantically defined (because is a null pointer
In computing, a null pointer or null reference is a value saved for indicating that the pointer or reference does not refer to a valid object. Programs routinely use null pointers to represent conditions such as the end of a list of unknown lengt ...
, the operations and have no meaning):
complex *p = NULL;
complex abs_p = sqrt (p->real * p->real + p->im * p->im);
As a simpler example,
int x;
printf("%d", x);
is syntactically valid, but not semantically defined, as it uses an uninitialized variable
In computing, an uninitialized variable is a variable that is declared but is not set to a definite known value before it is used. It will have ''some'' value, but not a predictable one. As such, it is a programming error and a common source of b ...
. Even though compilers for some programming languages (e.g., Java and C#) would detect uninitialized variable errors of this kind, they should be regarded as semantic
Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference, meaning, or truth. The term can be used to refer to subfields of several distinct disciplines, including philosophy, linguistics and comput ...
errors rather than syntax errors.Issue of syntax or semantics?
/ref>
See also
*Naming convention (programming)
In computer programming, a naming convention is a set of rules for choosing the character sequence to be used for identifiers which denote variables, types, functions, and other entities in source code and documentation.
Reasons for using a na ...
*Comparison of programming languages (syntax)
This comparison of programming languages compares the features of language syntax (format) for over 50 computer programming languages.
Expressions
Programming language expressions can be broadly classified into four syntax structures:
;pre ...
To quickly compare syntax of various programming languages, take a look at the list of "Hello, World!" program examples:
* Prolog syntax and semantics
* Perl syntax
* PHP syntax and semantics
* C syntax
C, or c, is the third letter in the Latin alphabet, used in the modern English alphabet, the alphabets of other western European languages and others worldwide. Its name in English is ''cee'' (pronounced ), plural ''cees''.
History
"C" ...
* C++ syntax
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
* Java syntax
The syntax of Java refers to the set of rules defining how a Java program is written and interpreted.
The syntax is mostly derived from C and C++. Unlike in C++, in Java there are no global functions or variables, but there are data members ...
* JavaScript syntax
The syntax of JavaScript is the set of rules that define a correctly structured JavaScript program.
The examples below make use of the log function of the console object present in most browsers for standard text output.
The JavaScript stand ...
* Python syntax and semantics
The syntax of the Python programming language is the set of rules that defines how a Python program will be written and interpreted (by both the runtime system and by human readers). The Python language has many similarities to Perl, C, and Ja ...
* Lua syntax
Lua ( ; from meaning ''moon'') is a lightweight, high-level, multi-paradigm programming language designed primarily for embedded use in applications. Lua is cross-platform, since the interpreter of compiled bytecode is written in ANSI C, an ...
* Haskell syntax
This article describes the features in Haskell (programming language), Haskell.
Examples
Factorial
A simple example that is often used to demonstrate the syntax of functional languages is the factorial function for non-negative integers, show ...
References
{{Reflist
External links
* Various syntactic constructs used i
computer programming languages
*Python error “ImportError: No module named” Why? How? Command-Line
[Solved2021
/nowiki>">olved2021">[Solved2021
/nowiki>
Programming_language_syntax.html" ;"title="olved2021
/nowiki>.html" ;"title="olved2021">[Solved2021
/nowiki>">olved2021">[Solved2021
/nowiki>
Programming language syntax">
Programming language topics
Source code