4.3 context-free languages

context-free language

a type of language (set of strings) that can be defined by a context-free grammar

context-free grammar

describes which strings are and are not possible in a context-free language by laying out production rules

production rules

rules for context-free grammar, notated by arrows, signifying possible replacements for a character, notated as:

symbol → string (strings can be empty)

backus-naur form

a way of notating context-free languages, using statements in which the left hand side is defined by the right hand side

non-terminals

text placed inside of <angle brackets> in BNF represents a non-terminal

non-terminals can be broken down into terminals and non-terminals

e.x.

<FullName> ::= <Title><Forename><Surname>

terminal

text without any brackets represents a terminal, which cannot be broken down any further and must be taken to be the written value

e.x. <digit> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0

( | is the OR operator )

digit is a non-terminal and 1,2,3,4,5,6,7,8,9 and 0 are terminals

recursion

the definition of a non-terminal using itself e.x.

<number> ::= <digit> | <digit><number>

allows numbers to be a string of digits of any length

syntax diagrams

visual, flowchart-like representations of non-terminals in a regular language

use rectangles to represent non-terminals and ellipses to represent terminals

shapes are joined by arrows which indicate how strings can be formed from the definitions