¿Cuáles son las diferencias entre PEG y CFG?

Question

Desde esta página wikipedia:

La diferencia fundamental entre gramáticas libres de contexto y el análisis gramáticas de expresión es que el operador elección del PEG se ordenó. Si la primera alternativa tiene éxito, se ignora la segunda alternativa . Por lo tanto, la opción ordenada no es conmutativa, a diferencia de elección desordenada como en las gramáticas y expresiones regulares sin contexto. La elección ordenada es análoga a los operadores de corte suaves disponibles en algunos lenguajes de programación lógicos .

¿Por qué el operador de elección de PEG cortocircuita la correspondencia? ¿Es porque para minimizar el uso de la memoria (debido a la memorización)?

No estoy seguro de cuál es el operador de elección en las expresiones regulares, pero supongamos que es esto: /[aeiou]/ para que coincida con una vocal. ¡Entonces esta expresión regular es conmutativa porque podría haberla escrito en cualquiera de las 5! (cinco factoriales) permutaciones de los caracteres vocálicos? es decir, /[aeiou]/ se comporta igual que /[eiaou]/. ¿Cuál es la ventaja de que sea conmutativa? (No conmutatividad de compárese con PEG)

La consecuencia es que si un CFG es transcrito directamente a un PEG, cualquier ambigüedad en el anterior se resuelve mediante recoger de forma determinista un análisis sintáctico árbol de los posibles análisis sintácticos. Por eligiendo cuidadosamente el orden en el que las alternativas de gramática están especificadas, un programador tiene un gran control sobre qué árbol de análisis está seleccionado.

¿Está diciendo esto que la gramática de PEG es superior a la de CFG?

Answer 1

Una gramática CFG no es determinista, lo que significa que alguna entrada podría dar como resultado dos o más posibles árboles de análisis. Aunque la mayoría de los generadores de analizadores basados ​​en CFG tienen restricciones sobre la determinabilidad de la gramática. Le dará una advertencia o un error si tiene dos o más opciones.

Una gramática PEG es determinista, lo que significa que cualquier entrada solo se puede analizar de una manera.

Para tomar un ejemplo clásico; La gramática

if_statement := "if" "(" expr ")" statement "else" statement 
       | "if" "(" expr ")" statement; 

aplica a la entrada

if (x1) if (x2) y1 else y2 

bien podría ser analizados como

if_statement(x1, if_statement(x2, y1, y2)) 

o

if_statement(x1, if_statement(x2, y1), y2) 

A CFG-parser generaría un desplazamiento/reducción -conflicto, ya que no puede decidir i f debe desplazarse (leer otro token) o reducir (completar el nodo) al llegar a la palabra clave "else". Por supuesto, hay formas de evitar este problema.

Un analizador PEG siempre elegiría la primera opción.

Cuál es mejor es para que usted decida. Mi opinión objetiva es que a menudo las gramáticas de PEG son más fáciles de escribir y las gramáticas de CFG más fáciles de analizar.

Answer 2

Creo que estás confundiendo CFG con LR y con ambigüedad. Las gramáticas no son deterministas/no deterministas, aunque sí lo sean sus analizadores. Una gramática ambigua sigue siendo CFG si cumple con la definición, y se puede construir un analizador determinístico para que haga lo que hace PEG.