« Vuelta de vacaciones
MSX: Una de nostalgia »

Autómata finito determinista para reconocer constantes numéricas

En este breve artículo voy a explicar el proceso de creación de un sencillo autómata finito determinista para reconocer constantes numéricas. Este autómata forma parte del analizador léxico que estoy implementando para el lenguaje de script, que utilizaré en el motor de aventuras gráficas que estoy desarrollando.

Al final del artículo incluiré el código del autómata en su totalidad.

Lo primero que debemos hacer es definir lo que será una constante numérica valida. Una constante numérica debe estar formada por al menos un dígito, puede ir precedida o no por el signo y puede tener o no decimales. Si contiene el punto decimal debe tener al menos un dígito en la parte de los decimales.

Autómata finito determinista reconocedor de constantes numéricas.
Autómata finito determinista reconocedor de constantes numéricas.

Se trata de un autómata conexo ya que todos los estados son accesibles desde el inicial. Es un autómata determinista, ya que desde un estado y para una determinada entrada solo existe transición a un estado, nunca a varios estados.

Una vez definida la constante numérica formalmente mediante el diagrama de estados anterior, la implementación del autómata es muy sencilla. Debemos definir cuales serán los estados finales (aquellos marcados con un doble circulo en la imagen) y que transiciones son válidas para cada estado según las entradas que reciba y cuales no. Una vez procesados todos los caracteres que forman la palabra, la habremos reconocido como una constante numérica correcta, si no se ha producido ninguna transición no válida y si estamos en uno de los estados finales.

MAXIMIZAR PLAIN TEXT
VB.NET:
  1. Option Explicit On
  2. Option Strict On
  3.  
  4. ''' <summary>
  5. ''' Autómata finito determinista que reconoce constantes numéricas. Pueden tener signo inicial y contener
  6. ''' el punto decimal o no. Si tiene el punto decimal debe tener al menos un digito despues. El 012 se
  7. ''' considera correcto
  8. ''' </summary>
  9. ''' <remarks></remarks>
  10. Public Class AFDCteNumerica
  11.     Private Const ESTADO_FINAL_1 As Integer = 2
  12.     Private Const ESTADO_FINAL_2 As Integer = 4
  13.  
  14.     Public Shared Function Reconocer(ByVal p As String) As Boolean
  15.         Dim estado As Integer
  16.         Dim correcto As Boolean
  17.         Dim i As Integer
  18.         Dim c As Char
  19.  
  20.         estado = 0 'estado inicial
  21.         i = 0
  22.         correcto = True
  23.         'recorremos todos los carácteres de la palabra
  24.         While correcto And i <p.Length
  25.             c = p.Chars(i)
  26.  
  27.             If Char.IsDigit(c) Then
  28.                 Select Case estado
  29.                     Case 0
  30.                         estado = 2
  31.                     Case 1
  32.                         estado = 2
  33.                     Case 2
  34.                         estado = 2
  35.                     Case 3
  36.                         estado = 4
  37.                     Case 4
  38.                         estado = 4
  39.                 End Select
  40.             ElseIf c = "."c Then
  41.                 Select Case estado
  42.                     Case 0
  43.                         correcto = False
  44.                     Case 1
  45.                         correcto = False
  46.                     Case 2
  47.                         estado = 3
  48.                     Case 3
  49.                         correcto = False
  50.                     Case 4
  51.                         correcto = False
  52.                 End Select
  53.             ElseIf c = "+"c Or c = "-"c Then
  54.                 Select Case estado
  55.                     Case 0
  56.                         estado = 1
  57.                     Case 1
  58.                         correcto = False
  59.                     Case 2
  60.                         correcto = False
  61.                     Case 3
  62.                         correcto = False
  63.                     Case 4
  64.                         correcto = False
  65.                 End Select
  66.             Else
  67.                 correcto = False
  68.             End If
  69.            
  70.             i = i + 1
  71.         End While
  72.  
  73.         Return correcto And (estado = ESTADO_FINAL_1 Or estado = ESTADO_FINAL_2)
  74.     End Function
  75.  
  76. End Class

This entry was posted on Domingo, Agosto 20th, 2006 at 23:06 and is filed under Motor Aventura Gráfica, Artículos. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

4 Responses to “Autómata finito determinista para reconocer constantes numéricas”

  1. Sueco Says:
    Agosto 22nd, 2006 at 23:06

    El artículo está muy bien, sobre todo para refrescar la memoria de algunos sobre autómatas, compiladores, etc. Por cierto, hubiera estado bien también poner en notación BNF las constantes numéricas, hay páginas por ahí que parece que le mola a la gente esta representación. Un saludete y ánimo con el lenguaje de script y con el motor.

  2. brausoft Says:
    Agosto 22nd, 2006 at 23:34

    Gracias Sueco.
    Lo de la notación BNF estoy haciéndolo ahora mismo para el analizador sintáctico. Supongo que en un próximo artículo lo publicare.
    Un saludo

  3. Esteban Says:
    Octubre 17th, 2007 at 2:55

    como se podria con un lexico de las figuras geometricas o con alfanumericos

  4. brausoft Says:
    Octubre 18th, 2007 at 11:59

    No entiendo muy bien a que te refieres con lo de las figuras geométricas.
    En cuanto a las constantes alfanuméricas sería bastante sencillo y similar a lo que se comenta en este post. Lo primero sería definir el diagrama de estado del autómata que reconocerá la constante alfanumérica de forma similar al mostrado en la imagen que hay al inicio del post y a partir de eso crear una máquina de estados como la creada en el post.

Leave a Reply

Antispam. Escriba la palabra 'hola' (sin comillas)