BNFMetalanguagesSlide 3BNF metasymbolsBNF uses recursionBNF Examples IBNF Examples IIBNF Examples IIIBNF Examples IVExtended BNFVariationsLimitations of BNFThe EndJan 14, 2019BNFMetalanguagesA metalanguage is a language used to talk about a language (usually a different one)We can use English as its own metalanguage (e.g. describing English grammar in English)We need a formal, precise means of describing the syntax of programming languagesFor decades, BNF has met that needOne of the irritating things about Java is that it has no official BNF definition—hence, it’s sometimes hard to tell what is legal syntaxIt is essential to distinguish between the metalanguage terms and the object language termsFor example, BNF uses the | symbol, as do many programming languages—so if we see a |, what is it?BNFBNF stands for either Backus-Naur Form or Backus Normal FormBNF is a metalanguage that is frequently used to describe the grammar of a programming languageBNF is formal and preciseBNF is essential in compiler constructionIf you know about “context-free grammars (CFGs),” BNF is one way of defining CFGsThere are many dialects of BNF in use, but……the differences are almost always minorBNF metasymbolsAnything enclosed in < > is a nonterminal that needs to be further expanded, e.g. <variable>That is, if you see <variable> in the description of a programming language, that means “a variable goes here”Symbols not enclosed in < > are terminals; they represent themselves, e.g. if, while, (That is, if you see while in the description of a programming language, that means “the actual word ‘while’ goes here”The symbol ::= means is defined asThe symbol | means or; it separates alternatives, for example, <addop> ::= + | -That is, if you see an <addop>, it means “either a ‘+’ or a ‘-’ goes here”BNF uses recursion<integer> ::= <digit> | <integer> <digit> or<integer> ::= <digit> | <digit> <integer>Many people find recursion confusing“Extended BNF” (which we’ll talk about shortly) allows repetition as well as recursionRepetition is often easier to implement (with a loop) than recursion, so Extended BNF has become popularBNF Examples I<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9This defines the metasymbol ‘<digit>’What it means is, “If the description of the syntax says ‘<digit>’, you need an actual digit in this location”<if statement> ::= if ( <condition> ) <statement> | if ( <condition> ) <statement> else <statement>The symbols if, (, ), and else are terminals—they stand for themselves <if statement>, <condition>, and <statement> are metasymbolsIf you see an <if statement>, you should replace it by either if (<condition>) <statement>or with if (<condition>) <statement> else <statement>Next, you need to replace <condition> and <statement> with their definitionsBNF Examples II <unsigned integer> ::= <digit> | <unsigned integer> <digit><integer> ::= <unsigned integer> | + <unsigned integer> | - <unsigned integer>BNF Examples III<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit><block> ::= { <statement list> }<statement list> ::= <statement> | <statement list> <statement>BNF Examples IV<statement> ::= <block> | <assignment statement> | <break statement> | <continue statement> | <do statement> | <for loop> | <goto statement> | <if statement> | . . .Extended BNFDialects differ, but the following are pretty standard:[ ] enclose an optional part of the ruleExample:<if statement> ::= if ( <condition> ) <statement> [ else <statement> ]{ } mean the enclosed can be repeated any number of times (including zero)Example:<parameter list> ::= ( ) | ( { <parameter> , } <parameter> )VariationsThe preceding notation is the original and most common notationBNF was designed before we had boldface, color, more than one font, etc.A typical modern variation might: Use boldface to indicate multi-character terminalsQuote single-character terminals (because boldface isn’t so obvious in this case)Example:if_statement ::= if "(" cond ition ")" statement [ else statement ]Limitations of BNFNo easy way to impose length limitations, such as maximum length of variable namesNo way to impose distributed requirements, such as, a variable must be declared before it is usedDescribes only syntax, not semanticsNothing clearly better has been devisedThe
View Full Document
Unlocking...