Parsing expression grammar
![Questa voce è orfana](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2e/Arrows-orphan.svg/19px-Arrows-orphan.svg.png)
![Niente fonti!](http://upload.wikimedia.org/wikipedia/commons/thumb/6/64/Question_book-4.svg/45px-Question_book-4.svg.png)
In informatica, una parsing expression grammar, o PEG, è una grammatica formale analitica, ossia descrive un linguaggio formale in termini di un insieme di regole per riconoscere le stringhe che appartengono al linguaggio. Il formalismo è stato proposto nel 2004 ed è intimamente legato alla famiglia dei linguaggi analizzabili top-down introdotti nei primi anni settanta. Sintatticamente, le PEG somigliano anche alle grammatiche libere da contesto (CFG), ma hanno una diversa interpretazione: in una PEG l'operatore di scelta seleziona la prima corrispondenza, mentre in una CFG resta non deterministico. Ciò si avvicina alla pratica del riconoscimento delle stringhe ad esempio mediante un parser a discesa ricorsiva. A differenza delle CFG, le PEG non possono essere ambigue; se una stringa può essere derivata essa ammette esattamente un solo albero di derivazione. Si pensa che esistano linguaggi liberi che non possano essere analizzati tramite PEG, ma ciò non è ancora stato dimostrato. Le PEG sono indicate per l'analisi di linguaggio di programmazione (e linguaggi artificiali come Lojban), ma non per linguaggi naturali per i quali le prestazioni sono paragonabili a quelle degli algoritmi generali per CFG, ad esempio, l'algoritmo di Earley.
Collegamenti esterni
- (EN) A Generic Parser for the Entire Class of Context-free Grammars, su accent.compilertools.net. URL consultato il 19 aprile 2017 (archiviato dall'url originale il 18 luglio 2011).
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Computer_n_screen.svg/24px-Computer_n_screen.svg.png)