Parsing expression grammar: differenze tra le versioni

Versione delle 16:10, 2 ago 2017

Versione attuale delle 18:04, 9 lug 2025

(4 versioni intermedie di 4 utenti non mostrate)

Riga 1:

{{OF|informaticaprogrammazione|agostoaprile 2017}}

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 1970|anni settanta]]. Sintatticamente, le PEG somigliano anche alle [[Grammatica_libera_dal_contestoGrammatica libera dal contesto|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.

{{F|informatica|aprile 2017}}

A differenza delle CFG, le PEG non possono essere ambigue; se una stringa può essere derivata essa ammette esattamente un solo [[Albero sintattico|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 [[linguaggi di programmazione|linguaggio di programmazione]] (e [[Lingua_artificialeLingua artificiale|linguaggi artificiali]] come [[Lojban]]), ma non per [[Linguaggio naturale|linguaggi naturali]] per i quali le prestazioni sono paragonabili a quelle degli algoritmi generali per CFG, ad esempio, l'algoritmo di Earley.

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 1970|anni settanta]]. Sintatticamente, le PEG somigliano anche alle [[Grammatica_libera_dal_contesto|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 sintattico|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 [[linguaggi di programmazione|linguaggio di programmazione]] (e [[Lingua_artificiale|linguaggi artificiali]] come [[Lojban]]), ma non per [[Linguaggio naturale|linguaggi naturali]] per i quali le prestazioni sono paragonabili a quelle degli algoritmi generali per CFG, ad esempio, l'algoritmo di Earley.

== Collegamenti esterni ==

* {{Cita web|url=http://accent.compilertools.net/Entire.html|titolo=A Generic Parser for the Entire Class of Context-free Grammars|lingua=en|accesso=19 aprile 2017|dataarchivio=18 luglio 2011|urlarchivio=https://web.archive.org/web/20110718121743/http://accent.compilertools.net/Entire.html|urlmorto=sì}}

{{portale|Informaticainformatica}}

[[Categoria:Programmazione dinamica]]