Next: Backus-Naur-Form 25
Up: Allgemeines zu Sprachen
Previous: Wortproblem 21
Contents
Index
Syntaxbäume 23
Einer Ableitung eines Wortes in einer Typ 2 (oder 3) Grammatik
kann man einen Syntaxbaum oder Ableitungsbaum
zuordnen. Sei
und sei
eine Ableitung eines Wortes . Um den Baum zu erstellen gehe wie
folgt vor:
- Beschrifte die Wurzel des Syntaxbaumes mit der Startvariable
- Für
gehe man wie folgt vor:
Auf diese Weise erhält man eine Baum mit den Symbolen aus an
den Blättern.
- Verschiedene Ableitungen können den selben Syntaxbaum besitzen
- Linksableitung: Immer am weitesten Links
stehende Variable zuerst ableiten
- Rechtsableitung: Immer am weitesten
Rechts stehende Variable zuerst ableiten
- Für ein und das selbe Wort kann es verschiedene Syntaxbäume geben.
Die Grammatik ist dann mehrdeutig.
- Eine kontextfreie Sprache heißt inhärent mehrdeutig,
wenn jede Grammatik mit
mehrdeutig ist.
Next: Backus-Naur-Form 25
Up: Allgemeines zu Sprachen
Previous: Wortproblem 21
Contents
Index
Marco Möller 18:11:27 24.10.2005