regex - online - regular expression remove spaces
¿Cuáles son las diferencias entre PEG y CFG? (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.
De esta página wikipedia :
La diferencia fundamental entre las gramáticas libres de contexto y las gramáticas de expresión de análisis es que el operador de elección del PEG está ordenado. Si la primera alternativa tiene éxito, se ignora la segunda alternativa. Por lo tanto, la elección ordenada no es conmutativa, a diferencia de la opción no ordenada, como en las gramáticas libres de contexto y las expresiones regulares. La opción ordenada es análoga a los operadores de corte suave disponibles en algunos lenguajes de programación lógica.
¿Por qué el operador de elección de PEG cortocircuita el emparejamiento? ¿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 hacer coincidir 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? ie /[aeiou]/ comporta igual que /[eiaou]/ . ¿Cuál es la ventaja de que sea conmutativa? (cf no-conmutatividad de PEG)
La consecuencia es que si un CFG se translitera directamente a un PEG, cualquier ambigüedad en el primero se resuelve eligiendo determinísticamente un árbol de análisis sintáctico de los posibles análisis. Al elegir cuidadosamente el orden en que se especifican las alternativas de gramática, un programador tiene un gran control sobre qué árbol de análisis sintáctico se selecciona.
¿Esto está diciendo que la gramática de PEG es superior a la de CFG?
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;
aplicado a la entrada
if (x1) if (x2) y1 else y2
podría ser analizado como
if_statement(x1, if_statement(x2, y1, y2))
o
if_statement(x1, if_statement(x2, y1), y2)
Un analizador CFG generaría un conflicto Shift / Reduce, ya que no puede decidir si debería 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 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.