Analisador de descida recursiva com recuo e retrocesso

Question

Tenho tentado encontrar um algoritmo de analisador de descida recursiva que também seja adequado para recuo com retrocesso.Mas continuo encontrando soluções problemáticas para isso.

Existe algum recurso por aí que também lide com recuo?

Obrigado

Answer 1

Com base na sua pergunta, presumo que você esteja escrevendo seu próprio analisador descendente recursivo para uma linguagem sensível à indentação.

Já experimentei linguagens baseadas em indentação antes e resolvi o problema tendo um estado que monitora o nível de indentação atual e dois terminais diferentes que correspondem ao recuo.Ambos correspondem às unidades de recuo (digamos, dois espaços ou uma tabulação) e as contam.Vamos chamar o nível de indentação correspondente matched_indentation e o nível de recuo atual expected_indentation.

Para o primeiro, vamos chamá-lo indent:

• se matched_indentation < expected_indentation, isto é um dedent, e a partida é um fracasso.
• se matched_indentation == expected_indentation, a partida é um sucesso.O matcher consome o recuo.
• se matched_indentation > expected_indentation, você tem um erro de sintaxe (recuo do nada) e deve tratá-lo como tal (lançar uma exceção ou algo assim).

Para o segundo, vamos chamá-lo dedent:

• se matched_indentation < expected_indentation, a partida foi bem-sucedida.Você reduz expected_indentation por um, mas você não consome a entrada.Isto é para que você possa encadear vários dedent terminais para fechar vários escopos.

• se matched_indentation == expected_indentation, a correspondência foi bem-sucedida e desta vez você consome a entrada (este é o último dedent terminal, todos os escopos estão fechados).

  se matched_indentation > expected_indentation, a partida simplesmente falha, você não tem um dedent aqui.

Os terminais e não terminais após os quais você espera um aumento no recuo devem aumentar expected_indentation por um.

Digamos que você queira implementar uma instrução if do tipo python (usarei a notação do tipo EBNF), seria algo assim:

indented_statement : indent statement newline;    

if_statement : 'if' condition ':' newline indented_statement+ dedent ;

Agora vamos examinar o trecho de código a seguir e também supor que um if_statement faz parte do seu statement regra:

1|if cond1:                 <- expected_indentation = 0, matched_indentation = 0
2|  if cond2:               <- expected_indentation = 1, matched_indentation = 1
3|    statement1            <- expected_indentation = 2, matched_indentation = 2
4|    statement2            <- expected_indentation = 2, matched_indentation = 2
5|                          <- expected_indentation = 2, matched_indentation = 0

• Nas primeiras quatro linhas você combinará com sucesso um indent terminal
• Na última linha, você combinará dois dedent terminais, fechando ambos os escopos e resultando em expected_indentation = 0

Uma coisa com a qual você deve ter cuidado é onde você coloca seu indent e dedent terminais.Neste caso, não precisamos de um no if_statement regra porque é um statement, e indented_statement já espera um recuo.

Lembre-se também de como você trata as novas linhas.Uma opção é consumi-los como uma espécie de terminador de instrução, outra é fazê-los preceder o recuo, então escolha o que melhor lhe convier.