In che modo i parser cercano i modelli di token?

Question

In che modo i parser cercano i modelli di token?

#1 da (3 voti)

5

Potresti spiegare come i parser cercano modelli di token come in markdown?

Probabilmente potrei trovare qualcosa che corrisponda solo al modello di parentesi graffe []() non appena i pattern annidati sono coinvolti, mi viene in mente.

Ad esempio in qualcosa di simile

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

il tokenizzatore probabilmente esplode la stringa in questi token

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

e lo passa al parser per riconoscere i pattern, che è un link e che le parentesi corrispondono e persino a capire lo stile grassetto all'interno dell'etichetta.

Suppongo che sia una sorta di macchina a stati, ma in realtà pensa che non appena un [ si presenta potrebbe significare qualcosa memorizzare il token e se i token successivi non corrispondono quindi scartare questo stato e trasformare i token separatori in un valore letterale normale. Ciò significherebbe che doveva tornare a cambiare il significato di tutto il resto se non c'era ( dopo la chiusura di ] . Trovo troppo complesso?

Sembra che sia facile da implementare quando lo guardo, ma se dovessi inventare un algoritmo per questo, non potrei.

algorithms parsing lexer

posta t3chb0t 06.11.2016 - 18:44

fonte

1 risposta

Leggi altre domande sui tag algorithms parsing lexer

Concetto di notifiche push: perché è solo sulle piattaforme mobili? OSX / Windows / Linux? Lo stato del monitoraggio cambia in base alla durata del tempo in stato

score 3 · Accepted Answer

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.

Per fortuna alcune persone hanno già :)

È un argomento complicato, e c'è molto da fare, ma un run-down veloce è:

Hai ragione che il tokenizzatore esploda la stringa nei token. Quindi il parser avrà una grammatica definita al suo interno, solitamente usando qualcosa come BNF, per adattare i pezzi insieme.

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

potrebbe essere analizzato da una grammatica come:

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 '_'

Si noti che è ricorsivo. Alcune regole come word_text si riferiscono direttamente a se stesse, altre come <line> si riferiscono a qualcosa che fa riferimento a <line> . (Il python language doc è pieno di tali esempi)

Dopo aver creato una grammatica per la tua lingua, potresti scrivere ad es. un parser di discesa ricorsivo per "leggerlo". O più comunemente, usa uno strumento come YACC o ANTLR per fare in modo che il parser per te sia basato direttamente sulla grammatica.

Per quanto riguarda una macchina a stati: penso che YACC implementa i suoi parser in termini di tabelle di stato giganti - ho pensato che potrei sbagliarmi su questo. È passato un po 'di tempo da quando l'ho usato.