Parsing Expresions Grammars

Abstract

Las Parsing expression grammars son un formalismo que describen un lenguaje formal en términos de un conjunto de reglas, para el reconocimiento de cadenas en el lenguaje. Dichos reconocedores de lenguajes (parsers) son especificados de tal forma que no es necesario dividir la especificación en la parte léxica y la parte libre de contexto. Una especificación de una parsing expression grammar puede verse como la descripción de un parser descendente recursivo con backtracking. Las alternativas en la gramática se procesan en el orden dado en la especificación, lo que se conoce como priorized choice. Las especificaciones basadas en este formalismo son más compactas y los parsers aceptan una clase de lenguajes más amplia que la mayoría de los parsers clásicos determinísticos, como los basados en gramáticas LL(k) o LR(k). Si bien existen varias implementaciones de expression grammars, generalmente no incluyen características deseables como informe y recuperación de errores o generación automática de ASTs (Abstract Syntac Tree). En particular este trabajo describe las Parsing Expression Grammars y el desarrollo de EgLib y EgParserGen y sus características que las diferencian de herramientas similares.