V počítačové vědě , a zejména v teorii jazyků , nazýváme terminální a nekoncové symboly symboly používané v pravidlech produkce formální gramatiky . Tyto koncové symboly a nonterminál symboly jsou součástí disjunktních množin .
Terminálové symboly jsou doslovné znaky, které se mohou objevit v produkčních pravidlech (vstupu nebo výstupu) formální gramatiky a nelze je rozdělit na menší prvky. Jedná se přesněji o prvky, které nelze změnit pomocí pravidel gramatiky. Například gramatika definovaná dvěma pravidly:
present má jako symbol terminálu, protože neexistuje žádné pravidlo, které by jej změnilo na něco jiného ( x však není terminál, protože přijímá dvě pravidla, která mají být změněna). Formální jazyk definovaný (nebo generované ) určitým gramatiky je sada řetězce nebo slova z koncových postav produkovaných gramatiky; terminály, které nejsou zcela konstruovány z terminálů, se nemohou jevit jako lexémy patřící k jazyku. V kontextu syntaktické analýzy, která je v rozporu s teorií programovacích jazyků a překladačů , jsou termíny symbol a token často považovány za synonyma. Podle knihy draků :
"V kompilátoru čte lexikální analyzátor znaky ze zdrojového programu, seskupuje je do sémantických jednotek zvaných lexémy a vytváří tokeny představující tyto lexémy." Token se skládá ze dvou prvků, názvu tokenu a hodnoty atributu. Názvy tokenů jsou abstraktní symboly, které analyzátor používá k analýze. Tyto názvy se často nazývají terminálové tokeny , protože se v gramatice programovacího jazyka objevují jako terminální symboly. Hodnota atributu, pokud je k dispozici, je ukazatel na tabulku symbolů, kde jsou obsaženy další informace o tokenu. Tato informace není součástí gramatiky, takže pokud jde o parsování, budeme na tokeny a terminály odkazovat synonymně. "
Terminálové symboly nebo jen terminální symboly jsou základní symboly jazyka definovaného formální gramatikou .
Tyto non-terminální symboly , nebo non-terminály , jsou symboly, které mohou být nahrazeny; existují proto řetězce složené z terminálních a neterminálních symbolů. Mohou se také nazývat syntaktické proměnné nebo proměnné . Formální gramatika zahrnuje počáteční symbol , určený člen množiny neterminálů, ze kterých lze pomocí postupných aplikací nebo produkčních pravidel odvodit všechny jazykové řetězce. Jazyk definovaný gramatikou je ve skutečnosti přesně sada koncových řetězců, které lze takto odvodit.
Nekontextové gramatiky je gramatiky, v níž levá člen každé pravidlo výroby je jednoduchá bez svorky. Toto omezení není triviální, ne všechny jazyky lze generovat bezkontextovými gramatikami. Nazývají se nekontextové jazyky. Jedná se o jazyky, které jsou rozpoznávány nedeterministickými pushdown automaty . Nekontextové jazyky tvoří teoretický základ syntaxe většiny programovacích jazyků.
Gramatika je definována produkčními pravidly, která určují, které lexémy nahrazují jiné lexémy; tato pravidla lze použít ke generování řetězců nebo k jejich analýze. Každé produkční pravidlo má hlavu nebo levého člena, který představuje řetězec, který má být nahrazen, a tělo nebo pravý člen, který představuje řetězec, který jej nahradí. Pravidla jsou často psána ve formě hlava → tělo ; například pravidlo z0 → z1 určuje, že z0 lze nahradit z1.
V klasické formalizaci generativních gramatik, kterou navrhl Noam Chomsky v padesátých letech, se gramatika G skládá z:
Gramatika je formálně definována jako uspořádaná čtyřnásobek .
Například, abychom reprezentovali možná podepsané číslo, můžeme navrhnout následující gramatiku (vyjádřenou v pseudo- BNF notaci ):
<entier> ::= ['-'] <chiffre> {<chiffre>} <chiffre> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'V této gramatice jsou symboly (-, 0,1,2,3,4,5,6,7,8,9) terminály; symboly <chiffre>a <entier>jsou nekoncové.