Linguaggio context-free

linguaggio context-free

linguaggio context-free linguaggio formale generato da una → grammatica generativa G = 〈A_N, A, P, s〉, dove A è l’alfabeto dei simboli terminali, A_N è l’alfabeto dei simboli non terminali, s ∈ A_N è l’assioma, P è un insieme di regole di riscrittura (produzioni) del tipo α → β, così intendendo che la stringa a sinistra della freccia può essere rimpiazzata da quella a destra, con α ∈ A_N e β ∈ (A_N ∪ A)⁺. Tali regole indicano che un simbolo non terminale può essere sostituito da una stringa non vuota di simboli terminali e non terminali. Poiché a sinistra della freccia compare solo un simbolo non terminale, la regola si applica indipendentemente dal contesto (context-free). Linguaggi di questo tipo sono alla base di linguaggi di programmazione, a partire da uno dei primi linguaggi evoluti l’_ALGOL, da cui si sono sviluppati i linguaggi di programmazione oggi in uso.