Editing Computer program (section)

===Syntax and semantics===
[[File:Terminal and non-terminal symbols example.png|300px|thumb|right|Production rules consist of a set of terminals and non-terminals.]]

The [[Syntax (programming languages)|syntax]] of a ''computer program'' is a [[list]] of [[Production (computer science)|production rules]] which form its [[formal grammar|grammar]].<ref name="cpl_3rd-ch12-290_quote">{{cite book
  | last = Wilson
  | first = Leslie B.
  | title = Comparative Programming Languages, Third Edition
  | publisher = Addison-Wesley
  | year = 2001
  | page = 290
  | quote = The syntax (or grammar) of a programming language describes the correct form in which programs may be written[.]
  | isbn = 0-201-71012-9
}}</ref> A programming language's grammar correctly places its [[Declaration (computer programming)|declarations]], [[Expression (computer science)|expressions]], and [[Statement (computer science)|statements]].<ref name="cpl_3rd-ch4-78_quote1">{{cite book
  | last = Wilson
  | first = Leslie B.
  | title = Comparative Programming Languages, Third Edition
  | publisher = Addison-Wesley
  | year = 2001
  | page = 78
  | isbn = 0-201-71012-9
  | quote = The main components of an imperative language are declarations, expressions, and statements.
}}</ref> Complementing the ''syntax'' of a language are its [[Semantics (computer science)|semantics]]. The ''semantics'' describe the meanings attached to various syntactic constructs.<ref name="cpl_3rd-ch12-290">{{cite book
  | last = Wilson
  | first = Leslie B.
  | title = Comparative Programming Languages, Third Edition
  | publisher = Addison-Wesley
  | year = 2001
  | page = 290
  | isbn = 0-201-71012-9
}}</ref> A syntactic construct may need a semantic description because a production rule may have an invalid interpretation.<ref name="cpl_3rd-ch12-294">{{cite book
  | last = Wilson
  | first = Leslie B.
  | title = Comparative Programming Languages, Third Edition
  | publisher = Addison-Wesley
  | year = 2001
  | page = 294
  | isbn = 0-201-71012-9
}}</ref> Also, different languages might have the same syntax; however, their behaviors may be different.

The syntax of a language is formally described by listing the production rules. Whereas the syntax of a [[natural language]] is extremely complicated, a subset of the English language can have this production rule listing:<ref name="discrete-ch10-p615">{{cite book
  | last = Rosen
  | first = Kenneth H.
  | title = Discrete Mathematics and Its Applications
  | publisher = McGraw-Hill, Inc.
  | year = 1991
  | page = [https://archive.org/details/discretemathemat00rose/page/615 615]
  | isbn = 978-0-07-053744-6
  | url = https://archive.org/details/discretemathemat00rose/page/615}}</ref>
# a '''sentence''' is made up of a '''noun-phrase''' followed by a '''verb-phrase''';
# a '''noun-phrase''' is made up of an '''article''' followed by an '''adjective''' followed by a '''noun''';
# a '''verb-phrase''' is made up of a '''verb''' followed by a '''noun-phrase''';
# an '''article''' is 'the';
# an '''adjective''' is 'big' or
# an '''adjective''' is 'small';
# a '''noun''' is 'cat' or
# a '''noun''' is 'mouse';
# a '''verb''' is 'eats';
The words in '''bold-face''' are known as ''non-terminals''. The words in 'single quotes' are known as ''terminals''.<ref name="cpl_3rd-ch12-291">{{cite book
  | last = Wilson
  | first = Leslie B.
  | title = Comparative Programming Languages, Third Edition
  | publisher = Addison-Wesley
  | year = 2001
  | page = 291
  | isbn = 0-201-71012-9
}}</ref>

From this production rule listing, complete sentences may be formed using a series of replacements.<ref name="discrete-ch10-p616">{{cite book
  | last = Rosen
  | first = Kenneth H.
  | title = Discrete Mathematics and Its Applications
  | publisher = McGraw-Hill, Inc.
  | year = 1991
  | page = [https://archive.org/details/discretemathemat00rose/page/616 616]
  | isbn = 978-0-07-053744-6
  | url = https://archive.org/details/discretemathemat00rose/page/616}}</ref> The process is to replace ''non-terminals'' with either a valid ''non-terminal'' or a valid ''terminal''. The replacement process repeats until only ''terminals'' remain. One valid sentence is:
* '''sentence'''
* '''noun-phrase''' '''verb-phrase'''
* '''article''' '''adjective''' '''noun''' '''verb-phrase'''
* ''the'' '''adjective''' '''noun''' '''verb-phrase'''
* ''the'' ''big'' '''noun''' '''verb-phrase'''
* ''the'' ''big'' ''cat'' '''verb-phrase'''
* ''the'' ''big'' ''cat'' '''verb''' '''noun-phrase'''
* ''the'' ''big'' ''cat'' ''eats'' '''noun-phrase'''
* ''the'' ''big'' ''cat'' ''eats'' '''article''' '''adjective''' '''noun'''
* ''the'' ''big'' ''cat'' ''eats'' ''the'' '''adjective''' '''noun'''
* ''the'' ''big'' ''cat'' ''eats'' ''the'' ''small'' '''noun'''
* ''the'' ''big'' ''cat'' ''eats'' ''the'' ''small'' ''mouse''

However, another combination results in an invalid sentence:
* ''the'' ''small'' ''mouse'' ''eats'' ''the'' ''big'' ''cat''
Therefore, a ''semantic'' is necessary to correctly describe the meaning of an ''eat'' activity.

One ''production rule'' listing method is called the [[Backus–Naur form]] (BNF).<ref name="discrete-ch10-p623">{{cite book
  | last = Rosen
  | first = Kenneth H.
  | title = Discrete Mathematics and Its Applications
  | publisher = McGraw-Hill, Inc.
  | year = 1991
  | page = [https://archive.org/details/discretemathemat00rose/page/623 623]
  | isbn = 978-0-07-053744-6
  | url = https://archive.org/details/discretemathemat00rose/page/623}}</ref> BNF describes the syntax of a language and itself has a ''syntax''. This recursive definition is an example of a [[metalanguage]].<ref name="cpl_3rd-ch12-290"/> The ''syntax'' of BNF includes:
* <code>::=</code> which translates to ''is made up of a[n]'' when a non-terminal is to its right. It translates to ''is'' when a terminal is to its right.
* <code>|</code> which translates to ''or''.
* <code><</code> and <code>></code> which surround '''non-terminals'''.

Using BNF, a subset of the English language can have this ''production rule'' listing:
<syntaxhighlight lang="bnf">
<sentence> ::= <noun-phrase><verb-phrase>
<noun-phrase> ::= <article><adjective><noun>
<verb-phrase> ::= <verb><noun-phrase>
<article> ::= the
<adjective> ::= big | small
<noun> ::= cat | mouse
<verb> ::= eats
</syntaxhighlight>

Using BNF, a signed-[[Integer (computer science)|integer]] has the ''production rule'' listing:<ref name="discrete-ch10-p624">{{cite book
  | last = Rosen
  | first = Kenneth H.
  | title = Discrete Mathematics and Its Applications
  | publisher = McGraw-Hill, Inc.
  | year = 1991
  | page = [https://archive.org/details/discretemathemat00rose/page/624 624]
  | isbn = 978-0-07-053744-6
  | url = https://archive.org/details/discretemathemat00rose/page/624}}</ref>
<syntaxhighlight lang="bnf">
<signed-integer> ::= <sign><integer>
<sign> ::= + | -
<integer> ::= <digit> | <digit><integer>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
</syntaxhighlight>

Notice the recursive production rule:
<syntaxhighlight lang="bnf">
<integer> ::= <digit> | <digit><integer>
</syntaxhighlight>
This allows for an infinite number of possibilities. Therefore, a ''semantic'' is necessary to describe a limitation of the number of digits.

Notice the leading zero possibility in the production rules:
<syntaxhighlight lang="bnf">
<integer> ::= <digit> | <digit><integer>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
</syntaxhighlight>
Therefore, a ''semantic'' is necessary to describe that leading zeros need to be ignored.

Two formal methods are available to describe ''semantics''. They are [[denotational semantics]] and [[axiomatic semantics]].<ref name="cpl_3rd-ch12-297">{{cite book
  | last = Wilson
  | first = Leslie B.
  | title = Comparative Programming Languages, Third Edition
  | publisher = Addison-Wesley
  | year = 2001
  | page = 297
  | isbn = 0-201-71012-9
}}</ref>