Expresión Regular Vs Gramática Libre de Contexto

Las expresiones regulares son capaces de describir la sintaxis de los tokens. Cualquier construcción sintáctica que pueda ser descrita por la expresión regular también puede ser descrita por la gramática libre de contexto.

Expresión regular:

(a|b)(a|b|01) 

Gramática libre de contexto:

S --> aA|bA
A --> aA|bA|0A|1A|e 

*e denota épsilon.

La gramática libre de contexto forma NFA para la expresión regular utilizando las siguientes reglas de construcción:

1. Para cada estado hay un símbolo No terminal.
2. Si el estado A tiene una transición al estado B en un símbolo a
   
3. SI el estado A pasa al estado B, el símbolo de entrada es e
   
4. Si A está aceptando el estado.
   
5. Haga el símbolo de inicio de la NFA con el símbolo de inicio de la gramática.

Cada conjunto regular se puede describir con la gramática libre de contexto, por eso estamos usando la expresión regular. Hay varias razones y son:

Expresiones regulares	gramática libre de contexto
Las reglas léxicas son bastante simples en el caso de las expresiones regulares.	Las reglas léxicas son difíciles en el caso de la gramática libre de contexto.
Las notaciones en expresiones regulares son fáciles de entender.	Las notaciones en la gramática libre de contexto son bastante complejas.
Se define un conjunto de strings en el caso de expresiones regulares.	En la gramática libre de contexto el lenguaje se define por el conjunto de producciones.
Es fácil construir un reconocedor eficiente a partir de expresiones regulares.	Al usar la gramática libre de contexto, es muy difícil construir el reconocedor.
Existe un procedimiento adecuado para el análisis léxico y sintáctico en el caso de expresiones regulares.	No existe una guía específica para el análisis léxico y sintáctico en el caso de la gramática libre de contexto.
Las expresiones regulares son más útiles para describir la estructura de la construcción léxica, como identificadores, constantes, etc.	Las gramáticas libres de contexto son más útiles para describir la estructura de la string anidada o la estructura sintáctica, como paréntesis equilibrados, si no, etc., y estos no se pueden definir mediante expresiones regulares.