Nesta seção, mudamos nosso foco para a geração geral guiada pelo analisador e começamos com um simples passo a passo para uma gramática semelhante a Python fornecida como um CFG.
Considere um vocabulário que consiste em strings como "d" e "ef" que podem ser combinadas para produzir uma sintaxe semelhante ao Python de acordo com um CFG implícito e suponha que essas strings sejam amostradas sequencialmente e concatenadas de acordo com um processo como o Algoritmo 1.
Além disso, considere um símbolo terminal DEF no CFG que corresponde à string "def" e é dado pela expressão regular trivial def. Além disso, considere um símbolo de NOME dado pela expressão regular [^\W\d]\w* (por exemplo, identificadores Python). Queremos analisar sequencialmente strings amostradas do vocabulário mencionado acima de uma forma que siga a sintaxe do Python.
Por exemplo, o seguinte poderia ser uma dessas sequências: ["d", "ef", " f", "oo(", "):", " ", "pass"]. Todos os elementos da sequência são, por definição, elementos do vocabulário. Concatenar a sequência produz "def foo(): pass", que é uma sequência válida de tokens que definem uma função. Na situação que estamos considerando, teremos observado todos os tokens até um certo ponto e não saberemos nada sobre os tokens posteriores a esse ponto.
Por exemplo, na terceira observação da sequência de exemplo, temos a string concatenada "def f". Se fôssemos lex/analisar esta string, uma abordagem tradicional retornaria a sequência de símbolos DEF NAME, que identifica erroneamente o "f" como um token NAME completo. Como podemos ver no restante da sequência, o token NAME correto será "foo".
Em geral, as próximas strings válidas que podem ser amostradas do vocabulário são aquelas que
continuar expandindo/avançando o NOME atualmente começando com "f" (como faz a sequência completa em nosso exemplo) e/ou
qualquer coisa que comece com "(" – ou seja, um símbolo LPAR com expressão regular (– e prossiga para especificar uma assinatura de argumento válida.
No primeiro caso, o "f" pode ser visto como um símbolo NAME parcialmente correspondente em Python, e – lembrando que sua expressão regular é [^\W\d]\w* – podemos dizer que ele corresponde a ambos os subpadrões (ou seja, [^\W\d] e \w*) na expressão regular. Nosso uso de FSMs formaliza a noção de subpadrões por meio dos estados de um FSM. Neste caso, a regex para NAME pode ser representada por um FSM, M, com três estados: 0 (ou seja, o estado inicial q0), 1 (ou seja, [^\W\d]) e 2 (ou seja, \w*) , onde 1, 2 ∈ F.
Utilizando o Algoritmo 3, obteríamos as sequências de estado FSM (0, 1), (1, 2), (2, 2) para "f" e o FSM, M, correspondente ao símbolo NOME. Essas sequências FSM para "f" nos dizem que a correspondência pode começar para essa sequência de vocabulário nos estados 0, 1 ou 2 e pode terminar nos estados 1 ou 2.
De acordo com o caso 1. acima, a análise pode ser continuada – para o símbolo NOME – após terminar anteriormente nos estados 1 ou 2. De acordo com o caso 2., a próxima string também poderia começar ou conter uma LPAR, implicando que M teria terminado , o que pode ser dado que 1 e 2 são estados finais em M nos quais a análise teria parado após a leitura de "f". A terminação M também indica que um símbolo NAME foi concluído e que uma transição para um estado que aceita LPAR foi permitida pela gramática.
Nesta ilustração, as próximas sequências de vocabulário válidas são pelo menos "d", "ef", "pass", " ", "oo(", porque todas essas sequências expandiriam o NAME parcialmente correspondido, e a última também seria progredir o estado de análise para um que leia uma LPAR. A string restante, "):", do subconjunto do vocabulário que consideramos resultaria em uma sequência com sintaxe inválida.
Em relação à abordagem de indexação FSM, isso significa que o Algoritmo 4 mapearia os estados 0, 1 e 2 do FSM para o subconjunto "d", "ef", "pass", " ", "oo(" para o símbolo NAME e seu FSM, M.
Esta ilustração omite os estados subjacentes do analisador que determinam quais símbolos gramaticais e transições são permitidos. Usamos autômatos pushdown (PDA) como um meio de estender a abordagem FSM e abordar os detalhes restantes.
4.1 Formulação de Autômatos Pushdown
Definimos autômatos pushdown usando a seguinte representação de 6 tuplas [Sipser, 1996, Definição 2.13]:
Para construir uma abordagem de indexação para um analisador baseado em PDA, precisamos usar a conexão entre os símbolos de um CFG – por meio do alfabeto de um PDA correspondente – e as etapas de lexing e varredura que produzem os símbolos lidos por um PDA.
Mais especificamente, os analisadores são suportados por lexers e scanners que identificam símbolos a partir de uma sequência de entradas de caracteres, como ilustramos implicitamente na Seção 4. Listas ordenadas de símbolos terminais podem ser construídas para cada estado de análise/PDA com base nas transições permitidas de símbolos e pilhas. pelo mapa δ em cada estado. Isso significa que podemos construir um FSM para cada estado de análise que é a união de cada FSM correspondente a símbolos terminais lidos pelo estado.
Uma etapa de varredura identificará então um conjunto de possíveis símbolos terminais V ⊂ Σ para os caracteres lidos desde o último símbolo totalmente identificado no processo de análise. Por exemplo, no estado inicial q0 de um PDA para o CFG semelhante ao Python na Seção 4, a varredura e o lexing da string "de" resultarão em V = {DEF, NAME}: ou seja, DEF para qualquer string de vocabulário que complete a string "def" –seguido por uma string que também não é lida pelo FSM NAME (por exemplo, "def") – e NAME por quaisquer outras strings lidas pelo seu FSM (por exemplo, "default"). Observe que as etapas do scanner – e as etapas de amostragem do LLM – eventualmente reduzirão o conjunto V até que um único símbolo terminal v ∈ V seja determinado.
Ao aplicar o Algoritmo 3 a cada string em V usando os FSMs combinados para cada estado de análise, podemos determinar configurações do analisador que consistem nos estados PDA, nos estados FSM correspondentes e nos símbolos terminais potenciais.
Por analogia com as etapas do Algoritmo 3, podemos usar a pré-imagem do mapa de transição do PDA para determinar os valores da pilha do PDA que irão ler os estados do PDA q ∈ Q e os conjuntos de símbolos terminais V de uma configuração de analisador:
Os valores de pilha fornecidos por este mapa são necessários para encontrar caminhos - se houver - através do PDA que permitem análises completas e bem-sucedidas de cada string em V, começando a partir de suas possíveis configurações de analisador. Para combinações de estados e terminais do analisador que correspondem às operações REDUCE de um analisador LALR(1), essas configurações do analisador consistirão em mais do que apenas os valores do topo da pilha em Γ; eles consistirão em subpilhas correspondentes a todos os prefixos válidos para as operações REDUCE decorrentes de uma sequência de vocabulário. Em última análise, cada configuração do analisador que permite uma análise completa de uma sequência de vocabulário é adicionada como uma entrada no índice do PDA e, neste caso, o índice precisará ser uma estrutura de dados experimental para permitir consultas no analisador. valores de pilha.
Este artigo está sob licença CC 4.0.
L O A D I N G . . . comments & more!
About Author
Writings, Papers and Blogs on Text Models@textmodels
We publish the best academic papers on rule-based techniques, LLMs, & the generation of text that resembles human text.
