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

实现编程语言翻译器（词法、句法分析）

  • 772

作为编译器工作的一部分，我必须编写一个文本编辑器来接收 Visual Basic 语言作为输入并将其转换为我选择的另一种语言。我目前正在使用 Visual Basic 对上述内容进行编程。

编辑器文本

我做的第一件事是接收输入字符串并将其分离为标记，将它们分类为保留字、变量、分组符号和运算符。

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

评估令牌的方法：

'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

自动机评估令牌是否为数字：

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

由自动机评估后的令牌我将它们存储在 ListViews 中，然后我将其显示在一个窗口中。

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

代币

对于这个翻译器，我不必进行组符号验证，检查是否缺少括号或花括号。仅将获得的标记转换为另一种语言。最终语言可以是任何语言。

此外，我必须转换的不是整个语言，只有 For、While 和 If 的结构。

例如，如果我有：

For i = 1 To i <= 5

Next

我必须将其转换为：

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

}

在这种情况下，我拥有的令牌是： 第 1 行：

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

第 2 行：

PalabraReservada "Next" Token5

我已经尝试了几种方法，但我无法让令牌的翻译为我工作。

我需要帮助的是，如果你能告诉我如何制作一个模板来接收令牌并将它们更改为新语言。请。

如果有人可以帮助我，我将不胜感激。

vb.net

1 Answers

  1. Best Answer

    制作编译器是一件相对复杂的事情，我一直在尝试做一些个人的事情，但没有什么是我以前没有实现的。您想要做的是需要大量分析时间的事情，而这个答案基本上是我大约 2 年前读过的一本书的摘要。

    调味代码（用大量盐）

    我将假设您已经拥有完整的词法分析器，它将接受输入并将其“拆分”为称为标记的小单元，并且您使用以下类来存储 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

    如果你注意到，它TType是 type TokenTypes，它又是Enum如下定义的：

    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

    此枚举包含Token编译器将要处理的不同类型，以及（目前）解析器将要使用的类型，目前我们不会使用所有 VB.NET 令牌类型，因为列表现在不会结束。

    语义（或句法）分析器应该看到标记的方式类似于以下（类似 JSON）：

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

    稍后您可以保存找到该标记的确切行和列，但现在这并不重要。

    班级Parser

    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

    我们制作的语义/句法分析器（Bad, but good）可以翻译表达式：

    For i = 0 To 10 Step 1
Next

    A：

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

    但这是因为我们还没有做出相应的调整来让它转换更多的表达式。

    阅读此答案后的下一步是阅读任何有关构建编译器的实用书籍，这样您就可以获得开发编译器的更广泛且更易于理解的想法。

    参考资料及其他：

    • 17