Como os analisadores pesquisam padrões de token?

5

Você poderia explicar como os analisadores pesquisam padrões de tokens como no markdown?

Eu provavelmente poderia criar algo que correspondesse apenas ao padrão de chaves []() assim que os padrões aninhados estiverem envolvidos, isso me surpreenderá.

Por exemplo, em algo parecido com isto

foo [**baz**](baz) qux

o tokenizer provavelmente explode a string nesses tokens

"foo ", "[", "**", "baz", "**", "]", "(", "baz", ")", " qux"

e passa para o analisador para reconhecer os padrões, que é um link e que as chaves correspondem e, em seguida, até mesmo entendem o estilo arrojado dentro do rótulo.

Eu acho que é algum tipo de máquina de estado, mas realmente pensa que assim que [ ocurrs pode significar algo, então armazene o token e se os tokens subseqüentes não corresponderem em seguida, descarte esse estado e transforme os tokens separadores em um literal normal. Isso significaria que ele teria que voltar a mudar o significado de todo o resto se não houvesse ( após o fechamento ] . Eu acho muito complexo?

Parece que foi fácil implementá-lo quando o analiso, mas se eu inventar um algoritmo para ele, não pude.

    
por t3chb0t 06.11.2016 / 18:44
fonte

1 resposta

3

It looks like it was easy to implement when I look at it, but if I should invent an algorithm for it, I couldn't.

Felizmente algumas pessoas já têm :)

  1. link
  2. link
  3. link

É um assunto complicado, e há muito por aí, mas uma rápida descida é:

Você está certo de que o tokenizador explode a string nos tokens. Em seguida, o analisador terá uma gramática definida dentro dele, geralmente usando algo como BNF, para encaixar as peças.

"foo ", "[", "**", "baz", "**", "]", "(", "baz", ")", " qux"

poderia ser analisado por uma gramática como:

line = <rounds> | <squares> | <markdown_stuff> | <line>
rounds = '(' <line> ')'
squares = '[' <line> ']'
markdown_stuff = <italics> | <bold> | <word_text>
italics = '*' <word_text> '*' 
bold = '**' <word_text> '**'
word_text = <word_char> | <word_char> <word_text>
word_char= 'a', 'b', 'c', 'd'... etc 'A', 'B', 'C', etc '0', '1', '2', '3', etc '_'

Observe que é recursivo. Algumas regras como word_text referem-se diretamente a si mesmas, outras, como <line> , referem-se a algo que se refere a <line> . (O doc. De idioma do python está repleto de exemplos)

Depois de criar uma gramática para o seu idioma, você escreveria, por exemplo: um analisador descendente recursivo para "lê-lo". Ou mais comumente, use uma ferramenta como YACC ou ANTLR para fazer o analisador para você com base diretamente na gramática.

Quanto a uma máquina de estado: acho que o YACC implementa seus analisadores em termos de tabelas de estado gigantes - achei que poderia estar errado nisso. Já faz um tempo desde que eu usei.

    
por 06.11.2016 / 23:19
fonte