Home / Questions / 165850
Accepted
raintrooper
Asked: 2020-05-20 00:52:14 +0800 CST 2020-05-20 00:52:14 +0800 CST

Implement Programming Language Translator (Lexical, Syntactic Analysis)

  • 772

As part of a Compilers job, I must program a text editor that receives the Visual Basic language as input and transforms it to another language of my choice. I am currently using Visual Basic to program the above.

EditorText

The first thing I did was receive the input string and separate it into tokens, classifying them into reserved words, variables, grouping symbols, and operators.

Public Sub Procesar(Cadena As String, lstResultado As ListView, lstSimbolos As ListView)
        Try
            Dim cadenaAux As String = ""
            Dim cadenaSimbolos As String = ""
            ' Microsoft.VisualBasic.ChrW(13) se agrega este tipo de propiedad para saber cuando hay un salto de linea 
            Cadena &= Microsoft.VisualBasic.ChrW(10) & "!" 'bandera que indica si es final de texto
            Dim contador As Integer = 0

            While (Cadena.Chars(contador) <> "!")
                'verifica que exista un salto de linea para insertar token a la lista, tambien verifica que este vacio la cadena aux
                'en el textbox si funcion ay detecta la libreriade microsoft visual para el chrw13 que es la tecla intro pero en richtextbox no funciona
                'detexta al final de la cadena el chrw(13) porque se le concatena a la cadena que se evualua, de lo contrario no lo detectara. 
                If (Cadena.Chars(contador) = Microsoft.VisualBasic.ChrW(10)) AndAlso cadenaAux.Trim <> "" Then

                    Dim palabras As String() = cadenaAux.TrimStart.Split(",")
                    cadenaAux = ""
                    cadenaSimbolos = ""
                    For x As Integer = 0 To palabras.Count - 1
                        If Comparador(palabras(x), Propiedad) Then
                            cadenaAux &= " (RESERVADO) " & palabras(x)
                        ElseIf Comparador(palabras(x), Operador) Then
                            cadenaSimbolos &= " (OPERADOR) " & palabras(x)
                        ElseIf Comparador(palabras(x), Delimitador) Then
                            cadenaSimbolos &= " (DELIMITADOR) " & palabras(x)
                        ElseIf EsNumero(palabras(x)) Then
                            cadenaAux &= " (NUMERO) " & palabras(x)
                        Else
                            cadenaAux &= " (PALABRA) " & palabras(x)
                        End If
                    Next

                    Dim lst As New ListViewItem(cadenaAux)
                    lstResultado.Items.Add(lst)
                    lst = New ListViewItem(cadenaSimbolos)
                    lstSimbolos.Items.Add(lst)
                    cadenaAux = ""
                    cadenaSimbolos = ""
                End If

                'se reemplaza proceso anterior por funcion que verifica y valida el doble o triple o multiple espacios 
                cadenaAux &= GetToken(Cadena.Chars(contador))

                contador += 1
            End While
        Catch ex As Exception
            Throw
        End Try
    End Sub

Method to evaluate tokens:

'evalua la lista de token obtenidas del proceso que analiza todo el texto
    Public Sub Evalua(lstResultado As ListView, lstPropiedad As ListView, lstOperador As ListView, lstIdentificador As ListView, lstNumero As ListView, lstError As ListView)
        Try
            Dim CadenaAux As String = ""
            Dim Palabra As String = ""
            Dim contador As Integer = 0

            For x As Integer = 0 To lstResultado.Items.Count - 1

                Dim item As ListViewItem = lstResultado.Items(x)
                CadenaAux = item.SubItems(0).Text
                CadenaAux &= ",!" 'se coloca la coma antes del fin de cadena para saber que el caracter a continuacion es el fin de cadena

                'algoritmo que compara las palabras encontradas para saber en que lista insertarlas
                While CadenaAux.Chars(contador) <> "!"
                    If (CadenaAux.Chars(contador) = ",") Then
                        If Comparador(Palabra, Operador) Then
                            Dim lst As New ListViewItem(Palabra)
                            lstOperador.Items.Add(lst)
                        ElseIf Comparador(Palabra, Propiedad) Then
                            Dim lst As New ListViewItem(Palabra)
                            lstPropiedad.Items.Add(lst)
                        Else
                            'si no encuentra la palabra en las listas creadas, las evalua para saber si son identificadores o numeros. 

                            'Verifica si el primer caracter es numero con el algoritmo dado en clase si no lo manda al otro analizador de caracteres.
                            If EsNumero(Palabra.Chars(0)) Then
                                MsgBox(Palabra & "Numero ")
                                AnalizadorNumerico(Palabra, lstNumero, lstError) ' por automata
                            Else
                                MsgBox(Palabra & "Palabra ")
                                Analizador(Palabra, lstIdentificador, lstNumero, lstError)
                            End If

                        End If
                        Palabra = ""
                    Else
                        Palabra &= CadenaAux.Chars(contador)
                    End If
                    contador += 1
                End While

                'Reinicio de las variables auxiliares
                contador = 0
                Palabra = ""
                CadenaAux = ""
            Next
        Catch ex As Exception
            Throw
        End Try
    End Sub

Automata to evaluate if token is number:

Private Sub AnalizadorNumerico(Palabra As String, lstNumero As ListView, lstError As ListView)
        Dim Estado As Integer = 1
        Dim contador As Integer = 0
        Dim Analizado As Boolean = True
        Dim PalabraAux As String = Palabra & "!"

        'algoritmo de analizador lexico 
        While PalabraAux.Chars(contador) <> "!"
            Select Case Estado
                Case 1
                    If EsNumero(PalabraAux.Chars(contador)) Then
                        Estado = 2
                    Else
                        Analizado = False
                    End If
                Case 2
                    If EsNumero(PalabraAux.Chars(contador)) Then
                        Estado = 2
                    ElseIf PalabraAux.Chars(contador) = "." Then
                        Estado = 3
                    ElseIf PalabraAux.Chars(contador) = "E" Then
                        Estado = 5
                    Else
                        Analizado = False
                    End If
                Case 3
                    If EsNumero(PalabraAux.Chars(contador)) Then
                        Estado = 4
                        Analizado = True
                    Else
                        Analizado = False
                    End If
                Case 4
                    If EsNumero(PalabraAux.Chars(contador)) Then
                        Estado = 4
                        Analizado = True
                    ElseIf PalabraAux.Chars(contador) = "E" Then
                        Estado = 5
                    Else
                        Analizado = False
                    End If
                Case 5
                    If EsNumero(PalabraAux.Chars(contador)) Then
                        Estado = 7
                        Analizado = True
                    ElseIf PalabraAux.Chars(contador) = "-" Then
                        Estado = 6
                    ElseIf PalabraAux.Chars(contador) = "+" Then
                        Estado = 6
                    Else
                        Analizado = False
                    End If
                Case 6
                    If EsNumero(PalabraAux.Chars(contador)) Then
                        Estado = 7
                        Analizado = True
                    Else
                        Analizado = False
                    End If
                Case 7
                    If EsNumero(PalabraAux.Chars(contador)) Then
                        Estado = 7
                        Analizado = True
                    End If

            End Select
            contador += 1
        End While

        'evaluacion de la palabra encontrada 
        'e inserta en su lista respectiva
        'If (Estado = 4 Or Estado = 7 Or Estado = 2) And Analizado Then
        If (Estado = 4 Or Estado = 7 Or Estado = 2) And Analizado Then
            Dim lst As New ListViewItem(Palabra)
            lstNumero.Items.Add(lst)
        ElseIf Not Analizado Then
            Dim lst As New ListViewItem(Palabra)
            lstError.Items.Add(lst)
        End If
    End Sub

The tokens after being evaluated by automata I store them in ListViews, which I then show in a window.

Private Sub MnuResultado_ItemClick(sender As Object, e As DevExpress.XtraBars.ItemClickEventArgs) Handles MnuResultado.ItemClick
        Try
            Dim frm As New FrmAnalizadorLexico
            For Each item In lstReservadas.Items
                frm.lstDatos.Items.Add(item.Text)
            Next
            For Each item In lstSimbolos.Items
                frm.lstSimbolos.Items.Add(item.Text)
            Next
            frm.ShowDialog()
            frm = Nothing
        Catch ex As Exception
            cls.MensajeError(ex.Message)
        End Try
    End Sub

tokens

For this translator I don't have to do group sign validations, which check if parentheses or curly braces are missing. Only transform the obtained tokens to another language. The final language can be any.

Also it is not the whole language that I have to convert, only the structure of a For, While and If.

For example if I have:

For i = 1 To i <= 5

Next

I must convert it to:

for(int i = 1; i <= valor 5; i = i + 1)
{

}

In this case the tokens I have are: Line 1:

PalabraReservada "For" Token1
Identificador "i = 1" Token2
PalabraReservada "To" Token3
Identificador "i <= 5"  Token4

Line 2:

PalabraReservada "Next" Token5

I have tried in several ways, but I can't get the translation of the tokens to work for me.

What I need help with is if you can tell me how to make a template that receives the tokens and changes them to the new language. Please.

If anyone can help me I'd be very grateful.

vb.net

1 Answers

  1. Best Answer

    Making a compiler is something relatively complicated, I've been trying to do something personal for a long time, but nothing I haven't achieved before. What you want to do is something that requires a lot of analysis time and this answer is basically the summary of a book that I read about 2 years ago.

    Seasoning the code (with a lot of salt)

    I will assume that you already have the full lexical analyzer, the one that is going to take the input and "split" it into small units called a token, and that you use the following class to store a Token:

    Public Class Token
  Public TType As TokenTypes
  Public Value As Object
  Public Sub New()
    ' Constructor Vacio.
  End Sub
  Public Sub New(tokType As TokenTypes, val As Object)
    TType = tokType
    Value = val
  End Sub
End Class

    If you notice, it TTypeis of type TokenTypes, which in turn is a Enumdefined as follows:

    Public Enum TokenTypes
    AddOp       ' +
    SubOp       ' -
    MulOp       ' *
    DivOp       ' /
    LesserThan  ' <
    LesserEq    ' <=
    Equals      ' = (Es el mismo que asignación)
    NotEquals   ' <>
    GreaterThan ' >
    GreaterEq   ' >=
    BoolAnd     ' And
    BooOr       ' Or
    BoolNot     ' Not
    ' Los que terminan en "Kwd" son palabras clave.
    IfKwd       ' If
    ElseIfKwd   ' ElseIf
    ElseKwd     ' Else
    ForKwd      ' For
    ToKwd       ' To
    StepKwd     ' Step
    NextKwd     ' Next [ Next i, ...  ]
    ExitKwd     ' Exit [ For, While.. ]
    DimKwd      ' Dim
    AsKwd       ' As
    IntegerKwd  ' Integer
    Ident       ' Cualquier identificador.
    Number      ' Cualquier número entero.
End Enum

    This enumeration contains the different types Tokenthat your compiler is going to handle and well, the ones that (for now) your parser is going to use, at the moment we are not going to use all the VB.NET token types, because the list would not end now.

    The way in which the semantic (or syntactic) analyzer should see the tokens would be something like the following (JSON-like) :

    "Token": { "TType": "Integer", "Value": "Integer" }

    Later you can save the exact line and column where you found that token, but for now it doesn't matter.

    ClassParser

    Asumo que sabes que esta etapa se encarga de validar la sintaxis de tu lenguaje (Hasta donde yo se, pueden corregirme) y producir una especie de Arbol de Sintaxis que posteriormente podrá ser traducido a cualquier otra cosa (Bytecode u otro lenguaje de programación).

    Esto sería nuestro Parser:

    Public Class Parser
  ' Nuestra Lista para almacenar los tokens temporalmente.
  Private Tokens As IList(Of Token)
  Private Index As Integer
  ' La cadena en otro lenguaje de programación como resultado.
  Private Output As String

  Public Sub New(Source As IList(Of Token))
    Tokens = Source
    Index = 0
    Output = ""
  End Sub

  Private Function MatchAndEat(T As TokenTypes) As Boolean
    Dim TT = GetToken
    If Not Object.Equals(TT, Nothing) Then
      If TT.TType = T
        Index += 1 ' Avanza al siguiente token.
        Return True
      End If
    End If
    Console.WriteLine("Error: Token inesperado, se esperaba '" & T.ToString() & "'.")
    Return False
  End Function

  Private Function GetToken() As Token
    Return if(Index < Tokens.Count, Tokens(Index), Nothing)
  End Function

  Private Sub Emitir(Texto As String)
    Output = Output & Texto ' Vamos hombre...
  End Sub

  Public Function Parse() As String
     Return Output ' Todavia no vamos por aquí, asi que espera chavalito.
  End Function

End Class

    La función MatchAndEat juega un papel bastante importante en nuestro parser, ya que con el nos daremos cuenta de los tokens que necesitamos, retorna Boolean debido a que si el valor retornado no es True, debemos terminar el análisis, porque no recibimos lo que esperabamos.

    Actualmente no vamos a construir ningun arbol de sintaxis, por lo que no hace falta tener una tabla de simbolos y esas cosas, solo vamos a emitir el código de un lenguaje de destino, para eso tenemos el método Parse.

    Parse es el método principal del analizador y lo que hace es que compara los tokens, si encuentra un If, de una va y le deja el control a ParseIf o a otra función que se encargue de trabajar el If.

    Determinando Patrones

    En esta respuesta solo voy a trabajar con lo que sería la detección de un For para su posterior traducción (Sin instrucciones dentro del mismo), debido a que los patrones son similares y es facil de deducir lo que sigue.

    Esta es la etapa más sencilla y más compleja, determinar los patrones que coincidan con la definición de tu lenguaje, vamos a considerar la siguiente sintaxis:

    For i = 0 To 10 Step 2
  ' Body
Next

    Se puede entender una de dos cosas:

    • La variable i es inline, es decir, propia del ciclo, o
    • La variable i fue definida en otro lugar para su posterior uso.

    Esto hay que tenerlo bastante en cuenta, para nuestro patrón vamos a asumir que los ciclos For van a tener su variable propia, como el código de arriba aunque de todas formas debemos manejar las expresiones aritmeticas para poder hacer algo como el for en C#, C o en cualquier otro lenguaje.

    El algoritmo es algo más o menos como lo siguiente:

    • Encontramos un For, lo dejamos pasar con MatchAndEat(TokenTypes.ForKwd).
    • Le damos el control a la función ParseFor:
      • Si el siguiente token no es un identificador, abortar y producir error.
      • De lo contrario, emitir el token como procede en el lenguaje de destino (for(int <Nombre>).
      • Consumir el identificador.
      • Si el siguiente token no es un signo de asignación abortar y producir error.
      • De lo contrario emitir el signo de igual y la operación aritmetica.
      • Consumir el signo de igual y la operacion aritmetica.
      • Etc...

    Lo de arriba es un poco tedioso, mejor hablemos un lenguaje que entendamos:

    ' Ahora si sabemos para que sirve Parse()
Public Function Parse() As String
  If Tokens(Index).TType = TokenTypes.For Then
    ParseFor ' Le damos el control :)
  Else
    Console.WriteLine("Token inesperado '" & Tokens(Index).TType & "', abortando.")
    Return ""
  End If
End Function

    Eso trae consigo, otra función llamada ParseFor() _(Disculpen mi VB.NET, estoy bastante oxidado :P, código completo en el fiddle) :

      Private Sub ParseFor()
    Dim T As Token
    Dim VarName As String
    Try
      MatchAndEat(TokenTypes.ForKwd)
      Emitir("for (int ")
      T = GetToken
      If Not MatchAndEat(TokenTypes.Ident)
        Exit Sub
      End If
    ...
  End Sub

    Ya con esto y el siguiente método Main, tienes para comprobar que si traduce un conjunto de tokens en lo que sería la salida "deseada":

    Public Sub Main()
  Dim Entrada = New List(Of Token) From { _
      New Token(TokenTypes.ForKwd, Nothing) _
    , New Token(TokenTypes.Ident, "hello") _
    , New Token(TokenTypes.Equals, "=") _
    , New Token(TokenTypes.Number, "10") _
    , New Token(TokenTypes.ToKwd, "To") _
    , New Token(TokenTypes.Number, "30") _
  }
  Dim Analizador = New Parser(Entrada)
  Console.WriteLine("Producido:")
  Console.WriteLine(Analizador.Parse())
End Sub

    The semantic/syntactical analyzer we made (Bad, but good) can translate the expression:

    For i = 0 To 10 Step 1
Next

    A:

    for (int i = 0; i <= 10; i++) {
}

    But this is because we have not made the corresponding tweaks to make it convert more expressions.

    The next step after reading this answer is to read any practical book that deals with building compilers, this way you gain a broader and much more understandable idea of ​​developing compilers.

    References and other things:

    • 17