Misplaced Pages

#100899

80-443: Over time, many extensions and variants of the original Backus–Naur notation have been created; some are exactly defined, including extended Backus–Naur form (EBNF) and augmented Backus–Naur form (ABNF). BNFs describe how to combine different symbols to produce a syntactically correct sequence. BNFs consist of three components: a set of non-terminal symbols, a set of terminal symbols, and rules for replacing non-terminal symbols with

160-528: A <term> followed by a sequence <addop> <term> . A class is an abstraction; we can talk about it independent of its formation. We can talk about term, independent of its definition, as being added or subtracted in expr. We can talk about a term being a specific data type and how an expr is to be evaluated having specific combinations of data types, or even reordering an expression to group data types and evaluation results of mixed types. The natural-language supplement provided specific details of

240-406: A b c ′ {\displaystyle abc'} is numbered 110 2  = 6 10 and denoted m 6 {\displaystyle m_{6}} . Given the truth table of a logical function, it is possible to write the function as a "sum of products" or "sum of minterms". This is a special form of disjunctive normal form . For example, if given the truth table for

320-437: A Karnaugh map . The Quine–McCluskey algorithm can solve slightly larger problems. The field of logic optimization developed from the problem of finding optimal implementations of Boolean functions, such as minimal PoS and SoP forms. The sample truth tables for minterms and maxterms above are sufficient to establish the canonical form for a single bit position in the addition of binary numbers, but are not sufficient to design

400-612: A context-free grammar . EBNF is used to make a formal description of a formal language such as a computer programming language . They are extensions of the basic Backus–Naur form (BNF) metasyntax notation. The earliest EBNF was developed by Niklaus Wirth , incorporating some of the concepts (with a different syntax and notation) from Wirth syntax notation . Today, many variants of EBNF are in use. The International Organization for Standardization adopted an EBNF Standard , ISO/IEC 14977, in 1996. According to Zaytsev, however, this standard "only ended up adding yet another three dialects to

480-409: A minterm is a product term in which each of the n {\displaystyle n} variables appears exactly once (either in its complemented or uncomplemented form). Thus, a minterm is a logical expression of n variables that employs only the complement operator and the conjunction operator ( logical AND ). A minterm gives a true value for just one combination of the input variables,

560-412: A nonterminal : This production rule defines the nonterminal digit which is on the left side of the assignment. The vertical bar represents an alternative and the terminal symbols are enclosed with quotation marks followed by a semicolon as terminating character. Hence a digit is a 0 or a digit excluding zero that can be 1 or 2 or 3 and so forth until 9 . A production rule can also include

640-411: A 1-input NOR, is slower but for any word length the design only pays that penalty once (when the leftmost sum digit is developed). That's because those calculations overlap, each in what amounts to its own little pipeline without affecting when the next bit position's sum bit can be calculated. And, to be sure, the co ′ out of the leftmost bit position will probably have to be complemented as part of

720-421: A 4-input NOR gate we need to restate it as a product of sums (PoS), where the sums are the opposite maxterms. That is, In the maxterm example above, we wrote c o ( c i , x , y ) = M 0 M 1 M 2 M 4 {\displaystyle co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}} but to perform this with a 4-input NOR gate we need to notice

800-563: A drawback when trying to implement a function in canonical form, but there is a compensating bonus: such a gate with only one input implements the complementing function, which is required frequently in digital logic. This example assumes the Apollo parts inventory: 3-input NOR gates only, but the discussion is simplified by supposing that 4-input NOR gates are also available (in Apollo, those were compounded out of pairs of 3-input NORs). A set of 8 NOR gates, if their inputs are all combinations of

880-498: A few years later in IBM 's PL/I definition), the notation is now universally recognised. Augmented Backus–Naur form (ABNF) and Routing Backus–Naur form (RBNF) are extensions commonly used to describe Internet Engineering Task Force (IETF) protocols . Parsing expression grammars build on the BNF and regular expression notations to form an alternative class of formal grammar , which

SECTION 10

#1732775859101

960-407: A major difference between the BNF metalanguage and a Chomsky context-free grammar. Metalinguistic variables do not require a rule defining their formation. Their formation may simply be described in natural language within the <> brackets. The following ALGOL 60 report section 2.3 comments specification, exemplifies how this works: For the purpose of including text among the symbols of a program

1040-423: A metalanguage for talking about ALGOL. An example of its use as a metalanguage would be in defining an arithmetic expression: The first symbol of an alternative may be the class being defined, the repetition, as explained by Naur, having the function of specifying that the alternative sequence can recursively begin with a previous alternative and can be repeated any number of times. For example, above <expr>

1120-482: A primary goal of minimizing the number of gates, and/or of minimizing the fanouts of signals to other gates since big fanouts reduce resilience to a degraded power supply or other environmental factors. In such a case, a designer may develop the canonical-form design as a baseline, then try a bottom-up development, and finally compare the results. The bottom-up development involves noticing that u = ci XOR ( x XOR y ), where XOR means eXclusive OR [true when either input

1200-407: A problem is the duality of minterms and maxterms, i.e. each maxterm is the complement of the like-indexed minterm, and vice versa. In the minterm example above, we wrote u ( c i , x , y ) = m 1 + m 2 + m 4 + m 7 {\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}} but to perform this with

1280-605: A proposed ISO/IEC 14977 standard, by R. S. Scowen, page 7, tables 1 and 2. Even EBNF can be described using EBNF. Consider below grammar (using conventions such as "-" to indicate set disjunction, "+" to indicate one or more matches, and "?" for optionality): A Pascal -like programming language that allows only assignments can be defined in EBNF as follows: For example, a syntactically correct program then could be: The language can easily be extended with control flows , arithmetical expressions, and Input/Output instructions. Then

1360-418: A rule in one line, whereas in EBNF a terminating character, the semicolon character “ ; ” marks the end of a rule. Furthermore, EBNF includes mechanisms for enhancements, defining the number of repetitions, excluding alternatives, comments, etc. As examples, the following syntax rules illustrate the facilities for expressing repetition: Terminal strings defined by these rules are as follows: According to

1440-426: A sequence of symbols. These so-called "derivation rules" are written as where: All syntactically correct sequences must be generated in the following manner: Applying rules in this manner can produce longer and longer sequences, so many BNF definitions allow for a special "delete" symbol to be included in the specification. We can specify a rule that allows us to replace some symbols with this "delete" symbol, which

1520-467: A sequence of terminals or nonterminals, each separated by a comma: Expressions that may be omitted or repeated can be represented through curly braces { ... }: In this case, the strings 1 , 2 , ..., 10 , ..., 10000 , ... are correct expressions. To represent this, everything that is set within the curly braces may be repeated arbitrarily often, including not at all. An option can be represented through squared brackets [ ... ]. That is, everything that

1600-399: A similar manner, a canonical maxterm form can be reduced to various minimal PoS forms. While this example was simplified by applying normal algebraic methods [ f = ( a ′ + a ) b c {\displaystyle f=(a'+a)bc} ], in less obvious cases a convenient method for finding minimal PoS/SoP forms of a function with up to four variables is using

1680-522: A small, usable programming language would be developed. Any grammar defined in EBNF can also be represented in BNF, though representations in the latter are generally lengthier. E.g., options and repetitions cannot be directly expressed in BNF and require the use of an intermediate rule or alternative production defined to be either nothing or the optional production for option, or either the repeated production of itself, recursively, for repetition. The same constructs can still be used in EBNF. The BNF uses

SECTION 20

#1732775859101

1760-632: A subject for teaching, rather than scientific study; descriptions were informal and targeted at practical usage. In the first half of the 20th century, linguists such as Leonard Bloomfield and Zellig Harris started attempts to formalize the description of language, including phrase structure . Meanwhile, string rewriting rules as formal logical systems were introduced and studied by mathematicians such as Axel Thue (in 1914), Emil Post (1920s–40s) and Alan Turing (1936). Noam Chomsky , teaching linguistics to students of information theory at MIT , combined linguistics and mathematics by taking what

1840-481: Is "not a normal form in the conventional sense", unlike, for instance, Chomsky normal form . The name Pāṇini Backus form was also once suggested in view of the fact that the expansion Backus normal form may not be accurate, and that Pāṇini had independently developed a similar notation earlier. BNF is described by Peter Naur in the ALGOL 60 report as metalinguistic formula : Sequences of characters enclosed in

1920-441: Is a code that expresses the syntax of a formal language. An EBNF consists of terminal symbols and non-terminal production rules which are the restrictions governing how terminal symbols can be combined into a valid sequence. Examples of terminal symbols include alphanumeric characters , punctuation marks , and whitespace characters . The EBNF defines production rules where sequences of symbols are respectively assigned to

2000-414: Is a pair of gates cross-coupled to make a flip-flop: the output of each is wired as one of the inputs to the other.) There is also no need to create the complement form of the sum u . However, the carry out of one bit position must be passed as the carry into the next bit position in both direct and complement forms. The most straightforward way to do this is to pass co through a 1-input NOR gate and label

2080-412: Is a rule; for example one rule begins with <name-part> ::= . The other part of that rule (aside from a line-end) is an expression, which consists of two lists separated by a vertical bar | . These two lists consists of some terms (three terms and two terms, respectively). Each term in this particular rule is a rule-name. There are many variants and extensions of BNF, generally either for

2160-617: Is defined as a <term> followed by any number of <addop> <term> . In some later metalanguages, such as Schorre's META II , the BNF recursive repeat construct is replaced by a sequence operator and target language symbols defined using quoted strings. The < and > brackets were removed. Parentheses ( ) for mathematical grouping were added. The <expr> rule would appear in META II as These changes enabled META II and its derivative programming languages to define and extend their own metalanguage, at

2240-511: Is equivalent to a smaller SoP form. This smaller form would still consist of a sum of product terms, but have fewer product terms and/or product terms that contain fewer variables. For example, the following 3-variable function: has the canonical minterm representation f = a ′ b c + a b c {\displaystyle f=a'bc+abc} , but it has an equivalent SoP form f = b c {\displaystyle f=bc} . In this trivial example, it

2320-416: Is essentially analytic rather than generative in character. Many BNF specifications found online today are intended to be human-readable and are non-formal. These often include many of the following syntax rules and extensions: Extended Backus%E2%80%93Naur form In computer science , extended Backus–Naur form ( EBNF ) is a family of metasyntax notations, any of which can be used to express

2400-455: Is essentially Thue's formalism as the basis for the description of the syntax of natural language . He also introduced a clear distinction between generative rules (those of context-free grammars ) and transformation rules (1956). John Backus , a programming language designer at IBM , proposed a metalanguage of "metalinguistic formulas" to describe the syntax of the new programming language IAL, known today as ALGOL 58 (1959). His notation

2480-425: Is given a truth table of a logical function, it is possible to write the function as a "product of sums" or "product of maxterms". This is a special form of conjunctive normal form . For example, if given the truth table for the carry-out bit co of one bit position's logic of an adder circuit, as a function of x and y from the addends and the carry in, ci : Observing that the rows that have an output of 0 are

Backus–Naur form - Misplaced Pages Continue

2560-471: Is interpreted as "or". The metasymbols < > are delimiters enclosing a class name. BNF is described as a metalanguage for talking about ALGOL by Peter Naur and Saul Rosen . In 1947 Saul Rosen became involved in the activities of the fledgling Association for Computing Machinery , first on the languages committee that became the IAL group and eventually led to ALGOL. He was the first managing editor of

2640-460: Is made into an AND gate by passing each of its inputs through a 1-input NOR gate. However, this approach not only increases the number of gates used, but also doubles the number of gate delays processing the signals, cutting the processing speed in half. Consequently, whenever performance is vital, going beyond canonical forms and doing the Boolean algebra to make the unenhanced NOR gates do the job

2720-451: Is meant to indicate that we can remove the symbols from our sequence and still have a syntactically correct sequence. As an example, consider this possible BNF for a U.S. postal address : This translates into English as: Note that many things (such as the format of a first-name, apartment number, ZIP-code, and Roman numeral) are left unspecified here. If necessary, they may be described using additional BNF rules. The idea of describing

2800-415: Is most commonly used as a parser generator , and its roots are obviously BNF. BNF today is one of the oldest computer-related languages still in use. BNF's syntax itself may be represented with a BNF like the following: Note that "" is the empty string . The original BNF did not use quotes as shown in <literal> rule. This assumes that no whitespace is necessary for proper interpretation of

2880-450: Is obvious that b c = a ′ b c + a b c {\displaystyle bc=a'bc+abc} , and the smaller form has both fewer product terms and fewer variables within each term. The minimal SoP representations of a function according to this notion of "smallest" are referred to as minimal SoP forms . In general, there may be multiple minimal SoP forms, none clearly smaller or larger than another. In

2960-507: Is of great importance in the optimization of Boolean formulas in general and digital circuits in particular. Other canonical forms include the complete sum of prime implicants or Blake canonical form (and its dual), and the algebraic normal form (also called Zhegalkin or Reed–Muller). For a boolean function of n {\displaystyle n} variables x 1 , … , x n {\displaystyle {x_{1},\dots ,x_{n}}} ,

3040-407: Is set within the square brackets may be present just once, or not at all: Therefore, an integer is a zero ( 0 ) or a natural number that may be preceded by an optional minus sign . EBNF also provides, among other things, the syntax to describe repetitions (of a specified number of times), to exclude some part of a production, and to insert comments in an EBNF grammar. The following represents

3120-521: Is tabulated as: The description of the bottom-up development mentions co ′ as an output but not co . Does that design simply never need the direct form of the carry out? Well, yes and no. At each stage, the calculation of co ′ depends only on ci ′, x ′ and y ′, which means that the carry propagation ripples along the bit positions just as fast as in the canonical design without ever developing co . The calculation of u , which does require ci to be made from ci ′ by

3200-419: Is the respective maxterm. That is, each maxterm is assigned an index based on the opposite conventional binary encoding used for minterms. The maxterm convention assigns the value 0 to the direct form ( x i ) {\displaystyle (x_{i})} and 1 to the complemented form ( x i ′ ) {\displaystyle (x'_{i})} . For example, we assign

3280-426: Is true but not when both are true], and that co = ci x + x y + y ci . One such development takes twelve NOR gates in all: six 2-input gates and two 1-input gates to produce u in 5 gate delays, plus three 2-input gates and one 3-input gate to produce co ′ in 2 gate delays. The canonical baseline took eight 3-input NOR gates plus three 4-input NOR gates to produce u, co and co ′ in 2 gate delays. If

Backus–Naur form - Misplaced Pages Continue

3360-448: Is using the fact that parentheses in EBNF cannot be placed next to identifiers (they must be concatenated with them). The following is valid EBNF: The following is not valid EBNF: Therefore, an extension of EBNF could use that notation. For example, in a Lisp grammar, function application could be defined by the following rule: Canonical form (Boolean algebra) In Boolean algebra , any Boolean function can be expressed in

3440-509: Is well worthwhile. We have now seen how the minterm/maxterm tools can be used to design an adder stage in canonical form with the addition of some Boolean algebra, costing just 2 gate delays for each of the outputs. That's the "top-down" way to design the digital circuit for this function, but is it the best way? The discussion has focused on identifying "fastest" as "best," and the augmented canonical form meets that criterion flawlessly, but sometimes other factors predominate. The designer may have

3520-410: The canonical disjunctive normal form ( CDNF ), minterm canonical form , or Sum of Products ( SoP or SOP ) as a disjunction (OR) of minterms. The De Morgan dual is the canonical conjunctive normal form ( CCNF ), maxterm canonical form , or Product of Sums ( PoS or POS ) which is a conjunction (AND) of maxterms. These forms can be useful for the simplification of Boolean functions, which

3600-507: The 1 "true" value, a NOR gate is the simplest possible useful logical element. Specifically, a 3-input NOR gate may consist of 3 bipolar junction transistors with their emitters all grounded, their collectors tied together and linked to V cc through a load impedance. Each base is connected to an input signal, and the common collector point presents the output signal. Any input that is a 1 (high voltage) to its base shorts its transistor's emitter to its collector, causing current to flow through

3680-421: The 1st, 2nd, 3rd, and 5th, we can write co as a product of maxterms M 0 , M 1 , M 2 {\displaystyle M_{0},M_{1},M_{2}} and M 4 {\displaystyle M_{4}} . If we wish to verify this: evaluated for all 8 combinations of the three variables will match the table. It is often the case that the canonical minterm form

3760-407: The BNF metalanguage by explaining that the digit sequence can have no white space between the digits. English is only one of the possible natural languages. Translations of the ALGOL reports were available in many natural languages. The origin of BNF is not as important as its impact on programming language development. During the period immediately following the publication of the ALGOL 60 report BNF

3840-515: The Communications of the ACM. BNF was first used as a metalanguage to talk about the ALGOL language in the ALGOL 60 report. That is how it is explained in ALGOL programming course material developed by Peter Naur in 1962. Early ALGOL manuals by IBM, Honeywell, Burroughs and Digital Equipment Corporation followed the ALGOL 60 report using it as a metalanguage. Saul Rosen in his book describes BNF as

3920-458: The ISO 14977 standard EBNF is meant to be extensible, and two facilities are mentioned. The first is part of EBNF grammar, the special sequence, which is arbitrary text enclosed with question marks. The interpretation of the text inside a special sequence is beyond the scope of the EBNF standard. For example, the space character could be defined by the following rule: The second facility for extension

4000-1052: The arithmetic sum bit u of one bit position's logic of an adder circuit, as a function of x and y from the addends and the carry in, ci : Observing that the rows that have an output of 1 are the 2nd, 3rd, 5th, and 8th, we can write u as a sum of minterms m 1 , m 2 , m 4 , {\displaystyle m_{1},m_{2},m_{4},} and m 7 {\displaystyle m_{7}} . If we wish to verify this: u ( c i , x , y ) = m 1 + m 2 + m 4 + m 7 = ( c i ′ , x ′ , y ) + ( c i ′ , x , y ′ ) + ( c i , x ′ , y ′ ) + ( c i , x , y ) {\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}=(ci',x',y)+(ci',x,y')+(ci,x',y')+(ci,x,y)} evaluated for all 8 combinations of

4080-426: The brackets <> represent metalinguistic variables whose values are sequences of symbols. The marks "::=" and "|" (the latter with the meaning of "or") are metalinguistic connectives. Any mark in a formula, which is not a variable or a connective, denotes itself. Juxtaposition of marks or variables in a formula signifies juxtaposition of the sequence denoted. Another example from the ALGOL 60 report illustrates

SECTION 50

#1732775859101

4160-616: The chaos" and, after noting its lack of success, also notes that the ISO EBNF is not even used in all ISO standards. Wheeler argues against using the ISO standard when using an EBNF and recommends considering alternative EBNF notations such as the one from the W3C Extensible Markup Language (XML) 1.0 (Fifth Edition). This article uses EBNF as specified by the ISO for examples applying to all EBNFs. Other EBNF variants use somewhat different syntactic conventions. EBNF

4240-453: The circuit inventory actually includes 4-input NOR gates, the top-down canonical design looks like a winner in both gate count and speed. But if (contrary to our convenient supposition) the circuits are actually 3-input NOR gates, of which two are required for each 4-input NOR function, then the canonical design takes 14 gates compared to 12 for the bottom-up approach, but still produces the sum digit u considerably faster. The fanout comparison

4320-428: The complement operator and the disjunction operator ( logical OR ). Maxterms are a dual of the minterm idea, following the complementary symmetry of De Morgan's laws . Instead of using ANDs and complements, we use ORs and complements and proceed similarly. It is apparent that a maxterm gives a false value for just one combination of the input variables, i.e. it is true at the maximal number of possibilities. For example,

4400-622: The complementation pattern of the variables, where the variables are written in a standard order, usually alphabetical. This convention assigns the value 1 to the direct form ( x i {\displaystyle x_{i}} ) and 0 to the complemented form ( x i ′ {\displaystyle x'_{i}} ); the minterm is then ∑ i = 1 n 2 i − 1 value ⁡ ( x i ) {\displaystyle \sum \limits _{i=1}^{n}2^{i-1}\operatorname {value} (x_{i})} . For example, minterm

4480-405: The cost of the ability to use a natural language description, metalinguistic variable, language construct description. Many spin-off metalanguages were inspired by BNF. See META II , TREE-META , and Metacompiler . A BNF class describes a language construct formation, with formation defined as a pattern or the action of forming the pattern. The class name expr is described in a natural language as

4560-534: The digital logic unless your inventory of gates includes AND and OR. Where performance is an issue (as in the Apollo Guidance Computer), the available parts are more likely to be NAND and NOR because of the complementing action inherent in transistor logic. The values are defined as voltage states, one near ground and one near the DC supply voltage V cc , e.g. +5 VDC. If the higher voltage is defined as

4640-449: The direct and complement forms of the 3 input variables ci, x, and y , always produce minterms, never maxterms—that is, of the 8 gates required to process all combinations of 3 input variables, only one has the output value 1. That's because a NOR gate, despite its name, could better be viewed (using De Morgan's law) as the AND of the complements of its input signals. The reason this is not

4720-574: The equality to the NOR of the same minterms. That is, One might suppose that the work of designing an adder stage is now complete, but we haven't addressed the fact that all 3 of the input variables have to appear in both their direct and complement forms. There's no difficulty about the addends x and y in this respect, because they are static throughout the addition and thus are normally held in latch circuits that routinely have both direct and complement outputs. (The simplest latch circuit made of NOR gates

4800-419: The following "comment" conventions hold: Equivalence here means that any of the three structures shown in the left column may be replaced, in any occurrence outside of strings, by the symbol shown in the same line in the right column without any effect on the action of the program. Naur changed two of Backus's symbols to commonly available characters. The ::= symbol was originally a :≡ . The | symbol

4880-475: The index 6 to the maxterm a ′ + b ′ + c {\displaystyle a'+b'+c} (110) and denote that maxterm as M 6 . The complement ( a ′ + b ′ + c ) ′ {\displaystyle (a'+b'+c)'} is the minterm a b c ′ = m 6 {\displaystyle abc'=m_{6}} , using de Morgan's law . If one

SECTION 60

#1732775859101

4960-430: The interested reader, assisted by one more algebraic formula: u = ci ( x XOR y ) + ci ′( x XOR y )′]′. Decoupling the carry propagation from the sum formation in this way is what elevates the performance of a carry-lookahead adder over that of a ripple carry adder . One application of Boolean algebra is digital circuit design, with one goal to minimize the number of gates and another to minimize

5040-428: The language class semantics to be used by a compiler implementation and a programmer writing an ALGOL program. Natural-language description further supplemented the syntax as well. The integer rule is a good example of natural and metalanguage used to describe syntax: There are no specifics on white space in the above. As far as the rule states, we could have space between the digits. In the natural language we complement

5120-483: The load impedance, which brings the collector voltage (the output) very near to ground. That result is independent of the other inputs. Only when all 3 input signals are 0 (low voltage) do the emitter-collector impedances of all 3 transistors remain very high. Then very little current flows, and the voltage-divider effect with the load impedance imposes on the collector point a high voltage very near to V cc . The complementing property of these gate circuits may seem like

5200-411: The logic determining whether the addition overflowed. But using 3-input NOR gates, the bottom-up design is very nearly as fast for doing parallel addition on a non-trivial word length, cuts down on the gate count, and uses lower fanouts ... so it wins if gate count and/or fanout are paramount! We'll leave the exact circuitry of the bottom-up design of which all these statements are true as an exercise for

5280-400: The maxterm a ′ + b + c ′ is false only when a and c both are true and b is false—the input arrangement where a = 1, b = 0, c = 1 results in 0. There are again 2 maxterms of n variables, since a variable in the maxterm expression can also be in either its direct or its complemented form—two choices per variable. The numbering is chosen so that the complement of a minterm

5360-402: The minimum nontrivial amount. For example, a b ' c , is true only when a and c both are true and b is false—the input arrangement where a = 1, b = 0, c = 1 results in 1. There are 2 minterms of n variables, since a variable in the minterm expression can be in either its direct or its complemented form—two choices per variable. Minterms are often numbered by a binary encoding of

5440-422: The minterm m 7 {\displaystyle m_{7}} , and the gate that generated it could have been eliminated. Nevertheless, it is still a good trade. Now we could have implemented those functions exactly according to their SoP and PoS canonical forms, by turning NOR gates into the functions specified. A NOR gate is made into an OR gate by passing its output through a 1-input NOR gate; and it

5520-489: The output co ′, but that would add a gate delay in the worst possible place, slowing down the rippling of carries from right to left. An additional 4-input NOR gate building the canonical form of co ′ (out of the opposite minterms as co ) solves this problem. The trade-off to maintain full speed in this way includes an unexpected cost (in addition to having to use a bigger gate). If we'd just used that 1-input gate to complement co , there would have been no use for

5600-475: The rule. <EOL> represents the appropriate line-end specifier (in ASCII , carriage-return, line-feed or both depending on the operating system ). <rule-name> and <text> are to be substituted with a declared rule's name/label or literal text, respectively. In the U.S. postal address example above, the entire block-quote is a <syntax> . Each line or unbroken grouping of lines

5680-408: The sake of simplicity and succinctness, or to adapt it to a specific application. One common feature of many variants is the use of regular expression repetition operators such as * and + . The extended Backus–Naur form (EBNF) is a common one. Another common extension is the use of square brackets around optional items. Although not present in the original ALGOL 60 report (instead introduced

5760-402: The settling time. There are sixteen possible functions of two variables, but in digital logic hardware, the simplest gate circuits implement only four of them: conjunction (AND), disjunction (inclusive OR), and the respective complements of those (NAND and NOR). Most gate circuits accept more than 2 input variables; for example, the spaceborne Apollo Guidance Computer , which pioneered

5840-463: The structure of language using rewriting rules can be traced back to at least the work of Pāṇini , an ancient Indian Sanskrit grammarian and a revered scholar in Hinduism who lived sometime between the 6th and 4th century BC . His notation to describe Sanskrit word structure is equivalent in power to that of Backus and has many similar properties. In Western society, grammar was long regarded as

5920-440: The symbols ( < , > , | , ::= ) for itself, but does not include quotes around terminal strings. This prevents these characters from being used in the languages, and requires a special symbol for the empty string. In EBNF, terminals are strictly enclosed within quotation marks ( " ... " or ' ... ' ). The angle brackets (" < ... > ") for nonterminals can be omitted. BNF syntax can only represent

6000-445: The target language. Arithmetic-like grouping provided a simplification that removed using classes where grouping was its only value. The META II arithmetic expression rule shows grouping use. Output expressions placed in a META II rule are used to output code and labels in an assembly language. Rules in META II are equivalent to a class definitions in BNF. The Unix utility yacc is based on BNF with code production similar to META II. yacc

6080-423: The three variables will match the table. For a boolean function of n variables x 1 , … , x n {\displaystyle {x_{1},\dots ,x_{n}}} , a maxterm is a sum term in which each of the n variables appears exactly once (either in its complemented or uncomplemented form). Thus, a maxterm is a logical expression of n variables that employs only

6160-546: Was first used in the ALGOL 60 report. BNF is a notation for Chomsky's context-free grammars. Backus was familiar with Chomsky's work. As proposed by Backus, the formula defined "classes" whose names are enclosed in angle brackets. For example, <ab> . Each of these names denotes a class of basic symbols. Further development of ALGOL led to ALGOL 60 . In the committee's 1963 report, Peter Naur called Backus's notation Backus normal form . Donald Knuth argued that BNF should rather be read as Backus–Naur form , as it

6240-431: Was not originally used in describing BNF. Naur later described them as classes in ALGOL course materials. In the ALGOL 60 report they were called metalinguistic variables. Anything other than the metasymbols ::= , | , and class names enclosed in < > are symbols of the language being defined. The metasymbol ::= is to be interpreted as "is defined as". The | is used to separate alternative definitions and

6320-503: Was originally the word " or " (with a bar over it). BNF is very similar to canonical-form Boolean algebra equations that are, and were at the time, used in logic-circuit design. Backus was a mathematician and the designer of the FORTRAN programming language. Studies of Boolean algebra is commonly part of a mathematics curriculum. Neither Backus nor Naur described the names enclosed in < > as non-terminals. Chomsky's terminology

6400-524: Was the basis of many compiler-compiler systems. Some, like "A Syntax Directed Compiler for ALGOL 60" developed by Edgar T. Irons and "A Compiler Building System" Developed by Brooker and Morris, directly used BNF. Others, like the Schorre Metacompilers, made it into a programming language with only a few changes. <class name> became symbol identifiers, dropping the enclosing < , > and using quoted strings for symbols of

#100899