<expression> ::= <expression> + <term> | <term> <term> ::= <term> * <factor> | <factor> <factor> ::= ( <expression> ) | <name> | <integer> <name> ::= <letter> | <name> <letter> | <name> <digit> <integer> ::= <digit> | <integer> <digit> <letter> ::= A | B | ... |Z <digit> ::= 0 | 1 | 2 | ... | 9Here, we have used "::=" for is defined as rather than an arrow, --> as before. The metalanguage BNF (Backus-Naur Form) is a way of specifying context-free languages, and BNF was originally defined using ::= rather than -->. As long as we understand what is meant and what the capabilities of this grammatical notation are, the notation doesn't matter. We will often omit the angle brackets, <>, when writing BNF.
Unlike natural languages like English, all the legal strings in a programming language can be specified using a context-free grammar. However, grammars for programming languages specofy semantically incorrect strings as well. For example context-free languages cannot be used to tell if a variable, say, A, declared to be of type boolean is used in an arithmentic expression A + 1.
Parse Tree for A * B A parse tree shows the structure of a string using the grammar.
Terminals and Nonterminals
Sentential Form and Sentence
Send questions and comments to: Karen Lemone