Beispiel: Syntaxdefinition von Programmiersprachen

Spezifikationen von Programmiersprachen, die mit Hilfe von kontextfreien Grammatiken erstellt werden, machen regen Gebrauch von Rekursion -- das beste Beispiel ist die Definition einer Anweisung in C, die hier mit Hilfe von VDM modelliert ist:

 DOMAINS 
 *
Stmt =Ēxpr | Return | Break | Cont | Goto | Label |

 *
				If | While | Switch | Do | For | Block | Nullstmt
 *
Return		=		Optexpr 
 *
Break		=		ELEMENTARY 
 *
Cont		=		ELEMENTARY 
 *
Goto		::		s_gotoid : Ids_gotostmt : Stmt 
 *
Label		::		s_labelid : Ids_labelstmt : Stmt

If		::		s_ifexpr : Exprs_ifthen : Stmt s_ifelse : Optstmt 
 *
While		::		s_whileexpr : Exprs_whilestmt : Stmt 
 *
Switch		::		s_swexpr : Exprs_swcase : Case 
 *
Do		::		s_dostmt : Stmts_doexpr : Expr 
 *
For		::		s_forinit : Optexpr s_forexit : Optexpr
 *
				s_forincr : Optexpr s_forstmt : Stmt 
 *
Block		::		s_blkhd : Blkheads_blkstmts : Stmts 
 [0.5ex]
Nullstmt		=		ELEMENTARY 
 *
Optexpr		=		[ Expr ] 
 *
Optstmt		=		[ Stmt ] 
 *
Blkhead		=		[ Decls ] 
 *
Decls		::		s_decl : Decls_blkhead : Blkhead 
 *
Decl		=		Typedef | Extern | Localdata 
 *
Stmts		=		[ Single ] 
 *
Single		::		s_sstmt : Stmts_single : Stmts 
 *

Einige Anmerkungen dazu:

Nomenklatur Die Abkürzungen beziehen sich auf die üblichen englischen Bezeichnungen: statement (Anweisung), expression (Ausdruck), identifier (Bezeichner).

Case / Expr Die beiden Non-Terminale Case und Expr sind hier nicht weiter aufgelöst.

Terminale Die Terminalsymbole von C sind für die Modellierung eines Programms mit einem abstrakten Datentyp nicht wichtig, wenn der Quelltext richtig analysiert wurde (ist z.B. ein Stück des Quelltexts als for-Statement erkannt worden und wurden die maximal vier Bestandteile korrekt in einer Variablen vom Typ For untergebracht, ist der identifizierende Text for mit Klammern und Semikola nicht mehr erforderlich).

Return Die return-Anweisung hat ein optionales Argument, den Rückgabewert, der aus dem angegebenen Ausdruck berechnet wird.

ELEMENTARY Die Vereinbarung einiger ADT als ,,ELEMENTARY`` soll anzeigen, daß keine weitere Information zur Interpretation der Anweisung nötig ist (z.B. wird der Befehl break durch eine Variable repräsentiert, deren Anwesenheit dem Code-Generator anzeigt, daß der break-Befehl im Programm stand; das reicht aus, um den Quelltext richtig zu interpretieren).

for Alle Ausdrücke innerhalb der for-Schleife (Initialisierung, Abbruchbedingung, Inkrementierung) sind optional.

Block Ein Block beginnt mit einer optionalen, beliebig langen Liste (Blkhead) von Typdefinitionen, Deklarationen von externen Variablen und Definition von lokalen Variablen. Danach folgt eine optionale, beliebig lange Sequenz von Anweisungen, die auch leer sein kann; beide Bestandteile wurden durch eine verkettete Liste rekursiv definiert.

Ein größeres Beispiel Rekursive Typdefinition Implementation rekursiver Strukturen