imported>RandFreeman: Adding local short description: "Formal way to describe formal languages", overriding Wikidata description "metasyntax, or formal way to describe formal languages"

2025-06-23T19:05:23Z

Adding local short description: "Formal way to describe formal languages", overriding Wikidata description "metasyntax, or formal way to describe formal languages"

New page

{{Short description|Formal way to describe formal languages}}
{{Use dmy dates|date=March 2023}}
'''Wirth syntax notation''' ('''WSN''') is a [[metasyntax]], that is, a formal way to describe [[formal language]]s. Originally proposed by [[Niklaus Wirth]] in 1977 as an alternative to [[Backus–Naur form]] (BNF). It has several advantages over BNF in that it contains an explicit iteration construct, and it avoids the use of an explicit symbol for the empty string (such as <nowiki><empty></nowiki> or ε).<ref>{{Cite journal |last=Wirth |first=Niklaus |date=November 1977 |title=What Can We Do about the Unnecessary Diversity of Notations for Syntax Definitions? |journal=[[Communications of the ACM]] |volume=20 |issue=11 |pages=822–823 |doi=10.1145/359863.359883 |s2cid=35182224 |doi-access=free |authorlink=Niklaus Wirth}}</ref>

WSN has been used in several [[International Organization for Standardization|international standards]], starting with [[ISO 10303-21]].<ref>{{Cite journal |date=24 January 2002 |title=ISO 10303-21, Industrial automation systems and integration — Product data representation and exchange — Part 21: Implementation methods: Clear text encoding of the exchange structure |url=http://www.iso.org/iso/search/extendedsearchstandards.htm?from_js=true&type=adv&displayResult=true&published=on&formKeyword=&title=on&description=on&formISO_number=10303&formPart_number=21&formDocument_type=ALL&formSupp_type=&formICS=&formStage_code=&repost=1&formDate_stage=0&formOther_date=&formCommittee=&formSub_committee=&formSubmit=Search |publisher=International Organization for Standardization}}{{dead link|date=September 2021}}</ref> It was also used to define the syntax of [[ISO 10303-11|EXPRESS]], the [[data modelling]] language of [[ISO 10303|STEP]].

== WSN defined in itself ==
<syntaxhighlight lang="ebnf">
SYNTAX = { PRODUCTION } .
PRODUCTION = IDENTIFIER "=" EXPRESSION "." .
EXPRESSION = TERM { "|" TERM } .
TERM = FACTOR { FACTOR } .
FACTOR = IDENTIFIER
| LITERAL
| "[" EXPRESSION "]"
| "(" EXPRESSION ")"
| "{" EXPRESSION "}" .
IDENTIFIER = letter { letter } .
LITERAL = """" character { character } """" .
</syntaxhighlight>
The equals sign indicates a production. The element on the left is defined to be the combination of elements on the right. A production is terminated by a full stop (period).
*Repetition is denoted by curly brackets, ''e.g.,'' '''<nowiki>{a}</nowiki>''' stands for '''ε | a | aa | aaa | ...'''.
*Optionality is expressed by square brackets, ''e.g.,'' '''<nowiki>[a]b</nowiki>''' stands for '''ab | b'''.
*Parentheses serve for groupings, ''e.g.,'' '''(a|b)c''' stands for '''ac | bc'''.

We take these concepts for granted today, but they
were novel and even controversial in 1977. Wirth later incorporated some
of the concepts (with a different syntax and notation) into [[extended Backus–Naur form]].

Notice that <code>letter</code> and <code>character</code> are left undefined. This is because numeric characters (digits 0 to 9) may be included in both definitions or excluded from one, depending on the language being defined, ''e.g.'':
<syntaxhighlight lang="ebnf">
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
upper-case = "A" | "B" | … | "Y" | "Z" .
lower-case = "a" | "b" | … | "y" | "z" .
letter = upper-case | lower-case .
</syntaxhighlight>
If <code>character</code> goes on to include <code>digit</code> and other printable [[ASCII]] characters, then it diverges even more from <code>letter</code>, which one can assume does not include the digit characters or any of the special (non-[[alphanumeric]]) characters.

== Another example ==
The syntax of BNF can be represented with WSN as follows, based on translating [[Backus–Naur form#Further examples|the BNF example of itself]]:
<syntaxhighlight lang="ebnf">
syntax = rule [ syntax ] .
rule = opt-whitespace "<" rule-name ">" opt-whitespace "::="
opt-whitespace expression line-end .
opt-whitespace = { " " } .
expression = list [ "|" expression ] .
line-end = opt-whitespace EOL | line-end line-end .
list = term [ opt-whitespace list ] .
term = literal | "<" rule-name ">" .
literal = """" text """" | "'" text "'" .
</syntaxhighlight>
This definition appears overcomplicated because the concept of "optional [[Whitespace (computer science)|whitespace]]" must be explicitly defined in BNF, but it is implicit in WSN. Even in this example, <code>text</code> is left undefined, but it is assumed to mean "<code>[[ASCII|ASCII-character]] { ASCII-character }</code>". (<code>EOL</code> is also left undefined.) Notice how the [[kludge#Computer science|kludge]] <code>"<" rule-name ">"</code> has been used twice because <code>text</code> was not explicitly defined.

One of the problems with BNF which this example illustrates is that by allowing both single-quote and double-quote characters to be used for a <code>literal</code>, there is an added potential for human error in attempting to create a machine-readable syntax. One of the concepts that migrated to later meta syntaxes was the idea that giving the user multiple choices made it harder to write parsers for grammars defined by the syntax, so computer languages in general have become more restrictive in how a ''quoted-literal'' is defined.

==Syntax diagram==
[[Syntax diagram]]:
[[File:Wirth-syntax-notation.png]]

==References==
{{Reflist}}

{{Metasyntax}}
{{Wirth}}

[[Category:Metalanguages]]

Wirth syntax notation - Revision history

imported>RandFreeman: Adding local short description: "Formal way to describe formal languages", overriding Wikidata description "metasyntax, or formal way to describe formal languages"