Notación Bnf

Extensiones a la notación BNF

Las gramáticas BNF no constituyen una notación ideal APRA comunicar las reglas de sintaxis de lenguajes de programación al programador practico.

• Notación BNFextendida: permiten descripciones más fáciles de los lenguajes.
-Un elemento optativo se puede encerrar entre […]
-Una selección de alternativas puede usar el símbolo |
-Una serie arbitrariade casos de un elemento se indica {}*

• Diagrama de sintaxis (diagrama de ferrocarril): es una forma grafica de expresa reglas de BNF extendida. Cada regla esta representada por un camino queva de la entrada (a la izquierda) a la salida (a la derecha).

Autómatas de estados finitos

Todos los componentes léxicos de un lenguaje de programación tienen una estructura sencilla:-Un identificador comienza con una letra, seguida de letras o dígitos.
-Un entero es una serie de dígitos.
-La palabra reservada IF es la letra I seguida de la letra F.

En todos estoscasos, existe un modelo sencillo llamado autómata de estados finitos (FSA) o una maquina de estado que reconoce estas clases de componentes léxicos.

Un FSA tiene: Un estado inicial, Un estado finalo más y un conjunto de transiciones de un estado a otro.
Cualquier cadena que lleve a la maquina del estado inicial a un estado final a través de una serie de transiciones es aceptada por la maquina.Autómatas finitos no deterministas

Si, para cada FSA y para cada símbolo de entrada se tiene una transición exclusiva hacia el mismo estado o uno diferente, la clase del FSA se conoce comodeterminista.
Un autómata no determinista de estados finitos es un FSA con:
i. Un conjunto de estados (nodos en una grafica).
ii. Un estado de partida (uno de los nodos).
iii. Unconjunto de estados finales (subconjunto de nodos).
iv. Un alfabeto de entrada (rótulos en los arcos entre nodos).
v. Un conjunto de arcos de nodos a nodos, cada uno rotulado con un...