Generación guiada eficiente para modelos de lenguaje grandes: extensiones al análisis iterativo

Tabla de enlaces

• Resumen e introducción
• Muestreo LLM y generación guiada
• Procesamiento e indexación iterativo de FSM
• Extensiones al análisis iterativo
• Discusión, referencias y agradecimientos

4. Extensiones al análisis iterativo

En esta sección, nos centramos en la generación general guiada por el analizador y comenzamos con un recorrido sencillo por una gramática similar a Python proporcionada como CFG.

Considere un vocabulario que consta de cadenas como "d" y "ef" que se pueden combinar para producir una sintaxis similar a Python según un CFG implícito, y suponga que estas cadenas se muestrean y concatenan secuencialmente según un proceso como el Algoritmo 1.

Además, considere un símbolo terminal DEF en el CFG que corresponde a la cadena "def" y viene dado por la expresión regular trivial def. Además, considere un símbolo NOMBRE dado por la expresión regular [^\W\d]\w* (por ejemplo, identificadores de Python). Queremos analizar secuencialmente cadenas muestreadas del vocabulario antes mencionado de una manera que respete la sintaxis de Python.

Por ejemplo, la siguiente podría ser una de esas secuencias: ["d", "ef", "f", "oo(", "):", " ", "pass"]. Todos los elementos de la secuencia son por definición elementos del vocabulario. Concatenar la secuencia produce "def foo(): pass", que es una secuencia válida de tokens que definen una función. En la situación que estamos considerando, habremos observado todas las fichas hasta cierto punto y no sabremos nada sobre las que siguen a ese punto.

Por ejemplo, en la tercera observación de la secuencia de ejemplo, tenemos la cadena concatenada "def f". Si tuviéramos que leer/analizar esta cadena, un enfoque tradicional devolvería la secuencia de símbolos DEF NAME, que identifica erróneamente la "f" como un token NAME completo. Como podemos ver en el resto de la secuencia, el token NOMBRE correcto será "foo".

En general, las siguientes cadenas válidas que se pueden muestrear del vocabulario son aquellas que

1. continuar expandiendo/avanzando el NOMBRE que actualmente comienza con "f" (como lo hace la secuencia completa en nuestro ejemplo), y/o

   
   

2. cualquier cosa que comience con "(", es decir, un símbolo LPAR con expresión regular (y continúa especificando una firma de argumento válida.

En el primer caso, la "f" puede verse como un símbolo NOMBRE parcialmente coincidente en Python y, recordando que su expresión regular es [^\W\d]\w*, podemos decir que coincide con ambos subpatrones. (es decir, [^\W\d] y \w*) en la expresión regular. Nuestro uso de FSM formaliza la noción de subpatrones a través de los estados de un FSM. En este caso, la expresión regular de NOMBRE se puede representar mediante un FSM, M, con tres estados: 0 (es decir, el estado inicial q0), 1 (es decir, [^\W\d]) y 2 (es decir, \w*). , donde 1, 2 ∈ F.

Usando el Algoritmo 3, obtendríamos las secuencias de estados FSM (0, 1), (1, 2), (2, 2) para "f" y la FSM, M, correspondiente al símbolo NOMBRE. Estas secuencias FSM para "f" nos dicen que la coincidencia puede comenzar para esta cadena de vocabulario en los estados 0, 1 o 2, y puede terminar en los estados 1 o 2.

Según el caso 1 anterior, el análisis puede continuar (para el símbolo NOMBRE) después de terminar previamente en los estados 1 o 2. Según el caso 2, la siguiente cadena también podría comenzar con o contener una LPAR, lo que implica que M habría terminado , lo cual es posible dado que 1 y 2 son estados finales en M en los que el análisis se habría detenido después de leer "f". La terminación M también indica que se completó un símbolo NAME y que la gramática permitió una transición a un estado que acepta LPAR.

En esta ilustración, las siguientes cadenas de vocabulario válidas son al menos "d", "ef", "pass", " ", "oo(", porque todas esas cadenas expandirían el NOMBRE parcialmente coincidente y la última también avanzar el estado de análisis a uno que lea una LPAR. La cadena restante, "):", del subconjunto del vocabulario que hemos considerado daría como resultado una secuencia con sintaxis no válida.

En relación con el enfoque de indexación FSM, esto significa que el algoritmo 4 asignaría los estados FSM 0, 1 y 2 al subconjunto "d", "ef", "pass", " ", "oo(" para el símbolo NOMBRE y su MEV, M.

Esta ilustración omite los estados subyacentes del analizador que determinan qué símbolos gramaticales y transiciones están permitidas. Utilizamos autómatas pushdown (PDA) como medio para ampliar el enfoque FSM y abordar los detalles restantes.

4.1 Formulación de autómatas pushdown

Definimos los autómatas pushdown utilizando la siguiente representación de 6 tuplas [Sipser, 1996, Definición 2.13]:

Para construir un método de indexación para un analizador controlado por PDA, necesitamos utilizar la conexión entre los símbolos de un CFG (a través del alfabeto de una PDA correspondiente) y los pasos de lexing y escaneo que producen los símbolos leídos por una PDA.

Más específicamente, los analizadores son compatibles con lexers y escáneres que identifican símbolos a partir de una secuencia de entradas de caracteres, como ilustramos implícitamente en la Sección 4. Se pueden construir listas ordenadas de símbolos terminales para cada estado de análisis/PDA en función de las transiciones de símbolo y pila permitidas. por el mapa δ en cada estado. Esto significa que podemos construir una FSM para cada estado de análisis que sea la unión de cada FSM correspondiente a un símbolo terminal leído por el estado.

Luego, un paso de escaneo identificará un conjunto de posibles símbolos terminales V ⊂ Σ para los caracteres leídos desde el último símbolo completamente identificado en el proceso de análisis. Por ejemplo, en el estado inicial q0 de una PDA para el CFG tipo Python de la Sección 4, escanear y lexar la cadena "de" dará como resultado V = {DEF, NAME}: es decir, DEF para cualquier cadena de vocabulario que complete la cadena "def". –seguido de una cadena no leída también por la FSM NAME (por ejemplo, "def")– y NAME para cualquier otra cadena leída por su FSM (por ejemplo, "default"). Tenga en cuenta que los pasos del escáner (y los pasos de muestreo del LLM) eventualmente reducirán el conjunto V hasta que se determine un único símbolo terminal v ∈ V.

Al aplicar el algoritmo 3 a cada cadena en V utilizando los FSM combinados para cada estado de análisis, podemos determinar las configuraciones del analizador que consisten en los estados de PDA, los estados FSM correspondientes y los símbolos terminales potenciales.

Por analogía con los pasos del Algoritmo 3, podemos usar la imagen previa del mapa de transición del PDA para determinar los valores de la pila del PDA que leerán los estados del PDA q ∈ Q y los conjuntos de símbolos del terminal V de una configuración del analizador:

Los valores de pila proporcionados por este mapa son necesarios para encontrar rutas (si las hay) a través del PDA que permitan análisis completos y exitosos de cada cadena en V a partir de sus posibles configuraciones de analizador. Para combinaciones de terminal y estado del analizador que corresponden a operaciones REDUCIR de un analizador LALR(1), estas configuraciones del analizador consistirán en algo más que los valores de la parte superior de la pila en Γ; Consistirán en subpilas correspondientes a todos los prefijos válidos para las operaciones REDUCE implicadas por una cadena de vocabulario. En última instancia, cada configuración del analizador que permite un análisis completo de una cadena de vocabulario se agrega como una entrada en el índice de la PDA y, en este caso, el índice deberá ser una estructura de datos trie para permitir consultas en el analizador. valores de pila.