Startsymbolen

Startsymbolen zijn de tekens uit een formele grammatica die dienen als het beginpunt van een afleiding. In een grammatica G = (N, Σ, P, S) is S het startsymbool en S ∈ N het nonterminale teken waar alle afleidingen mee starten. De taal die door de grammatica wordt gegenereerd, bestaat uit alle strings w ∈ Σ* waarvoor S ⇒* w geldt. Het startsymbool staat ook centraal in de boomstructuur van parsebomen, waarbij de wortel van de boom is labeled met S.

In de meeste formalisms is er één startsymbool. Het is het signaalpunt voor parsers en compilers en bepaalt de hiërarchie van de toplaag van de grammatica. Sommige grammaticavormen staan toe dat er meerdere startsymbolen bestaan; om dit te realiseren wordt vaak een nieuw startsymbool S0 geïntroduceerd met regels S0 → S1 | S2 | …, zodat de taal het evenwicht van de verschillende startpunten kan omvatten.

Het startsymbool kan ε afleiden als de regels dit toelaten, wat betekent dat de lege string ε behoort tot de taal. Het startsymbool hoeft geen terminal te zijn; het is een niet-terminal dat tijdens derivaties wordt vervangen door andere symbolen.

Praktisch gezien bepaalt het startsymbool de topstructuur van programmestructuren in compilerontwerp en de basis van de taal die een grammatica beschrijft. Bij het ontwerpen van grammaticae is het belangrijk dat S bereikbaar is uit alle regels en dat de afleiding correct leidt tot uitsluitend terminals in de uiteindelijke taal.